數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找2024/3/12數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.1查找的基本概念1.查找表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合稱為查找表。2.對查找表進行的操作：（1）查找某個特定的數(shù)據(jù)元素是否存在。（2）檢索某個特定數(shù)據(jù)元素的屬性。（3）在查找表中插入一個數(shù)據(jù)元素。（4）在查找表中刪除一個數(shù)據(jù)元素。3.靜態(tài)查找：在查找過程中僅查找某個特定元素存在或查找其屬性，稱為靜態(tài)查找。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找4.動態(tài)查找：在查找過程中對查找表進行插入或刪除元素操作，稱為動態(tài)查找。5.關(guān)鍵字：數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標識數(shù)據(jù)元素（或記錄）。6.主關(guān)鍵字：可以唯一地標識一個記錄的關(guān)鍵字稱為主關(guān)鍵字。7.次關(guān)鍵字：可以標識若干個記錄的關(guān)鍵字稱為次關(guān)鍵字。8.查找：在查找表中確定是否存在一個數(shù)據(jù)元素的關(guān)鍵字等于給定值的操作，稱為查找（或檢索)。若表中存在這樣一個數(shù)據(jù)元素（或記錄），則查找成功；否則，查找失敗。9.內(nèi)查找和外查找：若整個查找過程全部在內(nèi)存進行，則稱為內(nèi)查找；若在查找過程中還需要訪問外存，則稱為外查找。10.平均查找長度：查找算法的效率，主要是看要查找的值與關(guān)鍵字的比較次數(shù)，通常用平均查找長度來衡量。對一個含n個數(shù)據(jù)元素的表，查找成功時：

其中,n是查找表中記錄的個數(shù)。pi是查找第i個記錄的概率,一般地,均認為每個記錄的查找概率相等,即pi=1/n(1≤i≤n),ci是找到第i個記錄所需進行的比較次數(shù)數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.2靜態(tài)查找表具有順序查找法、折半查找法和分塊查找法三種9.2.1順序查找順序查找法的特點是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。

監(jiān)視哨的作用：（1）省去判定循環(huán)中下標越界的條件，從而節(jié)約比較時間。（2）保存查找值的副本，查找時若遇到它，則表示查找成功。這樣在從后向前查找失敗時，不必判斷查找是否檢測完，從而達到算法統(tǒng)一。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找用平均查找長度分析順序查找算法的性能：假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：

ASL=

i=1nPiCi＝n1

i=1nCi＝n1

i=1n(n-i+1)=21(n+1)順序查找的缺點：當n很大時，平均查找長度較大，效率低；優(yōu)點：對表中數(shù)據(jù)元素的存儲沒有要求。另外，對于線性鏈表，只能進行順序查找。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.2.2折半查找法（二分法查找法）條件：要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。

基本過程：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找例如用折半查找法查找10、50的具體過程，其中mid=(low+high)/2，當high<low時，表示不存在這樣的子表空間，查找失敗。

6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=1mid=3high=5用折半查找法查找12的過程為：數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找6058463528252218151261234567891011low=1mid=1high=26058463528252218151261234567891011low=2mid=2high=2數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找用折半查找法查找50的過程：6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=7mid=9high=11數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找6058463528252218151261234567891011low=10mid=10high=116058463528252218151261234567891011low=10high=9數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找用平均查找長度分析折半查找算法的性能：折半查找成功時的平均查找長度為：ASLbs＝

i=1nPiCi＝n1

j=1nj×2j-1＝nn+1log2(n+1)-1優(yōu)點：比較次數(shù)少，查找速度快，平均性能好。缺點：要求待查的表為有序表，且插入、刪除困難。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.2.3分塊查找法分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：★首先將列表分成若干個塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。

★構(gòu)造一個索引表。其中每個索引項對應(yīng)一個塊并記錄每塊的起始位置，和每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序排列。

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找下圖為一個索引順序表2558888871605836453228825121418索引表各塊內(nèi)的最大關(guān)鍵字各塊的起始地址列表0123456789101112此表包括三個塊，第一個塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25;第二個塊的起始地址為5，塊內(nèi)最大關(guān)鍵字為58;第三個塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為88。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找分塊查找的基本過程為：（1）首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進行。（2）進一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素。

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找分塊查找的平均查找長度由兩部分組成：即查找索引表時的平均查找長度為LB，以及在相應(yīng)塊內(nèi)進行順序查找的平均查找長度LW。ASLbs=LB+LW

假定將長度為n的表分成b塊，且每塊含s個元素，則b=n/s。又假定表中每個元素的查找概率相等，則每個索引項的查找概率為1/b，塊中每個元素的查找概率為1/s。若用順序查找法確定待查元素所在的塊，則有：

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找LB＝b1∑j＝j(luò)=1bb＋12Lw＝s1∑j＝i=1ss＋12ASLbs=LB+LW＝2b+s+1將b=n/s代入，得ASLbs＝21+1sn+s)(數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找三種查找方法比較順序查找折半查找分塊查找ASL大小中表結(jié)構(gòu)要求無有序表分段有序（塊之間有序）數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.3動態(tài)查找9.3.1二叉排序樹1.二叉排序樹的定義二叉排序樹或者是一棵空樹,或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值。（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值。（3）左、右子樹也都是二叉排序樹。2.二叉排序樹的構(gòu)造根據(jù)二叉排序樹的性質(zhì)，每次都按結(jié)點大小從根結(jié)點查找到對應(yīng)的插入位置插入。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找例：有一組結(jié)點的關(guān)鍵字大小分別為：45、12、53、3、37、24、100、61、90、78求由這些結(jié)點構(gòu)造成的二叉排序樹的過程如圖所示。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找二叉排序樹的刪除

二叉排序的刪除刪除查找樹中鍵值為key的結(jié)點的操作可按以下步驟進行：首先確定被刪除結(jié)點的位置，如被刪結(jié)點不在樹，則函數(shù)返回；否則按以下多種情況作結(jié)點刪除。（1）如被刪除結(jié)點是根結(jié)點：①被刪除結(jié)點無左子樹；則以被刪除結(jié)點的右子樹作為刪除后的樹。②被刪除結(jié)點有左子樹，則以被刪除結(jié)點的左子結(jié)點作為根結(jié)點，并把被刪除結(jié)點的右子樹作為被刪結(jié)點的左子樹按中序遍歷得最后一結(jié)點的右子樹。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找二叉排序的刪除（續(xù)）（2）如被刪結(jié)點不是根結(jié)點，且被刪結(jié)點無左子結(jié)點。①如被刪結(jié)點是它的雙親結(jié)點的左子結(jié)子，則把被刪結(jié)點右子樹作為被刪結(jié)點的雙親結(jié)點的左子樹；②如被刪結(jié)點是它的雙親結(jié)點的右子結(jié)點，則被刪結(jié)點的右子樹作為被刪結(jié)點的雙親結(jié)點的右子樹。（3）如被刪結(jié)點不是根結(jié)點，且被刪結(jié)點有左子結(jié)點，把被刪結(jié)點的右子樹作為被刪結(jié)點的左子樹按中序遍歷得最后一結(jié)點的右子樹，同時進行以下操作：①如被刪結(jié)點是它的雙親結(jié)點的左子結(jié)點，則把被刪結(jié)點的左子樹作為被刪結(jié)點的雙親結(jié)點的左子樹。②如被刪結(jié)點是它雙親結(jié)點的右子結(jié)點，則把被刪結(jié)點的左子樹作為被刪結(jié)點的雙親結(jié)點的右子樹。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找二叉排序樹的刪除操作1、若p沒有左子樹，直接用p的右孩子取代它；2、

若p有左子樹，用p的左孩子取代它；找到其左子樹的最右邊的葉子結(jié)點r，把p的右子樹作為r

的右子樹。

數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.3.2平衡二叉樹(AVL樹)一、AVL樹（高度平衡的BST）概念1、定義——AVL或是空樹，或是具有下列性質(zhì)的BST：它的左、右子樹都是AVL樹，且左右子樹的高度之差的絕對值不超過1。2、舉例是二叉搜索樹樹和所有子樹的右左子樹高度之差絕對值不超過1屬AVL樹111514263971816-1000000013、平衡因子（balancefactor）結(jié)點左子樹高度減去右子樹高度所得高度差A(yù)VL樹中所有結(jié)點的平衡因子只能取0，1，－1數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找二、平衡化旋轉(zhuǎn)1、向AVL樹插入結(jié)點可能造成不平衡，此時要調(diào)整樹的結(jié)構(gòu)，使之重新達到平衡2、平衡化旋轉(zhuǎn)方法從插入位置沿通向根的路徑檢查各結(jié)點的平衡因子若發(fā)現(xiàn)不平衡結(jié)點，則從該結(jié)點起沿剛才回溯路徑取直接下兩層結(jié)點若三個結(jié)點在一條直線上(RR、LL型)，則采用單旋轉(zhuǎn)進行平衡化，此時處于中間位置的結(jié)點為旋轉(zhuǎn)中心若三結(jié)點不在一條直線上(LR、RL型)，則采用雙旋轉(zhuǎn)進行平衡化，此時處于下方位置的結(jié)點為旋轉(zhuǎn)中心數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找3、平衡化旋轉(zhuǎn)示例

RR型（逆時針單旋轉(zhuǎn)）hhhABCDE01(a)AVL樹hhh+1ABCDE12(b)E子樹中插入結(jié)點hhh+1ABCDE00(c)左向旋轉(zhuǎn)后的AVL樹二、平衡化旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找

LL型（順時針單旋轉(zhuǎn)）hhhABCDE0-1(a)AVL樹hhh+1ABCDE-1-2(b)D子樹中插入結(jié)點hhh+1ABCDE00(c)右向旋轉(zhuǎn)后的AVL樹3、平衡化旋轉(zhuǎn)示例二、平衡化旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找hhh-1hABCDEFG插入(a)F子樹插入結(jié)點高度變?yōu)閔-21-1hhh-1hABCDEFG(b)繞E，將B逆時針轉(zhuǎn)后hhh-1hABCDEFG(c)繞E，將A順時針轉(zhuǎn)后03、

