數(shù)據(jù)結(jié)構(gòu)-第八章查找

查找：根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。

在查找算法中要用到三類參量，即：①查找對象K（找什么）②查找范圍L（在哪找）③查找的結(jié)果（K在L中的位置）其中①、②為輸入?yún)⒘?，在函?shù)中不可缺少。③為輸出參量，可用函數(shù)返回值表示。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第1頁。平均查找長度：為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。

對于長度為n的列表，查找成功時的平均查找長度為：ASL=P1C1+P2C2+…+PnCn=i=1nPiCi其中Pi為查找列表中第i個數(shù)據(jù)元素的概率，Ci為找到列表中第i個數(shù)據(jù)元素時，已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第2頁。查找的基本方法：比較式查找法計算式查找法－HASH（哈希）查找法基于線性表的查找法基于樹的查找法數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第3頁。8.2基于線性表的查找法具有順序查找法、折半查找法和分塊查找法三種8.2.1順序查找法順序查找法的特點是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。

存儲結(jié)構(gòu)：順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第4頁。順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義：#defineLIST_SIZE20typedefstruct{ KeyTypekey; OtherTypeother_data; }RecordType;typedefstruct{ RecordTyper[LIST_SIZE+1];/*r[0]為工作單元*/ intlength; }RecordList;

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第5頁。設(shè)置監(jiān)視哨的順序查找算法intSeqSearch（RecordListl,KeyTypek）/*在順序表l中順序查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0*/{l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return（i）;}其中l(wèi).r[0]為監(jiān)視哨，可以起到防止越界的作用。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第6頁。不設(shè)置監(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!=k)i--;if(i>=1)return（i）elsereturn(0);}循環(huán)條件i>=1判斷查找是否越界。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第7頁。用平均查找長度分析順序查找算法的性能。

假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進(jìn)行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為：

ASL=i=1nPiCi＝n1i=1nCi＝n1i=1n(n-i+1)=21(n+1)數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第8頁。8.2.2折半查找法（二分法查找法）條件：要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。

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

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第9頁。例如用折半查找法查找10、50的具體過程，其中mid=(low+high)/2，當(dāng)high<low時，表示不存在這樣的子表空間，查找失敗。

6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=1mid=3high=5用折半查找法查找12的過程為：數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第10頁。6058463528252218151261234567891011low=1mid=1high=26058463528252218151261234567891011low=2mid=2high=2數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第11頁。用折半查找法查找50的過程：6058463528252218151261234567891011low=1mid=6high=116058463528252218151261234567891011low=7mid=9high=11數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第12頁。6058463528252218151261234567891011low=10mid=10high=116058463528252218151261234567891011low=10high=9數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第13頁。折半查找的算法如下：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ū)間進(jìn)行查找*/elselow=mid+1;/*繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/}return(0);}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第14頁。用平均查找長度分析折半查找算法的性能折半查找成功時的平均查找長度為：ASLbs＝i=1nPiCi＝n1j=1nj×2j-1＝nn+1log2(n+1)-1優(yōu)點：比較次數(shù)少，查找速度快，平均性能好。缺點：要求待查的表為有序表，且插入、刪除困難。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第15頁。8.2.3分塊查找法分塊查找法要求將列表組織成以下索引順序結(jié)構(gòu)：★首先將列表分成若干個塊（子表）。一般情況下，塊的長度均勻，最后一塊可以不滿。每塊中元素任意排列，即塊內(nèi)無序，但塊與塊之間有序。

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

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第16頁。下圖為一個索引順序表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)--第八章查找全文共100頁，當(dāng)前為第17頁。分塊查找的基本過程為：（1）首先，將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進(jìn)行。（2）進(jìn)一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素。

例如查找上圖索引表中36。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第18頁。分塊查找的平均查找長度由兩部分組成：即查找索引表時的平均查找長度為LB，以及在相應(yīng)塊內(nèi)進(jìn)行順序查找的平均查找長度LW。ASLbs=LB+LW

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

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第19頁。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)--第八章查找全文共100頁，當(dāng)前為第20頁。8.3基于樹的查找法基于樹的查找法（樹表查找法），是將待查表組織成特定樹的形式并在樹結(jié)構(gòu)上實現(xiàn)查找的方法?；跇涞牟檎曳ǘ媾判驑淦胶舛媾判驑銪樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第21頁。8.3.1二叉排序樹二叉排序樹（二叉查找樹），它是一種特殊結(jié)構(gòu)的二叉樹，其定義為：二叉樹排序樹或者是一棵空樹，或者是具有如下性質(zhì)的二叉樹：

（1）若它的左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；

（2）若它的右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；

（3）它的左右子樹也分別為二叉排序樹。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第22頁。

由定義可以得出二叉排序樹的一個重要性質(zhì)：中序遍歷一個二叉排序樹時可以得到一個遞增有序序列。

521436879二叉排序樹示例1CAOZHAODINGCHENWANG二叉排序樹示例2數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第23頁。使用二叉鏈表作為存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)說明如下：typedefstructnode{KeyTypekey;/*關(guān)鍵字的值*/structnode*lchild,*rchild;/*左右指針*/}bstnode,*BSTree;數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第24頁。1.二叉樹的插入和生成①若二叉排序樹是空樹，則Key成為二叉排序樹的根；②若二叉樹排序樹非空，則將key與二叉樹排序樹的根進(jìn)行比較，如果key的值等于根結(jié)點的值，則停止插入，如果key的值小于根結(jié)點的值，則將key插入左子樹，如果key的值大于根結(jié)點的值，則將key插入右子樹。

