算法與數(shù)據(jù)結構第7章查找

03四月2023第1頁第七章查找03四月2023第2頁【學習目的要求】:順序表、有序表、索引順序表的定義、查找及算法。散列表的定義及構造法。散列表沖突的處理方法。03四月2023第3頁何謂查找表？

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關系，因此查找表是一種應用靈便的結構。03四月2023第4頁對查找表經(jīng)常進行的操作:1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。03四月2023第5頁僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表查找表可分為兩類:03四月2023第6頁是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。關鍵字

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

若此關鍵字能識別若干記錄，則稱之謂“次關鍵字”。03四月2023第7頁

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

查找

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結果給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”。查找結果給出“空記錄”或“空指針”。03四月2023第8頁

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。

為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關系，換句話說，

用另外一種結構來表示查找表。如何進行查找？查找的方法取決于查找表的結構。03四月2023第9頁查找方法評價通常以“給定值與數(shù)據(jù)元素的關鍵碼值比較”作為基本操作，用“關鍵碼值的比較次數(shù)”來衡量查找算法的時間性能，“關鍵碼值的比較次數(shù)”稱為查找長度。平均查找長度ASL(AverageSearchLength)：為確定記錄在表中的位置，所需進行的關鍵碼比較次數(shù)的期望值03四月2023第10頁平均查找長度ASL03四月2023第11頁7.2

靜態(tài)查找表7.3

動態(tài)查找樹表7.4

哈希表03四月2023第12頁7.2

靜態(tài)查找表03四月2023第13頁

以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表03四月2023第14頁數(shù)據(jù)元素類型的定義為:typedefstruct{

keytypekey;//關鍵字域

……

//其它屬性域}

sqlist;SqlistR[n+1];03四月2023第15頁順序查找【基本思想】:

用給定的值與表中各個記錄的關鍵字值逐個進行比較，若找到相等的則查找成功，否則查找不成功，給出找不到的提示信息。03四月2023第16頁順序檢索舉例intseqsearch(sqlistR[],keytypek){inti=n;R[0].key=k;/*設置R[0]為監(jiān)視哨*/while(R[i].key!=k)i--;returni;/*返回檢索結果i*/}03四月2023第17頁RiRi60ik=64k=60i6403四月2023第18頁i

01234567891011513192137566475808892找6464監(jiān)視哨iiii本例比較次數(shù)：5【順序表的查找過程】：假設給定值k=64,要求R[i]=k,問:i=?從最后一個元素開始按照順序依次往下查找比較次數(shù)：查找第n個元素：1 (最好情況)查找第n-1個元素：2 ……….查找第1個元素：n (最懷情況)查找第i個元素：n+1-i查找失?。簄+103四月2023第19頁在等概率查找的情況下，

順序表查找的平均查找長度為：對順序表而言，Ci=n-i+1ASL=nP1+(n-1)P2+…+2Pn-1+Pn03四月2023第20頁

若查找概率無法事先測定，則查找過程采取的改進辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss

在

Pn≥Pn-1≥···≥P2≥P1時取極小值03四月2023第21頁優(yōu)點：算法簡單且適用面廣。它對表的結構無任何要求，無論記錄是否按關鍵字有序均可應用，而且上述所有討論對線性鏈表也同樣適用。

缺點:平均查找長度較大，特別是當n很大時，查找效率低。

03四月2023第22頁二、有序查找表

若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。03四月2023第23頁折半查找要求：查找表必須為有序表查找過程：先確定待查找記錄的范圍

然后逐步縮小范圍

直到：查找成功或不成功03四月2023第24頁Rn例如:key=64

的查找過程如下：lowhighmidlow

mid

high

midlow

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

指示查找區(qū)間的上界mid=(low+high)/203四月2023第25頁intbinarysearch(sglistR[],keytypek){intlow,mid,high;low=1;high=n;while(low<=high){mid=(low+high)/2;if(k==R[mid].key)returnmid;elseif(k<R[mid].key)high=mid-1;elselow=mid+1;}return0;}03四月2023第26頁折半查找遞歸算法intSearch(sqlistR[],keytypek,intlow,inthigh){if(low>high)return0;mid=(low+high)/2;if(key==R[mid].key)returnmid;∥找到待查元素elseif(key>R[mid].key)∥繼續(xù)在后半?yún)^(qū)間查找

returnSearch(R,key,mid+1,high);

else∥繼續(xù)在前半?yún)^(qū)間查找

returnSearch(R,key,low,mid-1);}

