2023年数据结构实验折半查找实验报告.pdf

《2023年数据结构实验折半查找实验报告.pdf》由会员分享，可在线阅读，更多相关《2023年数据结构实验折半查找实验报告.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、深 圳 大 学 实 验 报 告课程名称：_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _数据结构_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _实验项目名称：查找排序之折半查找_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _学院：信息工程学院_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _专业：电子信息工程_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _指导教师 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

2、_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _报告人;学号1 班级：电子1班实验时间：_ _ _ _ _ _ _ _ _ _ _ _ _ _2 023年 12月 2 日 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _实验报告提交时间:2 0 23年 12月 13日 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _教务处制一、实验目的与规定：实验目的：通过编程实现折半查找算法，掌握顺序查找方法的理论原理和实现过程，从而加深对顺序查找方法的理解，提高折半查找方法的编程应用技巧。实验规定：仔细阅

3、读程序框架代码，完毕框架中的代码编写规定，结果图参考示例，请输入多组数据检测算法,要验证查找成功和不成功的情况。根据规定编写程序实现折半查找算法，输入测试数据验证算法对的性，并进行代码分析和结果说明。二、方法、环节：折半查找算法的原理：折半查找的算法思想是将数列按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象,假如要找的元素值小于该中点元素，则将待查序列缩小为左半部分,否则为右半部分。通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。第一、一方面拟定整个查找区间的中间位置m i d =（l o w

4、+h i g h ）/2第二、用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功若大于，则在后（右）半个区域继续进行折半查找若小于，则在前（左）半个区域继续进行折半查找第三、对拟定的缩社区域再按折半公式，反复上述环节。最后，得到结果:要么查找成功，要么查找失败。三.实验过程及内容：(对程序代码进行说明和分析，越具体越好，代码排版要整齐,可读性要高)1、具体阅读折半查找算法的实现过程2、具体阅读老师提供的程序框架3、根据实验规定进行代码的编写4、进行代码的调试实验代码如下：#include#incl u de c onst int MaxLen=100;设定图最多包含100个顶点i

5、nt D at a M a x L e n;。/装载数据序列int Dn u m;/表达数据序列实际长度int icou n t;“/查找次数/Searc h _Bin 代码编写-int Sea r c h_B i n(int ST E,int len g t h,i nt k e y)in t 1 ow,mi d,h i g h;/1 ow,h igh,m i d 分别用来存放待查元素的上界,下界和中间位置1 ow=0;。/一方面low从数组S T 的第0 号开始high=length 1 ；/h i gh从数组ST的最后一位开始w h ile (low=high)循环直至1 ow 小于或等

6、于h i g h(i c ount+;“/查找次数力 口 一mid=(low+h i g h)/2;/取 m i d 的值A f(STmidJ=k e y)return mid;/若定值 key 等于 S Tmi d 则返回待查元素所在位置。日 s e if(keyST EmidJ)h i g h=mid-l；/不然又若定值 k e y 小于 ST m id 则让h igh指向m id的前面一位aelse 1 ow=mid+1 产 再不然则让1 ow 指向mi d 的后面一位)ret u rn-1;查找不成功返回-1 /Sear c h_Bin/*主函数*/i n t main()oin t

7、i,skey;。/输入数据pr i ntf(请输入数组长度(不小于5):0)；s canf(u%d,&Dn u m);叩r i ntf(“请按照从小到大的顺序输入数据序列：n)f o r(i=0;i Dnum;i+)oscanf(n%dn,&Da t a i);prin t f(请输入要查找的数据：);。s c a nf(%d ,&s k e y);o。调用函数s ea r c h_B i n,并将函数返回结果放在i中i =S ea rc h B i n(D a ta,D n u m,sk e y);pr i n t f(-n);if(i=-1 )/若 S e a rc h_ B in返回值为

8、-1 则显示查找失败pr i ntf(查找失败！n);el s e 不然则执行下面语句(oprintf(查找成功成)；opri ntf(查找的数据位置在(d)n,i)：。p rintf(查找次数(d),ic ount)；p r int f(n );return 0;四、实验结论：实结果图：情况一、可以在待查数组中查找到待查元素:Id 回寓I弑 辐 类 糯 省 截 煽 序 列:11 22 33 44 55 66信输入要查找的数据：11然 鬻 娜 置 在 初情况二、不可以在待查数组中查找到待查元素数据分析基于上面程序运营图可以很明显得知整个算法的实现过程，针对第一个图：1、一方面建立一个数组存放待

9、查元素2、针对定值k e y 进行折半查找，第一个图可以得到key=l 13、mid=(low+high)/2=(0+5)/2=2.得到的是 S T=3 3,查找了一次4、判断 ST2=33 大于 key=1 1,即执行 h i gh=mi d-1=15、mi d=(low+h i g h)/2 =(0+1)/2=0.得到的是 ST 0 =1 l=key,查找成功，查找了两次6、返回待查元素所在位置7、同理。若查找不成功则返回查找失败五、实验体会：本次实验很简朴，只要掌握折半查找算法的原理,那么剩下的就是花时间编写代码和调试程序。这次实验成功实现了折半查找算法。通过这次实验，对折半查找算法有了更加深刻的了解，同时在一定的限度上提高了编程能力。指导教师批阅意见:成绩评估:指导教师签字:年月日备注: