數(shù)據結構-第7章-查找

7.1查找的基本概念第7章查找查找又稱為檢索，其功能是從大量的數(shù)據元素中找出某個特定的滿足給定條件的記錄或數(shù)據元素。若找到滿足給定條件的記錄或數(shù)據元素，則稱查找是成功的，此時查找的結果為給出整個記錄的信息，或指示該記錄在查找表中位置的指針；相反，若未找到滿足給定條件的記錄或數(shù)據元素，則稱查找不成功，此時，查找的結果可給出一個“空”記錄或“空”指針。查找的目的一般有如下四種：（1）查找某指定的數(shù)據元素在查找表中是否存在；（2）檢索某個特定的數(shù)據元素的各種屬性；（3）在查找表的合理位置上插入一個數(shù)據元素；（4）從查找表中刪除某個數(shù)據元素。7.1查找的基本概念第7章查找關鍵字標識數(shù)據元素（或記錄）中某個數(shù)據項的值，用它可以標識一個數(shù)據元素（或記錄）。若此關鍵字可以唯一標識一個記錄，則稱此關鍵字為主關鍵字（不同的記錄，其主關鍵字均不同）。反之，把用以識別若干個記錄的關鍵字稱為次關鍵字。當數(shù)據元素只有一個數(shù)據項時，其關鍵字即為該數(shù)據元素的值。利用關鍵字的概念，查找運算的功能可確切地表述如下：根據給定的某個關鍵字值key，在某種數(shù)據結構中尋找一個其鍵值等于key的數(shù)據元素。若找到一個這樣的數(shù)據元素，則稱查找成功；否則，稱查找不成功。7.1查找的基本概念第7章查找靜態(tài)查找（staticsearch）若對查找表只做前兩種操作（即，肯定不會改變原查找表的內容），則稱此查找為靜態(tài)查找。動態(tài)查找（dynamicsearch）若在查找過程中同時插入查找表中不存在的數(shù)據元素，或者從查找表中刪除已存在的某個數(shù)據元素，則稱此查找為動態(tài)查找。平均查找長度（averagesearchlength,ASL）為確定所查找的數(shù)據元素在查找表中的位置而需和給定關鍵字進行比較的次數(shù)的平均值。ASL是衡量一個查找算法性能好壞的依據,因為查找的過程實際上是“將查找表中各數(shù)據元素的關鍵字與給定的關鍵字進行比較的過程”，所以比較次數(shù)越少，則查找所需的時間就越短，效率就越高。7.2靜態(tài)查找表第7章查找7.2.1順序查找順序查找是一種最簡單也是效率比較低下的查找算法。查找的基本思想是將每個結點的關鍵字與給定的待查的關鍵字值key依次進行比較，若當前掃描到的結點關鍵字值與key相等，則查找成功，返回該數(shù)據元素的存儲位置；反之，若掃描結束后，仍未找到關鍵字等于key的結點，則查找失敗，返回查找失敗標志。順序查找法既可以采用順序存儲結構，也可以采用鏈式存儲結構。//靜態(tài)查找表的順序存儲表示#definemaxsize100/*定義最大存儲容量*/typedefstruct{datatypedata[maxsize];intlength;}seqtable;/*靜態(tài)查找表的鏈式存儲表示*/typedefstructnode{datatypedata;structnode*next;}linktable;7.2靜態(tài)查找表第7章查找7.2.2折半查找折半查找也稱為“二分查找”,其查找效率較高，但要求待查找的數(shù)據元素采用順序存儲結構，而且查找表按關鍵字有序(已經按關鍵字排好序)。采用折半查找算法在有序表（假設為升序）中查找結點時，首先找到表的中間結點，將其關鍵字值與給定的要找的值key進行比較，若相等，則查找成功；若當前結點的關鍵字值大于要找的值key，則繼續(xù)在表的前半部分進行折半查找，否則繼續(xù)在表的后半部分進行折半查找。7.2靜態(tài)查找表第7章查找7.2.3分塊查找分塊查找是一種性能介于順序查找和二分查找之間的查找方法，但它要求先對查找表建立一個索引表，再進行分塊查找。索引表建立方法是先對查找表進行分塊，要求“分塊有序”，所謂“分塊有序”是指塊內關鍵字不一定有序，但塊間有序，即后一塊子表中所有數(shù)據元素的關鍵字值均大于前一塊中最大的關鍵字值。然后，抽取各塊中的最大關鍵字及其起始位置構成一個索引表，如圖7-3所示。分塊查找方法為分兩步進行，先查找索引表，因其有序，故可采用二分查找，以確定待查記錄在哪一塊，然后，在已確定的塊中再進行順序查找。7.3動態(tài)查找表第7章查找7.3.1二叉排序樹1．二叉排序樹定義二叉排序樹（BinarySortTree）或者是一棵空樹，或者是具有下列性質的二叉樹：(1)若左子樹不空，則左子樹上所有結點的值均小于根結點的值；若右子樹不空，則右子樹上所有結點的值均大于根結點的值。(2)左右子樹也都是二叉排序樹。從二叉排序樹的定義可得出二叉排序樹的一個重要性質：按中序遍歷該樹所得到的中序序列是一個遞增有序序列。7.3動態(tài)查找表第7章查找2．二叉排序樹的查找過程在二叉排序樹中查找關鍵字值為key的數(shù)據元素的基本思想是用給定值key與根結點的關鍵字值比較，如果key小于根結點的值，則要找的結點只可能在左子樹中，所以繼續(xù)在左子樹中查找，否則將繼續(xù)在右子樹中查找，依此方法，查找下去，直至查找成功或查找失敗為止。二叉排序樹的查找過程描述如下：（1）若二叉排序樹為空樹，則查找失?。唬?）若二叉排序樹非空，將給定值key與根結點關鍵字值比較，若相等，查找成功，結束查找過程；（3）否則，當結定值key小于根結點關鍵字值時，則繼續(xù)在根結點的左子樹中查找；（4）否則，當給定值key大于根結點關鍵字值時，則繼續(xù)在根結點的右子樹中查找。7.3動態(tài)查找表第7章查找3．二叉排序樹的插入二叉排序樹是一種動態(tài)樹表，樹的結構通常不是一成不變的，在一棵二叉排序樹中插入一個結點時，首先要在二叉排序樹中進行查找，若查找成功，則不用插入；查找不成功時，則插入，新插入結點一定是二叉排序樹的葉了結點。插入可以用一個遞歸過程實現(xiàn)，即：若二叉排序樹為空，則新結點作為二叉排序樹的根結點；否則，若給定結點的關鍵字值小于根結點關鍵字值，則插入在左子樹上；若給定結點的關鍵字值大于根結點的值，則插入在右子樹上。4.二叉排序樹的建立利用二叉排序樹的插入算法，可以很容易地實現(xiàn)創(chuàng)建二叉排序樹的操作，其基本思想是：由一棵空二叉樹開始，經過一系列的查找插入操作生成一棵二叉排序樹。7.3動態(tài)查找表第7章查找5．二叉排序樹刪除操作從二叉排序樹中刪除一個結之后，使得其仍能保持二叉排序樹的特性不變，即刪除一個結點后還是一棵二叉排序樹。下面分3種情況討論一下，如何確保從二叉排序樹中刪除一個結點后，不會影響二叉排序樹的性質。設待刪結點為*p(p為指向待刪結點的指針)，其雙親結點為*f，且不失一般性，可設*p是*f的左孩子結點（右孩子結點的情況類似）。7.3動態(tài)查找表第7章查找(1)若*p結點為葉結點，由于刪去葉子結點后不影響整棵樹的特性，所以，只需將被刪結點的雙親結點相應指針域改為空指針。如圖7-6所示。7.3動態(tài)查找表第7章查找(2)若*p結點只有右子樹PR或只有左子樹PL，此時，只要令PL或PR直接成為其雙親結點*f的左子樹即可，顯然，作此修改也不破壞二叉排序樹的特性。如圖7-7所示。7.3動態(tài)查找表第7章查找(3)*p結點既有左子樹PL，又有右子樹PR，可按中序遍歷保持有序進行調整。如圖7-8所示，刪除*p結點前，中序遍歷序列為：CL，C，…，QL，Q，SL,S,*P,PR,*f，…；則刪除結點*P后，為保持其它元素之間的相對位置不變，則中序序列為：CL，C，…，QL，Q，SL,S,PR,*f，…。以有兩種實現(xiàn)方法：其一是令*P的直接前驅（或直接后繼）替代*P，然后再從二叉排序樹中刪去它的直接前驅（或直接后繼），如圖7-8(a)所示。其二是令*P的左子樹為*f的左子樹，而*P的右子樹為S的右子樹，如圖7-8(b)所示。7.3動態(tài)查找表第7章查找7.3動態(tài)查找表第7章查找6．二叉排序樹查找性能分析在二叉排序樹上查找其關鍵字等于給定值的結點的過程，恰是走了一條從根結點到該結點的路徑的過程，和給定值比較的關鍵字個數(shù)等于路徑長度加1(或結點所在層次數(shù))，因此和折半查找類似，與給定值比較的關鍵字個數(shù)不超過樹的深度。但含有n個結點的判定樹是唯一的，而含有n個結點的二叉排序樹卻不唯一。例如，圖7-9（a）和圖7-9（b）所示的是結點數(shù)為6的兩棵二叉排序樹，圖7-9（a）中樹的深度為3，而圖7-9（b）中樹的深度為6。7.3動態(tài)查找表第7章查找7.3.2平衡二叉樹1．平衡二叉樹定義平衡二叉樹又稱AVL樹，它或者是—棵空樹，或者是具有下列性質的二叉排序樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹高度差的絕對值不超過1。圖7-10給出了兩棵二叉排序樹，每個結點旁邊所注數(shù)字是以該結點為根的二叉樹中左子樹與右子樹高度之差，稱這個數(shù)字為結點的平衡因子。由平衡二叉樹的定義可知，所有結點的平衡因子只能取-1，0，1三個值之一。若二叉排序樹中存在這樣的結點，其平衡因子的絕對值大于l，這棵樹就不是平衡二叉樹。如圖7-10（a）所示的二叉排序樹不是平衡二叉樹。7.3動態(tài)查找表第7章查找1．平衡二叉樹定義7.3動態(tài)查找表第7章查找2．二叉排序樹的平衡化在平衡二叉樹上插入或刪除結點后，可能使二叉樹失去平衡，因此，需要對失去平衡的二叉樹進行平衡化調整。設A結點為失去平衡的最小子樹根結點，對該子樹進行平衡化調整歸納起來有以下四種情況。（1）左單旋轉（RR型）這種失衡是因為在失衡結點的右孩子的右子樹上插入結點造成的。如圖7-11（a）為插入前的子樹。其中A的左子樹為AL，A的右孩子結點為B，BL、BR分別為結點B的左右子樹，AL、BL、BR三棵子樹的高度均為h。則圖7-10（a）所示的二叉樹是平衡二叉樹。7.3動態(tài)查找表第7章查找（1）左單旋轉（RR型）7.3動態(tài)查找表第7章查找（2）右單旋轉(LL型)這種失衡是因為在失衡結點的左孩子的左子樹上插入結點后，導致結點A的平衡因子由1變?yōu)?，如圖7-12（a）、（b）所示，此時應進行一次順時針旋轉操作，使結點A成為結點B的右孩子，如圖7-12（c）所示。7.3動態(tài)查找表第7章查找（3）先左后右雙向旋轉（LR型）這種失衡是因為在失衡結點的左孩子的右子樹上插入結點造成的。如圖7-13所示，插入前，根結點A的平衡因子為1，將結點x插入到B的右子樹上。并使結點B的右子樹高度增1，從而使結點A的平衡因子變?yōu)?，導致以結點A為根的子樹平衡被破壞，如圖7-14（a）、圖7-15（a）所示。7.3動態(tài)查找表第7章查找（4）先右后左雙向旋轉（RL型）這種失衡是因為在失衡結點的右孩子的左子樹上插入結點造成的。導致結點A的平衡因子由-1變?yōu)?2，則同樣需兩次旋轉，即先右后左雙向旋轉，調整過程與LR對稱，下面只給出雙向旋轉RL型I，如圖7-16所示。雙向旋轉RL型II，請讀者自行完成。7.3動態(tài)查找表第7章查找（4）先右后左雙向旋轉（RL型）7.3動態(tài)查找表第7章查找3.平衡二叉樹的插入在平衡二叉樹T上插入一個關鍵字為x的數(shù)據元素，遞歸算法的基本思想可描述如下：(1)若T為空樹，則插入的數(shù)據元素x為T的根結點，樹的深度增1；(2)若x和T的根結點關鍵字相等，則不進行插入；(3)若x小于T的根結點關鍵字值，而且在T的左子樹中不存在與x有相同關鍵字值的結點，則將新元素插入在T的左子樹上，并且插入之后的左子樹深度增加1時，分別就下列情況進行處理。7.3動態(tài)查找表第7章查找4.平衡二叉樹查找性能分析在平衡二叉樹上進行查找的過程和二叉排序樹類似，查找時和給定值進行比較的關鍵字數(shù)不超過樹的深度。下面我們討論含有n個關鍵字的平衡二叉樹的最大深度。假設以Nh表示深度為h的平衡二叉樹中含有的最少結點數(shù)。顯然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。含有n個結點的平衡二叉樹的最大深度為。利用歸納法可以證明：當h≥0，時間復雜度為O(log2n)。7.4散列表第7章查找7.4.1散列表的概念1．散列表設所有可能出現(xiàn)的關鍵字集合記為U(簡稱全集)。實際發(fā)生(即實際存儲)的關鍵字集合記為K(|K|比|U|小得多)。散列方法是使用函數(shù)h將U映射到表T[0..m-1]的下標上(m=O(|U|))。這樣以U中關鍵字為自變量，以h為函數(shù)的運算結果就是相應結點的存儲地址。從而達到在O(1)時間內就可完成查找。7.4散列表第7章查找2．散列表的沖突現(xiàn)象(1)沖突對于不同的關鍵字可能得到同一哈希地址，即key11key2，但h(key1)=h(key2)，該現(xiàn)象稱為沖突(Collision)或碰撞。發(fā)生沖突的兩個關鍵字稱為該散列函數(shù)的同義詞(Synonym)。7.4散列表第7章查找7.4.2散列函數(shù)的構造方法1．散列函數(shù)的選擇標準散列函數(shù)的選擇有兩條標準：簡單和均勻。簡單是指散列函數(shù)的計算簡單快速；均勻是指對于關鍵字集合中的任一關鍵字，散列函數(shù)能以等概率將其映射到散列表空間的任何一個位置上。也就是說，散列函數(shù)能將子集K隨機均勻地分布在表的地址集{0，1，…，m-1}上，以使沖突最小化。7.4散列表第7章查找2．常用散列函數(shù)為簡單起見，假定關鍵字是定義在自然數(shù)集合上，目前比較常用的散列函數(shù)有以下幾種：

