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

实 验 报告课程名称 数据结构 实验名称 查找与排序得实现 系别 专业班级 指导教师1 学号 姓名 实验日期 实验成绩 一、实验目得(1) 掌握交换排序算法（冒泡排序)得基本思想;(2) 掌握交换排序算法（冒泡排序)得实现方法；(3) 掌握折半查找算法得基本思想；(4) 掌握折半查找算法得实现方法;二、实验内容1. 对同一组数据分别进行冒泡排序，输出排序结果。要求：1) 设计三种输入数据序列：正序、反序、无序2) 修改程序:a) 将序列采用手工输入得方式输入b) 增加记录比较次数、移动次数得变量并输出其值,分析三种序列状态得算法时间复杂性2. 对给定得有序查找集合,通过折半查找与给定值k相等得元素。3. 在冒泡算法中若设置一个变量lstEchaIndex来标记每趟排序时经过交换得最后位置,算法如何改进？三、设计与编码1、本实验用到得理论知识2、算法设计、编码packe sot_seach；imo jav、utl、Snner；ulilass o_Sach /冒泡排序算法uc voiBubblSot（nt r) nt temp; cout0，move=0；ean la=tr;f(int 1;ir、lnhflag；i+)la=flse；ct+；or（in =;jy)high=mi1；elslw=mid;retrn ； /测试publc taic voidmain（ting rgs)o_earch s=new SotSearh(）；t=nw int1；Ss、ot、prinln(”依次输入3个整数为：）；canner cnewScanner（Sstem、in）；or（nt i=0;t、length；i+）ti=s、nextnt()；Sytm、u、pn(排序前得数组为： ）;for（i i=0；it、length；+）Sysem、ou、print（t+”）；Systm、ut、pintln(）；、BubblSort(t）; /查找ile（true）Sstm、ot、in（请输入要查找得数: ”);intk=c、nexInt（）;if（BnarySerch(t,k）0）System、ot、println（k 在数组中得位置就是第： + BnrySerc(t,k）)；seSse、o、prntn（k+” 在数组中查找不到！）； 四、运行与调试1. 在调试程序得过程中遇到什么问题,就是如何解决得?问题:在计算比较次数与移动次数时，计算数据明显出错。原因:在进行移动与比较得过程中，没有更新标志，导致计数出错。解决办法：在比较与移动得过程中,有进行比较与移动得操作时，更新标志.然后按标志计数。2. 设计了哪些测试数据?预计结果就是什么?说明: 测试了t类型数据：241 1723 4 4 3 43 89310 177 预计排序后结果为: 11 17 23 31 33 33459 101 177241 比较次数： 无序：8次 正序：1次 反序：12次移动次数: 无序：0次 正序:0次 反序:78次 查找数3得位置为：5 查找数01得位置为：10 查找数100得结果为：查找不到3. 程序运行得结果如何 、无序输入:II、正序输入:II、反序输入： 五、总结与心得六、思考题已知奇偶转换排序如下：第一趟对所有奇数得i，将ai与ai进行比较，第二趟对所有偶数得i，将a与ai+1进行比较，每次比较时若aiai+1，则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序. ）试问排序结束得条件就是什么？ b）实现上述排序过程得算法如何？（请用自然语言、代码、伪代码写出该算法)