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

第9章查找1.掌握順序查找、二分查找和分塊查找的方法。2.掌握二叉排序樹的相關(guān)運(yùn)算和查找過程。3.理解平衡二叉樹的建樹方法。4.掌握哈希表的建立方法和查找過程。5.掌握各種查找方法在等概率下的平均查找長度的計(jì)算方法。學(xué)習(xí)要點(diǎn)基本概念

查找表：是由同一類型的數(shù)據(jù)元素構(gòu)成的集合，由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)。

有關(guān)操作

查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；

在查找表中插入一個(gè)數(shù)據(jù)元素；

從查找表中刪去某個(gè)數(shù)據(jù)元素。查找表的分類靜態(tài)查找表：僅作查詢和檢索操作的查找表。動(dòng)態(tài)查找表：在查找過程中同時(shí)插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)數(shù)據(jù)元素。

關(guān)鍵字是數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”?；靖拍畈檎腋鶕?jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素。若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”?；靖拍顢?shù)據(jù)元素類型定義為：typedefstruct{KeyTypekey;//關(guān)鍵字域…//其他域}ElemType;基本概念9.1.1順序表的查找應(yīng)用范圍：以順序表或線性鏈表表示的靜態(tài)查找表，表內(nèi)元素之間無序。順序查找基本思想：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功；若直至第一個(gè)記錄，其關(guān)鍵字和給定值比較都不等，則查找不成功。順序存儲(chǔ)結(jié)構(gòu)的表示：

typedef

struct{

ElemType*elem;

intlength;}SSTable;9.1靜態(tài)查找表int

Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素

ST.elem[0].key=key;//哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;//查找不成功時(shí)i為0}//Search_Seq免去查找過程中每一步都要檢測整個(gè)表是否查找完畢順序查找算法int

Search_Seq(StableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素

for(i=0;i<ST.length;++i)

if(ST.elem[i].key==key)returni;return(0);//查找不成功時(shí)i為0}//Search_Seq順序查找算法8012n-3n-2n-1nST.elem

key例1：在下表中查找key=8的結(jié)點(diǎn)?！?00100713iiiiiii查找不成功，i=08012n-3n-2n-1nST.elem

key例2：在下表中查找key=8的結(jié)點(diǎn)?！?00100813iii查找成功，i=n-2

舉例說明1n查找成功情況下：設(shè)每個(gè)結(jié)點(diǎn)的查找概率相等ASL＝∑(n-i+1)＝(n+1)/2i=1n

和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值稱為查找成功時(shí)的平均查找長度。性能分析折半查找查找方式：每次將待查記錄所在區(qū)間縮小一半。適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表。算法實(shí)現(xiàn)：設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點(diǎn)，k為給定值。

初始時(shí)，令low=1，high=n，mid=(low+high)/2。

讓k與mid指向的記錄比較若k==ST.elem[mid].key，查找成功；

若k<ST.elem[mid].key，則high=mid-1；

若k>ST.elem[mid].key，則low=mid+1。重復(fù)上述操作，直至low>high時(shí)，查找失敗。9.1.2有序表的查找

舉例說明(1)low找key=215113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow找key=705113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhighlow5113219321437556664775880988109211midhigh

舉例說明(2)low5113219321437556664775880988109211midhighlow5113219321437556664775880988109211high

舉例說明(2)intSearch_bin(SStableST,KeyTypekey){//在有序表ST中折半查找關(guān)鍵字等于key的數(shù)據(jù)元素low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(EQ(ST.elem[mid].key,key)returnmid;elseif(LT(key,ST.elem[mid].key))high=mid-1;elselow=mid+1;}return0；}//Search_Bin折半查找算法判定樹：描述查找過程的二叉樹。有n個(gè)結(jié)點(diǎn)的判定樹的深度為log2n+1。

折半查找法在查找過程中進(jìn)行的比較次數(shù)最多不超過log2n+1。其ASL=log2(n+1)-1。

折半查找的優(yōu)點(diǎn)是比較的次數(shù)少，查找速度快，但前提是該表首先要進(jìn)行排序，而排序是一種很費(fèi)時(shí)運(yùn)算，并且折半查找只適用于順序存儲(chǔ)的有序表，不適用于鏈表存儲(chǔ)的有序表。5619800521886413753792折半查找性能分析5113219321437556664775880988109211索引順序查找(分塊查找)

查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找。適用條件：分塊有序表假設(shè)按元素關(guān)鍵字升序方式組織表中各塊，則要求第一塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第二塊中所有結(jié)點(diǎn)的關(guān)鍵字值；第二塊中任一結(jié)點(diǎn)的關(guān)鍵字值都小于第三塊中所有結(jié)點(diǎn)的關(guān)鍵字值；如此類推。然后選擇每塊中的最大(或最小)關(guān)鍵字值組成索引表。索引表中的結(jié)點(diǎn)個(gè)數(shù)等于線性表被分割的塊數(shù)。9.1.4索引順序表的查找1234567891011121314151617182212138920

334244382448

6058745786532248861713索引表查38最大關(guān)鍵字起始地址表及其索引表LLASLwbbs+=其中：Lb是查找索引表確定所在塊的平均查找長度；

Lw是在塊中查找元素的平均查找長度。若將表長n為的表平均分成b塊，每塊含s個(gè)記錄，并設(shè)表中每個(gè)記錄的查找概率相等，則：用順序查找確定所在塊用折半查找確定所在塊ASLbs=1)(21ssn++ASLbs=2)1(log2ssn++分塊查找性能分析9.2動(dòng)態(tài)查找表什么是二叉排序樹？或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：1.若左子樹不空，則左子樹上所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值；2.若右子樹不空，則右子樹上所有結(jié)點(diǎn)值均大于根結(jié)點(diǎn)值；3.根結(jié)點(diǎn)的左、右子樹也分別為二叉排序樹。45125333710024619078若二叉排序樹為空，則查找不成功；否則1.若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2.若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3.若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。具體實(shí)現(xiàn)如下：BiTree

SearchBST(BiTree

T,KeyTypekey){if((!T)||(EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key);elsereturnSearchBST(T->rchild,key);}二叉排序樹查找算法例如：在下圖中分別查找關(guān)鍵字值等于37，61和95過程。45125333710024619078從上述查找過程可見，在查找過程中，生成了一條查找路徑：1.從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)，表明查找成功。2.或者從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止，表明查找不成功。二叉排序樹查找過程基本思想：在每一步插入過程中，二叉排序樹中原有的結(jié)點(diǎn)位置均不動(dòng)，只是將待插入的結(jié)點(diǎn)作為一個(gè)葉結(jié)點(diǎn)插入到適當(dāng)?shù)奈恢?，使得樹中任何結(jié)點(diǎn)與其左、右子樹結(jié)點(diǎn)之間的關(guān)系仍然滿足二叉排序樹的性質(zhì)，向二叉樹T插入一個(gè)新結(jié)點(diǎn)s的過程為：若T為空的二叉樹，則將新結(jié)點(diǎn)作為根結(jié)點(diǎn)插入。若新結(jié)點(diǎn)s的值等于二叉排序樹的根結(jié)點(diǎn)，說明該結(jié)點(diǎn)已存在，不需要插入。若將新結(jié)點(diǎn)s的值小于二叉排序樹T的根結(jié)點(diǎn)，則將s插入到T的左子樹中去。若新結(jié)點(diǎn)s的值大于二叉排序樹T的根結(jié)點(diǎn)，則將s插入到T的右子樹中去。二叉排序樹的插入操作是一個(gè)遞歸過程。二叉排序樹插入算法思想

StatusSearchBST(BiTree

T,KeyType

key,BiTree

f,BiTree&p)//若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點(diǎn)，返回TRUE，否則p指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)并返回FALSE，f是指向T的雙親

{if(!T){p=f;returnFALSE;}elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);elsereturnSearchBST(T->rchild,key,T,p);}具體實(shí)現(xiàn)(1)StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p)){s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;elseif(LT(e.key,p->data.key))p->lchild=s;elsep->rchild=s;returnTRUE;}elsereturnFALSE;}具體實(shí)現(xiàn)(2)2712從空樹出發(fā)，經(jīng)過一系列的查找插入操作后，便可生成一棵二叉排序樹。例對于關(guān)鍵字序列{10，18，3，8，12，2，7}，構(gòu)造一棵BST。101838注意：對于同樣的數(shù)據(jù)，輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會(huì)建立起一棵單支樹，使得二叉排序樹的高度達(dá)到最大，這樣必然會(huì)降低查找性能。建立二叉排序樹中序遍歷二叉排序樹便可得到一個(gè)關(guān)鍵字的有序序列，也就是說，一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序序列。對下圖所示的二叉排序進(jìn)行中序遍歷，結(jié)果為(2，3，7，8，10，12，18)。每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉子結(jié)點(diǎn)，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針。這相當(dāng)于在一個(gè)有序列上插入一個(gè)記錄而又不需要移動(dòng)其他記錄。二叉排序樹既擁有折半查找的特性，又采用鏈?zhǔn)酱鎯?chǔ)。7212101838

