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

何謂查找表？

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。第九章查找對查找表經(jīng)常進行的操作:1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表查找表可分為兩類:是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。關(guān)鍵字

若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。

若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。

根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。

查找

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，

用另外一種結(jié)構(gòu)來表示查找表。如何進行查找？查找的方法取決于查找表的結(jié)構(gòu)。9.1靜態(tài)查找表9.2動態(tài)查找樹表9.3哈希表9.1靜態(tài)查找表typedefstruct{

//數(shù)據(jù)元素存儲空間基址，建表時

//按實際長度分配，0號單元留空

int

length;//表的長度}SSTable;假設(shè)靜態(tài)查找表的順序存儲結(jié)構(gòu)為ElemType

*elem;數(shù)據(jù)元素類型的定義為:typedefstruct{

keyTypekey;//關(guān)鍵字域

……

//其它屬性域}ElemType;,TElemType;一、順序查找表二、有序查找表三、索引順序表

以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表ST.elem順序表的查找過程：假設(shè)給定值e=64,要求ST.elem[k]=e,問:k=?kkintlocation(SqListL,ElemType&e,

Status(*compare)(ElemType,ElemType)){k=1;p=L.elem;

while(k<=L.length

&&

!(*compare)(*++p,e)))k++;if(k<=L.length)returnk;

elsereturn0;}有點費時ST.elemiST.elemi60ikey=64key=60i64intSearch_Seq(SSTableST,

KeyTypekey){

//在順序表ST中順序查找其關(guān)鍵字等于

//key的數(shù)據(jù)元素。若找到，則函數(shù)值為

//該元素在表中的位置，否則為0。

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;

--i);

//從后往前找

returni;

//找不到時，i為0}

定義：

查找算法的平均查找長度

(AverageSearchLength)

為確定記錄在查找表中的位置，需和給定值

進行比較的關(guān)鍵字個數(shù)的期望值

其中:n為表長，Pi

為查找表中第i個記錄的概率，且，Ci為找到該記錄時，曾和給定 值比較過的關(guān)鍵字的個數(shù)。分析順序查找的時間性能在等概率查找的情況下，

順序表查找的平均查找長度為：對順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn

上述順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。ST.elemST.length例如:key=64

的查找過程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/2intSearch_Bin(SSTableST,KeyTypekey){

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

while(low<=high){mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))

returnmid;//找到待查元素

elseif(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間進行查找

else

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

}return0;//順序表中不存在待查元素}//Search_Bin21

先看一個具體的情況，假設(shè)：n=11分析折半查找的平均查找長度391425781011判定樹122333344446比較次數(shù)折半查找優(yōu)劣：折半查找的效率比順序查找高，但只適用于有序表，而且限于順序存儲結(jié)構(gòu)，對線性鏈表無法進行折半查找。在n>50時，可得近似結(jié)果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結(jié)點的完全二叉樹的深度相同。索引順序表的查找過程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個區(qū)間內(nèi)進行查找?？梢姡?/p>

索引順序查找，是一個“縮小區(qū)間”的查找過程。具體實現(xiàn)是分塊查找。例如：22121389203342443824486058744986531234567891011121314151617182248861713索引表最大關(guān)鍵字起始地址key=38ijkey=29ij索引順序查找的平均查找長度ASLbs=

查找“索引”的平均查找長度Lb

+查找“順序表”的平均查找長度Lw設(shè):表的長度：n均勻分成的塊數(shù)：b，每塊記錄個數(shù)：s若用順序查找確定所在的塊，則：ASLbs＝Lb＋Lw=當s=時，ASLbs最?。剑?9.2動態(tài)查找表一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹五、哈希表一、二叉排序樹（二叉查找樹）1．定義2．查找算法3．插入算法4．刪除算法（1）若它的左子樹不空，則左子樹上

所有結(jié)點的值均小于根結(jié)點的值；1．定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：（3）它的左、右子樹也都分別是二叉排序樹。（2）若它的右子樹不空，則右子樹上

所有結(jié)點的值均大于根結(jié)點的值；503080209010854035252388例如:是二叉排序樹。66不

通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)typedefstruct

BiTNode

