數(shù)據(jù)結(jié)構(gòu)試驗(yàn)---折半查找試驗(yàn)報(bào)告

1、深圳大學(xué)實(shí)驗(yàn)報(bào)告課程名稱：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目名稱:查找排序之折半查找學(xué)院：信息工程學(xué)院專業(yè)：電子信息工程指導(dǎo)教師:報(bào)告人:學(xué)號(hào)：2009100000班級(jí):電子1班實(shí)驗(yàn)時(shí)間：2011年12月2日實(shí)驗(yàn)報(bào)告提交時(shí)間：2011年12月13日教務(wù)處制一、實(shí)驗(yàn)?zāi)康呐c要求：實(shí)驗(yàn)?zāi)康模和ㄟ^編程實(shí)現(xiàn)折半查找算法，掌握順序查找方法的理論原理和實(shí)現(xiàn)過程，從而加深對(duì)順序查找方法的理解，提高折半查找方法的編程應(yīng)用技巧。實(shí)驗(yàn)要求：仔細(xì)閱讀程序框架代碼，完成框架中的代碼編寫要求，結(jié)果圖參考示例，請(qǐng)輸入多組數(shù)據(jù)檢測算法，要驗(yàn)證查找成功和不成功的情況。根據(jù)要求編寫程序?qū)崿F(xiàn)折半查找算法，輸入測試數(shù)據(jù)驗(yàn)證算法正確性，并進(jìn)行代碼分析和

2、結(jié)果說明。二、方法、步驟：折半查找算法的原理：折半查找的算法思想是將數(shù)列按有序化（遞增或遞減）排列，查找過程中采用跳躍式方式查找，即先以有序數(shù)列的中點(diǎn)位置為比較對(duì)象，如果要找的元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區(qū)間縮小一半。折半查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。第一、首先確定整個(gè)查找區(qū)間的中間位置mid=（low+high）/2第二、用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進(jìn)行比較；若相等，則查找成功若大于，則在后（右）半個(gè)區(qū)域繼續(xù)進(jìn)行折半查找若小于，則在前（左）半個(gè)區(qū)域繼續(xù)進(jìn)行折半查找第三、對(duì)確定的縮小區(qū)域再按折半公

3、式，重復(fù)上述步驟。最后，得到結(jié)果：要么查找成功，要么查找失敗。三.實(shí)驗(yàn)過程及內(nèi)容：(對(duì)程序代碼進(jìn)行說明和分析，越詳細(xì)越好，代碼排版要整齊，可讀性要高)1、詳細(xì)閱讀折半查找算法的實(shí)現(xiàn)過程2、詳細(xì)閱讀老師提供的程序框架3、根據(jù)實(shí)驗(yàn)要求進(jìn)行代碼的編寫4、進(jìn)行代碼的調(diào)試實(shí)驗(yàn)代碼如下：#include<iostream.h>#include<stdio.h>constintMaxLen=100;設(shè)定圖最多包含100個(gè)頂點(diǎn)intDataMaxLen;裝載數(shù)據(jù)序列intDnum;表示數(shù)據(jù)序列實(shí)際長度inticount;查找次數(shù)/-Search_Bin代碼編寫intSearch_Bin

4、(intST,intlength,intkey)intlow,mid,high;/low,high,mid分別用來存放待查元素的上界，下界和中間位置low=0;首先low從數(shù)組ST口的第0號(hào)開始high=length-1;/high從數(shù)組ST口的最后一位開始while(low<=high)/循環(huán)直至low小于或等于highicount+;/查找次數(shù)加一mid=(low+high)/2;/取mid的值if(STmid=key)returnmid;若定值key等于STmid則返回待查元素所在位置elseif(key<STmid)high=mid-1;/不然又若定值key小于STmid則

5、讓high指向mid的前面一位elselow=mid+1;再不然則讓low指向mid的后面一位return-1;查找不成功返回-1/Search_Bin/*主函數(shù)*/intmain()inti,skey;輸入數(shù)據(jù)printf("請(qǐng)輸入數(shù)組長度(不小于5):");scanf("%d",&Dnum);printf("請(qǐng)按照從小到大的順序輸入數(shù)據(jù)序列：n");for(i=0;i<Dnum;i+)scanf("%d",&Datai);printf("請(qǐng)輸入要查找的數(shù)據(jù)：");sca

6、nf("%d",&skey);調(diào)用函數(shù)Search_Bin,并將函數(shù)返回結(jié)果放在i中i=Search_Bin(Data,Dnum,skey);printf("n");if(i=-1)若Search_Bin返回值為-1則顯示查找失敗printf("查找失??！n");else/不然則執(zhí)行下面語句printf("查找成功!n");printf("查找的數(shù)據(jù)位置在(d)n",i);printf("查找次數(shù)(%d)",icount);printf("n");

7、return0;四、實(shí)驗(yàn)結(jié)論:實(shí)結(jié)果圖：情況一、能夠在待查數(shù)組中查找到待查元素continue"CUinistrmtor'DesIdQpT卓面還原數(shù)據(jù)結(jié)相曲聆五IoI回情況二、不能夠在待查數(shù)組中查找到待查元素*C:UsersAdministratorDesktopMX15層鏤Z握結(jié)構(gòu)實(shí)迨五口回度大"的長到S找免小5查數(shù)H44要7SIYJ-kt型輸33好7據(jù)l的7數(shù)一敗數(shù)an一失次£一要BS-屋屋rtrr-GUsersAdministratorDesktopM面還原播唱結(jié)構(gòu)'實(shí)驗(yàn)五一3'再數(shù)據(jù)分析基于上面程序運(yùn)行圖可以很明顯得知整個(gè)算法的實(shí)現(xiàn)過程，針對(duì)第一個(gè)圖：1、首先建立一個(gè)數(shù)組存放待查元素2、針對(duì)定值key進(jìn)行折半查找，第一個(gè)圖可以得到key=113、mid=(low+high)/2=(0+5)/2=2.得到的是ST2=33,查找了一次4、判斷ST2=33大于key=11,即執(zhí)行high=mid-1=15、mid=(low+high)/2=(0+1)/2=0.得到的是ST0=11=key,查找成功，查找了兩次6、返回待查元素所在位置7、同理。若查找不成功則返回查找失敗五、實(shí)驗(yàn)體會(huì)：本次實(shí)驗(yàn)