本章介紹了 線性表 樹和散列表 的查找方法算法實現以及各種查找方法的時間性能分析 重點 是 順序查找 二分查找 二叉樹查找 以及 散列表上查找 的基本思想和算法實現
一基本概念( 識記 )
查找的同時對表做修改操作(如插入或刪除)則相應的表稱之為 動態查找表 否則稱之為 靜態查找表
衡量一個查找算法次序優劣的標准是在查找過程中對關鍵字需要執行的平均比較次數(即平均查找長度ASL)
二線性表的查找( 簡單應用 )
線性表 上進行查找的方法主要有 三種 順序查找 二分查找 和 分塊查找
順序查找的算法基本思想是從表的一端開始順序掃描線性表依次將掃描到的結點關鍵字與給定值K比較若當前掃描到的結點關鍵字與k相等則查找成功;若掃描結束後仍未找到關鍵字等於K的結點則查找失敗
順序查找 方法可用 鏈式 存儲結構和 順序存儲結構 實現
在 順序存儲結構的順序查找算法 中所設的 哨兵 是為了簡化循環的邊界條件而引入的附加結點(元素)其作用是使for循環中省去判定防止下標越界的條件從而節省了比較的時間
在等概率情況下 查找成功 時其平均查找長度約為表長的一半(n+)/ 查找失敗 的話其平均查找長度為n+
二分查找 (又稱折半查找)它的算法思想是對一有序表中的元素從初始的查找區間開始每經過一次與當前查找區間的中點位置上的結點關鍵字進行比較若相等則查找成功否則當前查找區間的縮小一半按k值大小在某半個區間內重復相同的步驟進行查找直到查找成功或失敗為止
二分查找的遞歸算法如下(看看就行)
int BinSearch (SeqList Rint low int hightRecType k)
{
int mid=(low+hight)/;
if(low<=hight)
{
if(R[mid]key==k)return mid;//查找成功返回
if(R[mid]key>k)return BinSearch(Rlowmidk);
else return BinSearch(Rmid+hightk);
}
else return ;
}//BinSearch
二分查找在等概率的情況下查找成功的平均查找長度ASL為lg(n+)在查找失敗時所需比較的關鍵字個數不超過判定樹的深度最壞情況下查找成功的比較次數也不超過判定樹的深度┌lg(n+)┐(不小於lg(n+)的最小整數)
二分查找 只適用 於 順序存儲結構 而 不能 用 鏈式存儲結構 實現因為鏈表無法進行隨機訪問如果要訪問鏈表的中間結點就必須先從頭結點開始進行依次訪問這就要浪費很多時間還不如進行順序查找而且用鏈存儲結構將無法判定二分的過程是否結束因此無法用鏈表實現二分查找
分塊查找 (又稱索引順序查找)的基本思想是將原表分成若干塊各塊內部不一定有序但表中的塊是分塊有序的並抽取各塊中的最大關鍵字及其起始位置建立索引表因為索引表是有序的分塊查找就是先用二分查找或順序查找確定待查結點在哪一塊然後在已確定的塊中進行順序查找(不能用二分查找因為塊內是無序的)分塊查找實際上是兩次查找過程它的算法效率介與順序查找和二分查找之間
以上三種查找方法的比較如下表
查找算法 存儲結構 優點 缺點 適用於
順序查找 順序結構
鏈表結構 算法簡單且對表的結構無任何要求 查找效率低 n較小的表的查找和查找較少但改動較多的表(用鏈表作存儲結構)
二分查找 順序結構 查找效率高 關鍵字要有序且只能用順序存儲結構實現 特別適用於一經建立就很少改動又經常需要查找的線性表
分塊查找 順序結構
鏈表 在表中插入或刪除記錄時就只要在該記錄所屬塊內操作因為塊內記錄的存放是隨意的所以插入和刪除比較容易 要增加一個輔助數組的存儲空間並要進行將初始表分塊排序運算 適用於有分塊特點的記錄如一個學校的學生登記表可按系號或班號分塊
三樹的查找( 簡單應用 )
以 樹 做為表的組織形式有一個好處就是可以實現對 動態查找表 進行 高效率 的查找這裡講到了二叉排序樹和B樹以及在這些樹表上進行查找和修改操作的方法
二叉排序樹 (BST)又稱二叉查找樹其定義是二叉排序樹要或者是空樹或者滿足如下性質的二叉樹
()若它的左子樹非空則左子樹上所有結點的值均小於根結點的值;
()若它的右子樹非空則右子樹上所有結點的值均大於根結點的值;
()左右子樹本身又是一棵二叉排序樹
二叉排序樹實際上是滿足BST性質的二叉樹
二叉排序樹的插入建立的算法平均時間性能是O(nlgn)但其執行時間約為堆排序的至倍二叉排序樹的刪除操作可分三種情況進行處理
()*P是葉子則直接刪除*P即將*P的雙親*parent 中指向*P的指針域置空即可
()*P只有一個孩子*child此時只需將*child和*p的雙親直接連接就可刪去*p
()*p有兩個孩子則將操作轉換成刪除*p結點的中序後繼在刪去它之前把這個結點的數據復制到原來要刪的結點位置上就完成了刪除
二叉排序樹上的查找和二分查找類似它的關鍵字比較次數不超過樹的深度在最好的情況下二叉排序樹在生成的過程中比較勻稱此時的叉排序樹是平衡的二叉樹(也就是樹中任一結點的左右子樹的高度大致相同)它的高度約為lgn完全平衡的二叉樹高度約為lgn在最壞的情況下輸入的實例產生的二叉排序樹的高度將達到O(n)這種情況應當避免
關於 B樹 (多路平衡查找樹)它 適合 在 磁盤等直接存取設備 上組織動態的查找表是一種 外查找算法
B樹的 階 是指B樹的度數B樹的結點具有 k 個孩子時該結點必有 k(k>=) 個關鍵字
實際上B樹是二叉排序樹的推廣它就是一棵m叉樹且滿足四個性質這些性質與二叉排序樹有相似之處請仔細理解之
有關B樹的其他內容比較復雜領略一番也就是了
四散列技術( 簡單應用 )
上面的幾種查找方法均是建立在比較關鍵字的基礎上因此它們的平均和最壞情況下所需的比較次數的下界是lgn+O()
而 散列技術 可以 無需任何比較 就找到待查關鍵字其查找的期望時間為O()
散列表的概念不容易用一兩句話說清楚簡單的理解就是將所有可能出現的關鍵字的集合U(全集)映射到一個表T[m]的下標集上這個表就是散列表
而關鍵字與這個表地址之間以什麼樣的關系發生聯系呢這就要通過一個函數來建立這個函數是以U中的關鍵字為自變量以相應結點的存儲地址為函數值它就稱為 散列函數 將結點按其關鍵字的散列地址存儲到散列表的過程稱為 散列
根據某種散列函數一個關鍵字的散列函數值是唯一的但是有可能兩個或多個不同關鍵字的函數值是相同的這時就會把幾個結點存儲到同一個表位置上這時就造成 沖突 (或 碰撞 )現象這兩個關鍵字稱為該散列函數的 同義詞
要完全(不是安全)避免沖突需滿足 兩個條件 一是關鍵字集合U不大於散列表長m另一個是選擇合適的散列函數如果用h(k i )=)這樣的函數的話看看有什麼結果?:)
通常情況下U總是大大於m的因此不可能完全避免沖突沖突的頻繁程度還與表的填滿程度相關 裝填因子 α表示表中 填入的 結點數 與 表 長 的比值 通常取α ≤ 因為α越大表越滿沖突的機會也越大
散列函數 的選擇有 兩條標准 簡單和均勻 看看h(k i )=這樣的函數簡單是簡單但絕不均勻下面是常見的幾種散列函數構的造方法
平方取中法
除余法 它是用表長m來除關鍵字取余數作為散列地址若選除數m是關鍵字的基數的冪次就會使得高位不同而低位相同的關鍵字互為同義詞因此最好選取素數為除數
相乘取整法 有兩個步驟先用關鍵字key乘上某個常數A(
4.隨機數法 ，此法以關鍵字為自變量，通過一隨機函數得到的值作為散列地址。TW.WinGWIT.com
處理沖突的方法 ：當不可避免發生沖突時，就必須對沖突加以解決，使發生沖突的同義詞能存儲到表中。通常有兩類方法處理沖突： 開放定址法和拉鏈法 。前者是將所有結點均存放在散列表T[0..m-1]中，後者是將互為同義詞的結點鏈成一個單鏈表，而將此鏈表的頭指針放在散列表中。
開放定址法的一般形式為：
h i =(h(key)+d i )%m 1 ≤ i ≤ m-1
開放定址法要求散列表的裝填因子α ≤1。 開放定址法又有線性探查法、二次探查法和雙重散列法之分。
由於線性探查法在構造散列表時，遇到沖突(有同義詞)的時候會按探查序列向後面的空地址插入，從而使原來應插入到此位置的結點又與它發生沖突，當一連串的位置均已有結點時，本應插入到這些位置的結點又只能將其插入到更後面的同一個空結點上，這種散列地址不同的結點爭奪同一個後繼散列地址的現象就是 聚集 或 堆積 。(注意， 同義詞 發生 沖突不是堆積 )
為了減小堆積現象的發生，可以用 二次探查法 和 雙重散列法 進行探查。
拉鏈法 解決沖突的做法是，將所有關鍵字為 同義詞的結點 鏈接 在同一個單鏈表中。與開放定址法相比，拉鏈法有如下幾個 優點 ：
(1)拉鏈法處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，因此平均查找長度較短;( 簡單無堆積 )
(2)由於拉鏈法中各鏈表上的結點空間是動態申請的，故它更適於造表前無法確定表
From:http://tw.wingwit.com/Article/program/sjjg/201311/23743.html
