大話資料結構（二 ）第八章

文章目錄

• **大話資料結構（二 ）第八章**
• • 第八章 查找
  • • 8.1順序查找（O(n)）
    • 8.2有序表查找
    • • 8.2.1 二分查找（O(logn)）
      • 8.2.2 插值查找（O(logn)）
      • 8.2.3 斐波那契查找（O(logn)）
    • 8.3 線性索引查找
    • 8.4 二叉排序樹（O(logn)）
    • 8.5 平衡二叉樹（O(logn)）
    • 8.6 多路查找樹（B-tree）
    • • 8.7.1 散列函數的構造方法

第八章 查找

8.1順序查找（O(n)）

優化查找的方法：設定一個哨兵i，如果不是，那麼繼續向後進行

8.2有序表查找

8.2.1 二分查找（O(logn)）

二分查找又稱為折半查找，前提是線性表中必須是有序的，順序存儲

mid=(low+ high)/2

8.2.2 插值查找（O(logn)）

關鍵字key與查找表中最大最小記錄的關鍵字比較後的查找方法，适合均勻分布的資料

mid=low + (high - low)* (key-a[low])/(a[high]-a[low])

8.2.3 斐波那契查找（O(logn)）

mid=low + F[k-1] -1 (F=｛0,1,1,2,3,5,8,13,21｝)

8.3 線性索引查找

索引分為：線性索引，樹形索引，多級索引

其中線性索引分為：稠密索引，分塊索引，反向索引

分塊索引運用的比較多

8.4 二叉排序樹（O(logn)）

二叉排序樹是鍊式存儲，易于查找，并且插入友善，删除隻需要修改連結指針即可。

8.5 平衡二叉樹（O(logn)）

查詢和插入查找都是O(logn)

平衡二叉樹（AVL樹）是一種二叉排序樹，其中每一個結點的左子樹和右子樹的高度差至多等于1（-1，0，+1）

平衡因子（Balance Factor）：二叉樹上結點的左子樹深度減去右子樹深度的值，僅有右子樹為-1，僅有左子樹為+1，有1左1右，BF=0

最小不平衡子樹：距離插入結點最近的，且平衡因子的絕對值大于1的結點為根的子樹，我們成為最小不平衡子樹

如何建構平衡二叉樹：找到最小不平衡子樹的根結點，進行旋轉：前提根節點和子節點的符号應一緻，若BF為負值，左旋（逆時針旋轉）；如果符号不一緻，進行右旋或左旋使得符号相同，再反向旋轉依次才能夠完成平衡操作。

8.6 多路查找樹（B-tree）

2-3 樹

2-3-4 樹

B 樹

B+ 樹

###8.7散清單（哈希表）

Hash哈希函數： 存儲位置=f(關鍵字)

散清單是面向查找的存儲結構，最适合的求解問題是查找與給定值相等的記錄。相當于資料庫中的主鍵，有且僅有一個的關鍵字。

散清單不适合範圍查找，适合單條記錄查找

8.7.1 散列函數的構造方法

原則：

1.計算簡單，散列函數的計算時間不應該超過其他查找技術與關鍵字比較的時間

2.散列位址分布均勻

• 直接定址法 适用于有關鍵字可以當作主鍵的

• 數字分析法 适用于手機号有大量數字，且有固定結構的，對後四位可用于散列位址，但是遇到前三位不同，後四位相同情況的手機号的時候可以反轉左環位移，前後疊加等方法，确定其唯一性。

• 平方取中法 适用于不知道關鍵字的分布，而且位數不是很大的情況

• 折疊法 将關鍵字從左到右分割成位數相等的幾部分，然後疊加求和，适用于不需要知道關鍵字的分布，且關鍵字位數比較多的情況。

• 除留餘數法 取模是mod求餘數的意思，關鍵在于選取合适的p，經驗就是若散清單表長為m，通常p為小于或等于表長（最好接近m）的最小質數或不包含小于20質因子的合數。

• 随機數法 random(key)，适用于關鍵字的長度不等時

所有的這些都可以轉化成 ASCII 或者 Unicode 編碼

關鍵字的考慮因素：

（1）計算散列位址所需要的時間

（2）關鍵字的長度

（3）散清單的大小

（4）關鍵字的分布情況

（5）記錄查找的頻率