03四月2023第27頁midlowhigh1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid

查找的數(shù)據(jù)在表中：找到03四月2023第28頁1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid

查找的數(shù)據(jù)不在表中：03四月2023第29頁1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighlow>high查找失敗03四月2023第30頁1185210741936判定樹：1234567891011513192137566475808892

二分查找過程可用二叉樹來描述,我們把當前查找區(qū)間的中間位置上的記錄作為根,左子表和右子表中的記錄分別作為根的左子樹和右子樹,由此得到的二叉樹,稱為描述二分查找的判定樹或比較樹。03四月2023第31頁先看一個具體的情況，假設：n=11分析折半查找的平均查找長度6391425781011判定樹1223333444403四月2023第32頁假設n=2h-1并且查找概率相等則

在n>50時，可得近似結果

一般情況下，表長為n的折半查找的判定樹的深度和含有n個結點的完全二叉樹的深度相同。03四月2023第33頁

例對于給定11個數(shù)據(jù)元素的有序表{2,3,10,15,20,25,28,29,30,35,40},采用二分查找,試問：(1)若查找給定值為20的元素,將依次與表中哪些元素比較？(2)若查找給定值為26的元素,將依次與哪些元素比較？(3)假設查找表中每個元素的概率相同,求查找成功時的平均查找長度和查找不成功時的平均查找長度。03四月2023第34頁二分查找判定樹

(2)若查找給定值為26的元素,依次與25,30,28元素比較,共比較3次。(3)在查找成功時,會找到圖中某個圓形結點,則成功時的平均查找長度：

(1)若查找給定值為20的元素,依次與表中25,10,15,20元素比較,共比較4次。

在查找不成功時,會找到圖中某個方形結點,則不成功時的平均查找長度：03四月2023第35頁分塊查找又稱索引順序查找，它是順序查找方法的一種改進方法，是介于順序查找和二分法查找之間的一種折中查找方法。它的基本思想是把線性表分成若干塊，在每一塊中數(shù)據(jù)元素的存放次序是任意的，但是塊與塊之間必須有序，即前一塊中的最大關鍵字必須小于后一塊中的最小關鍵字。另外還要建立一個索引表，把每塊中最大的關鍵字值按關鍵字值大小存入索引表，使索引表保持為有序表。分塊檢索03四月2023第36頁索引表A的每個元素包含兩個字段，一個是該塊的最大關鍵字值，另一個是指向子表的指針。03四月2023第37頁

查找步驟：首先用給定值在索引表中查找，確定滿足條件的數(shù)據(jù)元素應存放在哪一塊中，對索引表查找的方法既可以采用二分法查找，也可以采用順序查找，然后再到相應的塊中進行順序查找，便可以得到查找的結果。【分塊查找算法】03四月2023第38頁例如，給定關鍵字序列如下：{22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53},假設B=3，即將該序列分成3個子表（如何劃分此處不考慮），每個子表有6個元素，則得到的主表和索引表如圖：22121389203342443824486058744986532248861713以每塊中最大關鍵字作為該塊所有元素的索引03四月2023第39頁12345678910111213141516171822121389203342443824486058745786532248861713索引表查3803四月2023第40頁索引順序查找的平均查找長度=

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

+查找“順序表”的平均查找長度【分析分塊查找的平均查找長度】當時，ASL取最小，即所以，ASL=(n/s+s)/2+1

其中，n是線性表中數(shù)據(jù)元素個數(shù)，s是每塊中的元素個數(shù)03四月2023第41頁【三種查找方法比較】順序查找折半查找分塊查找平均查找長度最大等概率查找最小次小表的結構有序表、無序表均可僅適用于有序表表中元素逐段有序表的存儲結構順序、鏈式結構均可僅適用于順序存儲順序、鏈式均可，索引表順序存儲03四月2023第42頁7.3

動態(tài)查找樹表1二叉檢索樹定義：二叉檢索樹也叫二叉排序樹：或是一棵空樹，或是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值它的左、右子樹也分別為二叉排序樹1027481812310594818123二叉排序樹特點：中序遍歷，得到一個按關鍵碼遞增有序的序列。二叉排序樹的檢索過程在二叉檢索樹，則檢索關鍵字值等于給定值k的記錄的過程為：⑴

若二叉檢索樹為空，檢索失敗，返回特定值NULL；⑵

若二叉檢索樹非空，用給定值k與根結點的關鍵字值比較：

①

相等時，檢索成功，返回指向當前根結點的指針；

