数据结构实验---折半查找实验报告

《数据结构实验---折半查找实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深圳大学实验报告课程名称：数据结构实验项目名称：查找排序之折半查找学院：信息工程学院专业：电子信息工程指导教师：报告人：学号：2009100000班级：电子1班实验时间：2011年12月2日实验报告提交时间：2011年12月13日教务处制一、实验目的与要求：实验目的：通过编程实现折半查找算法，掌握顺序查找方法的理论原理和实现过程，从而加深对顺序查找方法的理解，提高折半查找方法的编程应用技巧。实验要求：仔细阅读程序框架代码，完成框架中的代码编写要求，结果图参考示例，请输入多组数据检测算法，要验证查找成功和不成功的情况。根据要求编写程序实现折半查找算法，输入测试数据验

2、证算法正确性，并进行代码分析和结果说明。二、方法、步骤：折半查找算法的原理：折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。第一、首先确定整个查找区间的中间位置　　mid=（low+high）/2第二、用待查关键字值与中间位置的关键字值进行比较；　　若相等，则查找成功　　若大于，则在后（右）半个区域继续进行折半查找　　

3、若小于，则在前（左）半个区域继续进行折半查找第三、对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功，要么查找失败。三．实验过程及内容：(对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高)1、详细阅读折半查找算法的实现过程2、详细阅读老师提供的程序框架3、根据实验要求进行代码的编写4、进行代码的调试实验代码如下：#include#includeconstintMaxLen=100;//设定图最多包含100个顶点intData[MaxLen];//装载数据序列intDnum;//表示数据

4、序列实际长度inticount;//查找次数//----Search_Bin代码编写--------------------intSearch_Bin(intST[],intlength,intkey){intlow,mid,high;//low，high,mid分别用来存放待查元素的上界，下界和中间位置low=0;//首先low从数组ST[]的第0号开始high=length-1;//high从数组ST[]的最后一位开始while(low<=high)//循环直至low小于或等于high{icount++;//查找次数加一mid=(low+high)/2;//取

5、mid的值if(ST[mid]==key)returnmid;//若定值key等于ST[mid]则返回待查元素所在位置elseif(key

6、f("%d",&Dnum);printf("请按照从小到大的顺序输入数据序列：");for(i=0;i

7、);else//不然则执行下面语句{printf("查找成功!");printf("查找的数据位置在(%d)",i);}printf("查找次数(%d)",icount);printf("");return0;}四、实验结论：实结果图：情况一、能够在待查数组中查找到待查元素情况二、不能够在待查数组中查找到待查元素数据分析基于上面程序运行图可以很明显得知整个算法的实现过程，针对第一个图：1、首先建立一个数组存放待查元素2、针对定值key进行折半查找，第一个图可以得到key=113、mid=（low+high）/2=（0+5）/2=2.得到的是ST[2]=

8、33,查找