數(shù)據(jù)結(jié)構(gòu)（Java版）課件 第8章 查找

第8章查找目錄2查找的基本概念和查找表衡量查找算法效率標(biāo)準(zhǔn)靜態(tài)表查找動態(tài)表查找小結(jié)第一節(jié)查找的基本概念和查找表1.1查找的定義1.2查找結(jié)果的表現(xiàn)形式1.3查找表1.1查找的定義

查找是數(shù)據(jù)結(jié)構(gòu)的一種基本操作，就是在由一組記錄組成的集合中尋找屬性值符合特定條件的數(shù)據(jù)元素。若集合中存在符合條件的記錄，則查找成功，否則查找失敗。查找條件由包含指定關(guān)鍵字的數(shù)據(jù)元素給出。1.2查找結(jié)果的表現(xiàn)形式根據(jù)不同的應(yīng)用需求，查找結(jié)果有以下表示形式：

(1)如果判斷數(shù)據(jù)結(jié)構(gòu)是否包含某個特定元素，則查找結(jié)果為是、否兩個狀態(tài)。

(2)如果根據(jù)關(guān)鍵字查找以獲得特定元素的其他屬性，則查找結(jié)果為特定數(shù)據(jù)元素。

(3)如果數(shù)據(jù)結(jié)構(gòu)中含有多個關(guān)鍵字值相同的數(shù)據(jù)元素，需要確定返回首次出現(xiàn)的元素或者是返回數(shù)據(jù)元素集合。

(4)如果查找不成功，返回相應(yīng)的信息。1.3查找表

查找表是一種以同一類型的記錄構(gòu)成的集合為邏輯結(jié)構(gòu)、以查找為核心運算的靈活的數(shù)據(jù)結(jié)構(gòu)。

在查找表中常做的操作有建表、查找、讀表、插入和刪除。查找表分為靜態(tài)查找表和動態(tài)查找表兩種。靜態(tài)查找表是指對表的操作不包括對表的修改的表；動態(tài)查找表是指對表的操作包括對表中的記錄進行插入和刪除的表。第二節(jié)衡量查找算法效率標(biāo)準(zhǔn)2.1平均查找長度2.衡量查找算法效率標(biāo)準(zhǔn)——平均查找長度查找的主要操作是關(guān)鍵字的比較，所以衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)是比較次數(shù)的期望值。給定值與關(guān)鍵字值的比較次數(shù)的期望值也稱為平均查找長度(AverageSearchLength)，記為ASL。對于一個含有n個記錄的查找表，查找成功時的平均查找長度如下：其中，pi是查找第i條記錄的概率，ci是查找第i條記錄時關(guān)鍵字值和給定值比較的次數(shù)。第三節(jié)靜態(tài)表查找3.1順序查找3.2二分查找3.3分塊查找

靜態(tài)查找表是指對表的操作不包括對表的修改的表，可以用順序表或線性鏈表進行表示。本節(jié)中只討論順序表上查找的實現(xiàn)方法，分為順序查找、二分查找和分塊查找3種。3.1順序查找1、順序查找算法

順序查找是指從順序表的一端開始依次將每一個數(shù)據(jù)元素的關(guān)鍵字值與給定值進行比較，若某個數(shù)據(jù)元素的關(guān)鍵字值和給定值相等，則查找成功，否則查找失敗。順序查找又叫線性查找。3.1順序查找

2.算法性能分析假設(shè)查找每個數(shù)據(jù)元素的概率相等，對于一個長度為n的順序表，其平均查找長度如下：若查找失敗，關(guān)鍵字比較次數(shù)為n，因此順序查找的時間復(fù)雜度為O(n)。3.2二分查找1.二分查找算法的實現(xiàn)

二分查找是對有序表進行的查找。通常假定有序表按關(guān)鍵字值從小到大有序排列，二分查找首先取整個表的中間數(shù)據(jù)元素的關(guān)鍵字值和給定值進行比較，若相等，則查找成功；若給定值小于該元素的關(guān)鍵字值，則在左子表中重復(fù)上述步驟；若給定值大于該元素的關(guān)鍵字值，則在右子表中重復(fù)上述步驟，直到找到關(guān)鍵字值為key的記錄或子表長度為0。二分查找又叫折半查找。算法實現(xiàn)2.算法性能分析