已知一個關(guān)鍵字值為Key的結(jié)點s，插入的方法：數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第25頁。二叉排序樹的插入算法：voidInsertBST(BSTree*bst,KeyTypekey)/*若在二叉排序樹中不存在關(guān)鍵字等于key的元素，插入該元素*/{BiTrees;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插入右子樹*/}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第26頁。

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

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第27頁。生成二叉排序樹的算法：voidCreateBST(BSTree*bst)/*從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹*/{

KeyTypekey;*bst=NULL;scanf("%d",&key);while(key!=ENDKEY)/*ENDKEY為自定義常數(shù)*/{InsertBST(bst,key);scanf("%d",&key);}}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第28頁。設(shè)關(guān)鍵字的輸入順序為：45，24，53，12，28，90，按上述算法生成的二叉排序樹的過程：空樹45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第29頁。對同樣一些元素值，如果輸入的順序不同，則所建的二叉樹形態(tài)也不同。如果將上述例子中的關(guān)鍵字順序變?yōu)椋?4，53,90,12,28,45,則生成的二叉排序樹為：241228539045數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第30頁。2.二叉排序樹的刪除刪除操作：首先確定被刪除的結(jié)點是否在二叉排序樹中。若不在

，則不做任何操作；否則，假設(shè)要刪除的結(jié)點為p，結(jié)點p的雙親結(jié)點為f，并假設(shè)結(jié)點p是結(jié)點f的左孩子（右孩子的情況類似）。

從二叉排序樹中刪除一個結(jié)點，必須保證刪除后所得的二叉樹仍然滿足二叉排序樹的性質(zhì)不變。下面分三種情況討論：數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第31頁。（2）若p結(jié)點只有左子樹，或只有右子樹，則可將p的左子樹或右子樹直接改為其雙親結(jié)點f的左子樹。即：f->lchild=p->lchild（或f->lchild=p->rchild）；free(p)；

（1）若p為葉結(jié)點，則可直接將其刪除：

f->lchild=NULL；free(p)；

（3）若p既有左子樹，又有右子樹，如下圖(a)，則處理的方法有兩種：FPPLPRfp(a)P的左右子樹均不空數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第32頁。方法一：首先找到p結(jié)點在中序序列中的直接前驅(qū)s結(jié)點，如圖

(b)所示，然后將p的左子樹改為f的左子樹，而將p的右子樹改為s的右子樹：f->lchild=p->lchild；s->rchild=p->rchild；free(p)；結(jié)果如圖

(c)所示。

FPCPRfpcSQQLSLqsCL(b)S為P的直接前驅(qū)CLFCSSLPRfc(c)將P的左子樹改為F的左子樹，將P的右子樹改為S的右子樹。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第33頁。方法二：首先找到p結(jié)點在中序序列中的直接前驅(qū)s結(jié)點，如圖