{//結(jié)點結(jié)構(gòu)

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;TElemTypedata;2．二叉排序樹的查找算法：1）若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)點的關(guān)鍵字，則繼續(xù)在左子樹上進行查找；3）若給定值大于根結(jié)點的關(guān)鍵字，則繼續(xù)在右子樹上進行查找。否則，若二叉排序樹為空，則查找不成功；50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095,從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){在根指針T

所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，則返回指針

p指向該數(shù)據(jù)元素的結(jié)點，并返回

函數(shù)值為TRUE;}//SearchBST

…………否則表明查找不成功，返回指針

p

指向查找路徑上訪問的最后一個結(jié)點，并返回函數(shù)值為FALSE,指針f指向當前訪問的結(jié)點的雙親，其初始調(diào)用值為NULLif(!T)elseif

(EQ(key,T->data.key))

elseif

(LT(key,T->data.key))

else{p=f;returnFALSE;}//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);

//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);

//在右子樹中繼續(xù)查找30201040352523fT設(shè)key=48fTfT22pfTfTTTTfffp根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進行；3．二叉排序樹的插入算法若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。StatusInsertBST(BiTree&T,ElemTypee)

{//當二叉排序樹中不存在關(guān)鍵字等于e.key的//數(shù)據(jù)元素時，插入元素值為e的結(jié)點，并返//回TRUE;否則，不進行插入并返回FALSE

if

(!SearchBST(T,e.key,NULL,p))

{

}elsereturnFALSE;}//InsertBST……s=(BiTree)malloc(sizeof(BiTNode));

//為新結(jié)點分配空間s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s為新的根結(jié)點elseif(LT(e.key,p->data.key))p->lchild=s;

//插入*s為*p的左孩子elsep->rchild=s;//插入*s為*p的右孩子returnTRUE;//插入成功（1）被刪除的結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹；（3）被刪除的結(jié)點既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：

和插入相反，刪除在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。50308020908540358832（1）被刪除的結(jié)點是葉子結(jié)點例如:被刪關(guān)鍵字=2088其雙親結(jié)點中相應(yīng)指針域的值改為“空”50308020908540358832（2）被刪除的結(jié)點只有左子樹或者只有右子樹

其雙親結(jié)點的相應(yīng)指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字=408050308020908540358832（3）被刪除的結(jié)點既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關(guān)鍵字=50Status

DeleteBST(BiTree&T,KeyTypekey)

{//若二叉排序樹T中存在其關(guān)鍵字等于key的

//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回

//函數(shù)值TRUE，否則返回函數(shù)值FALSE

if(!T)returnFALSE; //不存在關(guān)鍵字等于key的數(shù)據(jù)元素

else{}}//DeleteBST算法描述如下：……if(EQ(key,T->data.key))

//找到關(guān)鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;}

DeleteBST(T->lchild,key);

//繼續(xù)在左子樹中進行查找DeleteBST(T->rchild,key);//繼續(xù)在右子樹中進行查找voidDelete(BiTree&p){//從二叉排序樹中刪除結(jié)點p，

//并重接它的左子樹或右子樹

if

(!p->rchild)

{}

elseif

(!p->lchild)

{}

else{}}//Delete其中刪除操作過程如下所描述：………………//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;free(q);ppqqpp//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);ppqqppq=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}//s指向被刪結(jié)點的前驅(qū)//左右子樹均不空p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;//重接*q的左子樹free(s);pqs5．查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2二、二叉平衡樹何謂“二叉平衡樹”？二叉平衡樹的查找性能分析如何構(gòu)造“二叉平衡樹”

二叉平衡樹是二叉查找樹的另一種形式，其特點為：

樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1。例如:548254821是平衡樹不是平衡樹結(jié)點的平衡因子：該結(jié)點的左子樹的深度減去

(-101)

右子樹的深度

構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。失去平衡后進行調(diào)整的規(guī)律可歸納為下列4種情況：

假設(shè)由于在二叉排序樹上插入結(jié)點而失去平衡的最小子樹根結(jié)點為A，沿插入路徑取直接下兩層的結(jié)點為B和C，如果這三個結(jié)點處于一條直線上，則采用單旋轉(zhuǎn)進行平衡化；如果這三個結(jié)點處于一條折線上，則采用雙旋轉(zhuǎn)進行平衡化。

