实验二-折半查找算法设计.doc

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

1、实验二折半查找算法设计题目：折半查找算法设计问题描述：（1）分析掌握折半查找算法思想，在此基础上，设计出递归算法和循环结构两种实现方法的折半查找函数。（2）编写程序实现：在保存于数组的10000个有序数据元素中查找数据元素x是否存在。数据元素x要包含两种情况：一种是数据元素x包含在数组中；另一种是数据元素x不包含在数组中（3）数组中数据元素的有序化既可以初始赋值时实现，也可以设计一个排序函数实现。（4）根据两种方法的实际运行时间，进行两种方法时间效率的分析对比。基本要求：（1）10000个数据可以

2、初始赋值时实现，也可以调用系统的随机函数，再设计一个排序函数实现。（2）两种方法时间效率的分析对比可以有两种方法，一种是理论分析方法，一种是实际记录运行时间。（3）提交实验报告。测试数据：运行算法时，当输入的数据小于10000，例如输入9999时，显示该数据在数组中，下标为9998，并且分别显示递归和循环结构下的时间；当输入的数据大于10000时，例如输入20000时，显示这个这个数据不再该数组中。算法思想：设有数组a中元素按从小到大的次序排列，a的下界下标为low，上界下标为high，首先计算出

3、a的中间位置下标mid=（low+high)/2,1.递归算法思想：比较x和a[mid],若x=a[mid]，则查找成功；若xa[mid]，则随后调用算法自身在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。2.循环结构思想：用while(low<=high)控制循环，比较x和a[mid]，若x=a[mid]，则查找成功；若x

4、界下标为mid-1的区间继续查找；若x>a[mid]，则随后在下标为mid+1，上界下标为high的区间继续查找。当查找区间小于等于0时，查找过程结束。模块划分：1.头文件time.h中包含time()和difftime(end,start)函数，分别实现取系统当前时间和end减去start的时间差；2.头文件stdlib.h中包含rand()函数，实现随机数的生成；3.voidlist(inta[])实现对随机数从小到大的排序；4.intSearch(inta[],intlow,inthigh,

5、intx)用递归算法实现折半查找数据元素的函数；5.intBSearch(inta[],intlow,inthigh,intx)用循环结构实现折半查找数据元素的函数；6.voidmain()主函数，测试用递归算法和循环结构实现折半查找数据元素的函数。数据结构：源程序：#include#includeintBsearch(inta[],intx,intlow,inthigh){intmid;if(low>high)return-1;mid=(low+high)/2;

6、if(x==a[mid])returnmid;elseif(xtest[i])low=i+1;elsehigh=i-1;}if(i>=high)return

7、-1;}voidmain(){time_tstart,end;doubledif;intBsearch(inta[],intx,intlow,inthigh);intCsearch(inttest[],intx,intlow,inthigh);inta[10000],x;intlow=0,high=10000,mid=0;printf("请输入要查找的元素：");scanf("%ld",&x);printf("x=%ld",x);for(inti=0;i

8、;intbn;time(&start);bn=Bsearch(a,x,0,10000);if(bn==-1)printf("x不在数组a中！");elseprintf("x在数组a中，下标为%d",bn);time(&end);dif=difftime(end,start);printf("递归折半方法耗时为：%f秒",dif);intflag;time(&start);flag=Csearch(a,x,0,10000);if(flag==-1)printf("x不在数