(b)所示，然后用s結(jié)點的值，替代p結(jié)點的值，再將s結(jié)點刪除，原s結(jié)點的左子樹改為s的雙親結(jié)點q的右子樹：p->data=s->data；q->rchild=s->lchild；free(s)；結(jié)果如圖

(d)所示。

FPCPRfpcSQQLSLqsCL(b)S為P的直接前驅(qū)(d)將原P結(jié)點的值改為S結(jié)點的值，刪除原S結(jié)點并將原S的左子樹改為Q的右子樹FSCPRfpcQQLSLqCL數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第34頁。在二叉排序樹中刪除結(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;}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第35頁。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*/}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第36頁。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*/

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第37頁。3.二叉排序樹的查找根據(jù)二叉排序樹的特點，首先將待查關(guān)鍵字k與根結(jié)點關(guān)鍵字t進(jìn)行比較，如果：（1）k=t：則返回根結(jié)點地址；

（2）k<t：則進(jìn)一步查左子樹；

（3）k>t：則進(jìn)一步查右子樹。

顯然，這是一個遞歸過程?？捎萌缦逻f歸算法實現(xiàn)：

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第38頁。二叉排序樹查找的遞歸算法為：BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指針bst所指二叉排序樹中，遞歸查找某關(guān)鍵字等于key的元素，若查找成功，返回指向該元素結(jié)點指針，否則返回空指針。*/{if(!bst)returnNULL;elseif(bst->key==key)returnbst;/*查找成功*/elseif(key<bst->key)returnSearchBST(bst->lchild,key);/*在左子樹繼續(xù)查找*/elsereturnSearchBST(bst->rchild,key);/*在右子樹繼續(xù)查找*/}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第39頁。二叉排序樹查找的非遞歸算法：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;/*在右子樹中查找*/}returnNULL;/*查找失敗*/}/*SearchBST*/數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第40頁。4.二叉排序樹的查找性能

對于含有同樣關(guān)鍵字序列的一組結(jié)點，結(jié)點插入的先后次序不同，所構(gòu)成的二叉排序樹的形態(tài)和深度不同。而二叉排序樹的平均查找長度ASL與二叉排序樹的形態(tài)有關(guān)，二叉排序樹的各分支越均衡，樹的深度淺，其平均查找長度ASL越小。例如：452412375393(a)輸入關(guān)鍵字序列為{45,24,53,12,37,93}時的二叉排序樹12122437455393(b)輸入關(guān)鍵字序列為{12,24,37,45,53,93}時的二叉排序樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第41頁。

假設(shè)每個元素的查找概率相等，則它們的平均查找長度分別是：

ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6由此可見，在二叉排序樹上進(jìn)行查找時的平均查找長度和二叉排序樹的形態(tài)有關(guān)。

若考慮把n個結(jié)點，按各種可能的次序插入到二叉排序樹中，則有n！棵二叉排序樹（其中有的形態(tài)相同），可以證明，對這些二叉排序樹進(jìn)行平均，得到的平均查找長度仍然是O(log2n)。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第42頁。8.3.2平衡二叉排序樹平衡二叉排序樹又稱為AV樹。一棵平衡二叉排序樹或者是空樹，或者是具有下列性質(zhì)的二叉排序樹：

（1）左子樹與右子樹高度之差的絕對值小于等于1；

（2）左子樹和右子樹也是平衡二叉排序樹。

