顺序查找与折半查找

《数据结构》实验报告七实验内容：顺序查找与折半查找学号：20095101249姓名：程方洁一、上机实验的问题和要求（需求分析）：[题目]设有关键字序列k={5,14,18,21,23,29,31,35}。用折半查找的方法分别查找21,25，输出查找结果。二、程序设计的基本思想，原理和算法描述：在有序（设为升序）表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无该数据元素，查找失败。三、调试和运行程序过程中产生的问题及采取的措施：1、注意循环语句for(i=ST.length;!EQ(ST.elem[i],key);--i);循环体中为空语句；四、源程序及注释[源程序]程序名：7.cpp#includestdio.h#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)(b))#defineMAXSIZE100typedefintKeyType;typedefstruct{intelem[MAXSIZE];intlength;}SSTable;intsearch_seq(SSTableST,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;}return0;}voidmain(){SSTableST;intkey,m,n,i,num;ST.length=0;printf(请输入表的总元素数(零号单元不用)：);scanf(%d,&num);printf(请输入表的元素：);for(i=1;inum;i++){scanf(%d,&ST.elem[i]);ST.length++;}printf(请输入要查找的元素：);scanf(%d,&key);m=search_seq(ST,key);//顺序查找n=search_bin(ST,key);//折半查找printf(%d,%d,m,n);}五、运行结果如输入输入表的总元素数(零号单元不用)：9输入表中元素为：514182123293135输入要查找的元素：21运行结果：4,4又如输入要查找的元素：25则运行结果为：0,0