《数据结构》课程设计试验报告.docx
- 文档编号:10755786
- 上传时间:2023-05-27
- 格式:DOCX
- 页数:32
- 大小:62.35KB
《数据结构》课程设计试验报告.docx
《《数据结构》课程设计试验报告.docx》由会员分享,可在线阅读,更多相关《《数据结构》课程设计试验报告.docx(32页珍藏版)》请在冰点文库上搜索。
《数据结构》课程设计试验报告
《数据结构》课程设计
实验报告
题目有关查找的操作
学院
专业信息管理和信息系统
班级
学号
学生姓名
同组成员
指导教师
编写日期2011年7月8日
目录
一、问题描述0
二、问题分析0
三、数据结构描述0
四、算法设计1
五、详细程序清单4
六、程序运行结果4
七、使用说明5
八、心得体会5
一、问题描述
1、顺序表的查找问题描述
顺序查找又称线性查找,它是一种最简单、最基本的查找方法。
它从顺序表的一端开始,依次将每一个数据元素的关键字值与给定Key进行比较,若某个数据元素的关键字值等于给定值Key,则表明查找成功;若直到所有数据元素都比较完毕,仍找不到关键字值为Key的数据元素,则表明查找失败。
2、有序表的查找问题描述
所谓“折半”也称为“二分”,故二分查找又称为折半查找。
作为二分查找对象的数据必须是顺序存储的有序表,通常假定有序表是按关键字值从小到大排列有序,即若关键字值为数值,则按数值有序,若关键字值为字符数据,则按对应的Unicode码有序。
二分查找的基本思想是:
首先取整个有序表的中间记录的关键字值与给定值相比较,若相等,则查找成功;否则以位于中间位置的数据元素为分界点,将查找表分成左、右两个子表,并判断待查找的关键字值key是在左子表还是在右子表,再在左或右子表中重复上述步骤,直到找待查找的关键字值为key的记录或子表长度为0.
3、哈希表的查找问题描述
在哈希表上进行查找的过程和哈希表构造的过程基本一致。
给定要查找的关键字K的值,根据构造哈希表时设定的哈希函数求得哈希地址,若此哈希地址上没有数据元素,则查找不成功;否则比较关键字,若相等,则查找成功;若不相等,则根据构造哈希表时设置的处理冲突的方法找下一个地址,直至某个位置上为空或关键字比较相等为止。
从哈希表的查找过程可见,虽然哈希表是在关键字和存储位置之间直接建立了映像,然而由于冲突的产生,哈希表的查找过程仍然是一个和关键字比较的过程。
因此,仍需用平均查找长度来衡量哈希表的查找效率。
查找过程中与关键字比较的次数取决于构造哈希表时选择的哈希函数和处理冲突的方法。
哈希函数的“好坏”首先影响出现冲突的频率,假设哈希函数是均匀的,即它对同样一组随机的关键字出现冲突的可能性是相同的。
因此,哈希表的查找效率主要取决于构造哈希表时处理冲突的方法。
4、二叉排序数的查找问题描述
在顺序表的3中查找方法中,二分查找具有最高的查找效率,但是由于二分查找要求表中记录按关键字有序,且不能用链表做存储结构,因此当表的插入、删除操作非常频繁时,为维护表的有序性,需要移动表中很多记录。
这种由移动记录引起的额外时间开销,就会抵消二分查找的优点。
这里讨论的不仅是二叉排序树具有二分查找的效率,同时又便于在查找表中进行记录的增加和删除操作。
二、问题分析
本人负责的是顺序表的查找操作,就是在由一组记录组成的集合中寻找主关键字值等于给定值的某个记录,或是寻找属性值符合特定条件的某些记录。
顺序查找算法涉及的顺序表类SeqList和记录结点类RecordNode。
利用不带监视哨的顺序查找算法从顺序表r[1]到r[n]的n个元素中顺序查找出关键字为key的元素。
若查找成功返回其下标,否则返回-1
三、数据结构描述
publicSeqList(intmaxSize){
this.r=newRecordNode[maxSize];//为顺序表分配maxSize个存储单元
this.curlen=0;//置顺序表的当前长度为0
}
//求顺序表中的数据元素个数并由函数返回其值
publicintlength(){
returncurlen;//返回顺序表的当前长度
}
publicintgetCurlen(){
returncurlen;
}
publicvoidsetCurlen(intcurlen){
this.curlen=curlen;
}
四、算法设计
1.程序功能模块图
程序功能模块图
2.算法设计
//【算法8.2】不带监视哨的顺序查找算法
//从顺序表r[1]到r[n]的n个元素中顺序查找出关键字为key的元素
//若查找成功返回其下标,否则返回-1
publicintseqSearch(Comparablekey){
inti=0,n=length();
while(i =0){ i++; } if(i returni; } else{ return-1; } } } 五、详细程序清单 1、xuanze类 importjava.util.Scanner; publicclassxuanze{ staticSeqListST=null; staticvoidcreateSeachList()throwsException{ intmaxSize=20; ST=newSeqList(maxSize); intcurlen; System.out.print("Pleaseinputtablelength: "); Scannersc=newScanner(System.in); curlen=sc.nextInt(); KeyType[]k=newKeyType[curlen]; System.out.print("Pleaseinputkeywordsequence: "); for(inti=0;i k[i]=newKeyType(sc.nextInt()); for(inti=0;i RecordNoder=newRecordNode(k[i]); ST.insert(i,r);//从1号存储单元开始存放数据元素 }} staticHashTable publicstaticvoidmain(Stringargs[])throwsException { System.out.println("/***********************************************/"); System.out.println("1.顺序表的查找操作"); System.out.println("2.有序表的查找操作"); System.out.println("3.哈希表的查找操作"); System.out.println("4.其它查找算法"); System.out.println("5.退出"); System.out.println("/***********************************************/"); System.out.println("请选择1-5,谢谢! ! "); Scannersc=newScanner(System.in); while(true){ switch(sc.nextInt()) { case1: createSeachList(); System.out.print("Pleaseinputsearchkeyword: "); Scannersc1=newScanner(System.in); KeyTypekey1=newKeyType(sc.nextInt()); KeyTypekey2=newKeyType(sc.nextInt()); System.out.println("seqSearch"+key1.getKey()+")="+ST.seqSearch(key1)); System.out.println("seqSearch("+key2.getKey()+")="+ST.seqSearch(key2)); System.out.println("如需其他操作,请继续选择,如不需要,请按5,谢谢! "); break; case2: createSeachList(); System.out.print("Pleaseinputsearchkeyword: "); Scannersc2=newScanner(System.in); KeyTypekey3=newKeyType(sc.nextInt()); KeyTypekey4=newKeyType(sc.nextInt()); System.out.println("binaryseqSearch("+key3.getKey()+")="+ST.binarySearch(key3)); System.out.println("binaryseqSearch("+key4.getKey()+")="+ST.binarySearch(key4)); System.out.println("如需其他操作,请继续选择,如不需要,请按5,谢谢! "); break; case3: String[]name={"Wang","Li","Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou","Du"}; HashTable Stringelem1,elem2; System.out.print("插入元素: "); for(inti=0;i ht.insert(name[i]); System.out.print(name[i]+""); } System.out.print("\n原哈希表: "); ht.printHashTable(); elem1=name[2]; System.out.print("查找"+elem1+","+(ht.contain(elem1)? "": "不")+"成功"); elem2="san"; System.out.print("查找"+elem2+","+(ht.contain(elem1)? "": "不")+"成功"); System.out.print("删除"+elem1+","+(ht.remove(elem1)? "": "不")+"成功"); System.out.print("删除"+elem2+","+(ht.remove(elem2)? "": "不")+"成功"); System.out.println("新哈希表: "); ht.printHashTable(); System.out.println("如需其他操作,请继续选择,如不需要,请按5,谢谢! "); break; case4: BSTreebstree=newBSTree(); int[]k={50,13,63,8,36,90,5,10,18,70}; String[]item={"Wang","Li","Zhang","Liu","Chen","Yang","Huang","Zhao","Wu","Zhou"}; KeyType[]key=newKeyType[k.length]; ElementType[]elem=newElementType[k.length]; System.out.println("原序列: "); for(inti=0;i key[i]=newKeyType(k[i]); elem[i]=newElementType(item[i]); if(bstree.insertBST(key[i],elem[i])){ System.out.print("["+key[i]+","+elem[i]+"]"); } } System.out.println("\n中根遍历二叉排序树: "); bstree.inOrderTraverse(bstree.root); System.out.println(); KeyTypekeyvalue=newKeyType(); keyvalue.setKey(63); RecordNodefound=(RecordNode)bstree.searchBST(keyvalue); if(found! =null){ System.out.println("查找关键码: "+keyvalue+",成功! 对应姓氏为: "+found.getElement()); } else{ System.out.println("查找关键码: "+keyvalue+",失败! "); } keyvalue.setKey(39); found=(RecordNode)bstree.searchBST(keyvalue); if(found! =null){ System.out.println("查找关键码: "+keyvalue+",成功! 对应姓氏为: "+found.getElement()); } else{ System.out.println("查找关键码: "+keyvalue+",失败! "); } keyvalue.setKey(13); found=(RecordNode)bstree.removeBST(keyvalue); if(found! =null){ System.out.println("删除关键码: "+keyvalue+",成功! 对应姓氏为: "+found.getElement()); } else{ System.out.println("删除关键码: "+keyvalue+",失败! "); } System.out.println("\n删除关键码: "+keyvalue+",后的中根遍历序列: "); bstree.inOrderTraverse(bstree.root); System.out.println(""); System.out.println("如需其他操作,请继续选择,如不需要,请按5,谢谢! "); break; case5: System.out.println("已成功退出! "); return; } }}} 2、RecordNode类 classRecordNode{ privateComparablekey;//关键字 privateObjectelement;//数据元素 publicObjectgetElement(){ returnelement; } publicvoidsetElement(Objectelement){ this.element=element; } publicComparablegetKey(){ returnkey; } publicvoidsetKey(Comparablekey){ this.key=key; } publicRecordNode(Comparablekey){//构造方法1 this.key=key; } publicRecordNode(Comparablekey,Objectelement){//构造方法2 this.key=key; this.element=element; } publicStringtoString(){//覆盖toString()方法 return"["+key+","+element+"]"; } } 3、KeyType类 classKeyTypeimplementsComparable privateintkey;//关键字 publicKeyType(){ } publicKeyType(intkey){ this.key=key; } publicintgetKey(){ returnkey; } publicvoidsetKey(intkey){ this.key=key; } publicintcompareTo(KeyTypeanother){//覆盖Comparable接口中比较关键字大小方法 intthisVal=this.key; intanotherVal=another.key; return(thisVal -1: (thisVal==anotherVal? 0: 1)); } } 4、SeqList类 classSeqList{ privateRecordNode[]r;//顺序表记录结点数组 privateintcurlen;//顺序表长度,即记录个数 //顺序表的构造方法,构造一个存储空间容量为maxSize的顺序表 publicSeqList(intmaxSize){ this.r=newRecordNode[maxSize];//为顺序表分配maxSize个存储单元 this.curlen=0;//置顺序表的当前长度为0 } //求顺序表中的数据元素个数并由函数返回其值 publicintlength(){ returncurlen;//返回顺序表的当前长度 } publicintgetCurlen(){ returncurlen; } publicvoidsetCurlen(intcurlen){ this.curlen=curlen; } //在当前顺序表的第i个结点之前插入一个RecordNode类型的结点x //其中i取值范围为: 0≤i≤length()。 //如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x, //当i=length()时表示在表尾插入一个数据元素x publicvoidinsert(inti,RecordNodex)throwsException{ if(curlen==r.length){//判断顺序表是否已满 thrownewException("顺序表已满"); } if(i<0||i>curlen){//i小于0或者大于表长 thrownewException("插入位置不合理"); } for(intj=curlen+1;j>i;j--){ r[j]=r[j-1];//插入位置及之后的元素后移 } r[i]=x;//插入x this.curlen++;//表长度增1 } 5、seqSearch类(顺序查找算法) publicintseqSearch(Comparablekey){ inti=0,n=length(); while(i =0){ i++; } if(i returni; } else{ return-1; } } 6、binarySearch类(二分查找算法) publicintbinarySearch(Comparablekey){ if(length()>0){ intlow=0,high=length()-1;//查找范围的下界和上界 while(low<=high){ intmid=(low+high)/2;//中间位置,当前比较元素位置 //System.out.print(r[mid].getKey()+"? "); if(r[mid].getKey().compareTo(key)==0){ returnmid;//查找成功 }elseif(r[mid].getKey().compareTo(key)>0){//给定值更小 high=mid-1;//查找范围缩小到前半段 }else{ low=mid+1;//查找范围缩小到后半段 } } } return-1;//查找不成功 } 7、Node类 classNode{ privateObjectdata; privateNodenext; publicNode(){ this(null,null); } publicNode(Objectdata){ this(data,null); } publicNode(Objectdata,Nodenext){ this.data=data; this.next=next; } publicObjectgetData(){ returndata; } publicNodegetNext(){ returnnext; } publicvoidsetData(Objectdata){ this.data=data; } publicvoidsetNext(Nodenext){ this.next=next; }} 8、LinkList类 classLinkList{ privateNodehead=newNode(); publicvoidcreate(intn)throwsException{ Scannersc=newScanner(System.in); for(intj=0;j insert(0,sc.next());} publicvoidinsert(inti,Objectx)throwsException{ Nodep=head; intj=-1; while(p! =null&&j p=p.getNext(); ++j; } if(j>i-1||p==null) thrownewException("插入位置不合法"); Nodes=newNode(x); s.setNext(p.getNext()); p.setNext(s); } publicvoidremove(inti)throwsException{
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 试验报告