結(jié)論和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性?？煞秩N情況討論：被刪除的結(jié)點(diǎn)是葉子；被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。二叉排序樹的刪除刪除葉子結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針置為空，再釋放它即可。如：刪除關(guān)鍵字值為7的結(jié)點(diǎn)。1018381227刪除葉子結(jié)點(diǎn)刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹，則使其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。如：(1)刪除關(guān)鍵字值為2的結(jié)點(diǎn)，它只有右子樹。(2)刪除關(guān)鍵字值為18的結(jié)點(diǎn)，它只有左子樹。1018581223刪除的結(jié)點(diǎn)只有左子樹或只有右子樹RQD中序遍歷：PL—D—R—Q

刪除后：PL—R—QPLRQPLRDQ中序遍歷：Q—R—PL—D

刪除后：Q—R—PLPLRQPLRQD中序遍歷：D—PR—R—Q

刪除后：PR—R—QPRRQPRRDQ中序遍歷：Q—R—D—PR

刪除后：Q—R—PRPRRQPR

具體解釋刪除葉結(jié)點(diǎn)和刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹這兩種操作，可通過下面語句實(shí)現(xiàn)。if(!p->rchild){q=p;p=p->lchild;free(q);}elseif(!p->lchild){q=p;p=p->rchild;free(q);}1018581223p

具體實(shí)現(xiàn)方法一：首先將結(jié)點(diǎn)D的右子樹鏈接到其中序前驅(qū)結(jié)點(diǎn)(結(jié)點(diǎn)D的左子樹中“最右下”且右指針域?yàn)榭盏慕Y(jié)點(diǎn))的右指針域，然后把結(jié)點(diǎn)R(結(jié)點(diǎn)D的雙親結(jié)點(diǎn))指向結(jié)點(diǎn)D的指針鏈接到結(jié)點(diǎn)D的左子樹上即可。RDQRRDRCCLQLGLGpfRQRRDRCCLQLGLGf該二叉排序樹的中序遍歷結(jié)果為：CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結(jié)點(diǎn)既有左子樹又有右子樹方法二：把結(jié)點(diǎn)D的中序前驅(qū)結(jié)點(diǎn)G的值賦給結(jié)點(diǎn)D，因?yàn)樵撝行蚯膀?qū)結(jié)點(diǎn)G只有左子樹GL，然后將結(jié)點(diǎn)G的雙親結(jié)點(diǎn)的右指針鏈接到GL即可。RDQRRDRCCLQLGLGpfRGQRRDRCCLQLGLpf該二叉排序樹的中序遍歷結(jié)果為：CL→C→QL→Q→GL→G→D→DR→R→RR刪除的結(jié)點(diǎn)既有左子樹又有右子樹刪除的結(jié)點(diǎn)既有左子樹又有右子樹，可通過下面語句實(shí)現(xiàn)。q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;free(s);RDQRRDRCCLQLGLGpf

具體實(shí)現(xiàn)

BST上查找過程，是從根結(jié)點(diǎn)到所找到結(jié)點(diǎn)的一條路徑。與給定值比較次數(shù)等于該路徑長度+1，最大次數(shù)不超過樹的深度。但含有n個(gè)結(jié)點(diǎn)的BST卻不唯一。因此，含有n個(gè)結(jié)點(diǎn)的BST的ASL和樹的形態(tài)有關(guān)。最差情況是退化為單支樹，ASL=(n+1)/2(同順序查找)。最好情況與折半查找相同，與log2n成正比。12452453123793(45,24,53,12,37,93)2437455393(12,24,37,45,53,93)ASL(a)=(1+2+2+3+3+3)/6=14/6ASL(b)=(1+2+3+4+5+6)/6=21/6

查找分析平衡二叉樹是二叉排序樹的另一種形式，其特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹高度之差的絕對值不大于1。若平衡因子定義為結(jié)點(diǎn)左子樹的高度減去右子樹的高度，則平衡二叉樹所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1的二叉排序樹。例如：20210平衡樹非平衡樹-2-20-100101平衡二叉樹

采取的方法是在向平衡二叉樹插入結(jié)點(diǎn)時(shí)進(jìn)行平衡化旋轉(zhuǎn)?；舅枷霝椋杭俣ㄏ蚱胶鈽洳迦胍粋€(gè)結(jié)點(diǎn)后破壞了其平衡性，則首先要找出唯一一棵最小不平衡子樹，然后再調(diào)整該子樹中有關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，使之成為一棵新的平衡二叉樹。最小不平衡子樹被調(diào)整為平衡子樹后，整個(gè)二叉排序樹又成為一棵平衡樹。

最小不平衡子樹是指離插入結(jié)點(diǎn)最近，且平衡因子絕對值大于1的祖先結(jié)點(diǎn)作為根的子樹。027511018410-110127511018410-211160構(gòu)造平衡二叉樹的方法(1)單向右旋平衡處理(LL型)：新插入結(jié)點(diǎn)在A的左子樹根結(jié)點(diǎn)的左子樹上。A的平衡因子由1增至2，導(dǎo)致失衡。調(diào)整規(guī)則：將結(jié)點(diǎn)A的左孩子B向上旋轉(zhuǎn)成為新二叉樹的根，將結(jié)點(diǎn)A及其右子樹向右下旋轉(zhuǎn)成為結(jié)點(diǎn)B的右子樹，而結(jié)點(diǎn)B原來的右子樹BR則成為結(jié)點(diǎn)A的左子樹。(進(jìn)行一次順時(shí)針旋轉(zhuǎn))調(diào)整方法分四種情況h+1h-1ABARBRBLh-10+2+1hh-1ABARBRBL00具體實(shí)現(xiàn)：lc=p->lchild;p->lchild=lc->rchild;lc->rchild=p;p=lc;p(2)單向左旋平衡處理(RR型)：新插入結(jié)點(diǎn)在A的右子樹根結(jié)點(diǎn)的右子樹上。A的平衡因子由-1增至-2，導(dǎo)致失衡。調(diào)整規(guī)則：將結(jié)點(diǎn)A的右孩子B向上旋轉(zhuǎn)成為新二叉樹的根，將結(jié)點(diǎn)A及其左子樹向左下旋轉(zhuǎn)成為結(jié)點(diǎn)B的左子樹，而結(jié)點(diǎn)B原來的左子樹BL則成為結(jié)點(diǎn)A的右子樹。(進(jìn)行一次逆時(shí)針旋轉(zhuǎn))調(diào)整方法分四種情況-2hh-1h-1BABRBLAL-10-1h0BABRBLALh-10具體實(shí)現(xiàn)：rc=p->rchild;p->rchild=rc->lchild;rc->rchild=p;p=rc;p(3)先左后右平衡處理(LR型)：新插入結(jié)點(diǎn)在A的左子樹根結(jié)點(diǎn)的右子樹上。A的平衡因子由1增至2，導(dǎo)致失衡。調(diào)整規(guī)則：將A的左孩子的右子樹的根結(jié)點(diǎn)C旋轉(zhuǎn)到結(jié)點(diǎn)A的位置成為新二叉樹的根，將結(jié)點(diǎn)B及其左子樹向左下旋轉(zhuǎn)成為C的左子樹，而C結(jié)點(diǎn)原來的左子樹CL則作為結(jié)點(diǎn)B的右子樹；將結(jié)點(diǎn)A及其右子樹向右下旋轉(zhuǎn)成為結(jié)點(diǎn)C的右子樹，C結(jié)點(diǎn)原來的右子樹CR作為結(jié)點(diǎn)A的左子樹。(需進(jìn)行兩次旋轉(zhuǎn)，先逆時(shí)針后順時(shí)針)調(diào)整方法分四種情況+2-1+1h-1ABARCLBLh-10CCRh-20h-1+1+2h-1CBARCLBLh-10CRh-2A+2h-10CBARCLBL0CRA-1將A的左孩子的右子樹的根結(jié)點(diǎn)C旋轉(zhuǎn)到結(jié)點(diǎn)A的位置成為新二叉樹的根，將結(jié)點(diǎn)B及其左子樹向左下旋轉(zhuǎn)成為C的左子樹，而C結(jié)點(diǎn)原來的左子樹CL則作為結(jié)點(diǎn)B的右子樹。(第一次逆時(shí)針旋轉(zhuǎn))將結(jié)點(diǎn)A及其右子樹向右下旋轉(zhuǎn)成為結(jié)點(diǎn)C的右子樹，C結(jié)點(diǎn)原來的右子樹CR作為結(jié)點(diǎn)A的左子樹。(第二次順時(shí)針旋轉(zhuǎn))調(diào)整過程調(diào)整方法分四種情況(4)先右后左平衡處理(RL型)：新插入結(jié)點(diǎn)在A的右子樹根結(jié)點(diǎn)的左子樹上。A的平衡因子由-1增至-2，導(dǎo)致失衡。調(diào)整規(guī)則：它與LR旋轉(zhuǎn)情況正好對稱的。調(diào)整實(shí)例假設(shè)一組數(shù)據(jù)對象為(40，28，16，56，50，32，30，63)，按次序插入每個(gè)對象生成一棵平衡二叉樹，根據(jù)插入過程指出每一步的調(diào)整類型：“單向左旋轉(zhuǎn)”、“單向右旋轉(zhuǎn)”、“先左后右旋轉(zhuǎn)”、“先右后左旋轉(zhuǎn)”、“無”。解釋：左子樹的左子樹上插入→“單向右旋轉(zhuǎn)”右子樹的右子樹上插入→“單向左旋轉(zhuǎn)”左子樹的右子樹上插入→“先左后右旋轉(zhuǎn)”右子樹的左子樹上插入→“先右后左旋轉(zhuǎn)”9.3哈希表9.3.1什么是哈希表？哈希查找：又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程。其基本思想是在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建立一個(gè)確定的對應(yīng)關(guān)系。這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一種對應(yīng)關(guān)系。按這種思想建立的表稱為哈希表。例假設(shè)有一批關(guān)鍵字序列18，75，60，43，54，90，46，給定散列函數(shù)H(k)=k%13，存貯區(qū)的內(nèi)存地址從0到15，則可以得到每個(gè)關(guān)鍵字的散列地址為：

