2023年數(shù)據(jù)結(jié)構(gòu)實驗報告6

廣東金融學(xué)院實驗報告課程名稱:數(shù)據(jù)結(jié)構(gòu)實驗編號及實驗名稱實驗二:排序和查找實驗系另U計算機科學(xué)與技術(shù)系姓名學(xué)號班級實驗地點實驗日期實驗時數(shù)6指導(dǎo)教師同組其他成員無成績一、實驗?zāi)康募耙?guī)定通過編寫和調(diào)用直接插入排序、希爾排序、冒泡排序和快速排序四種排序算法實現(xiàn)數(shù)據(jù)排序，充足理解各種排序算法的算法思想、排序過程及各自的時間復(fù)雜度、穩(wěn)定性。通過編寫和調(diào)用順序查找和二分查找算法實現(xiàn)數(shù)據(jù)查找，掌握兩個查找算法的基本思想、實現(xiàn)方法和時間性能。二、實驗環(huán)境及相關(guān)情況(包含使用軟件、實驗設(shè)備、重要儀器及材料等)1、實驗設(shè)備：微型計算機;2、軟件系統(tǒng)：WindowsXP、DWMXo三、實驗內(nèi)容(一)排序(1)參照課本,分別編寫Java程序,實現(xiàn)順序表記錄類RecordNode、類KeyType。(2)參照課本，編寫一個Java程序，實現(xiàn)順序表類SeqList,并在其中添加成員函數(shù)：1ength()求順序表的當(dāng)前長度；disp1ay()輸出數(shù)組元素的關(guān)鍵字;直接插入排序算法；帶監(jiān)視哨的直接插入排序;希爾排序算法;起泡排序算法；快速排序算法。(3)編寫主程序,循環(huán)選擇調(diào)用以上5個排序算法，對數(shù)組元素排序,并輸出排序過程。(二)杳找(1)在排序?qū)嶒灥幕A(chǔ)上,在類SeqList中添加成員函數(shù)：不帶監(jiān)視哨的順序查找算法;帶監(jiān)視哨的順序查找算法；二分查找算法。(2)編寫主程序，循環(huán)選擇調(diào)用以上3個查找算法,分別對鍵入的關(guān)鍵字記錄進行成功和不成功查找publicclassKeyTypeimplementsComparab1e<KeyType>{privateintkey；publicKeyType(){)opxiblicKeyType(intkey){this.key=key;)◎publicintgetKey(){returnkey;)pub1icvoidsetKey(intkey){this.key=key;五、實驗總結(jié)（涉及心得體會、問題回答及實驗改善意見）答：通過這次實驗，編寫和調(diào)用順序查找和二分查找算法實現(xiàn)數(shù)據(jù)查找，我掌握兩個查找算法的基本思想、實現(xiàn)方法和時間性能。六、教師評語1、完畢所有規(guī)定的實驗內(nèi)容，實驗環(huán)節(jié)對的，結(jié)果對的；2、完畢絕大部分規(guī)定的實驗內(nèi)容,實驗環(huán)節(jié)對的,結(jié)果對的；3、完畢大部分規(guī)定的實驗內(nèi)容，實驗環(huán)節(jié)對的，結(jié)果對的；4、基本完畢規(guī)定的實驗內(nèi)容，實驗環(huán)節(jié)基本對的，所完畢的結(jié)果基本對的；5、未能很好地完畢規(guī)定的實驗內(nèi)容或?qū)嶒灜h(huán)節(jié)不對的或結(jié)果不對的。6、其它:評估等級:優(yōu)秀良好中檔及格不及格教師署名：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(){//帶監(jiān)視哨的直接插入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("原數(shù)組：");a.display();0System.ou/.println(*"?)；oo3oSystem.out.print1n(“輸入0?5進行選擇");ooSystem.out.printIn("1直接插入排序”);?ooSystem.out.printIn("2帶監(jiān)視哨的直接插入排序”)；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