数据结构实验报告2.pdf

广东金融学院实验报告课程名称：数据结构实验编号及实验名称姓名实验地点指导教师1、实验二：排序和查找实验系别无电脑科学与技术系6学号实验日期同组其他成员班级实验时数成绩一、实验目的及要求通过编写和调用直接插入排序、 希尔排序、 冒泡排序和快速排序四种排序算法实现数据排序，充分理解各种排序算法的算法思想、排序过程及各自的时间复杂度、稳定性。2、通过编写和调用顺序查找和二分查找算法实现数据查找，掌握两个查找算法的基本思想、实现方法和时间性能。二、实验环境及相关情况包含使用软件、实验设备、主要仪器及材料等1、实验设备：微型电脑；2、软件系统：Windows XP、DWMX。三、实验内容（一） 排序装订线1参照课本，分别编写Java 程序，实现顺序表记录类RecordNode、类 KeyType。2参照课本，编写一个Java 程序，实现顺序表类SeqList，并在其中添加成员函数：length()求顺序表的当前长度； display()输出数组元素的关键字；直接插入排序算法；带监视哨的直接插入排序；希尔排序算法；起泡排序算法；快速排序算法。3编写主程序，循环选择调用以上5 个排序算法，对数组元素排序,并输出排序过程。二查找1在排序实验的基础上，在类SeqList 中添加成员函数：不带监视哨的顺序查找算法；带监视哨的顺序查找算法；二分查找算法。2编写主程序，循环选择调用以上3个查找算法，分别对键入的关键字记录进行成功和不成功查找publicpublic classclass KeyType implementsimplements Comparableprivateprivate intint key;publicpublic KeyType()publicpublic KeyType(intint key)thisthis.key=key;publicpublic intint getKey()returnreturn key;publicpublic voidvoid setKey(intint key)第 1 页 共 2 页thisthis.key=key;publicpublic String toString()publicpublic intint compareTo(KeyType another)intint thisVal=thisthis.key;intint anotherVal=another.key;returnreturn(thisValanotherVal? -1:(thisVal=anotherVal? 0:1);returnreturn key +;publicpublic classclass RecordNodeprivateprivate Comparable key;privateprivate Object element;publicpublic Object getElement()publicpublic voidvoid setElement(Object element)publicpublic Comparable getKey()publicpublic voidvoid setKey(Comparable key)publicpublic RecordNode(Comparable key)publicpublic RecordNode(Comparable key,Object element)thisthis.key=key;thisthis.element=element;thisthis.key=key;thisthis.key=key;returnreturn key;thisthis.element=element;returnreturn element;publicpublic classclass SeqListprivateprivate RecordNoder;privateprivate intint curlen;publicpublic SeqList(intint maxSize)publicpublic RecordNodegetRecord()第 2 页 共 10 页thisthis.r=newnew RecordNodemaxSize;thisthis.curlen=0;returnreturn r;publicpublic voidvoid setRecord(RecordNoder)publicpublic intint length()publicpublic voidvoid display()publicpublic voidvoid insert(intint i,RecordNode x)throwsthrows Exceptionpublicpublic voidvoid insertSort()RecordNode temp;publicpublic voidvoid shellSort(intintd)/希尔RecordNode temp;intint i,j;forfor(intint k=0;kd.length;k+)intint dk=dk;forfor(i=dk;i=0&temp.getKey() pareTo( rj.getKey()0;j-=dk)第 3 页 共 2 页thisthis.r=r;returnreturn curlen;forfor(intint i=0;icurlen;i+)System.out .print(ri.getKey()+ );ifif(curlen=r.length)throwthrow newnew Exception(顺序表已满);ifif(icurlen)throwthrow newnew Exception(插入位置不合理);forfor (intint j=curlen;ji;j-)ri=x;thisthis.curlen+;/直接插入rj=rj-1;intint i,j;forfor(i=1;i=0&temp.getKey() pareTo( rj.getKey()0;j-)rj+1=rj;rj+1=temp;rj+dk=temp;publicpublic voidvoid insertSortWithGuard()/带监视哨的直接插入intint i,j;publicpublic voidvoid bubbleSort()/冒泡RecordNode temp;publicpublic intint Partition(intint i,intint j)RecordNode pivot = rj;whilewhile (ij)whilewhile (ij & pivot.getKey() pareTo( rj.getKey()=0)ifif(ij)whilewhile(i0)ifif(ij)rj=ri;第 4 页 共 10 页forfor(i=1;ithisthis.curlen;i+)r0=ri;forfor(j=i-1;r0.getKey() pareTo( rj.getKey()0;j-)rj+1=rj;rj+1=r0;booleanboolean flag=truetrue;forfor(intint i=1;ithisthis.curlen&flag;i+)flag=falsefalse;forfor(intint j=0;j0)temp=rj;rj=rj+1;rj+1=temp;flag=truetrue; j-;ri=rj;i+;i+;j-;ri=pivot;returnreturn i;publicpublic voidvoid qSort(intint low,intint high)ifif(low0)elseelse第 5 页 共 2 页qSort(0,thisthis.curlen - 1);intint i=0;intint n=length();whilewhile(in&ri.getKey() pareTo(key)!=0)ifif(i0)returnreturn -1;intint low=0;intint high=length()-1;whilewhile(low0)elseelselow=mid+1;high=mid-1;returnreturn mid;packagepackage paixu;importimport java.util.Scanner;importimport paixu.RecordNode;importimport paixu.SeqList;publicpublic classclass Test2publicpublic staticstatic voidvoid main(String args) throwsthrows Exceptionwhilewhile(truetrue)SeqList a=newnew SeqList(6);String d=25,20,15,35,10,55;forfor(intint i=0;i6;i+)RecordNode c=newnew RecordNode(di);a.insert(i,c);Scanner in=newnew Scanner(System.in);System.out.print(原数组：);a.display();System.out.println();System.out.println(输入05进行选择);第 6 页 共 10 页System.out.println(1直接插入排序);System.out.println(2带监视哨的直接插入排序);System.out.println(3希尔排序);System.out.println(4冒泡排序);System.out.println(5快速排序);System.out.println(0退出);intint g=in.nextInt();switchswitch(g)casecase 0:casecase 4:a.bubbleSort();System.out.print(排序后:);a.display();System.out.println();breakbreak;a.quickSort();System.out.print(排序后:);a.display();System.out.println();breakbreak;returnreturn;a.insertSort();System.out.print(排序后:);a.display();System.out.println();breakbreak;a.insertSortWithGuard();System.out.print(排序后:);a.display();System.out.println();breakbreak;intint aa=1,3,5;a.shellSort(aa);System.out.print(排序后:);a.display();System.out.println();breakbreak;casecase 1:casecase 2:casecase 3:casecase 5:第 7 页 共 2 页importimport java.util.Scanner;publicpublic classclass Testpublicpublic staticstatic voidvoid main(String args)forfor(intint i=0;i4;i+)a.display();System.out.println();trytrySystem.out.println(输入第+i+个元素:);String c=in.next();RecordNode d=newnew RecordNode(c);a.insert(i, d);whilewhile(12)SeqList a=newnew SeqList(4);Scanner in=newnew Scanner(System.in);catchcatch(Exception e)System.out.println(错误：+e.getMessage();System.out.println(不带监视哨顺序查找方法查找1的结果为+a.seqSearch(1);System.out.println(带监视哨顺序查找方法查找2的结果为+a.seqSearchWithGuard(2);System.out.println(二分查找方法查找3的结果为+a.binarySearch(3);第 8 页 共 10 页四、实验步骤及结果包含简要的实验步骤流程、结论陈述，可附页排序运行结果：查找运行结果：第 9 页 共 2 页五、实验总结包括心得体会、问题答复及实验改良意见答:通过这次试验，编写和调用顺序查找和二分查找算法实现数据查找，我掌握两个查找算法的基本思想、实现方法和时间性能。六、教师评语1、完成所有规定的实验内容，实验步骤正确，结果正确；2、完成绝大部分规定的实验内容，实验步骤正确，结果正确；3、完成大部分规定的实验内容，实验步骤正确，结果正确；4、基本完成规定的实验内容，实验步骤基本正确，所完成的结果基本正确；5、未能很好地完成规定的实验内容或实验步骤不正确或结果不正确。6、其它：评定等级：优秀良好中等及格不及格教师签名：2011 年 7 月 10日第 10 页 共 10 页