




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
广东金融学院实验报告课程名称:数据结构实验编号及实验名称实验二:排序和查找实验系另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
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 桥式起重机培训
- 专升本考试题目及答案
- oppo面试题及答案
- 村居干部考试题及答案
- 护士技能考试题及答案
- 沙雅民警考试题及答案
- 科研诚信考试题及答案
- 九江银行面试题及答案
- 文旅融合背景下乡村文化旅游人才培养与职业发展研究报告
- 幼儿心理健康教育指导策略
- 绿植移植合同协议
- 胶质瘤术后护理查房
- 缝纫初步知识培训课件
- 2025年光伏行业上半年发展回顾与下半年形势展望
- 年中国金骨莲胶囊市场分析及发展策略研究预测报告
- 8.4 流体压强与流速的关系 课件-2024-2025学年沪科版物理八年级下册
- 输血管理相关制度
- 【北师大版】2024-2025学年一年级数学下册教学计划(及进度表)
- 商业安全培训
- 老年性痴呆病人的护理与管理
- 糖尿病足护理疑难病例讨论
评论
0/150
提交评论