数据结构实验---折半查找实验报告.doc
《数据结构实验---折半查找实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构实验---折半查找实验报告.doc（6页珍藏版）》请在冰点文库上搜索。
深圳大学实验报告
课程名称：
数据结构
实验项目名称：
查找排序之折半查找
学院：
信息工程学院
专业：
电子信息工程
指导教师：
报告人：
学号：
2009100000班级：
电子1班
实验时间：
2011年12月2日
实验报告提交时间：
2011年12月13日
教务处制
一、实验目的与要求：
实验目的：
通过编程实现折半查找算法，掌握顺序查找方法的理论原理和实现过程，从而加深对顺序查找方法的理解，提高折半查找方法的编程应用技巧。
实验要求：
仔细阅读程序框架代码，完成框架中的代码编写要求，结果图参考示例，请输入多组数据检测算法，要验证查找成功和不成功的情况。
根据要求编写程序实现折半查找算法，输入测试数据验证算法正确性，并进行代码分析和结果说明。
二、方法、步骤：
折半查找算法的原理：
折半查找的算法思想是将数列按有序化（递增或递减）排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。
通过一次比较，将查找区间缩小一半。
折半查找是一种高效的查找方法。
它可以明显减少比较次数，提高查找效率。
第一、首先确定整个查找区间的中间位置
mid=（low+high）/2
第二、用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
第三、对确定的缩小区域再按折半公式，重复上述步骤。
最后，得到结果：
要么查找成功，要么查找失败。
三．实验过程及内容：
（对程序代码进行说明和分析，越详细越好，代码排版要整齐，可读性要高）
1、详细阅读折半查找算法的实现过程
2、详细阅读老师提供的程序框架
3、根据实验要求进行代码的编写
4、进行代码的调试
实验代码如下：
#include
#include
constintMaxLen=100; //设定图最多包含100个顶点
intData[MaxLen]; //装载数据序列
intDnum; //表示数据序列实际长度
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;//取mid的值
if（ST[mid]==key）returnmid;//若定值key等于ST[mid]则返回待查元素所在位置
elseif（key elselow=mid+1; //再不然则让low指向mid的后面一位
}
return-1;//查找不成功返回-1
}//Search_Bin
/************主函数********************/
intmain（）{
inti,skey;
//输入数据
printf（"请输入数组长度（不小于5）：
"）;
scanf（"%d",&Dnum）;
printf（"请按照从小到大的顺序输入数据序列：
\n"）;
for（i=0;i printf（"请输入要查找的数据：
"）;
scanf（"%d",&skey）;
//调用函数Search_Bin，并将函数返回结果放在i中
i=Search_Bin（Data,Dnum,skey）;
printf（"----------------------------------------\n"）;
if（i==-1）//若Search_Bin返回值为-1则显示查找失败
printf（"查找失败!
\n"）;
else //不然则执行下面语句
{
printf（"查找成功!
\n"）;
printf（"查找的数据位置在（%d）\n",i）;
}
printf（"查找次数（%d）",icount）;
printf（"\n"）;
return0;
}
四、实验结论：
实结果图：
情况一、能够在待查数组中查找到待查元素
情况二、不能够在待查数组中查找到待查元素
数据分析
基于上面程序运行图可以很明显得知整个算法的实现过程，针对第一个图：
1、首先建立一个数组存放待查元素
2、针对定值key进行折半查找，第一个图可以得到key=11
3、mid=（low+high）/2=（0+5）/2=2.得到的是ST[2]=33,查找了一次
4、判断ST[2]=33大于key=11，即执行high=mid-1=1
5、mid=（low+high）/2=（0+1）/2=0.得到的是ST[0]=11=key，查找成功，查找了两次
6、返回待查元素所在位置
7、同理。
若查找不成功则返回查找失败
五、实验体会：
本次实验很简单，只要掌握折半查找算法的原理，那么剩下的就是花时间编写代码和调试程序。
这次实验成功实现了折半查找算法。
通过这次实验，对折半查找算法有了更加深刻的了解，同时在一定的程度上提高了编程能力。
指导教师批阅意见：
成绩评定：
指导教师签字：
年月日
备注：
升级会员 