數(shù)據(jù)結(jié)構(gòu)-C語言描述(第二版)課件：查找

查找8.1查找的基本概念8.2基于線性表的查找法8.3基于樹的查找法8.4計算式查找法——哈希法8.1查找的基本概念

列表：由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實現(xiàn)。關(guān)鍵字：數(shù)據(jù)元素的某個數(shù)據(jù)項的值，用它可以標識列表中的一個或一組數(shù)據(jù)元素。如果一個關(guān)鍵字可以唯一標識列表中的一個數(shù)據(jù)元素，則稱其為主關(guān)鍵字，否則為次關(guān)鍵字。當數(shù)據(jù)元素僅有一個數(shù)據(jù)項時，數(shù)據(jù)元素的值就是關(guān)鍵字。

查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。若找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時應(yīng)返回空地址及失敗信息，并可根據(jù)要求插入這個不存在的數(shù)據(jù)元素。顯然，查找算法中涉及到三類參量：①查找對象K（找什么）；②查找范圍L（在哪找）；③K在L中的位置（查找的結(jié)果）。其中①、②為輸入?yún)⒘浚蹫檩敵鰠⒘?，在函?shù)中，輸入?yún)⒘勘夭豢缮?，輸出參量也可用函?shù)返回值表示。

平均查找長度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。對于長度為n的列表，查找成功時的平均查找長度為：其中Pi為查找列表中第i個數(shù)據(jù)元素的概率，Ci為找到列表中第i個數(shù)據(jù)元素時，已經(jīng)進行過的關(guān)鍵字比較次數(shù)。由于查找算法的基本運算是關(guān)鍵字之間的比較操作，所以可用平均查找長度來衡量查找算法的性能。

查找的基本方法可以分為兩大類，即比較式查找法和計算式查找法。其中比較式查找法又可以分為基于線性表的查找法和基于樹的查找法，而計算式查找法也稱為HASH（哈希）查找法。8.2基于線性表的查找法8.2.1順序查找法順序查找法的特點是，用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。存儲結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈式結(jié)構(gòu)。下面給出順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義：＃defineLIST

-SIZE20

typedefstruct{

KeyTypekey;OtherTypeother

-data;

}RecordType;

typedefstruct{

RecordTyper［LIST-SIZE+1］;/*r［0］為工作單元*/intlength;

}RecordList;

基于順序結(jié)構(gòu)的算法如下：intSeqSearch（RecordListl,KeyTypek）/*在順序表l中順序查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/

{

l.r［0］.key=k;i=l.length;

while(l.r［i］.key![KG-*2]=k)i--;

return（i）;

}

【算法8.1設(shè)置監(jiān)視哨的順序查找法】其中l(wèi).r［0］稱為監(jiān)視哨，可以起到防止越界的作用。不用監(jiān)視哨的算法如下：intSeqSearch（RecordListl,KeyTypek）/*不用監(jiān)視哨法，在順序表中查找關(guān)鍵字等于k的元素*/

{

l.r［0］.key=k;i=l.length;

while(i>=1&&l.r［i］.key![KG-*2]=k)i--;

if(i>=1)return（i）

elsereturn(0);

}【算法8.2不設(shè)置監(jiān)視哨的順序查找法】其中，循環(huán)條件i>=1判斷查找是否越界。利用監(jiān)視哨可省去這個條件，從而提高查找效率。下面用平均查找長度來分析一下順序查找算法的性能。假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：8.2.2折半查找法

折半查找法又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過程是：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進一步查找前一子表，否則進一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。圖8.1給出了用折半查找法查找12、50的具體過程，其中mid=(low+high)/2，當high<low時，表示不存在這樣的子表空間，查找失敗。圖8.1折半查找示意折半查找的算法如下：intBinSrch（SqListl,KeyTypek）/*在有序表l中折半查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置*/

{

low=1;high=l.length;/*置區(qū)間初值*/

while(low<=high)

{

mid=(low+high)/2;

if(k==l.r［mid］.key)return（mid）;/*找到待查元素*/

elseif(k<l.r［mid］.key)high=mid-1;/*未找到，則繼續(xù)在前半?yún)^(qū)間進行查找*/

elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間進行查找*/

}

return(0);

}【算法8.3折半查找法】下面用平均查找長度來分析折半查找算法的性能。折半查找過程可用一個稱為判定樹的二叉樹描述，判定樹中每一結(jié)點對應(yīng)表中一個記錄，但結(jié)點值不是記錄的關(guān)鍵字，而是記錄在表中的位置序號。根結(jié)點對應(yīng)當前區(qū)間的中間記錄，左子樹對應(yīng)前一子表，右子樹對應(yīng)后一子表。例如對上述含11個記錄的有序表，其折半查找過程可如圖8.2所示的二叉判定樹表示。二叉樹結(jié)點內(nèi)的數(shù)值表示有序表中記錄的序號，如二叉樹的根結(jié)點表示第一次折半時找到的第6個記錄。圖8.2折半查找過程的二叉判定樹示例圖中的虛線表示查找關(guān)鍵字等于12的記錄的過程，虛線經(jīng)過的結(jié)點正是查找過程中和12比較過的記錄，包括第6、第3、第1和第2個記錄，需要的比較次數(shù)為4，因為關(guān)鍵字等于12的記錄在判定樹上位于第4層。因此，記錄在判定樹上的“層次”恰為找到此記錄時所需進行的比較次數(shù)。假設(shè)每個記錄的查找概率相同，則從圖8.2所示判定樹可知，對任意長度為11的有序表進行折半查找的平均查找長度為ASL=(1+2+2+3+3+3+3+4+4+4+4)/11=33/11=3顯然，找到有序表中任一記錄的過程，對應(yīng)判定樹中從根結(jié)點到與該記錄相應(yīng)的結(jié)點的路徑，而所做比較的次數(shù)恰為該結(jié)點在判定樹上的層次數(shù)。因此，折半查找成功時，關(guān)鍵字比較次數(shù)最多不超過判定樹的深度。由于判定樹的葉子結(jié)點所在層次之差最多為1，故n個結(jié)點的判定樹的深度與n個結(jié)點的完全二叉樹的深度相等，均為［log2n］+1。這樣，折半查找成功時，關(guān)鍵字比較次數(shù)最多不超過［log2n］+1。相應(yīng)地，折半查找失敗時的過程對應(yīng)判定樹中從根結(jié)點到某個含空指針的結(jié)點的路徑，因此，折半查找成功時，關(guān)鍵字比較次數(shù)最多也不超過判定樹的深度［log2n］+1。為便于討論，假定表的長度n=2h-1，則相應(yīng)判定樹必為深度是h的滿二叉樹，h=log2(n+1)。又假設(shè)每個記錄的查找概率相等，則折半查找成功時的平均查找長度為8.2.3分塊查找法