②k小時，繼續(xù)在根的左子樹中檢索，即轉⑴；

③k大時，繼續(xù)在根的右子樹中檢索，即轉⑴。10273818123二叉排序樹的查找查7pppp查15二叉檢索樹的二叉鏈表類型

設二叉排序樹以二叉鏈表作為存儲結構：typedefstructnode{keytypekey;/*關鍵字域*/elemtypeother;/*其它數(shù)據(jù)域*/structnode*lchild,*rchild;/*左右孩子指針域*/}bstnode;/*定義結點類型bstnode*/typedefbstnode*bstlist;/*定義二叉檢索樹表類型bstlist*/03四月2023二叉檢索樹的檢索算法描述

二叉檢索樹的檢索算法可描述如下：

bstlistbstsearch(bstlistt,keytypek){bstlistp;p=t;if((p==NULL)||(p->key==k))returnp;elseif(p->key<k)returnbstsearch(p->rchild,k);elsereturnbstsearch(p->lchild,k);}二叉排序樹的插入插入：若二叉排序樹為空，則插入結點應為新的根結點；否則，繼續(xù)在其左、右子樹上查找，直至某個結點的左子樹或右子樹為空為止，則插入結點應為該結點的左孩子或右孩子10273818123查15pppp==NULL03四月2023二叉排序樹的構造過程和插入操作

p=t;while(p!=NULL){q=p;if(p->key==k)returnt;elseif(p->key<k)p=p->rchild;elsep=p->lchild;}

插入算法的形式化描述如下：bstlistinsertbst(bstlistt,keytypek){bstlists,p,q;if(t==NULL){p=(bstlist)malloc(sigeof(bstnode));p->key=k;p->lchild=NULL;p->rchild=NULL;p->other=data;returnp;}03四月2023二叉排序樹的構造過程和插入操作

p=(bstlist)malloc(sizeof(bstnode));

p->key=k;p->lchild=NULL;p->rchild=NULL;p->other=data;if(k>q->key)q->rchild=p;elseq->lchild=p;returnt;}二叉排序樹構造：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹例{10，18，3，8，12，2，7，4}1010181018310183810183812101838122101838122710183812274ASL=?二叉排序樹的刪除要刪除二叉排序樹中的p結點，分三種情況：p為葉子結點，p只有左子樹或右子樹p只有左子樹，p只有右子樹，p左、右子樹均非空5845439832405570639010576210097中序遍歷：81012中序遍歷：1012(1)只需修改p雙親f的指針f->lchild=NULL

1012f中序遍歷：81012中序遍歷：810(2)10812pf10812fp108ff->rchild=NULL中序遍歷：PL

8

10

1210PL12中序遍歷：PL

10

12(3)中序遍歷：8

10PL

12108PL中序遍歷：8

10PL(4)用p的左孩子代替p108PL12fp108PL12fpf->lchild=p->lchild

f->rchild=p->lchild

中序遍歷：5PR

10

1210PR12中序遍歷：PR

10

12(5)中序遍歷：5

10

12PR105PR中序遍歷：5

10PR(6)用p的右孩子代替pf->lchild=p->rchildf->rchild=p->rchild105PR12fp105PR12fp方法一：找出待刪除結點p的中序前趨結點q，把q結點和p結點進行交換，即：

p->key=q->key;p->other=q->other;然后刪除其中序前趨結點q。5845439832405570639010576210097方法二：找出待刪除結點p的中序后繼結點q，把q結點和p結點進行交換：

p->key=q->key;p->other=q->other;然后刪除其中序后繼結點q。。5845439832405570639010576210097方法三：a)p為其雙親f的左孩子，令p的左孩子PL作為f的左孩子，令p的右子樹PR為p直接前驅的右子樹b)p為其雙親f的右孩子，令p的左孩子PL作為f的右孩子，令p的右子樹PR為p直接前驅的右子樹584543983240557063901057621009758454398324070639010576210097

方法四：a)p為其雙親f的左孩子，令p的右孩子PR作為f的左孩子，令p的左子樹PL為p直接后繼的左子樹b)p為其雙親f的右孩子，令p的右孩子PR作為f的右孩子，令p的左子樹PL為p直接后繼的左子樹584543983240557063901057621009758454398324070639010576210097例805012060110150557053刪除508060120110150557053刪除60805512011015053701042581375刪除1084257135刪除78425513

方法一和方法三中p的中序前趨q（即左子樹中的最右下結點）可以如下確定：

