數(shù)據(jù)結(jié)構(gòu)查找算法課程設(shè)計(jì)-文庫(kù)吧資料
2025-08-11 06:29本頁(yè)面
【正文】 =k) { i++。 while(in amp。}HashTable[MAXL]。 InfoType data。}BSTNode。 InfoType data。typedef NodeType SeqList[MAXL]。 InfoType data。typedef IdxType IDX[MAXI]。 int link。typedef int InfoType。注意：每次都要給sum重新賦值為零。調(diào)用SeqSearch、BinSearch、IdxSearch、SearchHT、SearchBST（CreateBST）。 /*查找失敗*/} 各模塊之間的調(diào)用關(guān)系以及算法設(shè)計(jì)函數(shù)的調(diào)用關(guān)系圖：MainSeqSearchBinSearchIdxSearchSearchHTSearchBSTCreateHTInsertHTCreateBSTInsertBST在主函數(shù)中需要定義一個(gè)SeqList R的順序表；HashTable ha 哈希表；索引表IDX I。 /*adr=（adr+1）mod m*/ } if(ha[adr].key==k) return i+1。 ha[adr].key!=k) /*采用線性探查法查找下一個(gè)地址*/ { i++。 while (ha[adr].key!=NULLKEY amp。 int m=50。 /*在左子樹(shù)中的遞歸查找*/ } else { return SearchBST(btrchild ,k) + 1。}int SearchBST(BSTNode *bt,KeyType k) /*二叉排序樹(shù)查找函數(shù)的返回值是BSTNode類型，函數(shù)有兩個(gè)參數(shù)分別是二叉排序樹(shù)bt和關(guān)鍵字k*/{ if(bt==NULL||btkey==k) /*遞歸的終結(jié)條件*/ return 1。 count++。amp。 }/* 應(yīng)在索引表的high+1中，再在對(duì)應(yīng)的線性表中進(jìn)行順序查找*/ i=I[high+1].link。 if(I[mid].key=k) high=mid1。 /*s為每塊的元素個(gè)數(shù)，應(yīng)為n/b的向上取整*/ while(low=high) /*索引表中進(jìn)行折半查找、找到的位置為high+1*/ { count++。 /*返回的是總的平均查找長(zhǎng)度*/ }}索引查找：int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /*索引查找函數(shù)值返回的是整型，函數(shù)有五個(gè)參數(shù)，分別是索引表I、分的塊數(shù)b、順序表R、關(guān)鍵字個(gè)數(shù)和關(guān)鍵字*/{ int low=0,high=b1,mid,i,count=0。 if(R[mid].keyk) /*繼續(xù)在R【low…mid1】中查找*/ high=mid1。 /*每循環(huán)一次count++*/ mid=(low+high)/2。 int count=0。 else return i+1。 R[i].key!=k) /*從表頭開(kāi)始找*/ i++。 while (in amp。哈希函數(shù)的構(gòu)造有直接定址法、除留余數(shù)法和數(shù)字分析法，常用的是除留余數(shù)法，它是用關(guān)鍵字k除以某個(gè)不大于哈希表長(zhǎng)度m的數(shù)p，將所得到的余數(shù)作為哈希地址。哈希表查找：在用哈希表查找時(shí)先建立一個(gè)哈希表，哈希表主要用于快速查找，哈希表的查找過(guò)程和建表過(guò)程類似。重要性質(zhì)：中序遍歷二叉排序樹(shù)所得到中序序列是以一個(gè)遞增有序序列。即動(dòng)態(tài)查找時(shí)就需要用到鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。注：索引表是一個(gè)遞增有序表 分塊查找的基本思路是：① 首先查找索引表，因?yàn)樗饕硎怯行虮?，所以可以采用折半查找或者順序查找，?lái)確定待查元素在哪一塊；② 再已確定的塊中進(jìn)行順序查找（因?yàn)閴K內(nèi)元素?zé)o序，所以只能用順序查找）列:設(shè)有一個(gè)線性表采用順序存儲(chǔ)，有20個(gè)元素，將其分成4（b=4）部分，每部分有5個(gè)元素（s=5），該索引表的存儲(chǔ)結(jié)構(gòu)如下圖所示： 08114263901441053452210666341585718LinkKey81993110401138125413661446157116781780188519100在如圖所示的存儲(chǔ)結(jié)構(gòu)中，查找關(guān)鍵字k=80時(shí)，首先將k和索引表中個(gè)關(guān)鍵字比較，直到找到大于等于k的值，因此若關(guān)鍵字k=80存在則必定在第四塊中，由 I
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1