數(shù)據(jù)結(jié)構(gòu)查找算法.doc

《數(shù)據(jù)結(jié)構(gòu)查找算法.doc》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、沈陽(yáng)工程學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)室名稱(chēng)：信息工程系信息安全實(shí)驗(yàn)室實(shí)驗(yàn)課程名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)項(xiàng)目名稱(chēng)：查找算法一．實(shí)驗(yàn)?zāi)康蘑耪莆諑追N典型的查找方法。⑵掌握二叉排序樹(shù)的建立和查找算法。⑶掌握哈希表的用法。二．實(shí)驗(yàn)環(huán)境VC++6.0.三．實(shí)驗(yàn)內(nèi)容及要求1.編寫(xiě)程序，使用折半查找算法在輸入的n個(gè)有序數(shù)中進(jìn)行查找；2.已知一棵二叉排序樹(shù)如下：①假如刪除關(guān)鍵字28，畫(huà)出新二叉樹(shù)。②若查找56，需和哪些關(guān)鍵字比較。3.已知散列表的地址區(qū)間為0～11，散列函數(shù)為H(k)=k%11，采用線(xiàn)性探測(cè)法處理沖突，將關(guān)鍵字序列20,30,70,15,8,12,18,63,

2、19依次存儲(chǔ)到散列表中，試構(gòu)造出該散列表，并求出在等概率情況下的平均查找長(zhǎng)度。4.設(shè)散列函數(shù)為H(k)=k%11，采用鏈地址法處理沖突，將上例中關(guān)鍵字序列依次存儲(chǔ)到散列表中，并求出在等概率情況下的平均查找長(zhǎng)度。5.若線(xiàn)性表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率∶若找到指定的結(jié)點(diǎn)，則將該結(jié)點(diǎn)和其前驅(qū)結(jié)點(diǎn)交換，使得經(jīng)常被查找的結(jié)點(diǎn)盡量位于表的前端。試對(duì)線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)寫(xiě)出實(shí)現(xiàn)上述策略的順序查找算法（查找時(shí)必須從表頭開(kāi)始向后掃描）（選做題）四．實(shí)驗(yàn)步驟及程序清單1.#include#include

3、b.h>#includeintnum;//元素的個(gè)數(shù)int*list;//指向線(xiàn)性表的指針inti;voidcreateList(){printf("請(qǐng)輸入元素的個(gè)數(shù)：");fflush(stdin);scanf("%d",&num);list=(int*)malloc(sizeof(int)*num);printf("長(zhǎng)度為%d的線(xiàn)性表初始化成功！",num);printf("");system("pause");system("cls");printf("請(qǐng)輸入線(xiàn)性表的信息!");for(i=0;i

4、

5、請(qǐng)輸入要查找的元素：");fflush(stdin);scanf("%d",&c);low=0;high=num-1;mid=(low+high)/2;while(!taget){if(!taget&&c==list[low]){printf("要查找的元素%d在線(xiàn)性表中的位置是%d",c,low);taget=1;}if(!taget&&c==list[mid]){printf("要查找的元素%d在線(xiàn)性表中的位置是%d",c,mid);taget=1;}if(!taget&&c==list[high]){printf("

6、要查找的元素%d在線(xiàn)性表中的位置是%d",c,high);taget=1;}if(clist[mid]){low=mid+1;mid=(high+low)/2;}if(!taget&&abs(low-high)==1){printf("要查找的元素%d不在此線(xiàn)性表中",c);taget=1;}}}voidmain(){createList();inputAll();search();}2.3.數(shù)值19127015183020863地址012

7、34567891011在等概率情況下的平均查找長(zhǎng)度=（5+1+1+2+1+1+1+3+4）/9=2.114.地址01234567891011　∧　∧∧　∧∧　　　∧∧↓↓↓↓↓1270173020↓↓158↓63在等概率情況下的平均查找長(zhǎng)度=(1+1+2+1+1+2+3+4+1)/9=1.77一．結(jié)果分析1.編寫(xiě)程序，使用折半查找算法在輸入的n個(gè)有序數(shù)中進(jìn)行查找；測(cè)試5個(gè)數(shù)：1,3,5,7,9.運(yùn)行結(jié)果：結(jié)果正確。教師評(píng)語(yǔ)：