數(shù)據(jù)結(jié)構(gòu)實驗---折半查找實驗報告

《數(shù)據(jù)結(jié)構(gòu)實驗---折半查找實驗報告》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

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

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

3、若小于，則在前（左）半個區(qū)域繼續(xù)進行折半查找第三、對確定的縮小區(qū)域再按折半公式，重復(fù)上述步驟。最后，得到結(jié)果：要么查找成功，要么查找失敗。三．實驗過程及內(nèi)容：(對程序代碼進行說明和分析，越詳細越好，代碼排版要整齊，可讀性要高)1、詳細閱讀折半查找算法的實現(xiàn)過程2、詳細閱讀老師提供的程序框架3、根據(jù)實驗要求進行代碼的編寫4、進行代碼的調(diào)試實驗代碼如下：#include#includeconstintMaxLen=100;//設(shè)定圖最多包含100個頂點intData[MaxLen];//裝載數(shù)據(jù)序列intDnum;//表示數(shù)據(jù)

4、序列實際長度inticount;//查找次數(shù)//----Search_Bin代碼編寫--------------------intSearch_Bin(intST[],intlength,intkey){intlow,mid,high;//low，high,mid分別用來存放待查元素的上界，下界和中間位置low=0;//首先low從數(shù)組ST[]的第0號開始high=length-1;//high從數(shù)組ST[]的最后一位開始while(low<=high)//循環(huán)直至low小于或等于high{icount++;//查找次數(shù)加一mid=(low+high)/2;//取

5、mid的值if(ST[mid]==key)returnmid;//若定值key等于ST[mid]則返回待查元素所在位置elseif(key

6、f("%d",&Dnum);printf("請按照從小到大的順序輸入數(shù)據(jù)序列：");for(i=0;i

7、);else//不然則執(zhí)行下面語句{printf("查找成功!");printf("查找的數(shù)據(jù)位置在(%d)",i);}printf("查找次數(shù)(%d)",icount);printf("");return0;}四、實驗結(jié)論：實結(jié)果圖：情況一、能夠在待查數(shù)組中查找到待查元素情況二、不能夠在待查數(shù)組中查找到待查元素數(shù)據(jù)分析基于上面程序運行圖可以很明顯得知整個算法的實現(xiàn)過程，針對第一個圖：1、首先建立一個數(shù)組存放待查元素2、針對定值key進行折半查找，第一個圖可以得到key=113、mid=（low+high）/2=（0+5）/2=2.得到的是ST[2]=

8、33,查找