H(18)=18%13=5，H(75)=75%13=10，H(60)=60%13=8H(43)=43%13=4，H(54)=54%13=2，H(90)=90%13=12H(46)=46%13=7于是，根據(jù)散列地址，可以將上述7個(gè)關(guān)鍵字序列存貯到一個(gè)一維數(shù)組HT(散列表)中，具體表示為：90756046184354151413121110987654321

0HT其中HT就是散列存貯的表，稱為散列表。從散列表中查找一個(gè)元素相當(dāng)方便，例如，查找75，只需計(jì)算出H(75)=75%13=10，則可以在HT[10]中找到75。舉例說明上面討論的散列表是一種理想的情形，即每一個(gè)關(guān)鍵字對應(yīng)一個(gè)唯一的地址。但是有可能出現(xiàn)這樣的情形，兩個(gè)不同的關(guān)鍵字有可能對應(yīng)同一個(gè)內(nèi)存地址。這樣，將導(dǎo)致后放的關(guān)鍵字無法存貯，我們把這種現(xiàn)象叫做沖突(collision)。即key1≠key2，而f(key1)=f(key2)。在散列存貯中，沖突是很難避免的，除非構(gòu)造出的散列函數(shù)為線性函數(shù)。散列函數(shù)選得比較差，則發(fā)生沖突的可能性越大。我們把相互發(fā)生沖突的關(guān)鍵字互稱為“同義詞”。

沖突問題1.直接定址法

可表示為H(key)=a*key+b，其中a、b均為常數(shù)。這種方法計(jì)算特別簡單，并且不會(huì)發(fā)生沖突，但當(dāng)關(guān)鍵字分布不連續(xù)時(shí)，會(huì)出現(xiàn)很多空閑單元，將造成大量存貯單元的浪費(fèi)。實(shí)際中使用此方法較少。例關(guān)鍵字集合為{100，300，500，700，800，900}，選取哈希函數(shù)為H(key)=key/100，則在哈希表中存放如下：

9.3.2哈希函數(shù)的構(gòu)造方法01001230034500567007800890092.數(shù)字選擇法對關(guān)鍵字序列進(jìn)行分析，取那些位上數(shù)字變化多的、頻率大的作為散列函數(shù)地址。例如，對如下的關(guān)鍵字序列：

