第10章查找-預(yù)覽頁
【正文】 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 key 其它域 位置 主表 索引表結(jié)構(gòu)圖 索引表中的數(shù)據(jù)元素由兩個域構(gòu)成 ， key域 為被索引的若干個數(shù)據(jù)元素中關(guān)鍵字的 最大值 ， link域 為被索引的若干個數(shù)據(jù)元素中 第一個 數(shù)據(jù)元素的位置編號 。不等長索引表中的 索引長度可隨著動態(tài)插入和動態(tài)刪除過程改變 ,因此不僅適用于 靜態(tài)查找 問題，而且也適用于 動態(tài)查找 問題。 一、基本概念 或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹： （ 1）左子樹的所有結(jié)點均小于根的值； （ 2）右子樹的所有結(jié)點均大于根的值； （ 3）它的左右子樹也分別為二叉排序樹。 } BiTreeNode。 if( p) p = prightChild。 插入算法設(shè)計如下 : int Insert(BiTreeNode **root, DataType item) { BiTreeNode *current, *parent = NULL, *p。 if(current ) current = currentrightChild。 pleftChild = NULL。 else parentrightChild = p。 (2)要刪除結(jié)點 只有左孩子結(jié)點 ， 刪除該結(jié)點且使被刪除結(jié)點的雙親結(jié)點指向被刪除結(jié)點的左孩子結(jié)點 。 include include include typedef int KeyType。 struct node *leftChild。 if(rootleftChild != NULL) InTraverse(rootleftChild)。 int n = 9, i, s。 i++) Insert(amp。 if(s == 1) printf(\n數(shù)據(jù)元素 %d存在 ！ , )。 當(dāng)二叉排序樹是一棵單分支退化樹時 ， 查找成功的平均查找長度和有序順序表的平均查找長度相同 ， 即為： ?????nininA S L12/)1(1成功若每個數(shù)據(jù)元素的查找概率相等，則二叉排序樹查找成功的平均查找長度為： )1(lo g)2(1 211 ???? ??? ninA S Lkii成功3 4 5 6 7 8 10 6 4 8 3 5 7 10 (a) (b) （ a） 滿二叉排序樹時， k = log2(7+1)=3，所以查找成功的平均查找長度為： 717)34221(71)2(1 11???????? ??? inA S L iki成功（ b） 左分支退化二叉排序樹時， k = n=7， 所以查找成功的平均查找長度為： 42/)17(2/)1(1?????? ??nininA S L 成功在最壞情況下，二叉排序樹的平均查找長度為 O(n)。 因此 B_樹的動態(tài)查找效率更高 。 1 50 20 41 1 72 2 1 44 3 23 30 35 1 15 1 60 3 77 80 88 ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ ∧ root 一棵 4階 B_樹 1. 查找算法 在 B_樹上查找數(shù)據(jù)元素 x的方法為：將 Ki逐個進行比較： （ 1） 若 =Ki則查找成功 。 2. 插入算法 插入過程分兩步完成： （ 1） 利用查找算法找出該關(guān)鍵字的插入結(jié)點 （ B_樹的插入結(jié)點一定是葉結(jié)點 ） 。 39。 c 100 20 60 120 180 195 5 10 25 40 80 90 110 116 132 a b 189 200 39。 （ 2） 在結(jié)點上刪除關(guān)鍵字 ： 一種是在葉結(jié)點上刪除關(guān)鍵字 ， 共有以下三種情況： （ a） 假如要刪除關(guān)鍵字結(jié)點的關(guān)鍵字個數(shù) n大于 m/2+1， 說明刪去該關(guān)鍵字后該結(jié)點仍滿足 B_樹的定義，則可直接刪去該關(guān)鍵字。在非葉結(jié)點上刪除關(guān)鍵字時，假設(shè)要刪除關(guān)鍵字 Ki（ 1≤i≤n）， 在刪去該關(guān)鍵字后，以該結(jié)點 Pi所指子樹中的最小關(guān)鍵字 Kmin來代替被刪關(guān)鍵字 Ki所在的位置（ Pi所指子樹中的最小關(guān)鍵字 Kmin一定是在葉結(jié)點上 ），然后再以指針 Pi所指結(jié)點為根結(jié)點查找并刪除 Kmin(在非葉結(jié)點上刪除問題就轉(zhuǎn)化成了葉結(jié)點上的刪除問題 )。 構(gòu)造哈希表時出現(xiàn) Ki≠Kj（ i≠j） ,但 h(Ki)=h(Kj)的現(xiàn)象稱作 哈希沖突 。 可見，構(gòu)造哈希表一定要使用主關(guān)鍵字，不能使用次關(guān)鍵字。 我們可適當(dāng)減少內(nèi)存單元個數(shù)。 (2)與所采用的 哈希函數(shù) 有關(guān) 。 具體實現(xiàn)方法： (1)線性探查法 ?????????? )11(m o d)1()(10mimddKhdii優(yōu)點： 只要哈希表未被填滿，保證能找到一個空地址單元存 放有沖突的元素； 缺點： 容易產(chǎn)生 “堆積 ” ，大大降低了查找效率。 a = {16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77, 66, 55}。第二種方法是為發(fā)生哈希沖突的 所有同義詞建立一個單鏈表。 設(shè)計： 數(shù)據(jù)結(jié)構(gòu)設(shè)計：結(jié)構(gòu)體 HashTable由哈希表數(shù)組 、 數(shù)組個數(shù)和當(dāng)前表項個數(shù)三部分組成 ， 其中哈希表數(shù)組中每個表項的數(shù)據(jù)類型是結(jié)構(gòu)體 HashItem。 }DataType。 typedef struct { HashItem *ht。 int Initiate(HashTable *hash, int mSize) { hashtableSize = mSize。 return 1。amp。 else return j。 hashht[i].info = Active。 } int Delete(HashTable *hash, DataType x) { int i = Find(hash, x)。 } else return 0。
公司管理相關(guān)推薦
鄂ICP備17016276號-1