1、2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第1頁(yè),第九章 查找表,何謂查找表 ？,查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。,由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第2頁(yè),對(duì)查找表經(jīng)常進(jìn)行的操作:,1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中； 2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性； 3）在查找表中插入一個(gè)數(shù)據(jù)元素； 4）從查找表中刪去某個(gè)數(shù)據(jù)元素。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第3頁(yè),僅作查詢和檢索操作的查找表。,靜態(tài)查找表,有時(shí)在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素

2、插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。,動(dòng)態(tài)查找表,查找表可分為兩類:,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第4頁(yè),是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。,關(guān)鍵字,若此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字”。,若此關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)鍵字”。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第5頁(yè),根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）,查找,若查找表中存在這樣一個(gè)記錄，則稱“查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置； 否則稱

3、“查找不成功”，查找結(jié)果：給出 “空記錄”或“空指針”。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第6頁(yè),由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率， 需要在查找表中的元素之間人為地 附加某種確定的關(guān)系，即用另外一種結(jié)構(gòu)來表示查找表。,如何進(jìn)行查找？,查找的方法取決于查找表的結(jié)構(gòu)。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第7頁(yè),9.1 靜態(tài)查找表,9.2 動(dòng)態(tài)查找表,9.3 哈希表,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第8頁(yè),9.1 靜 態(tài) 查 找 表,數(shù)據(jù)對(duì)象D：,數(shù)據(jù)關(guān)系R：,D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字

4、，可唯一標(biāo)識(shí)數(shù)據(jù)元素。,數(shù)據(jù)元素同屬一個(gè)集合。,ADT StaticSearchTable ,抽象數(shù)據(jù)類型靜態(tài)查找表的定義,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第9頁(yè),Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作 P：, ADT StaticSearchTable,/構(gòu)造一個(gè)含 n 個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。,/銷毀已存在靜態(tài)查找表ST。,/若 ST 中存在其關(guān)鍵字等于 key 的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。,/按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Vi

5、sit()失敗，則操作失敗。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第10頁(yè),假設(shè)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)為,typedef struct ElemType *elem; / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; / 表的長(zhǎng)度 SSTable;,數(shù)據(jù)元素類型的定義為:,typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ;,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第11頁(yè),一、順序查找表(以順序表或線性鏈表表示靜態(tài)查找表),ST.elem,回顧順序表的查找過程：,假設(shè)給定值 e = 64, 要求

6、ST.elemi = e, 問: i = ?,66,基本思想：從線性表的一端向另一端逐個(gè)將關(guān)鍵碼與給定值進(jìn)行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個(gè)表檢測(cè)完仍未找到與給定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第12頁(yè),int location( SqList L, ElemType e, Status (*compare)(ElemType, ElemType) i = 1; p = L.elem; while ( i=L.length /location,i=L.length,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第13頁(yè),ST

7、.elem,ST.elem,60,key = 64,key = 60,64,基本思想：設(shè)置“哨兵”。哨兵就是待查值，將它放在查找方向的盡頭處，免去了在查找過程中每一次比較后都要判斷查找位置是否越界，從而提高查找速度。,改進(jìn)的順序查找,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第14頁(yè),int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / 設(shè)置“哨兵” for (i=ST.length; -i); / 從后往前找

8、 return i; / 找不到時(shí)，i為0 / Search_Seq,ST.elemi.key!=key;,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第15頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第16頁(yè),順序表查找的平均查找長(zhǎng)度為：,對(duì)順序表而言，Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,在等概率查找的情況下，,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第17頁(yè),若查找概率無法事先測(cè)定，則查找過程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。,在不等概率查找的情況下，ASLss 在 PnPn-1P2P1 時(shí)取極小值,200

9、9-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第18頁(yè),平均查找長(zhǎng)度較大，特別是當(dāng)待查找集合中元素較多時(shí)，查找效率較低。,順序查找的缺點(diǎn)：,算法簡(jiǎn)單而且使用面廣。 對(duì)表中記錄的存儲(chǔ)沒有任何要求，順序存儲(chǔ)和鏈接存儲(chǔ)均可； 對(duì)表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。,順序查找的優(yōu)點(diǎn)：,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第19頁(yè),上述順序查找表的查找算法簡(jiǎn)單， 但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。,二、有序表的查找,若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。即先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。,2009-2,計(jì)算機(jī)

10、與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第20頁(yè),折半查找,使用條件： 線性表中的記錄必須按關(guān)鍵碼有序； 必須采用順序存儲(chǔ)。,基本思想：在有序表中，取中間記錄作為比較對(duì)象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值小于中間記錄的關(guān)鍵碼，則在中間記錄的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵碼，則在中間記錄的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第21頁(yè),ST.elem,ST.length,例如: key = 64 的查找過程如下,low,high,mid,low,mid,high,mid,low 指示查找區(qū)間的下界;

11、high 指示查找區(qū)間的上界; mid = (low+high)/2。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第22頁(yè),int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low = high) mid = (low + high) / 2; if （key = ST.elemmid.key ) return mid; / 找到待查元素 else if ( key ST.elemmid.key) ) high = mid - 1; / 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low