43010

4681015355

43010

1701128352

43010

3720818350

430102690605351

．．．．．．通過對上述關(guān)鍵字序列分析，發(fā)現(xiàn)前5位相同，第6、8、10位上的數(shù)字變化多些，若規(guī)定地址取3位，則散列函數(shù)可取它的第6、8、10位。于是有：

H(430104681015355)＝480H(430101701128352)＝101H(430103620805351)＝328H(430102690605351)＝2969.3.2哈希函數(shù)的構(gòu)造方法3.平方取中法取關(guān)鍵字平方后的中間幾位為散列函數(shù)地址。在選定散列函數(shù)時(shí)不一定知道關(guān)鍵字的全部信息，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，因此，可以使用隨機(jī)分布的關(guān)鍵字得到函數(shù)地址。如圖，隨機(jī)給出一些關(guān)鍵字，并取平方后的第2到4位為函數(shù)地址。9.3.2哈希函數(shù)的構(gòu)造方法關(guān)鍵字0100

(關(guān)鍵字)20010000函數(shù)地址010110012001210000144000021044011602061137040043105413703104.折疊法將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分的位數(shù)可以不同)，然后取這幾部分的疊加和(舍去進(jìn)位)作為散列函數(shù)地址，稱為折疊法。例如：假設(shè)關(guān)鍵字為某人身份證號(hào)碼430104681015355，則可以用4位為一組進(jìn)行疊加，即有5355+8101+1046+430=14932，舍去高位，則有H(430104681015355)＝4932為該身份證關(guān)鍵字的散列函數(shù)地址。9.3.2哈希函數(shù)的構(gòu)造方法5.除留余數(shù)法該方法是用關(guān)鍵字序列中的關(guān)鍵字k除以p(p是小于等于散列表長度m)所得余數(shù)作為散列函數(shù)的地址，即有H(k)＝k％p。

除留余數(shù)法計(jì)算簡單，適用范圍廣，是一種最常使用的方法。這種方法的關(guān)鍵是選取較理想的p值，使得每一個(gè)關(guān)鍵字通過該函數(shù)轉(zhuǎn)換后映射到散列空間上任一地址的概率都相等，從而盡可能減少發(fā)生沖突的可能性。

一般情形下，設(shè)散列表中允許的地址數(shù)為m，取一個(gè)不大于m，但最接近于或等于m的質(zhì)數(shù)p。9.3.2哈希函數(shù)的構(gòu)造方法由于散列存貯中選取的散列函數(shù)不是線性函數(shù)，故不可避免地會(huì)產(chǎn)生沖突，下面給出常見的解決沖突方法。1．開放定址法開放定址法就是從發(fā)生沖突的那個(gè)單元開始，按照一定的次序，從散列表中找出一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入關(guān)鍵字存儲(chǔ)到該單元中，從而解決沖突的發(fā)生。9.3.3解決沖突的方法假設(shè)散列表的地址為0∽m-1，則散列表的長度為m。若一個(gè)關(guān)鍵字在地址d處發(fā)生沖突，則依次探查d+1，d+2，…，m-1(當(dāng)達(dá)到表尾m-1時(shí)，又從0，1，2，….開始探查)等地址，直到找到一個(gè)空閑位置來裝沖突處的關(guān)鍵字，將這一種方法稱為線性探查法。探查下一位置的公式為di=(di-1+1)%m(1≤i≤m-1)，最后將沖突位置的關(guān)鍵字存入di地址中。線性探查法例給定序列為19，14，23，1，68，20，84，27，55，11，10，79，散到函數(shù)H(k)=k%13，散列表空間地址為0∽12，用線性探查法建立散列存貯結(jié)構(gòu)。得到的散列表如下圖所示。

H(19)=19%13=6;H(14)=14%13=1;H(23)=23%13=10;H(1)=1%13=1;H(68)=68%13=3;H(20)=20%13=7;H(84)=84%13=6;H(27)=27%13=1;H(55)=55%13=3;H(11)=11%13=11;H(10)=10%13=10;H(79)=79%13=1;線性探查法012345678910111219142316820842755111079方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)生沖突時(shí)，計(jì)算下一個(gè)哈希地址，直到?jīng)_突不再發(fā)生。即：Hi=Rhi(key)i=1,2,……,k其中：Rhi——不同的哈希函數(shù)