分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：

·

首先將列表分成若干個塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。

·

構(gòu)造一個索引表。其中每個索引項對應(yīng)一個塊并記錄每塊的起始位置，以及每塊中的最大關(guān)鍵字（或最小關(guān)鍵字）。索引表按關(guān)鍵字有序排列。圖8.3所示為一個索引順序表。其中包括三個塊，第一個塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25；第二個塊的起始地址為5，塊內(nèi)最大關(guān)鍵字為58；第三個塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為88。圖8.3分塊查找法示意

分塊查找的基本過程如下：

(1)首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進行。

(2)進一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素。例如，在上述索引順序表中查找36。首先，將36與索引表中的關(guān)鍵字進行比較，因為25＜36≤58，所以36在第二個塊中，進一步在第二個塊中順序查找，最后在8號單元中找到36。

分塊查找的平均查找長度由兩部分構(gòu)成，即查找索引表時的平均查找長度為LB，以及在相應(yīng)塊內(nèi)進行順序查找的平均查找長度為LW。ASLbs=LB+LW

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

基于樹的查找法又稱為樹表查找法，是將待查表組織成特定樹的形式并在樹結(jié)構(gòu)上實現(xiàn)查找的方法，主要包括二叉排序樹、平衡二叉排序樹和B樹等。8.3.1二叉排序樹二叉樹排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：（1）若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；（2）若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；（3）它的左右子樹也分別為二叉排序樹。

圖8.4二叉排序樹

在下面討論的二叉排序樹的操作中，使用二叉鏈表作為存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)說明如下：typedefstructnode

{KeyTypekey;/*關(guān)鍵字的值*/

structnode*lchild,*rchild;/*左右指針*/

}BSTNode,*BSTree;1.二叉排序樹的插入和生成

已知一個關(guān)鍵字值為key的結(jié)點s，若將其插入到二叉排序樹中，只要保證插入后仍符合二叉排序樹的定義即可。插入可以用下面的方法進行：①若二叉排序樹是空樹，則key成為二叉排序樹的根；②若二叉排序樹非空，則將key與二叉排序樹的根進行比較，如果key的值等于根結(jié)點的值，則停止插入；如果key的值小于根結(jié)點的值，則將key插入左子樹；如果key的值大于根結(jié)點的值，則將key插入右子樹。相應(yīng)的遞歸算法如下：voidInsertBST(BSTree*bst,KeyTypekey)

/*若在二叉排序樹中不存在關(guān)鍵字等于key的元素，插入該元素*/

{BSTrees;

if(*bst==NULL)/*遞歸結(jié)束條件*/

{

s=(BSTree)malloc(sizeof(BSTNode));/*申請新的結(jié)點s*/

s->key=key;

s->lchild=NULL;s->rchild=NULL;

*bst=s;

}

elseif(key<(*bst)->key)

InsertBST(&((*bst)->lchild),key);/*將s插入左子樹*/

elseif(key>(*bst)->key)

InsertBST(&((*bst)->rchild),key);/*將s插入右子樹*/

}【算法8.4二叉排序樹的插入】

假若給定一個元素序列，我們可以利用上述算法創(chuàng)建一棵二叉排序樹。首先，將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就建立一個新的結(jié)點并插入到當前已生成的二叉排序樹中，即調(diào)用上述二叉排序樹的插入算法將新結(jié)點插入。生成二叉排序樹的算法如下：voidCreateBST(BSTree*bst)

/*從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹*/

{KeyTypekey;

*bst=NULL;

scanf(″%d″,&key);

while(key![KG-*2]=ENDKEY)/*ENDKEY為自定義常數(shù)*/

{

InsertBST(bst,key);

scanf(″%d″,&key);

}

}【算法8.5創(chuàng)建二叉排序樹】圖8.5二叉排序樹的建立過程圖8.6輸入順序不同所建立的不同二叉排序樹2.二叉排序樹的刪除從二叉排序樹中刪除一個結(jié)點，不能把以該結(jié)點為根的子樹都刪去，只能刪掉該結(jié)點，并且還應(yīng)保證刪除后所得的二叉樹仍然滿足二叉排序樹的性質(zhì)不變。也就是說，在二叉排序樹中刪去一個結(jié)點相當于刪去有序序列中的一個結(jié)點。刪除操作前首先要進行查找，以確定被刪結(jié)點是否在二叉排序樹中。若不在，則不做任何操作；否則，假設(shè)要刪除的結(jié)點為p，結(jié)點p的雙親結(jié)點為f，并假設(shè)結(jié)點p是結(jié)點f的左孩子（右孩子的情況類似）。

下面分三種情況討論：

(1)若p為葉子結(jié)點，則可直接將其刪除：f->lchild=NULL；free(p)；

(2)若p結(jié)點只有左子樹，或只有右子樹，則可將p的左子樹或右子樹直接改為其雙親結(jié)點f的左子樹，即：f->lchild=p->lchild（或f->lchild=p->rchild）；free(p)；