q=p->lchild;while(q->rchild!=NULL)q=q->rchild;而方法二和方法四中p的中序后繼q（即右子樹中的最左下結點）的確定方法為：

q=p->rchild;while(q->lchild!=NULL)q=q->lchild;二叉檢索樹的刪除算法描述下面我們給出采用方法四刪除雙枝結點時的二叉檢索樹的刪除算法描述如下：

bstlistdeletebst(bstlistt,keytypek){bstlistp,q,r,f;p=t;f=NULL;while((p!=NULL)&&(k!=p->key)){f=p;if(k<p->key)p=p->lchild;elsep=p->rchild;}二叉檢索樹的刪除算法描述

if(p==NULL)break;/*檢索失敗時不用刪除*/if((p->lchild==NULL)||(p->rchild==NULL))q=p;/*待刪除的*p為葉子結點或單枝結點時*/else{q=p->rchild;while(q->lchild!=NULL)q=q->lchild;}if(p->lchild!=NULL)r=p->lchild;elser=p->rchild;二叉檢索樹的刪除算法描述if(p!=q)q->lchild=p->lchild;if(f->lchild==p)f->lchild=r;elsef->rchild=r;returnt;/*返回刪除操作后的二叉檢索樹*/}4.二叉檢索樹的檢索性能分析在二叉檢索樹上檢索關鍵字值等于給定值k的記錄，正好是走了一條從根結點到關鍵字值為k的結點的路徑，和給定值k的比較次數(shù)為結點所在層次數(shù)，其比較次數(shù)不超過樹的深度。{45，53，24，100，37，12}{12，24，37，45，53，100}ASL=?ASL=?二叉檢索樹的檢索性能分析

含有n個結點的二叉檢索樹的平均檢索長度和二叉檢索樹的形態(tài)有關，當先后插入的關鍵字按值有序時，構造的二叉檢索樹蛻變?yōu)閱沃?；樹的深度為n，平均檢索長度為(n+1)/2（和順序檢索相同），這是最差的情況。最好的情況是二叉檢索樹的形態(tài)和二分法檢索過程得到的樹相同，樹的高度和完全二叉樹的高度相同，其平均檢索長度為。為了保證樹型查找有較高的查找速度，我們希望該二叉樹接近滿二叉樹，也就是希望二叉樹的每一個結點的左、右子樹高度盡量接近平衡，即使按任意次序不斷地插入結點，也不要使此樹成為單支樹。平衡樹(Balancedtree)也稱為AVL樹，是由阿德爾森—維爾斯基和蘭迪斯(Adelson-velskiiandlandis)于1962年首先提出的。這是一種附加了一定限制條件的二叉樹。我們定義二叉樹中每一結點的左子樹高度減右子樹高度為該結點的平衡因子（Balancefactor），所謂平衡樹，是指一個二叉樹其任一結點的平衡因子值只能是+1，0或-1，即任一結點的左、右子樹高度之差不超過1。

假設給平衡樹某個結點的左子樹插入一個新結點，且此新結點使左子樹的高度加1，我們可能會遇到以下三種情況：(1)如果原來其左子樹高度hl與右子樹高度hr相等，即原來此結點的平衡因子等于0,插入新結點后將使平衡因子變成+1，但仍符合平衡樹的條件，不必對其加以調整；⑵如果原來hl>hr，即原來此結點的平衡因子等于+1,插入新結點后將使平衡因子變成+2，破壞了平衡樹的限制條件，需對其加以調整；⑶如果原來hl<hr，即原來此結點的平衡因子等于-1，插入新結點后將使平衡因子變成0，平衡更加改善，不必加以調整。如果給平衡樹某結點的右子樹插入一個結點，且設此新結點使右子樹的高度增加1，則也會遇到與之相對應的三種情況。LL型右單旋A+10BBLBRARhhhA+2+1BBLBRARhhhBABLAL（BR）ARhhh+1RR型A-10BBLBRALA-2-1BBLBRARBABRALBL左單旋LR型1A+10BBLCRARCCLhh-1h-1hA+2-1BBLCRARCCLhhh-1hC22BBLCRARACL0hhh-1hC0-1BBLCRARACL0hhhh-1LR型2A+10BBLCRARCCLA+2-1BBLCRARCCLC00BBLCRARACL1RL型1A-2AL+1BBRCRCCLA-10BBRALCRCCL0C-1AALCRBRBCL0RL型2A-2AL+1BBRCRCCLA-10BBRALCRCCLCAALCRBRBCL構造平衡二叉檢索樹舉例

