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

深圳大学实验报告

课程名称：__________________数据结构____________________

实验项目名称：查找排序之折半查找___________________

学院：信息工程学院_______________________

专业：电子信息工程___________________

指导教师^________________________________________________

报告人;学号1班级：电子1班

实验时间：______________2023年12月2日_________________

实验报告提交时间:2023年12月13日____________________

教务处制

一、实验目的与规定：

实验目的：通过编程实现折半查找算法，掌握顺序查找方法的理论原理和实现

过程，从而加深对顺序查找方法的理解，提高折半查找方法的编程应用技巧。

实验规定：仔细阅读程序框架代码，完毕框架中的代码编写规定，结果图参考

示例，请输入多组数据检测算法,要验证查找成功和不成功的情况。根据规定

编写程序实现折半查找算法，输入测试数据验证算法对的性，并进行代码分析

和结果说明。

二、方法、环节：

折半查找算法的原理：折半查找的算法思想是将数列按有序化（递增或递减）

排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对

象,假如要找的元素值小于该中点元素，则将待查序列缩小为左半部分,否则为

右半部分。通过一次比较，将查找区间缩小一半。折半查找是一种高效的查找

方法。它可以明显减少比较次数，提高查找效率。

第一、一方面拟定整个查找区间的中间位置

mid=（low+high）/2

第二、用待查关键字值与中间位置的关键字值进行比较；

若相等，则查找成功

若大于，则在后（右）半个区域继续进行折半查找

若小于，则在前（左）半个区域继续进行折半查找

第三、对拟定的缩社区域再按折半公式，反复上述环节。最后，得到结果:要

么查找成功，要么查找失败。

三.实验过程及内容：(对程序代码进行说明和分析，越具体越好，代码排版要整齐,可读性

要高)

1、具体阅读折半查找算法的实现过程

2、具体阅读老师提供的程序框架

3、根据实验规定进行代码的编写

4、进行代码的调试

实验代码如下：

#include<iostream.h>

#include<stdio.h>

constintMaxLen=100;〃设定图最多包含100个顶点

intData[MaxLen];。。//装载数据序列

intDnum;®//表达数据序列实际长度

inticount;“/查找次数

/Search_Bin代码编写---------------

intSearch_Bin(intSTE],intlength,intkey){

int1ow,mid,high;//1ow,high,mid分别用来存放待查元素的上界,下界和中间

位置

1ow=0;。。//一方面low从数组ST□的第0号开始

high=length—1；//high从数组ST[]的最后一位开始

while(low<=high)〃循环直至1ow小于或等于high

(

icount++;“/查找次数力口一

®mid=(low+high)/2;//取mid的值

Af(ST[midJ==key)returnmid;//若定值key等于ST[mid]则返回待查元

素所在位置

。日seif(key<STEmidJ)high=mid-l；//不然又若定值key小于ST[mid]

则让high指向mid的前面一位

aelse1ow=mid+1产〃再不然则让1ow指向mid的后面一位

)

®return-1;〃查找不成功返回-1

}//Search_Bin

/************主函数********************/

intmain(){

ointi,skey;

。//输入数据

printf("请输入数组长度(不小于5):0)；

scanf(u%d",&Dnum);

叩rintf(“请按照从小到大的顺序输入数据序列：\n)

®for(i=0;i<Dnum;i++)oscanf(n%dn,&Data[i]);

printf("请输入要查找的数据：");

。scanf("%d",&skey);

o

。〃调用函数search_Bin,并将函数返回结果放在i中

i=SearchBin(Data,Dnum,skey);»

printf("------——--——------——\n");

if(i==-1)//若Search_Bin返回值为-1则显示查找失败

printf("查找失败！\n");

»else〃不然则执行下面语句

°(

oprintf("查找成功成")；

oprintf("查找的数据位置在(％d)\n",i)：

°}

。printf("查找次数(％d)",icount)；

printf("\n");

return0;

四、实验结论：

实结果图：

情况一、可以在待查数组中查找到待查元素

:Id回

寓I弑辐类糯省截煽序列:

112233445566

信输入要查找的数据：11

然鬻娜置在初

情况二、不可以在待查数组中查找到待查元素

数据分析

基于上面程序运营图可以很明显得知整个算法的实现过程，针对第一个图：

1、一方面建立一个数组存放待查元素

2、针对定值key进行折半查找，第一个图可以得到key=l1

3、mid=(low+high)/2=(0+5)/2=2.得到的是ST⑵=33,查找了一次

4、判断ST[2]=33大于key=11,即执行high=mid-1=1

5、mid=(low+high)/2=(0+1)/2=0.得到的是ST[0]=1l=key,查找成功，查找了

两次

6、返回待查元素所在位置

7、同理。若查找不成功则返回查找失败

五、实验体会：

本次实验很简朴，只要掌握折半查找算法的原理,那么剩下的就是花时间编写代码和

调试程序。这次实验成功实现了折半查找算法。通过这次实验，对折半查找算法有了更

加深刻的了解，同时在一定的限度