第10章查找(存儲(chǔ)版)
【正文】 tChild = NULL。 (3)要?jiǎng)h除結(jié)點(diǎn) 只有右孩子結(jié)點(diǎn) ， 刪除該結(jié)點(diǎn)且使被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指向被刪除結(jié)點(diǎn)的右孩子結(jié)點(diǎn) 。 struct node *rightChild。 BiTreeNode *root = NULL。 else printf(\n數(shù)據(jù)元素不存在 ！ )。 B_樹中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱為 B_樹的階 ， 一棵 m階的 B_樹或者是一棵空樹，或者是滿足下列要求的 m叉樹： (1)樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)孩子結(jié)點(diǎn)。 （ 2） 判斷該結(jié)點(diǎn)是否還有空位置 ， 即判斷該結(jié)點(diǎn)是否滿足 nm1， 若該結(jié)點(diǎn)滿足 nm1， 說明該結(jié)點(diǎn)還有空位置 ， 直接把關(guān)鍵字；若該結(jié)點(diǎn)有 n=m1， 說明該結(jié)點(diǎn)已沒有空位置 ， 要插入就要分裂該結(jié)點(diǎn) 。 c 39。其過程如圖 (e)所示 100 20 40 189 5 10 25 60 120 132 200 (e)刪去 189后的狀態(tài) 哈希表 哈希函數(shù)： 數(shù)據(jù)元素的關(guān)鍵字和該數(shù)據(jù)元素的存放位置之間的映射函數(shù) 哈希表： 通過哈希函數(shù)來確定數(shù)據(jù)元素存放位置的一種特殊表結(jié)構(gòu)。 為什么？ 例 101 建立數(shù)據(jù)元素集合 a的哈希表 , a = {180,750,600,430,541,900,460},并比較 m取值不同時(shí)的哈希沖突情況。 (3)與解決哈希沖突的 哈希沖突函數(shù) 有關(guān) 。 要求哈希函數(shù)采用 除留余數(shù)法 ，解決沖突方法采用 鏈表法 。 結(jié)構(gòu)體 HashItem由數(shù)據(jù)元素和表項(xiàng)狀態(tài)兩部分組成 ， 其中數(shù)據(jù)元素僅包括一個(gè)關(guān)鍵字域 ， 表項(xiàng)狀態(tài)的數(shù)據(jù)類型為枚舉類型 ， 表項(xiàng)狀態(tài)域有 Empty, Active和 Deleted三種狀態(tài) ， 分別表示表項(xiàng)的空 、 已占用和被刪除三種狀態(tài) 。 int tableSize。 } } int Find(HashTable *hash, DataType x) { int i = % hashtableSize。 } int Insert(HashTable *hash, DataType x) { int i = Find(hash, x)。 if(i = 0) { hashht[i].info = Deleted。建立數(shù)據(jù)元素集合 a = {180,750,600,430,541,900,460}的哈希表，并分別測試哈希表長度m=13和 m=11兩種情況得到的哈希表。 } else return 0。 } if(hashht[j].info == Active) return j。 else { hashcurrentSize = 0。 }HashItem。 并設(shè)計(jì)一個(gè)測試程序進(jìn)行測試 。 例 102建立數(shù)據(jù)元素集合 a的哈希表 。 裝填因子是指哈希表中已存入的數(shù)據(jù)元素個(gè)數(shù)ｎ與哈希地址空間大?。淼谋戎?， 即 α ＝ ｎ /ｍ ， α 越小 ， 沖突的可能性就越小 ， 但哈希表中空閑單元的比例就越大； α 越大（ 最大可取 1） 時(shí) ， 沖突的可能性就越大 ， 但哈希表中空閑單元的比例就越小 ， 存儲(chǔ)空間的利用率就越高 。 把要存儲(chǔ)的 n個(gè)數(shù)據(jù)元素通過哈希函數(shù)映射到了 m個(gè)連續(xù)內(nèi)存單元中 ，從而完成了哈希表的構(gòu)造 。其過程如圖 (d)所示 另一種是在非葉結(jié)點(diǎn)上刪除關(guān)鍵字 。 39。 （ 4） 若 keyKn則沿著指針 Pn所指的子樹繼續(xù)查找 。 平衡是指所有葉結(jié)點(diǎn)都在同一層上 ， 從而可避免出現(xiàn)像二叉排序樹那樣的分支退化現(xiàn)象 。 s = Search(root, x)。 } void main(void) { DataType test[] = {4,5,7,2,1,9,8,11,3}, x = {9}。 typedef struct node { DataType data。 4 11 5 2 7 9 1 3 8 4 11 5 2 7 9 1 8 4 5 2 7 9 1 8 4 5 2 7 9 1 4 5 2 7 1 4 5 2 7 4 5 7 4 5 4 (d) (c) (b) (a) (g) (f) (e) (i) (h) 五、刪除算法 刪除操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在 ，若不存在則結(jié)束； 存在的情況及相應(yīng)的刪除方法有如下四種： (1)要?jiǎng)h除結(jié)點(diǎn) 無孩子結(jié)點(diǎn) ， 直接刪除該結(jié)點(diǎn) 。 pdata = item。 } 三、插入算法 插入操作要求首先查找數(shù)據(jù)元素是否在二叉排序樹中存在，若 存在則返回 ；若不存在， 插入查找失敗時(shí)結(jié)點(diǎn)的左指針或右指針上。 struct node *rightChild。反之稱為 不等長索引表 。 else high = mid 1。 } 算法分析 查找成功時(shí)的平均查找長度 ASL成功 為： ????????niinii ninCPA S L112/)1(1成功查找失敗時(shí)的平均查找長度 ASL失敗 為 2/)1(111???? ????ninCPA S Lniinii失敗時(shí)間效率為 O(n) 有序順序表上的查找算法主要有 順序查找 和 折半查找 兩種方法。 } DataType。 定義要 查找數(shù)據(jù)元素的結(jié)構(gòu)體為： typedef struct { KeyType key。 else return 1。 //查找成功 else if(a[mid].key key) low = mid + 1。二級(jí)以上的索引結(jié)構(gòu)稱作 多級(jí)索引結(jié)構(gòu) 等長索引表 :索引表中的每個(gè)索引項(xiàng)對應(yīng)主表中的數(shù)據(jù)元素個(gè)數(shù)相等 。 struct node *leftChild。 } } return 0。 } /*生成新結(jié)點(diǎn) */ p = (BiTreeNode *)malloc(sizeof(BiTreeNode))。 } 下圖是調(diào)用上述插入函數(shù)依次插入數(shù)據(jù)元素 4,5,7,2,1,9,8,11,3的過程 。 }DataType。 if(rootrightChild != NULL) InTraverse(rootr
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1