假設(shè)查找每個數(shù)據(jù)元素的概率相等，對于一個長度為n=2k-1的有序表，線性表最多被平分k=log2(n+1)次即可完成查找。又因為在i次查找中可以找到的元素個數(shù)為2i-1個，所以其平均查找長度如下：

因此，查找的時間復(fù)雜度為O(log2n)。3.3分塊查找

分塊查找是將線性表分為若干塊，塊之間是有序的，塊中的元素不一定有序，將每塊中最大的關(guān)鍵字值按塊的順序建立索引順序表，在查找時首先通過索引順序表確定待查找元素可能所在的塊，然后在塊中尋找該元素。

索引順序表是有序表，可以采用順序查找或者二分查找；塊中元素?zé)o序，必須采用順序查找。

假設(shè)線性表中數(shù)據(jù)元素的關(guān)鍵字為{23,12,3,4,5,56,75,24,44,33,77,76,78,90,98},有15個結(jié)點，被分為3塊，則要求每一塊中的最大關(guān)鍵字值小于后一塊中的最小關(guān)鍵字值，分塊有序表的索引存儲表如圖所示。2.算法性能分析由于分塊查找是順序查找和二分查找的結(jié)合，因此分塊查找的平均查找長度為查找索引表確定元素所在塊的平均查找長度Lb加上在塊中查找元素的平均查找長度Lc。一般將長度為n的線性表均勻分成b塊，每塊中含有s個元素，即b=。假定查找每個元素的概率相同，若使用順序查找確定元素所在的塊，則分塊查找的平均查找長度如下：若使用二分查找確定元素所在的塊，則分塊查找的平均查找長度如下：第四節(jié)動態(tài)表查找4.1二叉排序樹查找4.2平衡二叉樹4.3B-樹和B+樹4.4哈希表查找

動態(tài)查找表是指對表的操作包括對表的修改的表，即表結(jié)構(gòu)本身實際是在查找過程中動態(tài)生成的。動態(tài)查找表有多種不同的實現(xiàn)方法，本節(jié)中只討論在各種樹形結(jié)構(gòu)上查找的實現(xiàn)方法。4.1二叉排序樹查找1、二叉排序樹的概念二叉排序樹是具有下列性質(zhì)的二叉樹。(1)若右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值。(2)若左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值。(3)左、右子樹也為二叉排序樹。二叉排序樹可以為空樹，其結(jié)構(gòu)如圖所示2.二叉排序樹查找算法的實現(xiàn)二叉排序樹查找過程的主要步驟如下。

(1)若查找樹為空，則查找失敗。

(2)若查找樹非空，且給定值key等于根結(jié)點的關(guān)鍵字值，查找成功。

(3)若查找樹非空，且給定值key小于根結(jié)點的關(guān)鍵字值，在根結(jié)點的左子樹上進行查找過程。

(4)若查找樹非空，且給定值key大于根結(jié)點的關(guān)鍵字值，在根結(jié)點的右子樹上進行查找過程。二叉排序樹的節(jié)點算法定義二叉排序樹的類結(jié)構(gòu)算法定義二叉排序樹的查找算法

3.二叉排序樹插入算法的實現(xiàn)

在向二叉排序樹中插入一個結(jié)點時首先對二叉排序樹進行查找，若查找成功，則結(jié)點已存在，不需要插入；若查找失敗，再將新結(jié)點作為葉子結(jié)點插入到二叉排序樹中。4.二叉排序樹刪除算法的實現(xiàn)

在二叉排序樹中刪除一個元素要保證刪除后的樹仍然是二叉排序樹，分為3種情況進行討論。

(1)若待刪除的結(jié)點是葉子結(jié)點，可直接刪除。

(2)若待刪除的結(jié)點只有左子樹或右子樹，則將左子樹或右子樹的根結(jié)點代替被刪除結(jié)點的位置。