12、 = mid + 1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return 0; / 順序表中不存在待查元素 / Search_Bin,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第23頁(yè),先看一個(gè)具體的情況，假設(shè)：n=11,分析折半查找的平均查找長(zhǎng)度,6,3,9,1,4,2,5,7,8,10,11,判定樹,1,2,2,3,3,3,3,4,4,4,4,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第24頁(yè),假設(shè) n=2h-1 并且查找概率相等則,一般情況下，表長(zhǎng)為 n 的折半查找的判定樹的深度和含有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。,在 n50 時(shí)，可得近似結(jié)果,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第25頁(yè)

13、,分塊查找又稱為索引查找，它是一種性能介于順 序查找和二分查找之間的查找算法。 分塊查找要求將被查找表分成塊，建立塊索引。 每一塊中的關(guān)鍵字不一定有序，但前一塊中的最 大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字，即要 “分塊有序”。 抽取各塊中的最大關(guān)鍵字及其起始位置構(gòu)成一個(gè) 索引表。由于被查找表是分塊有序的，所以索引表是一個(gè)遞增有序表。,三、索引順序表（分塊查找）,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第26頁(yè),13,3,9,20,33,42,44,38,60,80,74,49,86,53,22,12,0,6,12,22,48,86,24,48,0 1 2 3 4 5 6 7 8 9 10 11

14、 12 13 14 15 16 17,分塊查找的基本思想：首先，查找索引表，因?yàn)樗饕硎怯行虮?，故可采用二分查找，也可以采用順序查找，以確定待查的結(jié)點(diǎn)在哪一塊；然后在以確定的那一塊中順序查找。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第27頁(yè),算法分析,由于分塊查找實(shí)際上是兩次查找過程，故整個(gè)算法的平均查找長(zhǎng)度應(yīng)該是兩次查找的平均查找長(zhǎng)度之和。若以二分查找來確定塊，則分塊查找的平均查找長(zhǎng)度約為：,若以順序查找來確定塊，則分塊查找的平均查找長(zhǎng)度約為：,對(duì)于后一種情況，當(dāng) 時(shí)，平均查找長(zhǎng)度為極小值。在實(shí)用中，可根據(jù)表的具體情況進(jìn)行分塊。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第28頁(yè),分塊查找的

15、性能介于順序查找和二分查找之間的，例如，對(duì)長(zhǎng)度為10000的線性表，它們的平均查找長(zhǎng)度分別是：,順序查找：約5000 分塊查找：約100 二分查找：約14,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第29頁(yè),9.2 動(dòng) 態(tài) 查 找 表,動(dòng)態(tài)查找表的特點(diǎn)：表結(jié)構(gòu)本身是在查找過程中動(dòng)態(tài)生成的，即對(duì)于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回，否則插入關(guān)鍵字等于key的記錄。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第30頁(yè),ADT DynamicSearchTable ,抽象數(shù)據(jù)類型動(dòng)態(tài)查找表的定義如下：,數(shù)據(jù)對(duì)象D： 數(shù)據(jù)關(guān)系R：,數(shù)據(jù)元素同屬一個(gè)集合。,D是具有相同特性的數(shù)

