資料結構實踐項目——查找（二）

本文針對：

9. b-樹

10. b+樹

11. 哈希表——散列結構

12. 哈希表的運算

13. 拓展：谷歌搜尋的資料結構

1、給定序列{4, 9, 0, 1, 8, 6, 3, 5, 2, 7}

（1）建立對應的3階b-樹b，請畫出構造過程

（2）從b中分别删除關鍵字為8和1的節點，畫出其過程

2、建立序列{16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}的哈希表，裝填因子定為0.8，哈希函數為h(k)=key%p，p=11

（1）采用線性探查法解決沖突，請寫出哈希表

（2）在上述哈希表中查找關鍵字為29的元素

（3）在上述哈希表中删除關鍵字為77的元素，再将其裝入

（4）采用拉鍊法解決沖突，請重做（1）-（3）

課後上機實踐

【項目1 - 驗證算法】

運作并本周視訊中所講過的算法，觀察結果并領會算法。

1、認真閱讀并驗證哈希表實施查找的相關算法，寫程式建立序列{16, 74, 60, 43, 54, 90, 46, 31, 29, 88, 77}的哈希表，裝填因子定為0.8，哈希函數為h(k)=key%p，p=11，采用線性探查法解決沖突。測試中：

（1）輸出建立的哈希表；

（2）完成關鍵字為29的元素的查找；

（3）在上述哈希表中删除關鍵字為77的元素，再顯示哈希表。

【項目2 - 用哈希法組織關鍵字】

　　已知一個關鍵字序列為if、while、for、case、do、break、else、struct、union、int、double、float、char、long、bool，共15個字元串，哈希函數h(key)為關鍵字的第一個字母在字母表中的序号，哈希表的表長為26。

　　（1）若處理沖突的方法采用線性探測法，請設計算法，輸出每個關鍵字對應的h(key)，輸出哈希表，并求成功情況下的平均查找長度。

　　（2）若處理沖突的方法采用鍊位址法，請設計算法，輸出哈希表，并計算成功情況和不成功情況下的平均查找長度。

【項目3 - b-樹的基本操作】（選看）

　　實作b-樹的基本操作。基于序列{4, 9, 0, 1, 8, 6, 3, 5, 2, 7}完成測試。

　　（1）建立對應的3階b-樹b，用括号法輸出b樹。

　　（2）從b中分别删除關鍵字為8和1的節點，用括号法輸出删除節點後的b樹。