数据结构实验五-查找与排序的实现(共7页).doc

精选优质文档-倾情为你奉上实 验 报 告课程名称 数据结构 实验名称 查找与排序的实现 系别 专业班级 指导教师11 学号 姓名 实验日期 实验成绩 一、实验目的(1) 掌握交换排序算法（冒泡排序）的基本思想；(2) 掌握交换排序算法（冒泡排序）的实现方法；(3) 掌握折半查找算法的基本思想；(4) 掌握折半查找算法的实现方法；二、实验内容1. 对同一组数据分别进行冒泡排序，输出排序结果。要求：1) 设计三种输入数据序列：正序、反序、无序2) 修改程序：a) 将序列采用手工输入的方式输入b) 增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂性2. 对给定的有序查找集合，通过折半查找与给定值k相等的元素。3. 在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置，算法如何改进？三、设计与编码1.本实验用到的理论知识2.算法设计3.编码package sort_search;import java.util.Scanner;public class Sort_Search /冒泡排序算法public void BubbleSort(int r) int temp;int count=0,move=0;boolean flag=true;for(int i=1;i<r.length&&flag;i+)flag=false;count+;for(int j=0;j<r.length-i;j+) if(rj>rj+1)temp=rj;rj=rj+1;rj+1=temp;move+;flag=true;System.out.println("排序后的数组为：");for(int i=0;i<r.length;i+)System.out.print(ri+" ");System.out.println();System.out.println("比较次数为："+count);System.out.println("移动次数为："+move);public static int BinarySearch(int r,int key) /折半查找算法int low=0,high=r.length-1;while(low<=high)int mid=(low+high)/2;if(rmid=key)return mid;else if(rmid>key)high=mid-1;elselow=mid+1;return -1; /测试public static void main(String args) Sort_Search ss=new Sort_Search();int t=new int13;System.out.println("依次输入13个整数为：");Scanner sc=new Scanner(System.in);for(int i=0;i<t.length;i+)ti=sc.nextInt();System.out.println("排序前的数组为： ");for(int i=0;i<t.length;i+)System.out.print(ti+" ");System.out.println();ss.BubbleSort(t); /查找while(true)System.out.println("请输入要查找的数： ");int k=sc.nextInt();if(BinarySearch(t,k)>0)System.out.println(k+" 在数组中的位置是第： "+ BinarySearch(t,k);elseSystem.out.println(k+" 在数组中查找不到！"); 四、运行与调试1. 在调试程序的过程中遇到什么问题，是如何解决的？问题：在计算比较次数和移动次数时，计算数据明显出错。原因：在进行移动和比较的过程中，没有更新标志，导致计数出错。解决办法：在比较和移动的过程中，有进行比较和移动的操作时，更新标志。然后按标志计数。2. 设计了哪些测试数据？预计结果是什么？说明： 测试了int类型数据： 241 17 23 45 37 4 31 43 11 89 33 101 177 预计排序后结果为：4 11 17 23 31 33 37 43 45 89 101 177 241 比较次数： 无序：8次 正序：1次 反序：12次 移动次数： 无序：30次 正序：0次 反序：78次 查找数33的位置为：5 查找数101的位置为：10 查找数100的结果为：查找不到3. 程序运行的结果如何 I.无序输入：II.正序输入：III.反序输入： 五、总结与心得六、思考题已知奇偶转换排序如下：第一趟对所有奇数的i，将ai和ai+1进行比较，第二趟对所有偶数的i,将ai和ai+1进行比较,每次比较时若ai>ai+1,则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序。 a)试问排序结束的条件是什么？ b)实现上述排序过程的算法如何？(请用自然语言、代码、伪代码写出该算法)专心-专注-专业