16、據(jù)元素的集合。 每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字， 可唯一標(biāo)識(shí)數(shù)據(jù)元素。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第31頁(yè),InitDSTable(,InsertDSTable(,DeleteDSTable(,TraverseDSTable(DT, Visit();,ADT DynamicSearchTable,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第32頁(yè),一、二叉排序樹（二叉查找樹）,1定義,2查找算法,3插入算法,4刪除算法,5查找性能的分析,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第33頁(yè),（1）若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；,1定義：,二叉排序樹或者是一

17、棵空樹；或者是具有如下特性的二叉樹：,（3）它的左、右子樹也都分別是二叉排序樹。,（2）若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第34頁(yè),例如:,是二叉排序樹。,不,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第35頁(yè),通常，取二叉鏈表作為二叉排序樹的存儲(chǔ)結(jié)構(gòu),typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;,TElemType data;,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第36頁(yè),2二叉排序樹的查找算

18、法：,1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功； 2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找； 3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。,若二叉排序樹為空，則查找不成功；否則,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第37頁(yè),例如:,二叉排序樹,查找關(guān)鍵字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第38頁(yè),從上述查找過程可見，,在查找過程中，生成了一條查找路徑:,從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);,或者,從根結(jié)點(diǎn)出發(fā)，沿著左分支或右

19、分支逐層向下直至指針指向空樹為止。,查找成功,查找不成功,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第39頁(yè),算法描述如下：,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree 否則表明查找不成功，返回 / 指針 p 指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為FALSE, 指針 f 指向當(dāng)前訪問 / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL / SearchBST, ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第40頁(yè),if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(k

20、ey, T-data.key) ) else, p = f; return FALSE; / 查找不成功, p = T; return TRUE; / 查找成功,return SearchBST (T-lchild, key, T, p ); / 在左子樹中繼續(xù)查找,return SearchBST (T-rchild, key, T, p ); / 在右子樹中繼續(xù)查找,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第41頁(yè),f,T,設(shè) key = 48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第42頁(yè),根據(jù)動(dòng)態(tài)查找表的定義，“插

21、入”操作在查找不成功時(shí)才進(jìn)行;,3二叉排序樹的插入算法,若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第43頁(yè),Status Insert BST(BiTree / Insert BST, ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第44頁(yè),s = (BiTree)malloc(sizeof( BiTNode); / 為新結(jié)點(diǎn)分配空間 s-data = e; s-lchild = s-rchild = NULL;,if ( !p ) T = s; / 插入 s 為新的根結(jié)點(diǎn),else

22、if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子 else p-rchild = s; / 插入 *s 為 *p 的右孩子,return TRUE; / 插入成功,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第45頁(yè),（1）被刪除的結(jié)點(diǎn)是葉子； （2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹； （3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。,4二叉排序樹的刪除算法,可分三種情況討論：,和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第46頁(yè)

23、,（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn),例如:,被刪關(guān)鍵字 = 20,88,其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第47頁(yè),（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹,其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為 “指向被刪除結(jié)點(diǎn)的左子樹或右子樹”。,被刪關(guān)鍵字 = 40,80,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第48頁(yè),（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹,40,40,以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn),被刪結(jié)點(diǎn),前驅(qū)結(jié)點(diǎn),被刪關(guān)鍵字 = 50,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第49頁(yè),Status DeleteBST (BiTree / 不存在關(guān)鍵字等

24、于key的數(shù)據(jù)元素 else / DeleteBST,算法描述如下：, ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第50頁(yè),if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于key的數(shù)據(jù)元素 else if ( LT (key, T-data.key) ) else, Delete (T); return TRUE; ,return DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹中進(jìn)行查找,return DeleteBST ( T-rchild, key ); / 繼續(xù)在右子樹中進(jìn)行查找,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第51頁(yè),vo

25、id Delete ( BiTree p = p-lchild; free(q);,q,q,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第53頁(yè),/ 左子樹為空樹只需重接它的右子樹,q = p; p = p-rchild; free(q);,p,p,q,q,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第54頁(yè),q = p; s = p-lchild; while (s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū),/ 左右子樹均不空,p-data = s-data; if (q != p ) q-rchild = s-lchild; else q-lchild

26、= s-lchild; / 重接*q的左子樹 free(s);,q,s,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第55頁(yè),5查找性能的分析,對(duì)于每一棵特定的二叉排序樹，均可按照平均查找長(zhǎng)度的定義來求它的 ASL 值，顯然，由值相同的 n 個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長(zhǎng) 度的值不同，甚至可能差別很大。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第56頁(yè),由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹,由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹，,例如：,2,1,3,4,5,3,5,4,1,2,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+

27、2+3+2+3）/ 5 = 2.2,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第57頁(yè),下面討論平均情況:,不失一般性，假設(shè)長(zhǎng)度為 n 的序列中有 k 個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵字，則必有 n-k-1 個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字,由它構(gòu)造的二叉排序樹,n-k-1,k,的平均查找長(zhǎng)度是 n 和 k 的函數(shù),P(n, k) ( 0 k n-1 ),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第58頁(yè),假設(shè) n 個(gè)關(guān)鍵字可能出現(xiàn)的 n! 種排列的可能性相同，則含 n 個(gè)關(guān)鍵字的二叉排序樹的平均查找長(zhǎng)度,在等概率查找的情況下，,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第59頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)

28、構(gòu),第60頁(yè),由此,可類似于解差分方程，此遞歸方程有解：,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第61頁(yè),平衡二叉樹是二叉查找樹的另一種形式，其特點(diǎn)為：,樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值不大于1 。,例如:,是平衡樹,不是平衡樹,平衡因子（BF）：結(jié)點(diǎn)的左、右子樹深度之差，任一結(jié)點(diǎn)的平衡因子只能取：-1、0 或 1。,二、平衡二叉樹,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第62頁(yè),如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。調(diào)整平衡過程為平衡旋轉(zhuǎn)。,平衡旋轉(zhuǎn)可以歸納為四類： LL平衡旋轉(zhuǎn) RR平衡旋轉(zhuǎn) LR平衡旋轉(zhuǎn) RL平衡旋轉(zhuǎn),2

29、009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第63頁(yè),從發(fā)生不平衡的結(jié)點(diǎn)起，得到一棵子樹。 如果這子樹上結(jié)點(diǎn)處于一條直線上，則采用單旋轉(zhuǎn)進(jìn)行平衡化。 如果這子樹上的結(jié)點(diǎn)處于一條折線上，則采用雙旋轉(zhuǎn)進(jìn)行平衡化。雙旋轉(zhuǎn)分為先左后右和先右后左兩類。,右單旋轉(zhuǎn),左單旋轉(zhuǎn),左右雙旋轉(zhuǎn),右左雙旋轉(zhuǎn),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第64頁(yè),右單旋轉(zhuǎn) (LL),h,h,h,A,C,E,B,D,(a) (b) (c),h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,在左子樹D上插入新結(jié)點(diǎn)使其高度增1，導(dǎo)致結(jié)點(diǎn)A的平衡因子增到 2，造成了不平衡。 為使樹恢復(fù)平衡，從A沿插入路徑連續(xù)

30、取3個(gè)結(jié)點(diǎn)A、B和D，它們處于一條方向?yàn)椤?”的直線上，需做右單旋轉(zhuǎn)。 以結(jié)點(diǎn)B為旋轉(zhuǎn)軸，將結(jié)點(diǎn)A順時(shí)針旋轉(zhuǎn)。,h,0,0,0,1,1,2,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第65頁(yè),左單旋轉(zhuǎn) (RR ),h,h,h,A,C,E,B,D,(a) (b) (c),h,h,h + 1,B,A,C,E,D,h,h,h + 1,C,E,A,B,D,如果在子樹E中插入一個(gè)新結(jié)點(diǎn)，該子樹高度增1導(dǎo)致結(jié)點(diǎn)A的平衡因子變成-2，出現(xiàn)不平衡。 沿插入路徑檢查三個(gè)結(jié)點(diǎn)A、C和E。它們處于一條方向?yàn)椤啊钡闹本€上，需要做左單旋轉(zhuǎn)。 以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，讓結(jié)點(diǎn)A反時(shí)針旋轉(zhuǎn)。,-1,-2,0,-1,0,0,2009-

31、2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第66頁(yè),先左后右雙旋轉(zhuǎn) (LR),在C的子樹CL或CR中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第67頁(yè),從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、B和C(“”型) 以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，做單向左下旋轉(zhuǎn) 再以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，做單向右下旋轉(zhuǎn),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第68頁(yè),先右后左雙旋轉(zhuǎn) (RL),在C的子樹CL或CR中插入新結(jié)點(diǎn)，該子樹的高度增1。結(jié)點(diǎn)A的平衡因子變?yōu)?2，發(fā)生了不平衡,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第69頁(yè),從結(jié)點(diǎn)A起沿插入路徑選取3個(gè)結(jié)點(diǎn)A、C和D(“”型

32、) 以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，作單向右旋 再以結(jié)點(diǎn)C為旋轉(zhuǎn)軸，作單向左旋,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第70頁(yè),例 設(shè)一組記錄的關(guān)鍵字按以下次序進(jìn)行插入：8，5，4，9，10，7，2，3，生成平衡二叉排序樹的過程如下：,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第71頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第72頁(yè),1.定義 一棵m階的B-樹,或?yàn)榭諛?或?yàn)闈M足下列特性的m叉樹: (1)樹中每個(gè)結(jié)點(diǎn)至多有m棵子樹。 (2)除非根結(jié)點(diǎn)為葉子結(jié)點(diǎn),否則至少有兩棵子樹。 (3)除根之外的所有非終端結(jié)點(diǎn)至少有m/2棵子樹。 (4)所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)如下:,其中,k1,k2,.,kn為n個(gè)按從