(3)若待刪除的結(jié)點有左、右兩棵子樹，在中序遍歷下則將待刪除結(jié)點的前驅(qū)結(jié)點或后繼結(jié)點代替被刪除結(jié)點的位置，并將該結(jié)點刪除。4.2平衡二叉樹1.平衡二叉樹的概念

平衡二叉樹是左、右子樹深度之差的絕對值小于2并且左、右子樹均為平衡二叉樹的樹。平衡二叉樹又叫AVL樹，可以為空，其某個結(jié)點的左子樹深度與右子樹深度之差稱為該結(jié)點的平衡因子或平衡度。2.平衡二叉樹的實現(xiàn)

在平衡二叉樹上刪除或插入結(jié)點后可能會使二叉樹失去平衡。對非平衡二叉樹的調(diào)整可依據(jù)失去平衡的原因分為4種情況進行，分別是LL型、RR型、LR型、RL型(假設(shè)在平衡二叉樹上因插入新結(jié)點而失去平衡的最小子樹的根結(jié)點為A)。1)LL型平衡旋轉(zhuǎn)(單向右旋)

原因：在A的左孩子的左子樹上插入新結(jié)點，使A的平衡度由1變?yōu)?，以A為根的子樹失去平衡。

調(diào)整：提升A的左孩子B為新子樹的根結(jié)點，A為B的右孩子，同時將B的右子樹BR調(diào)整為A的左子樹，如圖所示。2)RR型平衡旋轉(zhuǎn)(單向左旋)

原因：在A的右孩子的右子樹上插入新結(jié)點，使A的平衡度由-1變?yōu)?2，以A為根的子樹失去平衡。

調(diào)整：提升A的右孩子B為新子樹的根結(jié)點，A為B的左孩子，同時將B的左子樹BL調(diào)整為A的右子樹，如圖所示。3)LR型平衡旋轉(zhuǎn)(先左旋后右旋)

原因：在C的左孩子的右子樹上插入新結(jié)點，使C的平衡度由1變?yōu)?，以C為根的子樹失去平衡。

調(diào)整：提升C的左孩子A的右孩子B為新子樹的根結(jié)點，C為B的右孩子，A為B的左孩子，將B的左子樹BL調(diào)整為A的右子樹，將B的右子樹BR調(diào)整為C的左子樹，如圖所示。4)RL型平衡旋轉(zhuǎn)(先右旋后左旋)

原因：在A的右孩子的左子樹上插入新結(jié)點，使A的平衡度由-1變?yōu)?2，以A為根的子樹失去平衡。

調(diào)整：提升A的右孩子C的左孩子B為新子樹的根結(jié)點，A為B的左孩子，C為B的右孩子，將B的左子樹CL調(diào)整為A的右子樹，將B的右子樹BR調(diào)整為C的左子樹，如圖所示。3.算法性能分析

采用平衡二叉樹提高了查找操作的速度，但是使插入和刪除操作復(fù)雜化，因此平衡二叉樹適用于二叉排序樹一經(jīng)建立就很少進行插入和刪除操作而主要進行查找操作的場合中，其查找的時間復(fù)雜度為O(log2n)。4.3B-樹和B+樹1.B-樹的概念

B-樹是一種平衡的多路查找樹，在文件系統(tǒng)中B-樹已經(jīng)成為索引文件的一種有效結(jié)構(gòu)。一棵m階的B-樹是滿足下列特征的m叉樹。 (1)樹中的每個結(jié)點最多有m棵子樹。 (2)若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹。 (3)所有的非終端結(jié)點包含信息(n,P0,K1,P1,K2,P2,…,Kn,Pn)。其中，Ki(1≤i≤n)為關(guān)鍵字，且Ki<Ki+1；Pj(0≤j<n)是指向子樹根結(jié)點的指針且Pj所指子樹中所有結(jié)點的關(guān)鍵字值都小于Kj+1，Pn所指子樹中所有結(jié)點的關(guān)鍵字值均大于Kn。2.B+樹的結(jié)構(gòu)和差異B+和B-樹的結(jié)構(gòu)大致相同，一顆m階的B-樹和一顆m階的B+樹的差異在于：

（1）在B-樹中，每一個結(jié)點含有n個關(guān)鍵字和n+1棵子樹；而在B+樹中，每一個結(jié)點含有n個關(guān)鍵字和n棵子樹。

