实验六：折半查找

《实验六：折半查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验报告六实验内容：折半查找学号： 20105101132 姓名：许丽敏 一、上机实验的问题和要求（需求分析）：[题目]设有关键字序列k={5,14,18,21,23,29,31,35}。从键盘输入上述8个整数，存放在数组bub[8]中，并进行遍历，输出其值。用折半查找的方法分别查找21,25，输出查找结果。二、程序设计的基本思想，原理和算法描述：在有序（设为升序）表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，

2、则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无该数据元素，查找失败。三、调试和运行程序过程中产生的问题及采取的措施：1.表中SST.elem[i].key的使用四、源程序及注释[源程序]程序名：实验六：折半查找.cpp #include#include#defineOVERFLOW-1#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))typedefintKeyType;typ

3、edefstructElemType{KeyTypekey;}ElemType;typedefstructSSTable{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空intlength;//表长度}SSTable;voidCreate_SSTable(SSTable&ST,intr[],intn){//操作结果：由含n个数据元素的数组r构造有序静态顺序查找表STinti;ST.elem=(ElemType*)calloc(n+1,sizeof(ElemType));//动态生成n+1个数据元素空

4、间（0号单元不用）if(!ST.elem)exit(OVERFLOW);for(i=1;i<=n;i++)ST.elem[i].key=r[i-1];//将数组r的值依次赋给STST.length=n;}voidTraverse(SSTableST){inti;for(i=1;i<=ST.length;i++)printf("%4d",ST.elem[i]);}intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找关键字等于key的数据元素，若找到，则函数值为该元素在表中的位置，否则为0intl

5、ow,high,mid;low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//在前半区间进行查找elselow=mid+1;//在后半区间进行查找}return0;}//**************************以下是主函数*****************************

6、*****voidmain(){intN=8;inti,k,m,bub[8];//键盘上输入的8个数将存放在bub[8]中KeyTypes;SSTableST;printf("初始化数组元素为:");printf("k=");for(i=0;i

7、s);printf("操作结果是:");i=Search_Bin(ST,s);if(i)printf("%d",i);elseprintf("没找到");printf("");}}五、运行结果