(1)平方取中法先通過求關鍵字的平方值擴大相近數(shù)的差別，然后根據表長度取中間的幾位數(shù)作為散列函數(shù)值。又因為一個乘積的中間幾位數(shù)和乘數(shù)的每一位都相關，所以由此產生的散列地址較為均勻。7.4散列表第7章查找(2)除留余數(shù)法該方法是最為簡單常用的一種方法。它是以表長m來除關鍵字，取其余數(shù)作為散列地址。其散列函數(shù)的形式為：h(key)=key%m。其中，key是關鍵字。m的選取十分重要，如果m選擇不當，在某些情況下會造成嚴重沖突。例如，若m=2k，則h(key)的值僅依賴于最后k個比特。如果key是十進制數(shù)，則m應避免取10的冪次。多數(shù)情況下，選取一個不超過m的素數(shù)p，令散列函數(shù)為h(key)=key%p，會收到較好的效果。7.4散列表第7章查找(3)相乘取整法該方法包括兩個步驟：首先用關鍵字key乘上某個常數(shù)A(0<A<1)，并抽取出key×A的小數(shù)部分，然后用m乘以該小數(shù)后取整。即：

該方法最大的優(yōu)點是選取m不再像除留余數(shù)法那樣關鍵。雖然該方法對任何A的值都適用，但對某些值效果會更好。Knuth建議：7.4散列表第7章查找7.4.3處理沖突的方法散列表中的沖突現(xiàn)象是難以避免的，因此，尋求較好的解決沖突的方法是一個重要的問題。通常有兩類處理沖突的方法：開放定址(OpenAddressing)法和拉鏈(Chaining)法。前者是將所有結點均存放在散列表T[0..m-1]中；后者是將互為同義詞的結點鏈成一個單鏈表，而將此鏈表的頭指針放在散列表T[0..m-1]中。7.4散列表第7章查找1.開放定址法(1)開放地址法解決沖突的方法用開放定址法解決沖突的方法是：當沖突發(fā)生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找，直到找到給定的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止(若要插入，在探查到開放的地址時，則可將待插入的新結點存入到該地址單元)。查找時探查到開放的地址則表明表中無待查的關鍵字，即查找失敗。7.4散列表第7章查找(2)開放地址法的一般形式開放定址法的一般形式為：hi=(h(key)+di)%m1≤i≤m-1其中：①h(key)為散列函數(shù)，di為增量序列，m為表長；②h(key)是初始的探查位置，后續(xù)的探查位置依次是hl，h2，…，hm-1，即h(key)，hl，h2，…，hm-1形成了一個探查序列；③若令開放地址一般形式的i從0開始，并令d0=0，則h0=h(key)，hi=(h(key)+di)%m，1≤i≤m-1；探查序列可簡記為hi(0≤i≤m-1)。7.4散列表第7章查找(3)開放地址法對裝填因子的要求開放定址法要求散列表的裝填因子α≤1，實用中取α為0.5到0.9之間的某個值為宜。(4)形成探測序列的方法按照形成探查序列方法的不同，可將開放定址法分為線性探查法、二次探查法、雙重散列法等。①線性探查法(LinearProbing)該方法的基本思想是：將散列表T[0..m-1]看成是一個循環(huán)向量，若初始探查的地址為d(即h(key)=d)，則最長的探查序列為：d，d+l，d+2，…，m-1，0，1，…，d-1。即探查時從地址d開始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循環(huán)到T[0]，T[1]，…，直到探查到T[d-1]為止。7.4散列表第7章查找2．拉鏈法(1)拉鏈法解決沖突的方法拉鏈法解決沖突的方法是：將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數(shù)組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大于1，但一般均取α≤1。7.4散列表第7章查找(2)拉鏈法的特點與開放定址法相比，拉鏈法有如下幾個優(yōu)點：①拉鏈法處理沖突簡單，且無堆積現(xiàn)象，即非同義詞決不會發(fā)生沖突，因此平均查找長度較短；②由于拉鏈法中各鏈表上的結點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；③開放定址法為減少沖突，要求裝填因子α較小，故當結點規(guī)模較大時會浪費很多空間。而拉鏈法中可取α≥1，且結點較大時，拉鏈法中增加的指針域可忽略不計，因此節(jié)省空間；④在用拉鏈法構造的散列表中，刪除結點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應的結點即可。7.4散列表第7章查找7.4.4散列表的查找及分析1．散列表數(shù)據類型描述#defineNIL-1/*空結點標記依賴于關鍵字類型，本節(jié)假定關鍵字均為非負整數(shù)*/#defineM13/*表長度依賴于應用，但一般應確定M為一素數(shù)*/typedefin