数据结构实验五-查找与排序的实现.doc

《数据结构实验五-查找与排序的实现.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告课程名称数据结构实验名称查找与排序的实现系别专业班级指导教师11学号姓名实验日期实验成绩一、实验目的(1)掌握交换排序算法（冒泡排序）的基本思想；(2)掌握交换排序算法（冒泡排序）的实现方法；(3)掌握折半查找算法的基本思想；(4)掌握折半查找算法的实现方法；二、实验内容1.对同一组数据分别进行冒泡排序，输出排序结果。要求：1)设计三种输入数据序列：正序、反序、无序2)修改程序：a)将序列采用手工输入的方式输入b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂性2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。

2、3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，算法如何改进？三、设计与编码1.本实验用到的理论知识2.算法设计3.编码packagesort_search;importjava.util.Scanner;publicclassSort_Search{//冒泡排序算法publicvoidBubbleSort(intr[]){inttemp;intcount=0,move=0;booleanflag=true;for(inti=1;i

3、++;for(intj=0;jr[j+1]){temp=r[j];r[j]=r[j+1];r[j+1]=temp;move++;flag=true;}}}System.out.println("排序后的数组为：");for(inti=0;i

4、licstaticintBinarySearch(intr[],intkey){//折半查找算法intlow=0,high=r.length-1;while(low<=high){intmid=(low+high)/2;if(r[mid]==key){returnmid;}elseif(r[mid]>key){high=mid-1;}else{low=mid+1;}}return-1;}//测试publicstaticvoidmain(String[]args){Sort_Searchss=newSort_Search();intt[]=newint[13

5、];System.out.println("依次输入13个整数为：");Scannersc=newScanner(System.in);for(inti=0;i

6、：");intk=sc.nextInt();if(BinarySearch(t,k)>0)System.out.println(k+"在数组中的位置是第："+BinarySearch(t,k));elseSystem.out.println(k+"在数组中查找不到！");}}}四、运行与调试1.在调试程序的过程中遇到什么问题，是如何解决的？问题：在计算比较次数和移动次数时，计算数据明显出错。原因：在进行移动和比较的过程中，没有更新标志，导致计数出错。解决办法：在比较和移动的过程中，有进行比较和移动的操作时，更新标志。然后按标志计数。2.设计了哪些测试数据？

7、预计结果是什么？说明：测试了int类型数据：2411723453743143118933101177预计排序后结果为：4111723313337434589101177241比较次数：①无序：8次②正序：1次③反序：12次移动次数：①无序：30次②正序：0次③反序：78次查找数33的位置为：5查找数101的位置为：10查找数100的结果为：查找不到3.程序运行的结果如何I.无序输入：II.正序输入：III.反序输入：五、总结与心得六、思考题已知奇偶转换排序如下：第一趟对所有奇数的i，将a[i]和a[i+1]进行比较，第二趟对所有偶数的i,将a[i]和a[i

8、+1]进行比较,每次比较时若a[i]>a[i+1],则将二者交换，