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

《實(shí)驗(yàn)二-折半查找算法設(shè)計(jì).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、實(shí)驗(yàn)二折半查找算法設(shè)計(jì)題目：折半查找算法設(shè)計(jì)問題描述：（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ù)可以

2、初始賦值時(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ì)算出

3、a的中間位置下標(biāo)mid=（low+high)/2,1.遞歸算法思想：比較x和a[mid],若x=a[mid]，則查找成功；若xa[mid]，則隨后調(diào)用算法自身在下標(biāo)為mid+1，上界下標(biāo)為high的區(qū)間繼續(xù)查找。當(dāng)查找區(qū)間小于等于0時(shí)，查找過程結(jié)束。2.循環(huán)結(jié)構(gòu)思想：用while(low<=high)控制循環(huán)，比較x和a[mid]，若x=a[mid]，則查找成功；若x

4、界下標(biāo)為mid-1的區(qū)間繼續(xù)查找；若x>a[mid]，則隨后在下標(biāo)為mid+1，上界下標(biāo)為high的區(qū)間繼續(xù)查找。當(dāng)查找區(qū)間小于等于0時(shí)，查找過程結(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.voidlist(inta[])實(shí)現(xiàn)對(duì)隨機(jī)數(shù)從小到大的排序；4.intSearch(inta[],intlow,inthigh,

5、intx)用遞歸算法實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)；5.intBSearch(inta[],intlow,inthigh,intx)用循環(huán)結(jié)構(gòu)實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)；6.voidmain()主函數(shù)，測(cè)試用遞歸算法和循環(huán)結(jié)構(gòu)實(shí)現(xiàn)折半查找數(shù)據(jù)元素的函數(shù)。數(shù)據(jù)結(jié)構(gòu)：源程序：#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("請(qǐng)輸入要查找的元素：");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不在數(shù)組a中！");elseprintf("x在數(shù)組a中，下標(biāo)為%d",bn);time(&end);dif=difftime(end,start);printf("遞歸折半方法耗時(shí)為：%f秒",dif);intflag;time(&start);flag=Csearch(a,x,0,10000);if(flag==-1)printf("x不在數(shù)