（2）在B-樹中，每個結(jié)點中的關(guān)鍵字個數(shù)n的取值范圍是m2-1≤n≤m-1；而在B+樹中，每個結(jié)點中的關(guān)鍵字個數(shù)n的取值范圍是m2≤n≤m，樹的根結(jié)點的關(guān)鍵字個數(shù)的取值范圍是1≤n≤m。

（3）B+樹中的所有葉子結(jié)點包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，且所有葉子結(jié)點按關(guān)鍵字值從小到大的順序依次鏈接。

（4）B+樹中所有非葉子結(jié)點僅起到索引的作用，即結(jié)點中的每一個索引項只含有對應(yīng)子樹的最大關(guān)鍵字和指向該子樹的指針，不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。4.4哈希表查找1.相關(guān)概念

哈希存儲是以關(guān)鍵字值為自變量通過一定的函數(shù)關(guān)系(稱為散列函數(shù)或者哈希函數(shù))計算出數(shù)據(jù)元素的存儲地址，并將該數(shù)據(jù)元素存入到相應(yīng)地址的存儲單元。在查找時只需要根據(jù)查找的關(guān)鍵字采用同樣的函數(shù)計算出存儲地址即可到相應(yīng)的存儲單元取得數(shù)據(jù)元素。

對于含有n個數(shù)據(jù)元素的集合總能找到關(guān)鍵字與哈希地址一一對應(yīng)的函數(shù)。若選取函數(shù)f(key)=key，數(shù)據(jù)元素中的最大關(guān)鍵字為m，需要分配m個存儲單元，由于關(guān)鍵字集合比存儲空間大得多，可能造成存儲空間的很大浪費。此外，通過哈希函數(shù)變換后可能將不同的關(guān)鍵字映射到同一個哈希地址上，這種現(xiàn)象叫沖突。所以使用哈希方法進行查找時需要關(guān)注兩個問題，一是要構(gòu)造好的哈希函數(shù)，盡量加快地址計算速度，減少存儲空間的浪費；二是制定解決沖突的方法。

根據(jù)哈希函數(shù)和處理沖突的方法，將一組關(guān)鍵字映射到一個有限的、地址連續(xù)的地址集合空間上，并且數(shù)據(jù)元素的存儲位置由關(guān)鍵字通過哈希函數(shù)計算得來，這樣的表稱為哈希表。2哈希函數(shù)哈希函數(shù)的構(gòu)造需要遵循以下兩個原則：

1.盡可能將關(guān)鍵字均勻地映射到地址集合空間，減少存儲空間的浪費。

2.盡可能降低沖突發(fā)生的概率。(1)直接地址法：它是取關(guān)鍵字的某個線性函數(shù)值為哈希地址。

直接地址法簡單，不會產(chǎn)生沖突，但是關(guān)鍵字值往往是離散的，且關(guān)鍵字集合比哈希地址大，會造成存儲空間的浪費。(2)除留余數(shù)法：它是以關(guān)鍵字除p的余數(shù)作為哈希地址，其中m為哈希表長度。

使用除留余數(shù)法p的選擇很重要，否則會造成嚴(yán)重沖突。例如，若取p=2k，則H(key)=key%p的值僅僅是用二進制表示的key右邊的k個位，造成了關(guān)鍵字的映射并不均勻，易造成沖突。通常，為了獲得比較均勻的地址分布，一般令p為小于等于m的某個最大素數(shù)。(3)數(shù)字分析法:

對關(guān)鍵字的各位進行分析，丟掉分布不均勻的位，留下分布均勻的位作為哈希地址。對于不同的關(guān)鍵字集合，所保留的地址可能不相同，因此這種方法主要應(yīng)用于關(guān)鍵字的位數(shù)比存儲區(qū)域的地址碼位數(shù)多的情況，并且在使用時需要能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度的情況。(4)平方取中法:

取關(guān)鍵字平方的中間幾位作為哈希地址的方法。一個數(shù)的平方值的中間幾位和數(shù)的每一位都有關(guān)系，因此平方取中法得到的哈希地址和關(guān)鍵字的每一位都有關(guān)系，使得哈希地址的分布較為均勻。

