数据结构实验报告2.pdf

上传人:赵** 文档编号:38703417 上传时间:2022-09-04 格式:PDF 页数:10 大小:494.08KB
返回 下载 相关 举报
数据结构实验报告2.pdf_第1页
第1页 / 共10页
数据结构实验报告2.pdf_第2页
第2页 / 共10页
点击查看更多>>
资源描述

《数据结构实验报告2.pdf》由会员分享,可在线阅读,更多相关《数据结构实验报告2.pdf(10页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、广东金融学院实验报告课程名称:数据结构实验编号及实验名称姓名实验地点指导教师1、实验二:排序和查找实验系别无电脑科学与技术系6学号实验日期同组其他成员班级实验时数成绩一、实验目的及要求通过编写和调用直接插入排序、 希尔排序、 冒泡排序和快速排序四种排序算法实现数据排序,充分理解各种排序算法的算法思想、排序过程及各自的时间复杂度、稳定性。2、通过编写和调用顺序查找和二分查找算法实现数据查找,掌握两个查找算法的基本思想、实现方法和时间性能。二、实验环境及相关情况包含使用软件、实验设备、主要仪器及材料等1、实验设备:微型电脑;2、软件系统:Windows XP、DWMX。三、实验内容(一) 排序装订

2、线1参照课本,分别编写Java 程序,实现顺序表记录类RecordNode、类 KeyType。2参照课本,编写一个Java 程序,实现顺序表类SeqList,并在其中添加成员函数:length()求顺序表的当前长度; display()输出数组元素的关键字;直接插入排序算法;带监视哨的直接插入排序;希尔排序算法;起泡排序算法;快速排序算法。3编写主程序,循环选择调用以上5 个排序算法,对数组元素排序,并输出排序过程。二查找1在排序实验的基础上,在类SeqList 中添加成员函数:不带监视哨的顺序查找算法;带监视哨的顺序查找算法;二分查找算法。2编写主程序,循环选择调用以上3个查找算法,分别对

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;publicpub

4、lic 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;p

5、ublicpublic 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.k

6、ey=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

7、.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)/希尔Record

8、Node 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)thr

9、owthrow 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()/冒泡RecordN

10、ode 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;bo

11、oleanboolean 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);i

12、ntint 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;

13、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.

14、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:cas

15、ecase 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

16、.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 void

17、void 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.pri

18、ntln(错误:+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 页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 高考资料

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