實驗二-折半查找算法設(shè)計(1).doc

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