平方取中法適用于關(guān)鍵字中的每一位取值都不夠分散或者較分散的位數(shù)小于哈希地址所需要的位數(shù)的情況。(5)折疊法:

將關(guān)鍵字自左向右或自右向左分成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后將這幾部分疊加求和，并按哈希表的表長取最后幾位作為哈希地址。常用的折疊法有以下兩種。

(1)移位疊加法：將分割后的各部分的最低位對齊，然后相加。

(2)間界疊加法：從一端向另一端沿分割界來回折疊后對齊最后一位相加。折疊法適用于位數(shù)較多，并且每一位的取值都分散均勻的情況。(6)隨機數(shù)法：取關(guān)鍵字的隨機數(shù)函數(shù)值為它的哈希地址，即H(key)=random(key)此方法主要適用于關(guān)鍵字長度不相等的情況。3解決沖突的方法(1)開放定址法:

當(dāng)沖突發(fā)生時形成一個地址序列，沿著這個地址序列逐個探測，直到找到一個空的開放地址，將發(fā)生沖突的數(shù)據(jù)存放到該地址中。地址序列的值可表示如下：

其中H(key)是關(guān)鍵字值為key的哈希函數(shù)，m為哈希表長，di為每次探測時的地址增量。

根據(jù)地址增量取值的不同可以得到不同的開放地址處理沖突探測方法，主要分為3種。<1>線性探測法線性探測法的地址增量如下：

其中i為探測次數(shù)。這種方法在解決沖突時，依次探測下一個地址，直到找到一個空的地址，若在整個空間中都找不到空地址將產(chǎn)生溢出。

利用線性探測法解決沖突問題容易造成數(shù)據(jù)元素的“聚集”，即多個哈希地址不同的關(guān)鍵字爭奪同一個后繼哈希地址。假設(shè)表中的第i、i+1、i+2地址非空，則下一次哈希地址為i、i+1、i+2的數(shù)據(jù)都企圖填入到i+3的位置處。這種現(xiàn)象發(fā)生的根本原因是查找序列過分集中在發(fā)生沖突的存儲單元后面，沒有在整個哈希表空間分散開來。<2>二次探測法二次探測法的地址增量如下：其中m為哈希表長。這種方法能夠避免“聚集”現(xiàn)象的發(fā)生，但是不能探測到哈希表上的所有存儲單元。<3>雙哈希函數(shù)探測法雙哈希函數(shù)探測法是使用另外一個哈希函數(shù)RH(key)計算地址增量。哈希地址的計算方法可以表示如下：這種方法也可以避免“聚集”現(xiàn)象的發(fā)生。(2)鏈地址法

鏈地址法是將所有具有相同哈希地址的不同關(guān)鍵字的數(shù)據(jù)元素鏈接到同一個單鏈表中。若哈希表的長度為m，則可將哈希表定義為一個由m個頭指針組成的指針數(shù)組T［0..m-1］，凡是哈希地址為i的數(shù)據(jù)元素均以結(jié)點的形式插入到T［i］為頭指針的鏈表中。

假設(shè)一組數(shù)據(jù)元素的關(guān)鍵字序列為{2,4,6,7,9}，按照哈希函數(shù)H(key)=key%4和鏈地址法處理沖突得到的哈希表如圖所示。（3）公共溢出區(qū)法和再哈希法1.公共溢出區(qū)法公共溢出區(qū)法是另建一個溢出表，當(dāng)不發(fā)生沖突時數(shù)據(jù)元素存入基本表，當(dāng)發(fā)生沖突時數(shù)據(jù)元素存入溢出表。2.再哈希法再哈希法是當(dāng)發(fā)生沖突時再使用另一個哈希函數(shù)得到一個新的哈希地址，若再發(fā)生沖突，則再使用另一個函數(shù)，直到不發(fā)生沖突為止。此種方法需要預(yù)先設(shè)計一個哈希函數(shù)序列：這種方法不易產(chǎn)生“聚集”現(xiàn)象，但會增加計算的時間。4哈希表查找性能分析

使用平均查找長度來衡量哈希表的查找效率，在