数据结构实验报告2

金融学院实验报告XX课程名称数据结构实验编号与实计算机科学与技术实验二排序和查找实验系另IJ验名称系姓名学号班级实验地点实验日期实验时数6指导教师同组其他成员成绩无

一、实验目的与要求、通过编写和调用直接插入排序、希尔排序、冒泡排序和快速排序四种排序算法实现数据排序，充分理解各种排序算法的算法思想、排序过程与各自的时间复杂度、稳定性

1、通过编写和调用顺序查找和二分查找算法实现数据查找，掌握两个查找算法的基本思想、实现方法和时间性能2

二、实验环境与相关情况〔包含使用软件、实验设备、主要仪器与材料等、实验设备微型计算机；、软件系统、

三、实验内容12Windows XPDWMX一排序参照课本，分别编写程序，实现顺序表记录类类参照课本，编写一个程序，实现顺序表类并在其中添加成员函数1Java RecordNodeKeyType求顺序表的当前长度；输出数组元素的关键字；直接插入排序算法；带监视哨的直接插2Java SeqList,入排序；希尔排序算法；起泡排序算法；快速排序算法length display编写主程序，循环选择调用以上个排序算法，对数组元素排序，并输出排序过程二查找35在排序实验的基础上，在类中添加成员函数不带监视哨的顺序查找算法；带监视哨的顺序查找算法；二分查找算法1SeqList编写主程序，循环选择调用以上个查找算法，分别对键入的关键字记录进行成功和不成功查找23publicclass KeyType implementsComparable KeyType{privateintkey;public KeyType{public KeyTypeint key{this.key=key;publicint getKey{returnkey;}publicvoid setKeyint key{this.key=key;

五、实验总结（包括心得体味、问题回答与实验改进意见）答:通过这次试验，编写和调用顺序查找和二分查找算法实现数据查找，我掌握两个查找算法的基本思想、实现方法和时间性能

六、教师评语、完成所有规定的实验内容，实验步骤正确，结果正确；、完成绝大部份规定的实验内容，实验步骤正确，结果正确；

1、完成大部份规定的实验内容，实验步骤正确，结果正确；

2、基本完成规定的实验内容，实验步骤基本正确，所完成的结果基本正确；

3、未能很好地完成规定的实验内容或者实验步骤不正确或者结果不正确

4、其它56评定等级优秀良好中等与格不与格教师签名月日20XX710第页共页1010public StringtoString{returnkey+;publicint compareToKeyType another{int thisVal=this.key;int anotherVal=another.key;returnthisVal anotherVal-1:thisVal==anotherVal0:1;publicclass RecordNode{privateComparablekey;private Object element;public ObjectgetElement{returnelement;publicvoid setElementObject element{this.element=element;publicComparable getKey{returnkey;publicvoidsetKey Comparable key{this.key=key;public RecordNodeComparable key{this.key=key;public RecordNodeComparable key,Objectelement{this.key=key;this.element=element;publicclass SeqList{private RecordNode[]r;privateintcurlen;public SeqListint maxSize{this-r=new RecordNode[maxSize];this.curlen=0;public RecordNode[]getRecord{returnr;publicvoid setRecordRecordNode[]r{this.r=r;publicint length{returncurlen;out}publicvoid display{forint i=0;i curlen;i++{System..printr[i].getKey+;顺序表已满；publicvoid insert int i,RecordNode xthrows Exception{ifcurlen==r.length{插入位置不合理;thrownew Exceptionif i0||i curlen{thrownew Exception；forint j=curlen;j i;j--{r[j]=r[j-1]r[i]=x;this.curlen++;//直接插入publicvoid insertSort{RecordNode temp;int i,j;fori=1;i this.curlen;i++{temp=r[i];for j=i-1;j=0temp.getKey pareTo r[j].getKey0;j--{r[j+l]=r[j];r[j+1]=temp;〃希尔publicvoid shellSortint[]d{RecordNode temp;int i,j;for intk=0;k d.length;k++{int dk=d[k];fori=dk;i this.curlen;i++{temp=r[i];for j=i-dk;j=0temp.getKeypareTo r[j].getKey0;j-=dk{r[j+dk]=temp;//带监视哨的直接插入publicvoid insertSortWithGuard{int i,j;fori=1;i this.curlen;i++{r

[0]=r[i];for j=i-l;r

[0].getKeypareTo r[j].getKey0;j--{r[j+l]=r[j]3〃冒泡r[j+l]=r

[0];publicvoid bubbleSort{RecordNode temp;boolean flag=true;forint i=1;i this.curlenflag;i++{flag=false;for int j=0;j this.curlen-1;j++{if r[j].getKey pareTor[j+1].getKey0{temp=r[j];r r[]+1]=temp;flag=true;publicint Partitionint i,intj{RecordNode pivot=r[j];；while ij{while ijpivot.getKey pareTor[j].getKey=0{j--；if iJ{；r[i]=r[j]i++；while ijpivot.getKeypareTor[i].getKey0{i++；if iJ{r[j]=r[i];j-r[i]=pivot;return i;publicvoid qSortint low,int high{iflow high{int pivotloc=Partition low,high;qSort low,pivotloc-1;qSort pivotloc+1,high;publicvoid quickSort{qSort0,this.curlen-1;publicint seqSearchComparable key{int i=0;int n=length;；while inr[i].getKeypareTokey!=0{i++if in{return i;else{return-1;publicint seqSearchWithGuardComparable key{int i=length-1;；r

[0].setKey key;whiler[i].getKeypareTof key!=0[i--returnelse{return-1;publicint binarySearchComparablekey{iflength0{int low=0;int high=length-1;whilelow=high{int mid=low+high/2;if r[mid].getKey pareTokey==0{1return mid;elseif r[mid].getKey pareTokey0{high=mid-1;}else{low=mid+1;return-1;package paixu;import java.util.Scanner;import paixu.RecordNode;import paixu.SeqList;in;publicclass Test2{publicstaticvoid mainString[]args throwsException{Scanner in=new ScannerSystem.a=whiletrue{；SeqList new SeqList6;String d[]={,,,,,}for inti=0;i6;i++{RecordNode c=new RecordNoded[i];a.insert i,c;原数组out；out）；System..printa.display;out输入进行选择）;〜System..printinout直接插入排序）;System..printin5out带监视哨的直接插入排序）;System..printin希尔排序）;out System..printin冒泡排序）;out outSystem..printin快速排序）;out System..printinSystem..printin退出）；System..printinint g=in.nextlnt;switchg{case0:return;case1:排序后outa.insertSort;outSystem..print;a.display;System..printin;break;case2:排序后out outa-insertSortWithGuard;System..printSystem..printin;break;case3:int[]aa=[1,3,5};排序后outa.shellSort aa;outSystem..print;a.display;System..printin;break;case4:排序后outa.bubbleSort;outSystem..print;a.display;System..printin;break;case5:排序后out・a.quickSort;outSystem..print;a display;System..printin;break;import java.util.Scanner;publicclass Test{publicstaticvoid mainString[]args{while12{SeqList a=newSeqList4;in;Scanner in=new ScannerSystem.输入第个元素;outfor inti=0;iv4;i++{try{System..printin+i+String c=in.next;错误outRecordNode d=new RecordNodec;a.inserti,d;・out}catchException e{System..printin+e.getMessage;不带监视哨顺序查找方法查找的结果为out.a display;System..printin;System.printin1带监视哨顺序查找方法查找的结果为out.+a.seqSearch;System.printin2二分查找方法查找的结果为out+a.seqSearchWithGuard;System..printin3+a.binarySearch;

四、实验步骤与结果（包含简要的实验步骤流程、结论陈述，可附页）排序运行结果原刿组2520153510输入-进行选择5二直接插入排序芾监视哨的直接插入排序|2希尔排序3宿泡排序快速排序5退出排序后;“15202555原数组；2520153555冶人进行选探-5二直接插入排序带监视哨的直接插入排序2希尔排序3冒泡排序4快速排序5退出排序后,115202535原刿组，2520153510输入进行选择-5「直接插入排序芾监视哨的直接插入排序2希尔排序3冒泡排序4快速排序5退出查找运行结果饰人第个元崇:饰入籍工个元素;愉入第个元素:2渝入第个元素:3e不带监视哨顺序查找方法查找的结果为1带监视哨顺序交找方法充找的结果为二21分查找方法查找的结果为输入第个元3-1素，。