33、小到大順序排列的鍵值; p0,pl,p2,.,pn為(n+1)個(gè)指針,用于指向該結(jié)點(diǎn)的(n+l)棵子樹,p0所指向子樹中的所有關(guān)鍵字的值均小于kl,pn所指向子樹中的所有關(guān)鍵字的值均大于kn,pi(1in-1)所指向子樹中的所有關(guān)鍵字的值均大于ki且小于ki+1; n(nm-1)為鍵值的個(gè)數(shù),即子樹個(gè)數(shù)為(n+l)。,三、 B - 樹,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第73頁(yè),(5)所有葉子結(jié)點(diǎn)在同一個(gè)層次上,且不含有任何信息。,從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找 兩個(gè)過程交叉進(jìn)行。,2.查找過程：,若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)

34、中的位置；,若查找不成功，則返回插入位置。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第74頁(yè),a,t,b,c,d,f,g,e,h,例如，在圖9-13所示B_樹中查找關(guān)鍵字80和38,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第75頁(yè),性能分析 在B-樹上進(jìn)行查找需比較的結(jié)點(diǎn)數(shù)最多為B-樹的高度,B-樹的高度與B-樹的階m和鍵值總數(shù)N有關(guān)； 分析： (1)若B-樹的高度為h+1,則h+1層(即葉結(jié)點(diǎn)所在的層)的結(jié)點(diǎn)數(shù)為N+1。 因?yàn)槊總€(gè)非葉結(jié)點(diǎn)中的指針數(shù)等于其中的鍵值數(shù)加1,因此有: 結(jié)點(diǎn)總數(shù)=指針總數(shù)+1=(鍵值總數(shù)N+非葉結(jié)點(diǎn)數(shù))+l (h+1)層的結(jié)點(diǎn)數(shù)=葉結(jié)點(diǎn)數(shù)=結(jié)點(diǎn)總數(shù)非葉結(jié)點(diǎn)數(shù)=N+1

