数据结构实验折半查找实验报告Word下载.docx
- 文档编号:4454566
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:7
- 大小:122.42KB
数据结构实验折半查找实验报告Word下载.docx
《数据结构实验折半查找实验报告Word下载.docx》由会员分享,可在线阅读,更多相关《数据结构实验折半查找实验报告Word下载.docx(7页珍藏版)》请在冰点文库上搜索。
学号:
2009100000班级:
电子1班
实验时间:
2011年12月2日
实验报告提交时间:
2011年12月13日
教务处制
一、实验目的与要求:
实验目的:
通过编程实现折半查找算法,掌握顺序查找方法的理论原理和实现过程,从而加深对顺序查找方法的理解,提高折半查找方法的编程应用技巧。
实验要求:
仔细阅读程序框架代码,完成框架中的代码编写要求,结果图参考示例,请输入多组数据检测算法,要验证查找成功和不成功的情况。
根据要求编写程序实现折半查找算法,输入测试数据验证算法正确性,并进行代码分析和结果说明。
二、方法、步骤:
折半查找算法的原理:
折半查找的算法思想是将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素,则将待查序列缩小为左半部分,否则为右半部分。
通过一次比较,将查找区间缩小一半。
折半查找是一种高效的查找方法。
它可以明显减少比较次数,提高查找效率。
第一、首先确定整个查找区间的中间位置
mid=(low+high)/2
第二、用待查关键字值与中间位置的关键字值进行比较;
若相等,则查找成功
若大于,则在后(右)半个区域继续进行折半查找
若小于,则在前(左)半个区域继续进行折半查找
第三、对确定的缩小区域再按折半公式,重复上述步骤。
最后,得到结果:
要么查找成功,要么查找失败。
三.实验过程及内容:
(对程序代码进行说明和分析,越详细越好,代码排版要整齐,可读性要高)
1、详细阅读折半查找算法的实现过程
2、详细阅读老师提供的程序框架
3、根据实验要求进行代码的编写
4、进行代码的调试
实验代码如下:
#include<
iostream.h>
stdio.h>
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<
ST[mid])high=mid-1;
//不然又若定值key小于ST[mid]则让high指向mid的前面一位
elselow=mid+1;
//再不然则让low指向mid的后面一位
}
return-1;
//查找不成功返回-1
}//Search_Bin
/************主函数********************/
intmain(){
inti,skey;
//输入数据
printf("
请输入数组长度(不小于5):
"
);
scanf("
%d"
&
Dnum);
请按照从小到大的顺序输入数据序列:
\n"
for(i=0;
i<
Dnum;
i++)scanf("
Data[i]);
请输入要查找的数据:
skey);
//调用函数Search_Bin,并将函数返回结果放在i中
i=Search_Bin(Data,Dnum,skey);
----------------------------------------\n"
if(i==-1)//若Search_Bin返回值为-1则显示查找失败
printf("
查找失败!
else//不然则执行下面语句
{
查找成功!
查找的数据位置在(%d)\n"
i);
查找次数(%d)"
icount);
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、同理。
若查找不成功则返回查找失败
五、实验体会:
本次实验很简单,只要掌握折半查找算法的原理,那么剩下的就是花时间编写代码和调试程序。
这次实验成功实现了折半查找算法。
通过这次实验,对折半查找算法有了更加深刻的了解,同时在一定的程度上提高了编程能力。
指导教师批阅意见:
成绩评定:
指导教师签字:
年月日
备注:
THANKS!
!
致力为企业和个人提供合同协议,策划案计划书,学习课件等等
打造全网一站式需求
欢迎您的下载,资料仅供参考
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 折半 查找 报告