實(shí)驗(yàn)二-折半查找算法設(shè)計(jì)(1).doc

實(shí)驗(yàn)二 折半查找算法設(shè)計(jì)題目：折半查找算法設(shè)計(jì)問(wèn)題描述：（1）分析掌握折半查找算法思想，在此基礎(chǔ)上，設(shè)計(jì)出遞歸算法和循環(huán)結(jié)構(gòu)兩種實(shí)現(xiàn)方法的折半查找函數(shù)。（2）編寫程序?qū)崿F(xiàn)：在保存于數(shù)組的10000個(gè)有序數(shù)據(jù)元素中查找數(shù)據(jù)元素x是否存在。數(shù)據(jù)元素x要包含兩種情況：一種是數(shù)據(jù)元素x包含在數(shù)組中；另一種是數(shù)據(jù)元素x不包含在數(shù)組中（3）數(shù)組中數(shù)據(jù)元素的有序化既可以初始賦值時(shí)實(shí)現(xiàn)，也可以設(shè)計(jì)一個(gè)排序函數(shù)實(shí)現(xiàn)。（4）根據(jù)兩種方法的實(shí)際運(yùn)行時(shí)間，進(jìn)行兩種方法時(shí)間效率的分析對(duì)比?；疽螅海?）10000個(gè)數(shù)據(jù)可以初始賦值時(shí)實(shí)現(xiàn)，也可以調(diào)用系統(tǒng)的隨機(jī)函數(shù)，再設(shè)計(jì)一個(gè)排序函數(shù)實(shí)現(xiàn)。（2）兩種方法時(shí)間效率的分析對(duì)比可以有兩種方法，一種是理論分析方法，一種是實(shí)際記錄運(yùn)行時(shí)間。（3）提交實(shí)驗(yàn)報(bào)告。測(cè)試數(shù)據(jù)：運(yùn)行算法時(shí)，當(dāng)輸入的數(shù)據(jù)小于10000，例如輸入9999時(shí)，顯示該數(shù)據(jù)在數(shù)組中，下標(biāo)為9998，并且分別顯示遞歸和循環(huán)結(jié)構(gòu)下的時(shí)間；當(dāng)輸入的數(shù)據(jù)大于10000時(shí)，例如輸入20000時(shí)，顯示這個(gè)這個(gè)數(shù)據(jù)不再該數(shù)組中。算法思想：設(shè)有數(shù)組a中元素按從小到大的次序排列，a的下界下標(biāo)為low， 上界下標(biāo)為high，首先計(jì)算出a的中間位置下標(biāo)mid=（low+high)/2,1.遞歸算法思想：比較x和amid,若x=amid，則查找成功；若xamid，則隨后調(diào)用算法自身在下標(biāo)為mid+1，上界下標(biāo)為high的區(qū)間繼續(xù)查找。當(dāng)查找區(qū)間小于等于0時(shí)，查找過(guò)程結(jié)束。2.循環(huán)結(jié)構(gòu)思想：用while(low = high)控制循環(huán)，比較x和amid，若x=amid，則查找成功；若xamid，則隨后在下標(biāo)為mid+1，上界下標(biāo)為high的區(qū)間繼續(xù)查找。當(dāng)查找區(qū)間小于等于0時(shí)，查找過(guò)程結(jié)束。模塊劃分：1.頭文件time.h中包含time()和difftime(end,start)函數(shù)，分別實(shí)現(xiàn)取系統(tǒng)當(dāng)前時(shí)間和end減去start的時(shí)間差； 2.頭文件stdlib.h中包含rand()函數(shù)，實(shí)現(xiàn)隨機(jī)數(shù)的生成；3.void list(int a)實(shí)現(xiàn)對(duì)隨機(jī)數(shù)從小到大的排序；4.int Search(int a,int low,int high,int x)用遞歸算法實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)；5.int BSearch(int a, int low, int high, int x)用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)；6.void main()主函數(shù)，測(cè)試用遞歸算法和循環(huán)結(jié)構(gòu)實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)。數(shù)據(jù)結(jié)構(gòu)：源程序：#include#includeint Bsearch(int a,int x,int low,int high)int mid;if(lowhigh) return -1;mid=(low+high)/2;if(x=amid) return mid;else if(xamid)Bsearch(a,x,low,mid-1);elsereturn Bsearch(a,x,mid+1,high);int Csearch(int test,int x,int low,int high)for(int i=0;itesti) low=i+1;else high=i-1;if(i=high) return -1;void main()time_t start,end;double dif;int Bsearch(int a,int x,int low,int high);int Csearch(int test,int x,int low,int high);int a10000,x;int low=0,high=10000,mid=0;printf(請(qǐng)輸入要查找的元素：n);scanf(%ld,&x);printf(x=%ldn,x);for(int i=0;ihigh;i+)ai=i+1;int bn; time(&start);bn=Bsearch(a,x,0,10000);if(bn=-1) printf(x不在數(shù)組a中 ！n);else printf(x在數(shù)組a中，下標(biāo)為%dn,bn);time(&end);dif=difftime(end,start);printf(遞歸折半方法耗時(shí)為：%f秒n,dif); int flag; time(&start);flag=Csearch(a,x,0,10000);if(flag=-1) printf(x不在數(shù)組a中！n);else printf(x在數(shù)組a中，下標(biāo)為%ldn,flag);time(&end); dif=difftime(end,start);printf(循環(huán)折半算法耗時(shí)為：%f秒n,dif); 測(cè)試