調(diào)整方法：以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A向右旋轉(zhuǎn)成為B的右子樹，結(jié)點B代替原來A的位置，原來B的右子樹成為A的左子樹。

原因：在A

的左子樹根結(jié)點的左子樹上插入結(jié)點，A的平衡因子由1增至2，至使以A為根的子樹失去平衡。ABhChBRhAR插入結(jié)點（1）單向右旋平衡處理：(LLR)LLRABh+1ChBRhAR

調(diào)整方法：以結(jié)點B為旋轉(zhuǎn)軸，將結(jié)點A向左旋轉(zhuǎn)成為B的左子樹，結(jié)點B代替原來A的位置，原來B的左子樹成為A的右子樹。

原因：在A

的右子樹根結(jié)點的右子樹上插入結(jié)點，A的平衡因子由-1增至-2，至使以A為根的子樹失去平衡。ABhChBLhAL插入結(jié)點（2）單向左旋平衡處理：(RRL)RRLABh+1ChBLhAL

調(diào)整方法：先以C為旋轉(zhuǎn)軸，將結(jié)點B向左旋轉(zhuǎn)成為C的左子樹，結(jié)點C代替原來B的位置，原來C的左子樹成為B的右子樹。

原因：在A

的左子樹根結(jié)點的右子樹上插入結(jié)點，A的平衡因子由1增至2，至使以A為根的子樹失去平衡。（3）先左后右平衡處理：(LRLR)ABh-1CLh-1CRhAR插入結(jié)點ChBLBAhARhCLhBLCh-1CRBAhARhCLhBLCh-1CR

再以C為旋轉(zhuǎn)軸，將A向右旋轉(zhuǎn)成為C的右子樹，結(jié)點C代替原來A的位置，原來C的右子樹成為A的左子樹。LR

再以C為旋轉(zhuǎn)軸，將A向左旋轉(zhuǎn)成為C的左子樹，結(jié)點C代替原來A的位置，原來C的左子樹成為A的右子樹。

調(diào)整方法：先以C為旋轉(zhuǎn)軸，將結(jié)點B向右旋轉(zhuǎn)成為C的右子樹，結(jié)點C代替原來B的位置，原來C的右子樹成為B的左子樹。

原因：在A

的右子樹根結(jié)點的左子樹上插入結(jié)點，A的平衡因子由-1增至-2，至使以A為根的子樹失去平衡。（4）先右后左平衡處理：(RLRL)ABh-1CRh-1CLhAL插入結(jié)點ChBRBRAhALhCRhBCh-1CLBAhALhCRhBRCh-1CLRLABCABC例如:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)BCACBACBA426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9CAB在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)和log(n)

相當。

一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法

三、處理沖突的方法

四、哈希表的查找

五、哈希表的刪除操作9.3哈希表

以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系，一、哈希表是什么？

查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進行比較，

查找的效率取決于和給定值進行比較的關(guān)鍵字個數(shù)。

用這類方法表示的查找表，其平均查找長度都不為零。

不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進行比較的順序不同。

只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，

對于頻繁使用的查找表，希望ASL=0。

即：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。若以下標為000~999的順序表表示之。例如：為每年招收的1000名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為xx000~xx999(前兩位為年份)。則查找過程可以簡單進行：取給定值（學(xué)號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。但是，對于動態(tài)查找表而言，因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關(guān)系，以f(key)作為關(guān)鍵字為key的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。1)表長不確定；2)在設(shè)計查找表時，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。{Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對于如下9個關(guān)鍵字設(shè)

哈希函數(shù)f(key)=

(Ord(第一個字母)-Ord('A')+1)/2ChenZhaoQianSunLiWuHanYeDei問題:

若添加關(guān)鍵字Zhou,怎么辦？能否找到另一個哈希函數(shù)？1)哈希函數(shù)是一個映象，即：

將關(guān)鍵字的集合映射到某個地址集合上，

它的設(shè)置很靈活，只要這個地址集合的大小不超出允許范圍即可；從這個例子可見：2)由于哈希函數(shù)是一個壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，即：key1key2，而f(key1)=f(key2)。3)很難找到一個不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。

因此，在構(gòu)造這種特殊的“查找表”時，除了需要選擇一個“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”的方法。哈希表的定義：