LR型（先逆時針，后順時針雙旋轉(zhuǎn)）二、平衡化旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找hhh-1hABCDEFG插入(a)G子樹插入結(jié)點高度變?yōu)閔21-1hhh-1hABCDEFG(b)繞D，C順時針轉(zhuǎn)之后hhh-1hABCDEFG(c)繞D，A逆時針轉(zhuǎn)之后03、

RL型（先順時針，后逆時針雙旋轉(zhuǎn)）二、平衡化旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找三、AVL樹的建立對于一組關(guān)鍵碼的輸入序列，從空開始不斷插入結(jié)點，最后構(gòu)成AVL樹每插入一個結(jié)點后就應(yīng)判斷從該結(jié)點到根的路徑上有無結(jié)點發(fā)生不平衡如有不平衡問題，利用旋轉(zhuǎn)方法進行樹的調(diào)整，使之平衡化建AVL樹過程是不斷插入結(jié)點和必要時進行平衡化的過程建AVL樹過程舉例：數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.4哈希表及其查找9.4.1哈希表

哈希表又稱散列表，是一種非常實用的查找技術(shù)。查找為結(jié)點的存儲位置和它的關(guān)鍵碼之間建立一個確定的關(guān)系，從而就可使查找碼直接利用這個關(guān)系確定結(jié)點的位置。在散列表中，結(jié)點存儲時，以結(jié)點的關(guān)鍵碼為自變量，按某種公式計算其存儲位置，并以該位置存儲。查找時，以查找碼為自變量計算同一公式，就能得到對應(yīng)結(jié)點的存儲位置，去取出結(jié)點，所以散列表能進行快速查找。稱查找碼計算結(jié)點存儲位置的公式為散列函數(shù)，記為H（）。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.3.1哈希表

一般情況下，能存入散列表中的結(jié)點所有可能的不同關(guān)鍵碼個數(shù)比散列表能存儲的結(jié)點個數(shù)要大得多。因此兩個不同關(guān)鍵碼k1和k2的散列函數(shù)值可能相等：H（k1）=H(k2)且k1≠k2。這種現(xiàn)象稱為沖突，并稱k1和k2為同義詞。為了有效地使用散列技術(shù)，需要解決兩個問題：找一個好的散列函數(shù)，使出現(xiàn)沖突機會盡可能少；設(shè)計有效解決沖突的方法。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.3.2常見的散列函數(shù)

1.除留余數(shù)法令P是是一個整數(shù),若哈希表長為m,則要求p<=m，且接近m或等于m。設(shè)查找碼為key，計算的散列函數(shù)為Hash(key)=key%p2.直接定址法直接定址法是取關(guān)鍵字的某個線性函數(shù)值為哈希地址,即Hash(key)=a*key+b3.平方取中法讓查找碼自乘，取其中間若干位的值，并乘上某個比例因子，使值在0至m-1之間。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找9.3.3解決沖突的方法

1.線性探查法如按查找碼key求得的第H（key）桶以滿時，就得到另一個桶去找空位，將結(jié)點存入。線性探查法使用下列探查序列：H（key）,H（key）+1,H（key）+2,……，m-1，0，1……H（key）-1使用線性探查法解決沖突，會出現(xiàn)堆積現(xiàn)象?？赡軙l(fā)生這樣的情況，有某結(jié)點的關(guān)鍵碼計算出它的散列地址，希望按該地址存儲該結(jié)點，但該位置已被不是它的同義詞的結(jié)點所占用。因沖突沿著線性探查序列進行查找，而這些位置也可能已存入非同義詞的其他結(jié)點，結(jié)果使得不是同義詞的許多結(jié)點處在同一個探查序列中。2.雙散列函數(shù)法由于線性探查發(fā)容易產(chǎn)生堆積現(xiàn)象，會大大降低查找效率，可用雙散列函數(shù)法。散列函數(shù)H1（）產(chǎn)生0到m-1的桶號d，當沖突發(fā)生時，散列函數(shù)H2（）產(chǎn)生1到m-1,并與m互質(zhì)的數(shù)c作為對H1（）的補償，使探查序列跳躍式地分布在整個散列表中：（d+c）%m,(d+2c)%m,(d+3c)%m,……數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找3.拉鏈法用拉鏈法處理沖突，要求散列表的每個結(jié)點增加一個指針字段，用于鏈接同義詞的子表，鏈表中的結(jié)點都是同義詞。查找方法如下：（１）按散列函數(shù)計算出桶號i；（２）判斷對應(yīng)的同義詞鏈表指針是否為空，若為空則查找失敗結(jié)束。（３）遍用同義詞鏈表，查到則成功結(jié)束，若直到表尾仍未找到，則查找失敗。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查找建立一個公共溢出區(qū)：（1）一個基本表：每個單元只能存放一個元素；（2）一個溢出表：只要關(guān)鍵字對應(yīng)的哈希地址在基礎(chǔ)表上產(chǎn)生沖突，則所有這樣的元素一律存入該表中。數(shù)據(jù)結(jié)構(gòu)預(yù)算法第九章查