平衡因子：結(jié)點的左子樹深度與右子樹深度之差。由性質(zhì)可知，一棵平衡二叉樹的所有結(jié)點的平衡因子只能是-1、0或1。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第43頁。40256030507080-1-1-1-1000402550305860-1-21000200(a)一棵平衡二叉排序樹(b)一棵失去平衡的二叉排序樹當(dāng)我們在一個平衡二叉排序樹上插入一個結(jié)點時，有可能導(dǎo)致失衡，即出現(xiàn)絕對值大于1的平衡因子，如2、-2。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第44頁。下面通過實例來說明失衡情況以及相應(yīng)的調(diào)整方法1.在(a)圖A的左子樹的左子樹上插入15后，導(dǎo)致失衡，如(b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可將A改為B的右子，B原來的右子改為A的左子，圖?,即以B為軸，對A做一次順時針旋轉(zhuǎn)。402560203010000AB(a)平衡二叉排序樹402560203020101AB150(b)插入15后失去平衡25204015300010BA6000?調(diào)整后的二叉排序樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第45頁。2.在(a)圖A的右子樹B的右子樹上插入70后，導(dǎo)致失衡，如(b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可將A改為B的左子，B原來的左子改為A的右子，圖(c),即以B為軸，對A做一次逆時針旋轉(zhuǎn)。(a)平衡二叉排序樹2520403060-10000AB2520403060-2-10-10AB700(b)插入70后失去平衡40256030700-1000AB200?調(diào)整后的二叉排序樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第46頁。3.在(a)圖A的左子樹B的右子樹上插入45后，導(dǎo)致失衡，如(b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可首先將B改為C的左子，而C原來的左子改為B的右子；然后將A改為C的右子，C原來的右子改為A的左子，即對B做了一次逆時針旋轉(zhuǎn)，對A做一次順時針旋轉(zhuǎn)。18010904020306050708595A0000C000000B(a)一棵平衡二叉排序樹8010904020306050708595A0001C01000-1B4502(b)插入45后失去平衡060108040203050457090C-100100000BA859500?調(diào)整后的二叉排序樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第47頁。4.在(a)圖A的右子樹B的左子樹上插入55后，導(dǎo)致失衡，如(b)圖。為恢復(fù)平衡并保證二叉排序樹的特性，可首先將B改為C的右子，而C原來的右子改為B的左子；然后將A改為C的左子，C原來的左子改為A的右子，即對B做了一次順時針旋轉(zhuǎn)，對A做一次逆時針旋轉(zhuǎn)。(a)一棵平衡二叉排序樹-140A0508060709085950C00000B20103000000-240A1508060709085950C00-11B2010300040A508060709085950C00B201030005500(b)插入55后失去平衡040C20608090859500B402007050551030-100000A?調(diào)整后的二叉排序樹數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第48頁。綜上所述，失衡類型及相應(yīng)的調(diào)整方法可歸納為以下四種：1）LL型（以B軸，對A做了一次順時針旋轉(zhuǎn)）ABBLBRSAR21(a)插入新結(jié)點S后失去平衡BABLBRSAR00(b)調(diào)整后恢復(fù)平衡在一般二叉排序樹的結(jié)點中增加一個存放平衡因子的域bf。LL型失衡的特點是：A->bf=2，B->bf=1。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第49頁。相應(yīng)調(diào)整操作可用如下語句完成：

B=A->Lchild；

A->Lchild=b->rchild；

B->rchild=A；

A->bf=0；

B->bf=0；

1）LL型數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第50頁。最后，將調(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；

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第51頁。2）LR型（對B做了一次逆時針旋轉(zhuǎn)，對A做了一次順時針旋轉(zhuǎn)）ABCRCLSAR2-1(a)插入新結(jié)點S后失去平衡BLC1CBCRCLSAR00(b)調(diào)整后恢復(fù)平衡BLA-1LR型失衡的特點是：A->bf=2，B->bf=-1。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第52頁。相應(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)/*在CL下插入S*/{A->bf=-1；B->bf=0；C->bf=0；}if(S->key>C->key)/*在CR下插入S*/{A->bf=0；B->bf=1；C->bf=0；}if(S->key==C->key)/*C本身就是插入的新結(jié)點S*/{A->bf=0；B->bf=0；}

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第53頁。最后，將調(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；

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第54頁。3）RR型（以B為軸，對A做了一次逆時針旋轉(zhuǎn)）(a)插入新結(jié)點S后失去平衡ABBLBRSAL-21-1(b)調(diào)整后恢復(fù)平衡0BABLBRSAL0RR型失衡的特點是：A->bf=-2，B->bf=-1。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第55頁。相應(yīng)調(diào)整操作可用如下語句完成：

B=A->rchild；

A->rchild=B->lchild；

B->lchild=A；

A->bf=0；

B->bf=0；

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第56頁。最后，將調(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；

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第57頁。4）RL型（對B做了一次順時針旋轉(zhuǎn)，對A做了一次逆時針旋轉(zhuǎn)）ALCLCRBRS-21-1(a)插入新結(jié)點S后失去平衡BRCLCRALS001(b)調(diào)整過后恢復(fù)平衡RL型失衡的特點是：A->bf=-2，B->bf=1。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第58頁。相應(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；}

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第59頁。最后，將調(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；

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

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第61頁。平衡二叉排序樹的插入算法其中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{

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第62頁。/*首先查找S的插入位置FP，同時記錄距S的插入位置最近且平衡因子不等于0（等于-1或1）的結(jié)點a，a為可能的失衡結(jié)點*/A=*avlt；fa=NULL;p=*avlt；fp=NULLwhile(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的平衡因子*/數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第63頁。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；數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第64頁。ifFA=NULL*avlt=belseifA=FA->LchildFA->Lchild=BelseFA->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)數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第65頁。{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；}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第66頁。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；

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第67頁。A->bf=0；B->bf=0；

if(FA==NULL)*avlt=B;elseif(A==FA->Lchild)FA->Lchild=B;elseFA->rchild=B；}}}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第68頁。8.3.3B樹1.m路查找樹（m叉排序樹）定義：一棵m路查找樹，或者是一棵空樹，或者是滿足如下性質(zhì)的樹：

1)結(jié)點最多有m棵子樹，m—1個關(guān)鍵字，其結(jié)構(gòu)如下：

nP0K1P1K2P2KnPn其中n為關(guān)鍵字個數(shù)，Pi為指向子樹根結(jié)點的指針，0≤i≤n，Ki為關(guān)鍵字，1≤i≤n數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第69頁。2）Ki<Ki+1，1≤i≤n-13）子樹Pi中的所有關(guān)鍵字均大于Ki、小于Ki+1，1≤i≤n-14）子樹P0中的關(guān)鍵字均小于K1，而子樹Pn中的所有關(guān)鍵字均大于Kn

5）子樹Pi也是m路查找樹，0≤i≤n。

從定義可以看出，對任一關(guān)鍵字Ki而言，Pi-1相當(dāng)于其“左子樹”，Pi相當(dāng)于其“右子樹”，1≤i≤n。

例如3路查找樹見p210的圖8.17所示，查找35。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第70頁。2.B樹及其查找一棵B樹是一棵平衡的m路查找樹，它或者是空樹，或者是滿足如下性質(zhì)的樹：

（1）樹中每個結(jié)點最多有m棵子樹；（2）根結(jié)點至少有兩棵子樹；（3）除根結(jié)點之外的所有非葉結(jié)點至少有棵子樹；（4）所有葉結(jié)點出現(xiàn)在同一層上，并且不含信息，通常稱為失敗結(jié)點。失敗結(jié)點為虛結(jié)點，在B樹中并不存在，指向它們的指針為空指針。引入失敗結(jié)點是為了便于分析B樹的查找性能。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第71頁。例如p211的圖8.18是一棵4階B樹，查找58的過程為：首先由根指針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…PnParent為指向雙親結(jié)點的指針。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第72頁。在B樹中查找關(guān)鍵字為k的元素算法如下：#definem<階數(shù)>typedef intBoolean;typedef structMbtnode{ structMbtnode*parent; intkeynum; KeyTypekey[m+1]; structMbtnode*ptr[m+1];}Mbtnode,*Mbtree;

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第73頁。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;}}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第74頁。尋找小于等于關(guān)鍵字key的最大關(guān)鍵字序號算法intsearch(Mbtreembt,KeyTypekey){ n=mbt->keynum; i=1; while(i<=n&&mbt->key[i]<=key)i++;return(i–1)/*返回小于等于key的關(guān)鍵字序號，為0時表示應(yīng)到最左分支找，越界時表示應(yīng)到最右分支找*/}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第75頁。3.B樹的插入已知一棵3階B樹如圖p212的圖8.19(a)，要求插入52、20、49。具體過程見p212的圖(b),(c),(d),(e),(f),(g)。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第76頁。利用B樹的插入方法，從空樹開始，逐個插入關(guān)鍵字，從而創(chuàng)建一棵樹。例如關(guān)鍵字集為{37,70,12,45,90,3,24,61,53}。創(chuàng)建過程見p213的圖8.20所示。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第77頁。從B樹的構(gòu)造過程可得出以下結(jié)論：

（1）由于B樹是“從葉往根”長，而根對每個分支是公用的，所以不論根長到多“深”，各分支的長度同步增長，因而各分支是“平衡”的。

（2）生長的幾種情況：1)最底層某個結(jié)點增大，分支數(shù)不變，且各分支深度也不變。2)從最下層開始，發(fā)生單次或連續(xù)分裂，但根結(jié)點未分裂，此時分支數(shù)增1（最下層結(jié)點增1），但原分支深度不變，新分支深度與原分支相同。3)從最下層開始，連續(xù)分裂，根結(jié)點也發(fā)生分裂，產(chǎn)生一個新的根結(jié)點，此時分支數(shù)仍增1（最下層結(jié)點增1），但新、舊分支均為原分支長度加1。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第78頁。（3）根的形成過程：