35、。 (2)根據(jù)B-樹的定義,B-樹的第一層(即根結(jié)點(diǎn))的結(jié)點(diǎn)數(shù)至少為1個(gè),第二層的結(jié)點(diǎn)數(shù)至少為2,第三層的結(jié)點(diǎn)數(shù)至少為2*m/2,第四層的結(jié)點(diǎn)數(shù)至少為2*(m/2)2,以此類推,第h+1層的結(jié)點(diǎn)數(shù)至少為2*(m/2)h-1。 (3)綜上所述,可得到如下不等式: h1+logm/2(N+1)/2,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第76頁(yè),3、B-樹的插入操作 插入方法： 首先要經(jīng)過一個(gè)從樹根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的查找過程,如果鍵值k已在樹中,則不用做其他事;否則,找出插入位置,然后再進(jìn)行插入。對(duì)于葉子結(jié)點(diǎn)處于第(h+1)層的樹,插入的位置總是在第h層。若結(jié)點(diǎn)的關(guān)鍵字值個(gè)數(shù)不超過(m-l),直接

36、插入即可;否則需要把結(jié)點(diǎn)分裂成兩個(gè)。 分裂的做法： 取一新結(jié)點(diǎn),把原結(jié)點(diǎn)上的鍵和k按升序排序后,從中間位置(m/2)把鍵值(不包括中間位置的鍵值)分成兩部分,左部分所含鍵值放在舊結(jié)點(diǎn)中,右部分所含鍵值放在新結(jié)點(diǎn)中,中間位置鍵值連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到父親結(jié)點(diǎn)中。若父結(jié)點(diǎn)的鍵值個(gè)數(shù)超過(m-l),要再分裂,再往上插,直至這個(gè)過程傳到根結(jié)點(diǎn)為止。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第77頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第78頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第79頁(yè),4、B-樹的刪除 刪除方法 在深度為(h+l)的m階B-樹中刪除一個(gè)鍵值k,首先要查到鍵值k所在的結(jié)點(diǎn)

