2023年数据结构实验报告6

广东金融学院实验报告课程名称:数据结构实验编号及实验名称实验二:排序和查找实验系另U计算机科学与技术系姓名学号班级实验地点实验日期实验时数6指导教师同组其他成员无成绩一、实验目的及规定通过编写和调用直接插入排序、希尔排序、冒泡排序和快速排序四种排序算法实现数据排序，充足理解各种排序算法的算法思想、排序过程及各自的时间复杂度、稳定性。通过编写和调用顺序查找和二分查找算法实现数据查找，掌握两个查找算法的基本思想、实现方法和时间性能。二、实验环境及相关情况(包含使用软件、实验设备、重要仪器及材料等)1、实验设备：微型计算机;2、软件系统：WindowsXP、DWMXo三、实验内容(一)排序(1)参照课本,分别编写Java程序,实现顺序表记录类RecordNode、类KeyType。(2)参照课本，编写一个Java程序，实现顺序表类SeqList,并在其中添加成员函数：1ength()求顺序表的当前长度；disp1ay()输出数组元素的关键字;直接插入排序算法；带监视哨的直接插入排序;希尔排序算法;起泡排序算法；快速排序算法。(3)编写主程序,循环选择调用以上5个排序算法，对数组元素排序,并输出排序过程。(二)杳找(1)在排序实验的基础上,在类SeqList中添加成员函数：不带监视哨的顺序查找算法;带监视哨的顺序查找算法；二分查找算法。(2)编写主程序，循环选择调用以上3个查找算法,分别对键入的关键字记录进行成功和不成功查找publicclassKeyTypeimplementsComparab1e<KeyType>{privateintkey；publicKeyType(){)opxiblicKeyType(intkey){this.key=key;)◎publicintgetKey(){returnkey;)pub1icvoidsetKey(intkey){this.key=key;五、实验总结（涉及心得体会、问题回答及实验改善意见）答：通过这次实验，编写和调用顺序查找和二分查找算法实现数据查找，我掌握两个查找算法的基本思想、实现方法和时间性能。六、教师评语1、完毕所有规定的实验内容，实验环节对的，结果对的；2、完毕绝大部分规定的实验内容,实验环节对的,结果对的；3、完毕大部分规定的实验内容，实验环节对的，结果对的；4、基本完毕规定的实验内容，实验环节基本对的，所完毕的结果基本对的；5、未能很好地完毕规定的实验内容或实验环节不对的或结果不对的。6、其它:评估等级:优秀良好中档及格不及格教师署名：2023年7月10日)opub1icStringtoString(){returnkey+n";}opublicintcompareTo(KeyTypeanother){ointthisVal=this.key;ointanotherVal=another.key：oreturn(thisVal<anotherVai?-1:(thisVal==anotherVa1?0:1))；})pub1icclassRecordNode{privateComparab1ekey;oprivateObjecte1ement;pub1icObjectgetE1ement(){returnelement;0)opublicvoidsetE1ement(Objectelement){oothis.element=element;0)publie,ComparablegetKey(){ooreturnkey;)publicvoidsetKey(Comparablekey){oothis.key=key;0)opublicRcc0rdNOde(Comparablekey){othis.key=key；0}opublicRecordNode(Comparab1ekey,Objectelement){othis.key=key；this.element=e1ement;o))publieclassSeqList{oprivateRecordNode[]r;privateintcurIen；opub1icSeqList(intmaxSize){this.r=newRecordNode[maxSize];othis.curlen=0：}publieRecordNode[]getRecord(){returnr；publicvoidsetRecord(RecordNode[]r){oothis.r=r；)pub1icintlength{){oreturncurlen；)opublicvoiddisp1ay(){for(inti=0；i<curlen;i++){ooSystem.out.print(r[i].getKey()+H")；00)0)publicvoidinsert(inti,RecordN0dex)throwsExcepti0n{ooif(curlen==r.length){thr0wnewException("顺序表已满”)；0d)oif(i<0||i>curlen){oothrownewException(“插入位置不合理”)；0)ofor(intj=curlen：j>i;j--){oor[j]=r[j—1];0)oor[i]=x；oothis.curlen++;)publievoidinsertsort(){o〃直接插入oRecordNodetemp：ointi,j;ofOr(i=l;i<this.curien;i++){dtemp=r[i];oofor(j=i—1;j>=0&&temp.getKey().compareTo(r[j].qetKey())<0：j—-){。r[j+1]=r[j]；0)0or(j+1]=temp;))opublicvoidshellSort(int[]d){//希尔©RecordNodetemp；ointi,j;ofor(intk=0;k<d.1ength；k++){intdk=d[k]；ofor(i=dk;i<this.curlen;i++){ootemp=r[i]；oofor(j=i-dk;j>=0&&temp.getKey().compareTq(r〔j〕.getKey())<0;j-=dk){or[j+dk]=temp;0}}publievoidinsertSortWithGuard(){//带监视哨的直接插入ointi,j；0for(i=1;i<this.curien；i++){r[0]=r[i];ofor(j=i-1；r[0].getKey().c。mpareTo(rH].cetKey())<0;j--){0or[j+1]=r[j]：40or[j+1]=r[0];))publicvoidbubbleSort(){//冒泡RecordNodetemp;obooleanf1ag=true：afor(inti=1;i<this.cur1en&&flag;i+4-){f1ag=false;oofor(intj=0;j<this.curlen-1;j++){oooif(r[j]•getKey().compareTo(r[j+1].getKcy())>0){°temp=r[j]；00or[j]=r[j+1];oor[j+1]=temp;oflag=true;00}00))00)0opub1icintPartition(Inti,intj){aaRecordNodepivot=r[j]；owhile(i<j){whi1e(i<j&&pivot.qetKey().compareTo.getKey())<=0){TOC\o"1-5"\h\z00j；0。}0if(i<j)(oor[i]=r[j];ooi++；00)owhi1e(i<j&&pivot.qetKey()•compareTo(r[i].qetKey())>0)[oi++;00)00if(i<j){0r[j]=r[i];Oddj；01)oor[i]=pivot;«returni；)opublicvoidqSort(intlow,inthigh){oif(low<high){dintpivotloc=Partition(low,high);ooqSort(10wzpiv0tl0c-1)：aqSort(Pivotloc+1,high);oo)o)pub1icvoidquickSort(){qSort(0,this.curlen-1)；)opub1icintseqSearch(Comparablekey){inti=0;oointn=length();owhile(i<n&&r[i].getKey().compareTo(key)!=0){oi++；)ooif(i<n){oreturni；}oelse{return-1;。}}opublicintseqSearchWithGuard(Comparab1ekey){ointi=length()-1；r[0].setKey(key);whi1e((r[i).getKey()).compareTo(key)!=0){i——；o}ooif(i>0){®returni；}else(return-1;00)0}opublicintbinarySearch(Comparablekey){0if(length()>0){intlow=0;0ointhigh=length()-1;0while(1ow<=high)(soointmid=(low+high)/2；oif(r[mid].getKey().compareT。(key)==0){0aoreturnmid;00)00elseif(r[mid].getKey().compareTo(key)>0){0000high=mid-l：000)0oelse{0000low=niid+l；return-1；})packagepaixu;importjava.uti1.Scanner；importpaixu.RecordNode;importpaixu.SeqList；publicc1assTest2{pub1icstaticvoidmain(String[]args)throwsException{Scannerin=newScanner(System.in)；0while(true){bSeqLista=newSeqList(6)；00Stringd[]={"25,r,H20","15”，“35“，M10“，“55”};00ofor(inti=0；i<6；i++){00RecordNodec=newRecordNode(d[i]);0o0oa.insert(i,c);0aa}0o。oSystem.0ut.print("原数组：");a.display();0System.ou/.println(*"•)；oo3oSystem.out.print1n(“输入0〜5进行选择");ooSystem.out.printIn("1直接插入排序”);©ooSystem.out.printIn("2带监视哨的直接插入排序”)；ooooSystem,out.printin("3希尔排序");ooSystem.ouf.print1n("4冒泡排序”)；ooSystem,ou/.print1n(05快速排序”);ooooSystem.out.printIn("0退出")；oaointg=in.nextInt()；ooooswitch(g){oosease0：oooreturn：ooooocase1:oooa.insertSort()；ooooSystem.owt.print("排序后:;a.display。；ooooSystem.out.print1n("")；oooobreak;ocase2：ooa.insertSortWithGuard();oooooSystem.out.print("排序后：")；a.disp1ay();ooooooSystem.out.println("'*)；ooobreak;000oocase3::o3int[]aa={1,3»5};ooa.she11Sort(aa);ooSystem.<?ut.print("排序后:;a.display();ooooSystem.out.print1n(*'H);ooobreak;ooocase4：oo°oa.bubbleSort();oSystem,out:.print("排序后：*')：a.display();ooSystem.o〃t.print1n("”)；oooobreak；ocase5:ot>ooa.quickSort();ooooooSystem.out.print(“排序后：”)；a.disp1ay();oooooSystem.out.print1n("")；ooobreak：0000000}importjava.uti1.Scanner;publicclassTest{publicstaticvoidmain(String[]args){owhile(1<2){oSeqLista=newSeqList(4)；00oScannerin=newScannor(System.in);000oofor(inti=0：i<4;i++){try(oooSystem.ouf.println(输入第"+i+”个元素：");oooStringc=in.next();oooo