根據(jù)設(shè)定的哈希函數(shù)H(key)

和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，如此構(gòu)造所得的查找表稱之為“哈希表”。二、構(gòu)造哈希函數(shù)的方法

對數(shù)字的關(guān)鍵字可有下列構(gòu)造方法：

若是非數(shù)字關(guān)鍵字，則需先對其進行數(shù)字化處理。1.

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key

或者

H(key)=akey+b1.

直接定址法此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小此方法僅適合于：

能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。2.

數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。

以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。3.平方取中法

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多。5.除留余數(shù)法

設(shè)定哈希函數(shù)為:H(key)=keyMODp其中，

p≤m(表長)并且

p

應(yīng)為不大于m的素數(shù)或是不含20以下的質(zhì)因子

給定一組關(guān)鍵字為：12,39,18,24,33,21，若取p=9,則他們對應(yīng)的哈希函數(shù)值將為：3,3,0,6,6,3例如：為什么要對p加限制？

可見，若p中含質(zhì)因子3，則所有含質(zhì)因子3的關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。6.隨機數(shù)法設(shè)定哈希函數(shù)為:H(key)=Random(key)其中，Random為偽隨機函數(shù)

通常，此方法用于對長度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。

實際造表時，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。三、處理沖突的方法

“處理沖突”的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。1.開放定址法2.鏈地址法

為產(chǎn)生沖突的地址H(key)求得一個地址序列：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+di

)MODm

i=1,2,…,s1.開放定址法對增量

di

有三種取法：1)線性探測再散列

di=ci

最簡單的情況c=12)平方探測再散列

di=12,-12,22,-22,…,3)隨機探測再散列

di

是一組偽隨機數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測)即：產(chǎn)生的Hi

均不相同，且所產(chǎn)生的

s(m-1)個Hi

值能覆蓋哈希表中所有地址。則要求：

注意：增量di

應(yīng)具有“完備性”※

隨機探測時的m

和di沒有公因子?！?/p>

平方探測時的表長

m

必為形如4j+3

的素數(shù)（如:7,11,19,23,…等）；例如:

關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長=11)1901231455681901231468若采用線性探測再散列處理沖突若采用二次探測再散列處理沖突11823655118236112136251H2(key)是另設(shè)定的一個哈希函數(shù)，它的函數(shù)值應(yīng)和m

互為素數(shù)。若m

為素數(shù)，則H2(key)

可以是1

至m-1

之間的任意數(shù)；

若m

為2的冪次，則H2(key)

應(yīng)是1

至m-1

之間的任意奇數(shù)。例如，當m=11時，可設(shè)H2(key)=(3key)MOD10+1190123145568118236211121213{19,01,23,14,55,68,11,82,36}將所有哈希地址相同的記錄都鏈接在同一鏈表中。

2.鏈地址法0123456140136198223116855ASL=(6×1+2×2+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為H(key)=keyMOD7

查找過程和造表過程一致。假設(shè)采用開放定址處理沖突，則查找過程為：

四、哈希表的查找

對于給定值K，計算哈希地址i=H(K)若r[i]=NULL

則查找不成功若

r[i].key=K

則查找成功否則“求下一地址Hi”，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)為止。inthashsize[]={997,...};typedefstruct{ElemType*elem;

intcount;//當前數(shù)據(jù)元素個數(shù)

intsizeindex;//hashsize[sizeindex]為當前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//---開放定址哈希表的存儲結(jié)構(gòu)---StatusSearchHash(HashTableH,KeyTypeK,

int&p,int&c){//在開放定址哈希表H中查找關(guān)鍵碼為K的記錄}//SearchHashp=Hash(K);//求得哈希地址while(H.elem[p].key!=NULLKEY&&

!EQ(K,H.elem[p].key)）

collision(p,++c);//求得下一探查地址pif(EQ(K,H.elem[p].key))returnSUCCESS;//查找成功，返回待查數(shù)據(jù)元素位置pelsereturnUNSUCCESS;//查找不成功StatusInsertHash(HashTable&H,Elemtypee){

}//InsertHashc=0;if(HashSearch(H,e.key,p,c)==SUCCESS)returnDUPLICATE;