37、及在結(jié)點(diǎn)中的位置。若k所在結(jié)點(diǎn)的層數(shù)小于h,則把該結(jié)點(diǎn)的右邊(或左邊)指針?biāo)缸訕渲械淖钚?或最大)鍵值與k對(duì)調(diào),使k移到第h層,這樣可根據(jù)k所在結(jié)點(diǎn)為第h層結(jié)點(diǎn)的情況進(jìn)行刪除,從B_樹上第h層結(jié)點(diǎn)中刪除一個(gè)鍵值后,使得該結(jié)點(diǎn)的值個(gè)數(shù)n減1,此時(shí)應(yīng)分以下三種情況進(jìn)行處理: (1)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n m/21,在該結(jié)點(diǎn)中刪去鍵值k連同右邊的指針. (2)若刪除后結(jié)點(diǎn)中鍵值數(shù)目n m/21,且左(或右)兄弟結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目m/21,則把左(或右)兄弟結(jié)點(diǎn)中最大(或最小)鍵值移到父結(jié)點(diǎn)中,再把父結(jié)點(diǎn)大于(或小于)上移鍵值的鍵值下移到被刪關(guān)鍵字所在結(jié)點(diǎn)中。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu)

38、,第80頁(yè),(3)若刪除后結(jié)點(diǎn)中鍵值數(shù)目nm/21,及其左、右兄弟結(jié)點(diǎn)的鍵值數(shù)目都等于m/21,則進(jìn)行結(jié)點(diǎn)的“合并”,即把應(yīng)刪的鍵值刪去后,將該結(jié)點(diǎn)中的剩余鍵值和指針連同父結(jié)點(diǎn)中指向該結(jié)點(diǎn)指針的左邊(或右邊)一個(gè)鍵值ki一起合并到左兄弟(或右兄弟)結(jié)點(diǎn)中,將ki從父結(jié)點(diǎn)中刪去。如果因此使父結(jié)點(diǎn)中關(guān)鍵字?jǐn)?shù)目m/21,則對(duì)此父結(jié)點(diǎn)做同樣處理,以致于可能直到對(duì)根結(jié)點(diǎn)做這樣的處理而使整個(gè)樹減少一層。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第81頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第82頁(yè),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第83頁(yè),以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表