(3)若p既有左子樹，又有右子樹，如圖8.7(a)所示。此時有兩種處理方法：

圖8.7二叉排序樹刪除示意

方法1:

首先找到p結(jié)點在中序序列中的直接前驅(qū)s結(jié)點，如圖8.7(b)所示，然后將p的左子樹改為f的左子樹，而將p的右子樹改為s的右子樹：f->lchild=p->lchild；s->rchild=p->rchild；free(p)；結(jié)果如圖8.7(c)所示。方法2:首先找到p結(jié)點在中序序列中的直接前驅(qū)s結(jié)點，如圖8.7(b)所示，然后用s結(jié)點的值替代p結(jié)點的值，再將s結(jié)點刪除，原s結(jié)點的左子樹改為s的雙親結(jié)點q的右子樹：p->data=s->data；q->rchild=s->lchild；free(s)；結(jié)果如圖8.7(d)所示。綜上所述，可以得到下面的在二叉排序樹中刪去一個結(jié)點的算法。BSTNode*DelBST(BSTreet,KeyTypek)/*在二叉排序樹t中刪去關(guān)鍵字為k的結(jié)點*/{BSTNode*p,*f,*s,*q;

p=t;f=NULL;

while(p)/*查找關(guān)鍵字為k的待刪結(jié)點p*/

{if(p->key==k)break;/*找到，則跳出查找循環(huán)*/

f=p;/*f指向p結(jié)點的雙親結(jié)點*/

if（p->key>k）p=p->lchild;

elsep=p->rchild;

}

if(p==NULL)returnt;/*若找不到，返回原來的二叉排序樹*/

if(p->lchild==NULL)/*p無左子樹*/

{if(f==NULL)t=p->rchild;/*p是原二叉排序樹的根*/elseif(f->lchild==p)/*p是f的左孩子*/

f->lchild=p->rchild；/*將p的右子樹鏈到f的左鏈上*/

else/*p是f的右孩子*/

f->rchild=p->rchild;/*將p的右子樹鏈到f的右鏈上*/

free(p);/*釋放被刪除的結(jié)點p*/

}

else/*p有左子樹*/

{q=p;s=p->lchild;

while(s->rchild)/*在p的左子樹中查找最右下結(jié)點*/

{q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;/*將s的左子樹鏈到q上*/

elseq->rchild=s->lchild;

p->key=s->key;/*將s的值賦給p*/

free(s);

}

returnt;

}/*DelBST*/【算法8.6在二叉排序樹中刪除結(jié)點】3.二叉排序樹的查找因為二叉排序樹可看作是一個有序表，所以在二叉排序樹上進行查找與折半查找類似，也是一個逐步縮小查找范圍的過程。根據(jù)二叉排序樹的特點，首先將待查關(guān)鍵字k與根結(jié)點關(guān)鍵字t進行比較，如果：(1）k=t，則返回根結(jié)點地址；(2）k<t，則進一步查左子樹；(3）k>t，則進一步查右子樹。顯然，這是一個遞歸過程。可用如下遞歸算法實現(xiàn)：BSTreeSearchBST(BSTreebst,KeyTypekey)

/*在根指針bst所指二叉排序樹中，遞歸查找某關(guān)鍵字等于key的元素，若查找成功，則返回指向該元素結(jié)點指針，否則返回空指針*/

{

if(!bst)returnNULL;

elseif(bst->key==key)returnbst;/*查找成功*/

else

if(key<bst->key)

returnSearchBST(bst->lchild,key);/*在左子樹中繼續(xù)查找*/

else

returnSearchBST(bst->rchild,key);/*在右子樹中繼續(xù)查找*/

}【算法8.7二叉排序樹查找的遞歸算法】

根據(jù)二叉排序樹的定義，二叉排序樹查找的遞歸算法可以用循環(huán)方式直接實現(xiàn)。二叉排序樹的非遞歸查找過程如下：BSTreeSearchBST(BSTreebst,KeyTypekey)

/*在根指針bst所指二叉排序樹bst上，查找關(guān)鍵字等于key的結(jié)點，若查找成功，則返回指向該元素結(jié)點指針，否則返回空指針*/

{BSTreeq;

q=bst;

while(q)

{if(q->key==k)returnq;/*查找成功*/

if(key<q->data.key)q=q->lchild;/*在左子樹中查找*/

elseq=q->rchild;/*在右子樹中查找*/〖ZK)〗

}

returnNULL;/*查找失敗*/

}/*SearchBST*/【算法8.8二叉排序樹非遞歸查找算法】

4.二叉排序樹的查找性能顯然在二叉排序樹上進行查找，若查找成功，則是從根結(jié)點出發(fā)走了一條從根結(jié)點到待查結(jié)點的路徑。若查找不成功，則是從根結(jié)點出發(fā)走了一條從根到某個葉子結(jié)點的路徑。因此二叉排序樹的查找與折半查找過程類似，在二叉排序樹中查找一個記錄時，其比較次數(shù)不超過樹的深度。但是，對長度為n的表而言，無論其排列順序如何，折半查找對應(yīng)的判定樹是唯一的，而含有n個結(jié)點的二叉排序樹卻是不唯一的，所以對于含有同樣關(guān)鍵字序列的一組結(jié)點，結(jié)點插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)和深度不同。而二叉排序樹的平均查找長度ASL與二叉排序樹的形態(tài)有關(guān)，二叉排序樹的各分支越均衡，樹的深度越淺，其平均查找長度ASL越小。例如，圖8.8為兩棵二叉排序樹，它們對應(yīng)同一元素集合，但排列順序不同，分別是（45，24，53，12，37，93）和（12，24，37，45，53，93）。假設(shè)每個元素的查找概率相等，則它們的平均查找長度分別為

ASL=（1+2+2+3+3+3）/6=14/6

ASL=（1+2+3+4+5+6）/6=21/6圖8.8二叉排序樹的不同形態(tài)由此可見，在二叉排序樹上進行查找時的平均查找長度和二叉排序樹的形態(tài)有關(guān)。在最壞情況下，二叉排序樹是通過把一個有序表的n個結(jié)點依次插入生成的，由此得到二叉排序樹蛻化為一棵深度為n的單支樹，它的平均查找長度和單鏈表上的順序查找相同，也是（n+1）/2。在最好情況下，二叉排序樹在生成過程中，樹的形態(tài)比較均勻，最終得到的是一棵形態(tài)與二分查找的判定樹相似的二叉排序樹，此時它的平均查找長度大約是log2n。若考慮把n個結(jié)點按各種可能的次序插入到二叉排序樹中，則有n！棵二叉排序樹（其中有的形態(tài)相同），可以證明，對這些二叉排序樹的查找長度進行平均，得到的平均查找長度仍然是O(log2n)。8.3.2平衡二叉排序樹

平衡二叉排序樹又稱為AV樹。一棵平衡二叉排序樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：①左子樹與右子樹的高度之差的絕對值小于等于1；②左子樹和右子樹也是平衡二叉排序樹。引入平衡二叉排序樹的目的是為了提高查找效率，其平均查找長度為O（log#-2n）。在下面的描述中，需要用到結(jié)點的平衡因子（balancefactor）這一概念，其定義為結(jié)點的左子樹深度與右子樹深度之差。顯然，對一棵平衡二叉排序樹而言，其所有結(jié)點的平衡因子只能是-1、0，或1。當我們在一個平衡二叉排序樹上插入一個結(jié)點時，有可能導(dǎo)致失衡，即出現(xiàn)絕對值大于1的平衡因子，如2、-2。圖8.9中給出了一棵平衡二叉排序樹和一棵失去平衡的二叉排序樹。圖8.9平衡與不平衡的二叉排序樹

·

已知一棵平衡二叉排序樹如圖8.10（a）所示。在A的左子樹的左子樹上插入15后，導(dǎo)致失衡，如圖8.10（b）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可將A改為B的右子，B原來的右子改為A的左子，如圖8.10（c）所示。這相當于以B為軸，對A做了一次順時針旋轉(zhuǎn)。圖8.10不平衡二叉樹的調(diào)整(1)

·

已知一棵平衡二叉排序樹如圖8.11（a）所示。在A的右子樹B的右子樹上插入70后，導(dǎo)致失衡，如圖8.11（b）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可將A改為B的左子，B原來的左子改為A的右子，如圖8.11（c）所示。這相當于以B為軸，對A做了一次順時針旋轉(zhuǎn)。圖8.11不平衡二叉樹的調(diào)整(2)

·

已知一棵平衡二叉排序樹如圖8.12（a）所示。在A的左子樹B的右子樹上插入45后，導(dǎo)致失衡，如圖8.12（b）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可首先將B改為C的左子，而C原來的左子改為B的右子；然后將A改為C的右子，C原來的右子改為A的左子，如圖8.12（c）所示。這相當于對B做了一次逆時針旋轉(zhuǎn)，對A做了一次順時針旋轉(zhuǎn)。圖8.12不平衡二叉樹的調(diào)整(3)

·

已知一棵平衡二叉排序樹如圖8.13（a）所示。在A的右子樹的左子樹上插入55后，導(dǎo)致失衡，如圖8.13（b）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可首先將B改為C的右子，而C原來的右子改為B的左子；然后將A改為C的左子，C原來的左子改為A的右子，如圖8.13（c）所示。這相當于對B做了一次順時針旋轉(zhuǎn)，對A做了一次逆時針旋轉(zhuǎn)。圖8.13不平衡二叉樹的調(diào)整(4)

1）LL型假設(shè)最低層失衡結(jié)點為A，在結(jié)點A的左子樹的左子樹上插入新結(jié)點S后，導(dǎo)致失衡，如圖8.14（a）所示。由A和B的平衡因子容易推知，B

L、B

R以及A

R深度相同。為恢復(fù)平衡并保持二叉排序樹的特性，可將A改為B的右子，B原來的右子BR改為A的左子，如圖8.14（b）所示。這相當于以B為軸，對A做了一次順時針旋轉(zhuǎn)。圖8.14二叉排序樹的LL型平衡旋轉(zhuǎn)

在一般二叉排序樹的結(jié)點中增加一個存放平衡因子的域bf，就可以用來表示平衡二叉排序樹。在下面的討論中，我們約定：用來表示結(jié)點的字母，同時也用來表示指向該結(jié)點的指針。因此，LL型失衡的特點是：A->bf=2，B->bf=1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->lchild；

A->lchild=B->rchild；

B->rchild=A；

A->bf=0；B->bf=0；

最后，將調(diào)整后二叉樹的根結(jié)點B“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用B代替A做FA的左子或右子；否則原來A就是根結(jié)點，此時應(yīng)令根指針t指向B：

if(FA==NULL)t=B;

elseif(A==FA->lchild)FA->lchild=B;

elseFA->rchild=B；

2）LR型假設(shè)最低層失衡結(jié)點為A，在結(jié)點A的左子樹的右子樹上插入新結(jié)點S后，導(dǎo)致失衡，如圖8.15（a）所示。圖中假設(shè)在CL下插入S，如果是在CR下插入S，對樹的調(diào)整方法相同，只是調(diào)整后A、B的平衡因子不同。由A、B、C的平衡因子容易推知，CL與CR深度相同，BL與AR深度相同，且BL、AR的深度比CL

、CR的深度大1。為恢復(fù)平衡并保持二叉排序樹特性，可首先將B改為C的左子，而C原來的左子CL改為B的右子；然后將A改為C的右子，C原來的右子CR改為A的左子，如圖8.15（b）所示。這相當于對B做了一次逆時針旋轉(zhuǎn)，對A做了一次順時針旋轉(zhuǎn)。圖8.15二叉排序樹的LR型平衡旋轉(zhuǎn)LR型失衡的特點是：A->bf=2，B->bf=-1。相應(yīng)調(diào)整操作可用如下語句完成：

B=A->lchild；C=B->rchild；

B->rchild=C->lchild；

A->lchild=C->rchild；

C->lchild=B；C->rchild=A；然后針對上述三種不同情況，修改A、B、C的平衡因子：if(S->key<C->key)/*在C#-L下插入S*/

{A->bf=-1；B->bf=0；C->bf=0；}

if(S->key>C->key)/*在C#-R下插入S*/

{A->bf=0；B->bf=1；C->bf=0；}

if(S->key==C->key)/*C本身就是插入的新結(jié)點S*/

{A->bf=0；B->bf=0；}

最后，將調(diào)整后的二叉樹的根結(jié)點C“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用C代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向C：

if(FA==NULL)t=C;

elseif(A==FA->lchild)FA->lchild=C;

elseFA->rchild=C；3）RR型

RR型與LL型對稱。假設(shè)最底層失衡結(jié)點為A，在結(jié)點A的右子樹的右子樹上插入新結(jié)點S后，導(dǎo)致失衡，如圖8.16（a）所示。由A和B的平衡因子容易推知，BL、BR以及AL深度相同。為恢復(fù)平衡并保持二叉排序樹特性，可將A改為B的左子，B原來的左子BL改為A的右子，如圖8.15（b）所示。這相當于以B為軸，對A做了一次逆時針旋轉(zhuǎn)。

圖8.16二叉排序樹的RR型平衡旋轉(zhuǎn)RR型失衡的特點是：A->bf=-2，B->bf=-1。相應(yīng)調(diào)整操作可用如下語句完成：B=A->rchild；

A->rchild=B->lchild；

B->lchild=A；

A->bf=0；B->bf=0；

最后，將調(diào)整后二叉樹的根結(jié)點B“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用B代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向B：

if(FA==NULL)t=B;

elseif(A==FA->lchild)FA->lchild=B;

elseFA->rchild=B；

4）RL型

RL型與LR型對稱。假設(shè)最低層失衡結(jié)點為A，在結(jié)點A的右子樹的左子樹上插入新結(jié)點S后，導(dǎo)致失衡，如圖8.17（a）所示。圖中假設(shè)在CR下插入S，如果是在C

L下插入S，對樹的調(diào)整方法相同，只是調(diào)整后A、B的平衡因子不同。由A、B、C的平衡因子容易推知，CL與CR深度相同，AL與BR深度相同，且AL、BR的深度比CL、CR的深度大1。為恢復(fù)平衡并保持二叉排序樹特性，可首先將B改為C的右子，而C原來的右子CR改為B的左子；然后將A改為C的左子，C原來的左子CL改為A的右子，如圖8.17（b）所示。這相當于對B做了一次順時針旋轉(zhuǎn)，對A做了一次逆時針旋轉(zhuǎn)。圖8.17二叉排序樹的RL型平衡旋轉(zhuǎn)RL型失衡的特點是：A->bf=-2，B->bf=1。相應(yīng)調(diào)整操作可用如下語句完成：

B=A->rchild；C=B->lchild；

B->lchild=C->rchild；

A->rchild=C->lchild；

C->lchild=A；C->rchild=B；

然后針對上述三種不同情況，修改A、B、C的平衡因子：if(S->key<C->key)/*在CL下插入S*/

{A->bf=0；B->bf=-1；C->bf=0；}

if(S->key>C->key)/*在CR下插入S*/

{A->bf=1；B->bf=0；C->bf=0；}

if(S->key==C->key)/*C本身就是插入的新結(jié)點S*/

{A->bf=0；B->bf=0；}

最后，將調(diào)整后的二叉樹的根結(jié)點C“接到”原A處。令A(yù)原來的父指針為FA，如果FA非空，則用C代替A做FA的左子或右子；否則，原來A就是根結(jié)點，此時應(yīng)令根指針t指向C：

if(FA==NULL)t=C;

elseif(A==FA->lchild)FA->lchild=C;

elseFA->rchild=C；

綜上所述，在一個平衡二叉排序樹上插入一個新結(jié)點S時，主要包括以下三步：（1）查找應(yīng)插位置，同時記錄離插入位置最近的可能失衡結(jié)點A（A的平衡因子不等于0）。（2）插入新結(jié)點S，并修改從A到S路徑上各結(jié)點的平衡因子。（3）根據(jù)A、B的平衡因子，判斷是否失衡以及失衡類型，并做相應(yīng)處理。

下面給出完整算法，其中AVLTree為平衡二叉排序樹類型，AVLTNode為平衡二叉排序樹結(jié)點類型，請讀者參考前面二叉樹類型自己寫出。voidins

-AVLtree（AVLTree*avlt,KeyTypek）/*在平衡二叉排序樹中插入元素k，使之成為一棵新的平衡二叉排序樹*/

{

S=(AVLTree)malloc(sizeof(AVLTNode));

S->key=k;S->lchild=S->rchild=NULL;

S->bf=0;

if(*avlt==NULL)*avlt=S;

else

{

/*首先查找S的插入位置fp，同時記錄距S的插入位置最近且平衡因子不等于0（等于-1或1）的結(jié)點A，A為可能的失衡結(jié)點*/

A=*avlt；FA=NULL;

p=*avlt；fp=NULL

while(p!=NULL)

{if(p->bf!=0){A=p;FA=fp};

fp=p;

if(K<p->key)p=p->lchild;

elsep=p->rchild;

}

/*插入S*/

if(K<fp->key)fp->lchild=S;

elsefp->rchild=S;/*確定結(jié)點B，并修改A的平衡因子*/

if(K<A->key){B=A->lchild；A->bf=A->bf+1}

else{B=A->rchild；A->bf=A->bf-1}

/*修改B到S路徑上各結(jié)點的平衡因子（原值均為0）*/

p=B；

while(p!=S)

if(K<p->key){p->bf=1；p=p->lchild}

else{p->bf=-1；p=p->rchild}

/*判斷失衡類型并做相應(yīng)處理*/

if(A->bf==2&&B->bf==1)/*LL型*/

{

B=A->lchild；

A->lchild=B->rchild；B->rchild=A；

A->bf=0；B->bf=0；

ifFA=NULL*avlt=B

elseifA=FA->lchildFA->lchild=B

elseFA->rchild=B；

}

elseif(A->bf==2&&B->bf==-1)/*LR型*/

{

B=A->lchild；C=B->rchild；

B->rchild=C->lchild；

A->lchild=C->rchild；

C->lchild=B；C->rchild=A；if(S->key<C->key)

{A->bf=-1；B->bf=0；C->bf=0；}

elseif(S->key>C->key)

{A->bf=0；B->bf=1；C->bf=0；}

else{A->bf=0；B->bf=0；}

if(FA==NULL)*avlt=C;

elseif(A==FA->lchild)FA->lchild=C;

elseFA->rchild=C；

}

elseif(A->bf==-2&&B->bf==1)/*RL型*/

{

B=A->rchild；C=B->lchild；

B->lchild=C->rchild；

A->rchild=C->lchild；

C->lchild=A；C->rchild=B；

if(S->key<C->key)

{A->bf=0；B->bf=-1；C->bf=0；}

elseif(S->key>C->key)

{A->bf=1；B->bf=0；C->bf=0；}

else{A->bf=0；B->bf=0；}

if(FA==NULL)*avlt=C;

elseif(A==FA->lchild)FA->lchild=C;

elseFA->rchild=C；

}

elseif(A->bf==-2&&B->bf==-1)/*RR型*/

{

B=A->rchild；

A->rchild=B->lchild；

B->lchild=A；

A->bf=0；B->bf=0；

if(FA==NULL)*avlt=B;

elseif(A==FA->lchild)FA->lchild=B;

elseFA->rchild=B；

}

}

}【算法8.9平衡二叉排序樹的插入】8.3.3B樹1.m路查找樹

與二叉排序樹類似，可以定義一種“m叉排序樹”，通常稱為m路查找樹。一棵m路查找樹，或者是一棵空樹，或者是滿足如下性質(zhì)的樹：

(1）每個結(jié)點最多有m棵子樹、m-1個關(guān)鍵字，其結(jié)構(gòu)如下：nP0K1P1K2P2…KnPn

其中n為關(guān)鍵字個數(shù)，Pi(0≤i≤n)為指向子樹根結(jié)點的指針，Ki(1≤i≤n)為關(guān)鍵字。

(2）Ki<Ki+1，1≤i≤n-1。

(3）子樹Pi中的所有關(guān)鍵字均大于Ki、小于Ki+1，1≤i≤n-1。

(4）子樹P0中的關(guān)鍵字均小于K1，而子樹Pn中的所有關(guān)鍵字均大于Kn。

(5）子樹Pi也是m路查找樹，0≤i≤n。從上述定義可以看出，對任一關(guān)鍵字Ki而言，Pi-1相當于其“左子樹”，Pi相當于其“右子樹”，1≤i≤n。圖8.183路查找樹2.B樹及其查找一棵B樹是一棵平衡的m路查找樹，它或者是空樹，或者是滿足如下性質(zhì)的樹：（1）樹中每個結(jié)點最多有m棵子樹；（2）根結(jié)點至少有兩棵子樹；（3）除根結(jié)點之外的所有非葉子結(jié)點至少有［m/2］棵子樹；（4）所有葉子結(jié)點出現(xiàn)在同一層上，并且不含信息，通常稱為失敗結(jié)點。失敗結(jié)點為虛結(jié)點，在B樹中并不存在，指向它們的指針為空指針。引入失敗結(jié)點是為了便于分析B樹的查找性能。

圖8.19一棵4階B_樹

首先由根指針mbt找到根結(jié)點A，因為58>37，所以找到結(jié)點C，又因為40<58<85,所以找到結(jié)點G，最后在結(jié)點G中找到58。如果要查找32，首先由根指針mbt找到根結(jié)點A，因為32<37，所以找到結(jié)點B，因為32>25,所以找到結(jié)點E，又因為30<32<35,所以最后找到失敗結(jié)點f，表示32不存在，查找失敗。在具體實現(xiàn)時，采用如下結(jié)點結(jié)構(gòu)：parentnK1K2…KnP0P1…Pn＃definem<階數(shù)>

typedefintBoolean;

typedefstructMbtnode

{

structMbtnode*parent;

intkeynum;

KeyTypekey［m+1］;

structMbtnode*ptr［m+1］;

}Mbtnode,*Mbtree;Booleansrch

-mbtree(Mbtreembt,KeyTypek,Mbtree*np,int*pos)

/*在根為mbt的B樹中查找關(guān)鍵字k，如果查找成功，則將所在結(jié)點地址放入np，將結(jié)點內(nèi)位置序號放入pos，并返回true；否則，將k應(yīng)被插入的結(jié)點地址放入np，將結(jié)點內(nèi)應(yīng)插位置序號放入pos，并返回false*/

{

p=mbt;fp=NULL;found=false;i=0;

while(p!=NULL&&!found)

{

i=search(p,k);

if(i>0&&p->key［i］==k)found=true;

else{fp=p;p=p->ptr［i］;}

}

iffound{*np=p;*pos=i;returntrue;}

else{*np=fp;*pos=i;returnfalse;}

}【算法8.10在B樹中查找關(guān)鍵字為k的元素】intsearch(Mbtreembt,KeyTypekey)

/*在mbt指向的結(jié)點中，尋找小于等于key的最大關(guān)鍵字序號*/

{

n=mbt->keynum;

i=1;

while(i<=n&&mbt->key［i］<=key)i++;

return(i-1)/*返回小于等于key的最大關(guān)鍵字序號，為0時表示應(yīng)到最左分支找，越界時表示應(yīng)到最右分支找*/

}【算法8.11尋找小于等于關(guān)鍵字key的最大關(guān)鍵字序號】3.B樹的插入圖8.20給出了一個B樹的插入實例。已知一棵3階B樹如圖8.19（a）所示，要求插入52、20、49。插入52：首先查找應(yīng)插位置，即結(jié)點f中50的后面，插入后如圖8.20（b）所示。

·

插入20：直接插入后如圖8.19（c）所示，由于結(jié)點c的分支數(shù)變?yōu)?，超出了3階B樹的最大分支數(shù)3，需將結(jié)點c分裂為兩個較小的結(jié)點。以中間關(guān)鍵字14為界，將c中關(guān)鍵字分為左、右兩部分，左邊部分仍在原結(jié)點c中，右邊部分放到新結(jié)點c′中，中間關(guān)鍵字14插到其父結(jié)點的合適位置，并令其右指針指向新結(jié)點c′，如圖8.20（d）所示。圖8.20B_樹的插入實例

·

插入49：直接插入后如圖8.20（e）所示。f結(jié)點應(yīng)分裂，分裂后的結(jié)果如圖8.20（f）所示。50插到其父結(jié)點e的key［1］處，新結(jié)點f′的地址插到e的ptr［1］處，e中ptr［0］不變，仍指向原結(jié)點f。此時，e仍需要分裂，繼續(xù)分裂后的結(jié)果如圖8.20（g）所示。53存到其父結(jié)點a的key［2］處，ptr［2］指向新結(jié)點e′，ptr［1］仍指向原結(jié)點e。我們可以利用B樹的插入方法，從空樹開始，逐個插入關(guān)鍵字，從而創(chuàng)建一棵B樹。例如，已知關(guān)鍵字集為{37，70，12，45，90，3，24，61，53}，要求從空樹開始，逐個插入關(guān)鍵字，創(chuàng)建一棵3階B樹。創(chuàng)建過程如圖8.21所示。圖8.21從空樹開始，逐個插入關(guān)鍵字，創(chuàng)建一棵3階B樹

從上述B樹的構(gòu)造過程可得出以下結(jié)論：（1）由于B樹是“從葉往根”長，而根對每個分支是公用的，所以不論根長到多“深”，各分支的長度同步增長，因而各分支是“平衡”的。（2）生長的幾種情況：

·

最底層某個結(jié)點增大，分支數(shù)不變，且各分支深度也不變。

·

從最下層開始，發(fā)生單次或連續(xù)分裂，但根結(jié)點未分裂，此時分支數(shù)增1（最下層結(jié)點增1），但原分支深度不變，新分支深度與原分支相同。

·

從最下層開始，連續(xù)分裂，根結(jié)點也發(fā)生分裂，產(chǎn)生一個新的根結(jié)點，此時分支數(shù)仍增1（最下層結(jié)點增1），但新、舊分支均為原分支長度加1。顯然，對非空的B樹而言，根結(jié)點至少有兩棵子樹（包括由失敗結(jié)點構(gòu)成的子樹），這就是B樹定義中提到的第2條性質(zhì)。（3）根的形成過程：始未分裂的根：關(guān)鍵字個數(shù)為0~m-1，分支數(shù)為由分裂形成的根：關(guān)鍵字個數(shù)為1~m-1，分支數(shù)為2~m。根0(空樹)。2~m(失敗結(jié)點數(shù))。

（4）除根以外的非終端結(jié)點的形成過程：

由“滿結(jié)點”分裂而得。假設(shè)m階B樹中p結(jié)點中已有m-1個關(guān)鍵字，當再插入一個關(guān)鍵字后，結(jié)點中信息為m,A0,(k1,A1),(k2,A2),…,（km,Am）,有m+1個分支，為保持m階（m個分支），應(yīng)將p結(jié)點分裂為關(guān)鍵字個數(shù)盡量相等的p結(jié)點和新結(jié)點p1（或者說從p中分出一部分信息構(gòu)成p1）。分裂后p中剩余信息為：［m/2］-1,A0,(k1,A1),(k2,A2),…,（k［m/2］-1,A［m/2］-1），共有［m/2］-1個關(guān)鍵字，及這些關(guān)鍵字的［m/2］個左、右相鄰分支指針。

分裂出去的信息為：（k［m/2］,A［m/2］）,（k［m/2］+1,A［m/2］+1）,…,（km,Am），共計m-(［m/2］-1)=m-［m/2］+1個關(guān)鍵字及其右指針，其中k［m/2］上移到p的父結(jié)點中，其余信息存入新結(jié)點p1中，所以p1中信息為：m-［m/2］，A［m/2］,（k［m/2］+1,A［m/2］+1）,…,（km,Am）。顯然，分裂后的非終端結(jié)點（除根結(jié)點）所含關(guān)鍵字最少，分支也最少，其中p的分支數(shù)為B1=［m/2］，p1的分支數(shù)為B2=m-［m/2］+1。容易證明，B1≤B2，所以，除根之外的所有非終端結(jié)點至少有［m/2］棵子樹，這就是B樹定義中提到的第3條性質(zhì)。下面給出B樹插入的有關(guān)算法。Voidins

-mbtree(Mbtree*mbt,KeyTypek,Mbtreeq,inti);

/*在m階B樹t中插入k：如果mbt=NULL，則生成初始根（此時q=NULL,i=0）；否則q指向某個最下層非終端結(jié)點，k應(yīng)插在該結(jié)點中q->key［i+1］處，插入后如果q->keynum>m-1，則進行分裂處理*/

{

if(*mbt==NULL)

{

*mbt=(Mbtree)malloc(sizeof(Mbtnode));

(*mbt)->keynum=1;(*mbt)->parent=NULL;

(*mbt)->key［1］=k;(*mbt)->ptr［0］=NULL;(*mbt)->ptr［1］ =NULL;

}else

{x=k;/*將x插到q->key［i+1］處*/

ap=NULL;/*將ap插到q->ptr［i+1］處*/

fFinished=NULL;

while(q!=NULL&&!finished)/*q=NULL表示已經(jīng)分裂到根*/

{

insert(q,i,x,ap);

if(q->keynum<m)finished=TRUE/*不再分裂*/

else{

s=ceil((float)m/2);/*s=［m/2］*/

split(q,q1);/*分裂*/

x=q->key［s］;ap=q1;

q=q->parent;

if(q!=NULL)i=search(q,x);/*search()的定義參見B樹查找一節(jié)*/

}

}

if(!finished)/*表示根結(jié)點要分裂，并產(chǎn)生新根*/

{

new

-root=(Mbtree)malloc(sizeof(Mbtnode));

new

-root->keynum=1;new

-root->parent=NULL;new

-root->key［1］=x;new

-root->ptr［0］=*mbt;new

-root->ptr［1］=ap;

*mbt=new

-root;

}

}

}【算法8.12B樹的插入算法】voidinsert(Mbtreembp,intipos,KeyTypekey,Mbtreerp)

/*在mbp->key［ipos+1］處插上key,在mbp->ptr［ipos+1］處插上rp*/

{

for(j=mbp->keynum;j>=ipos+1;j--)

{mbp->key［j+1］=mbp->key［j］;

mbp->ptr［j+1］=mbp->ptr［j］;

}

mbp->key［ipos+1］=key;

mbp->ptr［ipos+1］=rp;

mbp->keynum++;

}【算法8.13在mbp->key［ipos+1］處插上key】voidsplit(Mbtreeoldp,Mbtree*newp)

{/*B樹的分裂過程*/

s=ceil((float)m/2);/*s=［m/2］*/

n=m-s;

newp=(Mbtree)malloc(sizeof(Mbtnode));

newp->keynum=n;

newp->parent=oldp->parent;

newp->ptr［0］=oldp->ptr［s］;

for(i=1;i<=n;i++)

{newp->key［i］=oldp->key［s+i］;

newp->ptr［i］=oldp->ptr［s+i］;

}

oldp->keynum=s-1;

}【算法8.14B樹的分裂算法】4.在B樹中刪除一個關(guān)鍵字

1）在最下層結(jié)點中刪除一個關(guān)鍵字圖8.21給出了在B樹最下層結(jié)點中刪除關(guān)鍵字的實例。圖8.22（a）所示為一棵4階B樹(m=4)，要求刪除11、53、39、64、27。

(1)刪除11時，13與其右的指針左移即可，如圖8.22（b）所示。

(2)刪除53后，如圖8.22（c）所示。結(jié)論：當最下層結(jié)點中的關(guān)鍵字數(shù)大于［m/2］-1時，可直接刪除。(3)刪除39時，為保持其“中序有序”，可將父結(jié)點中43下移至39處，而將右兄弟中最左邊的47上移至原43處，如圖8.22（d）所示。結(jié)論：當最下層待刪關(guān)鍵字所在結(jié)點中關(guān)鍵字數(shù)目為最低要求［m/2］-1時，如果其左（右）兄弟中關(guān)鍵字數(shù)目大于［m/2］-1，則可采用上述“父子換位法”。(4)刪除64后，為保持各分支等長（平衡），將刪除64后的剩余信息(在此為空指針)及78合并入右兄弟，如圖8.22（e）所示。也可將刪除64后的剩余信息及47與左兄弟合并。結(jié)論：當最下層待刪結(jié)點及其左右兄弟中的關(guān)鍵字數(shù)目均為最低要求數(shù)目［m/2］-1時，需要進行合并處理，合并過程與插入時的分裂過程“互逆”，合并一次，分支數(shù)少一，可能出現(xiàn)“連鎖合并”，當合并到根時，各分支深度同時減1。(5)刪除27時，首先將剩余信息(在此為空指針)與父結(jié)點中的18并入左兄弟，并釋放空結(jié)點，結(jié)果如圖8.22（f）所示。此時父結(jié)點也需要合并，將父結(jié)點中的剩余信息（指針p1）與祖父結(jié)點中的35并入47左端，釋放空結(jié)點后的結(jié)果如圖8.22（g）所示。至此，祖父結(jié)點仍需要合并，但由于待合并結(jié)點的父指針為NULL，故停止合并，直接將根指針bt置為指針p2的值，釋放空結(jié)點后的結(jié)果如圖8.22（h）所示。

2）在非最下層結(jié)點中刪除一個關(guān)鍵字圖8.23給出了在B

-樹的非最下層結(jié)點中刪除關(guān)鍵字的實例。圖8.23（a）所示為一棵4階B

-樹，要求刪除43、35。

(1)刪除43，在保持“中序有序”的前提下，可將43“右子樹”中的最小值47（“左下端”）代替43，而后在“左下端”中刪除47，結(jié)果如圖8.23（b）所示。

(2)刪除35，如果用35“左子樹”的“右下端”元素27代替35，結(jié)果如圖8.23（c）所示，然后再刪除“右下端”中的27，結(jié)果如圖8.23（d）所示。一般情況下，刪除非最下層結(jié)點中的關(guān)鍵字，可轉(zhuǎn)化為刪除最下層結(jié)點中的關(guān)鍵字。

圖8.22在B_樹最下層結(jié)點中刪除關(guān)鍵字圖8.23在B_樹非最下層刪除關(guān)鍵字8.4計算式查找法——哈希法

哈希法又稱散列法、雜湊法或關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表。這種方法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系H，使得p=H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計算出該元素的存儲位置p=H(k)，從而達到按關(guān)鍵字直接存取元素的目的。