2~m（失敗結(jié)點數(shù)）

根

初始未分裂的根：關(guān)鍵字個數(shù)為0~m-1，分支數(shù)為

0（空樹）由分裂形成的根：關(guān)鍵字個數(shù)為1~m-1，分支數(shù)為

2~m（4）除根以外的非終端結(jié)點的形成過程：由“滿結(jié)點”分裂而得。

下面給出B樹的插入算法：數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第79頁。Voidins_mbtree(Mbtree*mbt,KeyTypek,Mbtree q,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，則進(jìn)行分裂處理*/{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;}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第80頁。else{x=k;/*將x插到q->key[i+1]處*/ap=NULL; /*將ap插到q->ptr[i+1]處*/Finished=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;數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第81頁。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;}}}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第82頁。在mbp->key[ipos+1]處插上key算法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++;}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第83頁。B樹的分裂算法

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;}數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第84頁。4.在B樹中刪除一個關(guān)鍵字1）在最下層結(jié)點中刪除一個關(guān)鍵字(見p217的圖8.21)結(jié)論：當(dāng)最下層結(jié)點中的關(guān)鍵字?jǐn)?shù)

大于m/2

-1時

，可直接刪除。當(dāng)最下層待刪關(guān)鍵字所在結(jié)點中關(guān)鍵字?jǐn)?shù)目為最低要求m/2

