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

1、深 圳 大 學(xué) 實(shí) 驗(yàn) 報(bào) 告 課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)項(xiàng)目名稱(chēng)： 查找排序之折半查找 學(xué)院： 信息工程學(xué)院 專(zhuān)業(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)康模和ㄟ^(guò)編程實(shí)現(xiàn)折半查找算法，掌握順序查找方法的理論原理和實(shí)現(xiàn)過(guò)程，從而加深對(duì)順序查找方法的理解，提高折半查找方法的編程應(yīng)用技巧。實(shí)驗(yàn)要求：仔細(xì)閱讀程序框架代碼，完成框架中的代碼編寫(xiě)要求，結(jié)果圖參考示例，請(qǐng)輸入多組數(shù)據(jù)檢測(cè)算法，要驗(yàn)證查找成功和不成功的情況。根據(jù)要求編寫(xiě)程序?qū)崿F(xiàn)折半查找

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

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

4、數(shù)據(jù)序列實(shí)際長(zhǎng)度int icount;/查找次數(shù)/- Search_Bin代碼編寫(xiě)-int Search_Bin ( int ST, int length, int key ) int low,mid,high; /low，high,mid分別用來(lái)存放待查元素的上界，下界和中間位置 low=0; /首先low從數(shù)組ST的第0號(hào)開(kāi)始 high=length-1; /high從數(shù)組ST的最后一位開(kāi)始 while(low <= high) /循環(huán)直至low小于或等于high icount+;/查找次數(shù)加一mid=(low+high)/2; /取mid的值if(STmid=key) return

5、 mid; /若定值key等于STmid則返回待查元素所在位置else if (key<STmid) high=mid-1; /不然又若定值key小于STmid則讓high指向mid的前面一位else low=mid+1; /再不然則讓low指向mid的后面一位 return -1; /查找不成功返回-1 / Search_Bin/* 主函數(shù) */int main()int i, skey;/輸入數(shù)據(jù)printf("請(qǐng)輸入數(shù)組長(zhǎng)度（不小于5）：");scanf("%d", &Dnum);printf("請(qǐng)按照從小到大的順序輸入數(shù)據(jù)

6、序列：n");for(i=0; i<Dnum; i+) scanf("%d", &Datai);printf("請(qǐng)輸入要查找的數(shù)據(jù)：");scanf("%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í)行下面語(yǔ)句printf(

7、"查找成功!n");printf("查找的數(shù)據(jù)位置在(%d)n",i);printf("查找次數(shù)(%d)",icount);printf("n");return 0;四、實(shí)驗(yàn)結(jié)論： 實(shí)結(jié)果圖：情況一、能夠在待查數(shù)組中查找到待查元素情況二、不能夠在待查數(shù)組中查找到待查元素?cái)?shù)據(jù)分析基于上面程序運(yùn)行圖可以很明顯得知整個(gè)算法的實(shí)現(xiàn)過(guò)程，針對(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)很簡(jiǎn)單，只要掌握