顺序查找与折半查找.doc

《顺序查找与折半查找.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》实验报告七实验内容：顺序查找与折半查找学号：            姓名：  程方洁           一、上机实验的问题和要求（需求分析）：[题目]设有关键字序列k={5,14,18,21,23,29,31,35}。用折半查找的方法分别查找21,25，输出查找结果。二、程序设计的基本思想，原理和算法描述：在有序（设为升序）表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的

2、区域无该数据元素，查找失败。三、调试和运行程序过程中产生的问题及采取的措施：1、注意循环语句for(i=ST.length;!EQ(ST.elem[i],key);--i);循环体中为空语句；四、源程序及注释[源程序]程序名：7.cpp#include"stdio.h"#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineMAXSIZE100typedefintKeyType;typedefstruct{intelem[MAXSIZE];intlength;}SSTable;intsearch_seq(SSTableST

3、,KeyTypekey){//顺序查找inti;ST.elem[0]=key;for(i=ST.length;!EQ(ST.elem[i],key);--i);returni;}intsearch_bin(SSTableST,KeyTypekey){//折半查找intlow,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid]))returnmid;elseif(LT(key,ST.elem[mid]))high=mid-1;elselow=mid+1;}

4、return0;}voidmain(){SSTableST;intkey,m,n,i,num;ST.length=0;printf("请输入表的总元素数(零号单元不用)：");scanf("%d",&num);printf("请输入表的元素：");for(i=1;i

5、);}五、运行结果如输入输入表的总元素数(零号单元不用)：9输入表中元素为：514182123293135输入要查找的元素：21运行结果：4,4又如输入要查找的元素：25则运行结果为：0,0