-1時，如果其左（右）兄弟中關(guān)鍵字?jǐn)?shù)目大于m/2

-1，則可采用上述“父子換位法”。當(dāng)最下層待刪結(jié)點及其左右兄弟中的關(guān)鍵字?jǐn)?shù)目均為最低要求數(shù)目m/2

-1時，需要進(jìn)行合并處理，合并過程與插入時的分裂過程“互逆”，合并一次，分支數(shù)少一，可能出現(xiàn)“連鎖合并”，當(dāng)合并到根時，各分支深度同時減1。數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第85頁。2）在非最下層結(jié)點中刪除一個關(guān)鍵字

示例見p217的圖8.22所示。一般情況下，刪除非最下層結(jié)點中的關(guān)鍵字，可轉(zhuǎn)化為刪除最下層結(jié)點中的關(guān)鍵字。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第86頁。8.4計算式查找法－哈希法哈希法又稱散列法、雜湊法以及關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表。哈希法的基本思想：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系f，使得p=f(k)，f稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為f(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計算出該元素的存儲位置p=f(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第87頁。8.4.1哈希函數(shù)的構(gòu)造方法構(gòu)造原則：①函數(shù)本身便于計算；②計算出來的地址分布均勻，即對任一關(guān)鍵字k，f(k)對應(yīng)不同地址的概率相等，目的是盡可能減少沖突。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第88頁。構(gòu)造方法：1.數(shù)字分析法：如果事先知道關(guān)鍵字集合，并且每個關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。

2.平方取中法：當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。

數(shù)據(jù)結(jié)構(gòu)--第八章查找全文共100頁，當(dāng)前為第89頁。3.分段疊加法：這種方法是按哈希表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分（最后一部分可以較短），然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果就是該關(guān)鍵字的哈希地址。具體方法有折疊法與移位法。

123123603306247247112211+）020+）020———————————11