39、中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，查找的過程為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行比較，查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。,一、什么是哈希表？,9.3 哈 希 表,用這類方法表示的查找表，其平均查找長(zhǎng)度都不為零。不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第84頁(yè),只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，,對(duì)于頻繁使用的查找表，希望 ASL = 0。,即要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。,例如：為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為 xx000

40、xx999 (前兩位為年份)。,若以下標(biāo)為000 999 的順序表表示之。,則查找過程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查關(guān)鍵字。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第85頁(yè),但是，對(duì)于動(dòng)態(tài)查找表而言，,因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以 f(key) 作為關(guān)鍵字作為 key 的記錄在表中的位置，通常稱這個(gè)函數(shù) f(key) 為哈希函數(shù)。,1) 表長(zhǎng)不確定；,2) 在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所屬范圍，而不知道確切的關(guān)鍵字。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第86頁(yè),Zhao, Qian, Sun

41、, Li, Wu, Chen, Han, Ye, Den,例如：對(duì)于如下 9 個(gè)關(guān)鍵字,設(shè) 哈希函數(shù) f(key) = (Ord(第一個(gè)字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Den,問題: 若添加關(guān)鍵字 Zhou , 怎么辦？,能否找到另一個(gè)哈希函數(shù)？,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第87頁(yè),1) 哈希(Hash)函數(shù)是一個(gè)映象，即： 將關(guān)鍵字的集合映射到某個(gè)地址集合上，它的設(shè)置很靈活，只要這個(gè)地址集合的大小不超出允許范圍即可;,從這個(gè)例子可見，,2) 由于哈希函數(shù)是一個(gè)壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突”現(xiàn)象，

42、即： key1 key2，而 f(key1) = f(key2)。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第88頁(yè),3) 很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。 一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。,因此，在構(gòu)造這種特殊的“查找表” 時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突” 的方法。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第89頁(yè),哈希表的定義:,根據(jù)設(shè)定的哈希函數(shù) H(key) 和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個(gè)有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“像”作為相應(yīng)記錄在表中的存儲(chǔ)位置，

43、如此構(gòu)造所得的查找表稱之為“哈希表”。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第90頁(yè),二、構(gòu)造哈希函數(shù)的方法,對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法:,若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。,1. 直接定址法,3. 平方取中法,5. 除留余數(shù)法,4. 折疊法,6. 隨機(jī)數(shù)法,2. 數(shù)字分析法,設(shè)計(jì)散列函數(shù)一般應(yīng)遵循以下原則： 計(jì)算簡(jiǎn)單。散列函數(shù)不應(yīng)該有很大的計(jì)算量，否則會(huì)降低查找效率。 函數(shù)值(散列地址)分布均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲(chǔ)空間的有效利用并減少?zèng)_突。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第91頁(yè),哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key

44、或者 H(key) = a key + b,1. 直接定址法,此法僅適合于： 地址集合的大小 = = 關(guān)鍵字集合的大小,例：關(guān)鍵碼集合為10, 30, 50, 70, 80, 90，選取的散列函數(shù)為H(key)=key/10，則散列表為：,10,30,50,70,80,90,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第92頁(yè),此方法僅適合于： 能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。,2. 數(shù)字分析法,假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。,例：關(guān)鍵碼為8位十進(jìn)制數(shù)，散

45、列地址為2位十進(jìn)制數(shù),8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7, ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第93頁(yè),以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。,3. 平方取中法,此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。,例：散列地址為2位，則關(guān)鍵碼1234的散列地址為：,(1234)21522756,2009-2,計(jì)算機(jī)與

46、信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第94頁(yè),4. 折疊法,此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。事先不知道關(guān)鍵碼的分布。,將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。,例：設(shè)關(guān)鍵碼為2 5 3 4 6 3 5 8 7 0 5，散列地址為三位。,2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位疊加,2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 間界疊加,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第95頁(yè),5. 除留余數(shù)法,設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中， pm (表長(zhǎng)) 并且 p 應(yīng)為不大于

