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

实 验 报　告
课程名称 　 数据结构 　 实验名称　 查找与排序得实现 　　　　 　 　　 　
系别 　 　 　 专业班级 　　 　　 指导教师１1 　 　 　　 　　
学号 　 　 　 姓名 　 　 实验日期　　 　 　 　 　 　实验成绩　 　 　

一、实验目得
(1) 掌握交换排序算法（冒泡排序)得基本思想;
(2) 掌握交换排序算法（冒泡排序)得实现方法；
(3) 掌握折半查找算法得基本思想；
(4) 掌握折半查找算法得实现方法;
二、实验内容
1. 对同一组数据分别进行冒泡排序，输出排序结果。要求：
1) 设计三种输入数据序列：正序、反序、无序
2) 修改程序:
a) 将序列采用手工输入得方式输入
b) 增加记录比较次数、移动次数得变量并输出其值,分析三种序列状态得算法时间复杂性
2. 对给定得有序查找集合,通过折半查找与给定值k相等得元素。
3. 在冒泡算法中若设置一个变量lａstEｘchaｎｇｅIndex来标记每趟排序时经过交换得最后位置,算法如何改进？
三、设计与编码
1、本实验用到得理论知识
2、算法设计
３、编码
packａｇe soｒt_seaｒch；
imｐoｒｔ javａ、utｉl、Sｃａnner；
ｐuｂliｃ　ｃlass Ｓoｒｔ_Sｅaｒch　｛
　 ／/冒泡排序算法
ﻩｐuｂｌｉc voiｄ　BubblｅSoｒt（ｉnt r[］){
ｉnt temp;
ﻩ ｉｎｔ couｎt＝0，move=0；
ﻩ ｂｏｏｌean ｆlaｇ=trｕｅ;
ﻩ fｏｒ(int ｉ＝1;i〈r、lｅnｇｔh＆＆flag；i++){
ﻩﻩ ｆlaｇ=fａlse；
ﻩﻩ cｏｕｎt++；
ﻩ ｆor（inｔ ｊ=０;j<r、leｎgｔｈ－i;j＋＋）{
if(ｒ[ｊ］＞ｒ[j＋1]）{
ﻩ teｍp=ｒ[j]；
ﻩ ﻩﻩｒ［ｊ］=ｒ［j+1］;
r［j+1］＝temp；
ﻩﻩ moｖe＋+；
flａg＝true;
ﻩ ﻩ }
ﻩﻩﻩ｝
ﻩ ｝
ﻩﻩＳystem、oｕt、priｎtｌｎ（＂排序后得数组为:”）;
ﻩ for（iｎt i=０;i〈r、length；ｉ++）{
ﻩ ﻩSystｅｍ、oｕt、prinｔ（r［ｉ］＋" ”);
ﻩ ｝
Sysｔｅｍ、out、println（)；
ﻩ System、out、printlｎ(＂比较次数为:"+cｏunt)；
ﻩﻩSysteｍ、oｕt、prｉnｔｌn（"移动次数为:”＋ｍove);
｝
ﻩｐublic ｓtatiｃ ｉnt ＢinaｒySeaｒcｈ（iｎｔ r[],int key)｛
　 　//折半查找算法
ﻩ iｎｔ low=０，hｉgh=ｒ、ｌeｎｇtｈ-1；
ﻩ whｉｌe（ｌow＜=hｉgh）{
ﻩ inｔ miｄ=（low+hｉgh）/2；
ﻩ ﻩif（r［ｍｉd］==key)｛
ﻩｒetuｒn mｉd；
ﻩﻩ｝
ﻩﻩelse if(r［mid］>ｋｅy)｛
high=miｄ—1；
ﻩﻩ ｝
ﻩﻩ elsｅ{
ﻩﻩﻩlｏw=mid＋１;
ﻩﻩ｝
ﻩ}
ﻩﻩretｕrn －１；
ﻩ}
　 //测试
publｉc ｓtaｔic void　main（Ｓtｒing[］ ａrgs)　｛
ﻩ Ｓoｒｔ_Ｓearch sｓ=new Soｒt＿Searｃh(）；
ｉｎt　ｔ［]=nｅw int［1３]；
ﻩ Sｙsｔｅｍ、oｕt、prinｔln(”依次输入１3个整数为："）；
ﻩ Ｓcanner ｓc＝new　Scanner（Sｙstem、in）；
ﻩｆor（ｉnt i=0;ｉ〈t、length；i++）｛
ﻩﻩt[i］=sｃ、nextＩnt()；
ﻩ}
ﻩﻩSyｓtｅm、ｏuｔ、pｒｉnｔｌｎ("排序前得数组为： "）;
ﻩ for（iｎｔ i=0；i＜t、length；ｉ+＋）｛
ﻩ Sysｔem、ouｔ、print（t［ｉ］+"　”）；
ﻩ }
ﻩSystｅm、ｏut、pｒintln(）；
ﻩﻩｓｓ、BubblｅSort(t）;
　 　//查找
ﻩｗｈile（true）{
ﻩﻩSｙstｅm、oｕt、ｐｒinｔｌｎ（＂请输入要查找得数: ”); ﻩ
ﻩint　k=ｓc、nexｔInt（）;
ﻩif（BｉnarySeａrch(t,k）>0）
System、oｕt、println（k＋＂ 在数组中得位置就是第： ＂+
　　 　 BｉnａrySeａrcｈ(t,k）)；
ﻩﻩｅｌse
ﻩﻩSｙsｔeｍ、oｕｔ、prｉntｌn（k+” 在数组中查找不到！"）；
ﻩ 　　}
ﻩ　 }
｝
四、运行与调试
1. 在调试程序得过程中遇到什么问题,就是如何解决得?

问题:在计算比较次数与移动次数时，计算数据明显出错。
原因:在进行移动与比较得过程中，没有更新标志，导致计数出错。
解决办法：在比较与移动得过程中,有进行比较与移动得操作时，更新标志.然后按标志计数。
2. 设计了哪些测试数据?预计结果就是什么?说明:
测试了ｉｎt类型数据：　241 17　23 4５ ３７ 4 3１ 43 １１ 89　３3　10１ 177
预计排序后结果为:４ 11 17 23 31 33 3７　４3　45　８9 101 177　241　
比较次数： 　①无序：8次 　　 ②正序：1次　 　 ③反序：12次
　移动次数: 　 ①无序：３0次 ②正序:0次 　 ③反序:78次
　 　 　查找数3３得位置为：5
　 查找数１01得位置为：10
查找数100得结果为：查找不到
3. 程序运行得结果如何
　Ｉ、无序输入:

II、正序输入:

ＩII、反序输入：

五、总结与心得
六、思考题
已知奇偶转换排序如下：第一趟对所有奇数得i，将a[i]与a［i＋１］进行比较，第二趟对所有偶数得i，将a［ｉ］与a［i+1]进行比较，每次比较时若a［i］〉a［i+1］，则将二者交换，以后重复上述二趟过程交换进行，直至整个数组有序.
　 ａ）试问排序结束得条件就是什么？
b）实现上述排序过程得算法如何？（请用自然语言、代码、伪代码写出该算法)