例如，對于一組記錄其關鍵字序列為（18，5，10，15，12，11，20），要建立一棵平衡的二叉檢索樹，其構造過程如下圖所示：

03四月2023第79頁

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

三、處理沖突的方法

四、哈希表的查找7.4

哈希表03四月2023第80頁

前面討論的表示查找表的各種結構的共同特點：記錄在表中的位置和它的關鍵字之間不存在一個確定的關系，一、哈希表是什么？

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

查找的效率取決于和給定值進行比較的關鍵字個數(shù)。03四月2023第81頁

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

不同的表示方法，其差別僅在于：關鍵字和給定值進行比較的順序不同。03四月2023第82頁

只有一個辦法：預先知道所查關鍵字在表中的位置

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

即，要求：記錄在表中位置和其關鍵字之間存在一種確定的關系。03四月2023第83頁因此在一般情況下，需在關鍵字與記錄在表中的存儲位置之間建立一個函數(shù)關系，以f(key)作為關鍵字為key的記錄在表中的位置，通常稱這個函數(shù)f(key)為哈希函數(shù)。03四月2023第84頁{Zhao,Qian,

Sun,Li,Wu,Chen,Han,Ye,Dei}

例如：對于如下9個關鍵字設

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

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

若添加關鍵字Zhou,怎么辦？能否找到另一個哈希函數(shù)？

012345678910111213

03四月2023第85頁1)哈希函數(shù)是一個映象，即：

將關鍵字的集合映射到某個地址集合上，

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

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

哈希表的定義：

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

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

對數(shù)字的關鍵字可有下列構造方法：

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

直接定址法3.平方取中法5.除留余數(shù)法4.折疊法6.隨機數(shù)法2.數(shù)字分析法03四月2023第89頁哈希函數(shù)為關鍵字的線性函數(shù)

H(key)=key

或者

H(key)=akey+b1.

直接定址法03四月2023第90頁地址01…51年份19491950…2000人數(shù)…………關鍵字是年份，散列函數(shù)取關鍵字的線性函數(shù)：H(key)=key+(-1949)

例如：有一個解放后出生人口調查表，每個記錄包含年份、人數(shù)等數(shù)據(jù)項【注意】由于直接定址法所得地址集合和關鍵字大小相同，因此，關鍵字不會產(chǎn)生沖突，但實際應用中能夠使用這種散列函數(shù)的情況很少。03四月2023第91頁此方法僅適合于：

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

數(shù)字分析法

假設關鍵字集合中的每個關鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關鍵字集中的全體，并從中提取分布均勻的若干位或它們的組合作為地址。03四月2023第92頁例有80個記錄，關鍵碼為8位十進制數(shù)，假設表長為l00，則可取兩位十進制數(shù)(00～99)組成散列地址，取其中的哪兩位?8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址03四月2023第93頁

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

此方法適合于:

關鍵字中的每一位都有某些數(shù)字重復出現(xiàn)頻度很高的現(xiàn)象。03四月2023第94頁如圖:隨機給出一些關鍵字，取平方后的第2到3位為函數(shù)地址。

關鍵字

（關鍵字）2

函數(shù)地址

01000010000

11001210000

12001440000

11601370400

20614310541

利用平方取中法得到散列函數(shù)地址

012144373103四月2023第95頁

將關鍵字分割成位數(shù)相同若干部分（最后一部分的位數(shù)可以不同），然后取它們的疊加和（舍棄高位進位）為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。4.折疊法

此方法適合于:

關鍵字的數(shù)字位數(shù)特別多。03四月2023第96頁x=12320324111220從左到右按3個位數(shù)—段分割，共得到5個段：123、203、241、112、20。采用移位疊加得到：A(x)＝123+203+241+112+20＝699若采用間界疊加，則從左到右來回折疊中，第二、四段反轉為302和211得到：B(x)＝123+302+241+211+20＝897移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加03四月2023第97頁5.除留余數(shù)法

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

p≤m(表長)并且

p

應為不大于m的素數(shù)

或是不含20以下的質因子03四月2023第98頁

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

可見，若p中含質因子3，則所有含質因子3的關鍵字均映射到“3的倍數(shù)”的地址上，從而增加了“沖突”的可能。03四月2023第99頁6.隨機數(shù)法設定哈希函數(shù)為:H(key)=Random(key)

其中，Random為偽隨機函數(shù)

通常，此方法用于對長度不等的關鍵字構造哈希函數(shù)。03四月2023第100頁