47、m 的素?cái)?shù) 或是不含 20 以下的質(zhì)因子的合數(shù)。,除留余數(shù)法是一種最簡(jiǎn)單、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第96頁(yè),6.隨機(jī)數(shù)法,設(shè)定哈希函數(shù)為: H(key) = Random(key) 其中，Random 為偽隨機(jī)函數(shù),通常，此方法用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。,實(shí)際造表時(shí)，采用何種構(gòu)造哈希函數(shù)的方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到盡可能地小。,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第97頁(yè),三、處理沖突的方法,“處理沖突” 的實(shí)際含義是： 為產(chǎn)生沖突的

48、地址尋找下一個(gè)哈希地址,1. 開放定址法,3 .再哈希法,4.建一個(gè)公共溢出區(qū),2. 鏈地址法,通常有以下幾種處理沖突的方法:,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第98頁(yè),為產(chǎn)生沖突的地址 H(key) 求得一個(gè)地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s,1. 開放定址法,對(duì)增量 di 常有三種取法：,1) 線性探測(cè)再散列 di = c i 最簡(jiǎn)單的情況 c=1 2) 平方（二次）探測(cè)再散列 di = 12, -12, 22, -22, , 3) 隨機(jī)探測(cè)再散列 d

49、i 是一組偽隨機(jī)數(shù)列 或者 di=iH2(key) (又稱雙散列函數(shù)探測(cè)),2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第99頁(yè),即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的 s(即m-1)個(gè) Hi 值能覆蓋哈希表中所有地址。則要求：,注意：增量 di 應(yīng)具有“完備性”, 隨機(jī)探測(cè)時(shí)的 m 和 di 沒有公因子。, 平方探測(cè)時(shí)的表長(zhǎng) m 必為形如 4j+3 的素?cái)?shù)（如: 7, 11, 19, 23, 等）；,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第100頁(yè),例如: 關(guān)鍵字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,設(shè)定哈希函數(shù) H(key) = key MOD 11

50、( 表長(zhǎng)=11 ),19,01,23,14,55,68,19,01,23,14,68,若采用線性探測(cè)再散列處理沖突,若采用二次探測(cè)再散列處理沖突,11,82,36,55,11,82,36,1 1 2 1 3 6 2 5 1,ASL=(41+22+6+5+3)/9=22/9,1 1 2 1 2 1 4 1 2,ASL=(51+32+4)/9=15/9,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第101頁(yè),H2(key) 是另設(shè)定的一個(gè)哈希函數(shù)，它的函數(shù)值應(yīng)和 m 互為素?cái)?shù)。,若 m 為素?cái)?shù)，則 H2(key) 可以是 1 至 m-1 之間的任意數(shù);若 m 為 2 的冪次，則 H2(key) 應(yīng)是

51、1 至 m-1 之間的任意奇數(shù)。,例如，當(dāng) m=11時(shí)，可設(shè) di=H2(key)=(3 key) MOD 10+1,19,01,23,14,55,68,11,82,36,2 1 1 1 2 1 2 1 3,雙散列函數(shù)探測(cè), 19, 01, 23, 14, 55, 68, 11, 82, 36 ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第102頁(yè),將所有哈希地址相同的記錄都鏈接在同一鏈表中。,2. 鏈地址法,ASL=(61+22+3)/9=13/9,例如:同前例的關(guān)鍵字，哈希函數(shù)為 H(key)=key MOD 7, 19, 01, 23, 14, 55, 68, 11, 82, 36 ,2009-2,計(jì)算機(jī)與信息學(xué)院數(shù)據(jù)結(jié)構(gòu),第103頁(yè),再哈希法：,ii(key) RHi均是不同的哈希函數(shù)即：發(fā)生沖突時(shí)，計(jì)算另一個(gè)哈希函數(shù)地址，直到不再發(fā)生沖突為止。,建立一個(gè)公共溢出區(qū)：,假設(shè)哈希函數(shù)的值域?yàn)椋琺-1，則建一個(gè)基本表HashTable0