實際造表時，采用何種構造哈希函數(shù)的方法取決于建表的關鍵字集合的情況(包括關鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。03四月2023第101頁選取哈希函數(shù)，考慮以下因素：計算哈希函數(shù)所需時間關鍵碼長度哈希表長度（哈希地址范圍）關鍵碼分布情況記錄的查找頻率03四月2023第102頁三、處理沖突的方法

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

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

H0,H1,H2,…,Hs

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

)MODm

i=1,2,…,s1.開放定址法03四月2023第104頁對增量

di

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

di=ci

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

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

di

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

di=i×H2(key)(又稱雙散列函數(shù)探測)03四月2023第105頁例表長為11的哈希表中已填有關鍵字為17，60，29的記錄，H(key)=keyMOD11,現(xiàn)有第4個記錄，其關鍵字為38，按線性探測、二次探測處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突H1=(5+1)MOD11=6沖突H2=(5+2)MOD11=7沖突H3=(5+3)MOD11=8不沖突

38(2)H(38)=38MOD11=5沖突H1=(5+12)MOD11=6沖突H2=(5-12)MOD11=4不沖突38線性探測：二次探測：(3)H(38)=38MOD11=5沖突設偽隨機數(shù)序列為9，則：H1=(5+9)MOD11=3不沖突03四月2023第106頁線性探測法示例關鍵字為(13,19,39,24,28,57,76,51,84)，散列表長m=13，散列函數(shù)為H(key)=key%11

0123456789101112

13

39

19

1

1

1

1324

3919

12

11

1324

392819

12

121

03四月2023第107頁線性探測法示例(續(xù))－繼續(xù)插入

57,76,51,84

132457

392819

123

121

0123456789101112

132457

392819

76

123

121

1

132457

3928195176

123

12131

132457

392819517684

123

121315

03四月2023第108頁2.鏈地址法

將所有關鍵碼為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針，用鏈地址法解決沖突建立的散列表也叫開散列表。03四月2023第109頁例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數(shù)為：H(key)=keyMOD13,

0

1

2

3

4

5

6

7

8

9

10

111214^127796855198420231011^^^^^^^^^^^^03四月2023第110頁

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

四、哈希表的查找

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

則查找不成功若

R[i].key=K

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

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

或

R[Hi].key=K(查找成功)為止。03四月2023第111頁哈希查找過程給定k值計算H(k)此地址為空查找失敗Y關鍵字==kN查找成功Y按處理沖突方法計算HiN哈希查找分析哈希查找過程仍是一個給定值與關鍵碼進行比較的過程評價哈希查找效率仍要用ASL哈希表的記錄結構定義設哈希表的記錄結構定義如下：

#definem600/*定義表長*/typedefstruct/*定義記錄結構*/{keytypekey;/*關鍵字域*/datatypeother;/*其它數(shù)據(jù)域*/}hoshtable;用線性探查法消解地址沖突算法用線性探查法消解地址沖突的哈希檢索算法可描述如下：

inthoshsearch(hashtablehstable[],keytypek){inti,d;i=0;d=h(k);while((hstable[d].key!=k)&&(hstable[d]!=nullrecd)&&(i<m)){i++;d=(d+i)%m;}if(hstable[d].key==k)returnd;elsereturnm;}用拉鏈法消解地址沖突的結點說明

若用拉鏈法消解地址沖突，其結點說明如下：

#definem600/*定義表長*/typedefstructnode/*結點結構*/{keytypekey;/*關鍵字域*/datatypeother;/*其它數(shù)據(jù)域*/structnode*link;/*指針域*/}hsnode;/*定義結點類型*/typedefhsnode*hslink;typedefhslinkhstable[m];用拉鏈法消解地址沖突的算法描述

若用拉鏈法消解地址沖突，其算法描述如下：

hslinkhashseachlink(hstablehst,keytypek){intd;hslinkp;d=h(k);p=hst[d];while((p!=NULL)&&(p->key!=k))p=p->link;returnp;}03四月2023第116頁例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,哈希表長為m=16，設每個記錄的查找概率相等(1)用線性探測再散列處理沖突，即Hi=(H(key)+di)MODmH(55)=3沖突，H1=(3+1)MOD16=4沖突，H2=(3+2)MOD16=5H(79)=1沖突，H1=(1+1)MOD16=2沖突，H2=(1+2)MOD16=3沖突，H3=(1+3)MOD16=4沖突，H4=(1+4)MOD16=5