數(shù)據(jù)結(jié)構(gòu)第7章課件

1、第7章 查找表24 七月 2022本章概述 “查找”是日常生活中常有的事，人們幾乎每天都要做“查找”工作。例如，在電話號碼簿中查找某單位或某人的電話號碼；在閱讀文獻(xiàn)時查閱字典以確定某個詞的含義；在程序設(shè)計中，查找也是一種常用的基本運(yùn)算，如編譯程序中符號表的查找、信息處理系統(tǒng)中信息的查找等。因此，如何高效率地實現(xiàn)查找運(yùn)算是查找表的基本問題，也是本章的重點內(nèi)容。24 七月 20227.1 基本概念與術(shù)語 關(guān)鍵字:是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）。 若此關(guān)鍵字可以唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字為主關(guān)鍵字（primary key），不同的記錄其主關(guān)鍵字

2、不同，反之，稱用以識別若干記錄的關(guān)鍵字為次關(guān)鍵字（secondary key）。 查找（searching）：根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。24 七月 20227.2 順序表的查找 當(dāng)順序表作為線性表的存儲結(jié)構(gòu)時，存儲結(jié)點間的位置關(guān)系與對應(yīng)數(shù)據(jù)元素之間的邏輯關(guān)系（鄰接關(guān)系）是一致的，即數(shù)據(jù)元素在線性表中的次序與它們在順序表中次序相同。 順序表的存儲結(jié)構(gòu)如下： typedef strict ElemType *elem;/ 存儲空間基址,建表時按照實際長度分配,0號單元不用int length;/ 順序表長度STable;24 七月 2022 查找可分為靜態(tài)查

3、找和動態(tài)查找兩大類。 靜態(tài)查找是指在查找時只對數(shù)據(jù)元素進(jìn)行查詢和檢索。 動態(tài)查找除包括靜態(tài)查找的要求外，還包括插入數(shù)據(jù)元素集合中不存在的數(shù)據(jù)元素，或者從數(shù)據(jù)元素集合中刪除已存在的某個數(shù)據(jù)元素。 靜態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)稱作靜態(tài)查找表。 動態(tài)查找時構(gòu)造的存儲結(jié)構(gòu)稱作動態(tài)查找表。24 七月 2022 順序查找適用于線性表的順序存儲結(jié)構(gòu)，也適用于鏈?zhǔn)酱鎯Y(jié)構(gòu)，表內(nèi)的數(shù)據(jù)元素是無序的。 順序查找的查找過程為：從順序表中的最后一個記錄開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個記錄的關(guān)鍵字和給定值比較后相等，則查找成功，找到所查記錄；如果直至第一個記錄，關(guān)鍵字和給定值比較都不等，則表明表中沒有所查找

4、的記錄，查找失敗。 查找算法描述如算法7.1所示。7.2.1 順序查找24 七月 2022 int Search_Seq(STable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素 i=0; ST.elem0.key=key; / 設(shè)置監(jiān)視哨 for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 retirn i; / 找不到時，i為0 / Search_Seq算法 7.124 七月 2022 在查找之前先將ST.elem0的關(guān)鍵字賦值key，則ST.elem0 在此起到了哨兵的作用。目的是避免在查找的每

5、一步都要判斷整個表是否查找完畢，即在for循環(huán)中省去了判定下標(biāo)越界的條件，提高了算法的效率。ST.elemi.key表示第i個記錄的關(guān)鍵字，ST.length表示順序表中元素的個數(shù)，key為查找的對象。24 七月 2022 查找算法的基本操作也就是“將記錄的關(guān)鍵字和給定值進(jìn)行比較”，比較的次數(shù)依賴于這個數(shù)據(jù)元素在結(jié)構(gòu)中所處的位置。 為了確定要查找的記錄位置，與給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度ASL(average search length)。對于含有n個記錄的表，平均查找長度的計算公式為：24 七月 2022 其中，Pi為查找第i個記錄的概率， ； C

6、i為在表中找到其關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進(jìn)行過比較的關(guān)鍵字個數(shù)。一般情況下,Ci等于ni+1。 24 七月 2022若查找每個元素的概率相同，即為P1=P2 = =Pn =1/n。對于等概率的查找，其平均查找長度的計算公式可簡化為：ASL = =24 七月 2022 查找算法的平均查找長度應(yīng)是查找成功時的平均查找長度與查找不成功時的平均查找長度之和的一半。如果查找不成功，比較次數(shù)為n+1。假設(shè)查找成功與不成功的可能性相同，則 ASL = = 24 七月 2022 折半查找又稱為二分查找，是一種效率較高的查找方法，它要求線性表的結(jié)點必須是按關(guān)鍵字非遞減(或非遞增)的次序排列的

7、，并采用順序結(jié)構(gòu)存儲。 折半查找的查找過程是： 首先確定待查記錄所在的范圍，然后逐漸縮小范圍直到查到或者查不到結(jié)果為止。假設(shè)指針low指向待查記錄所在范圍的下界ST.elem1，指針high指向待查記錄所在范圍的上界ST.elemST.length，指針mid指向待查記錄所在范圍的中間位置，即mid = (low + high)/2。用給定值key與mid指定的值ST.elemmid相比較。若相等，則表示查找成功；若不相等，則縮小范圍，直到新的mid值等于給定值或者查找區(qū)間的大小小于零時為止。7.2.2 有序表的折半查找24 七月 2022 【例7-1】 已知如下10個數(shù)據(jù)元素的有序表(關(guān)鍵字

8、即為數(shù)據(jù)元素的值)7，18，25，37，54，62，76，80，89，98要求查找關(guān)鍵字為25和85的數(shù)據(jù)元素。解：首先看給定值key=25的查找過程：(1)令指針low指向第1個元素，指針high指向第10個數(shù)據(jù)元素，此時mid=(1+10)/2=5。24 七月 2022 (2)key小于ST.elemmid.key，說明待查找元素若存在，必在區(qū)間low，mid-1區(qū)間內(nèi)，令指針high等于mid-1(第4個數(shù)據(jù)元素)，重新得到mid=(1+4)/2=2。24 七月 2022(3)此時key大于ST.elemmid.key，說明待查元素若存在，必在區(qū)間mid+1，high區(qū)間內(nèi)，令指針low

9、等于mid+1 (第3個數(shù)據(jù)元素)，重新得到mid=(3+4)/2=3。（4)此時ST.elemmid.key等于25，與給定值相等，查找成功，返回該元素在表中的位置即指針mid的值。24 七月 2022 由例可見，當(dāng)key值小于ST.elemmid.key，說明待查元素位置在low和mid之間，則令指針high=mid-1，在表的前半部分取中間位置的記錄比較；當(dāng)key值大于ST.elemmid.key，說明待查元素的位置在mid和high之間，則令指針low = mid + 1，在表的后半部分再取中間位置的記錄進(jìn)行比較。 折半查找的算法可描述為算法7.2。 24 七月 2022 折半查找的過

10、程可用一棵二叉樹來表示，如下圖所示，樹中每個結(jié)點表示表中的一個記錄，結(jié)點的值對應(yīng)元素的關(guān)鍵字，結(jié)點上面的編號為對應(yīng)的值在表中的位置。每個根結(jié)點對應(yīng)當(dāng)前查找區(qū)間的中間元素ST.elemmid，它的左子樹和右子樹分別對應(yīng)該區(qū)間的前半部分和后半部分，通常把此二叉樹稱為折半查找的判定樹。24 七月 202224 七月 2022 由此圖得出結(jié)論，在有序表中折半查找成功的過程就是一條從根結(jié)點到滿足條件的記錄所對應(yīng)結(jié)點的路徑，給定值同關(guān)鍵字比較的次數(shù)就等于該路徑的結(jié)點數(shù)，或該結(jié)點在判定樹上的層次數(shù)，它最多不會超過樹的深度，而具有n個結(jié)點的判定樹的深度為log2n+1，所以折半查找在查找成功時和給定值進(jìn)行比較

11、的關(guān)鍵字個數(shù)至多為log2n+1。 24 七月 2022 折半查找不成功時，如該例查找給定值為85，在折半查找的判定樹上的路徑是從根結(jié)點出發(fā)最后指向空子樹的過程，該路徑中給定值與關(guān)鍵字進(jìn)行比較的次數(shù)仍為路徑中的結(jié)點數(shù)，所以折半查找不成功時，給定值與關(guān)鍵字進(jìn)行比較的次數(shù)也不超過log2n+1。24 七月 2022 假設(shè)表中每個記錄的查找概率都相等，即Pi=1/n，則查找成功時折半查找的平均查找長度為：24 七月 2022 斐波那契查找是根據(jù)斐波那契序列的特點對表進(jìn)行分割的。斐波那契序列定義為：F0=0，F(xiàn)1=1，F(xiàn)i=Fi-1+Fi-2（i2）。 設(shè)記錄個數(shù)比某個斐波那契數(shù)小1，即n=Fi-1，

12、斐波那契查找是把關(guān)鍵字key與ST.elemFi-1.key作比較，若相等，則成功；若keyST.elemFi-1.key，則繼續(xù)在ST.elemFi-1+1至ST.elemFi-1中查找，表的元素個數(shù)是(Fi-1) - (Fi-1+1)+1=Fi-Fi-1-1=Fi-2-1。 7.2.3 斐波那契查找24 七月 2022 與折半查找相比，F(xiàn)ibonacci查找法的明顯優(yōu)點在于它只涉及加法和減法運(yùn)算，而不用除法。因為除法比加減法要占去更多的機(jī)時，所以斐波那契查找的平均性能要比折半查找好，但最壞情況下的性能（雖然仍是O(logn)）卻比折半查找差。24 七月 2022 分塊查找又稱索引順序查找，

13、是順序查找的改進(jìn)方法。分塊查找算法中，除了表本身以外，還需建立一個“索引表”。 下圖中，表中18個記錄，分成三塊，對每一塊建立一個索引項。索引項有兩項內(nèi)容：關(guān)鍵字項，其值為該塊內(nèi)最大關(guān)鍵字的值；指針項，指示該塊中第一個記錄在表中的位置。索引表按關(guān)鍵字有序排列，表或者有序排列或者分塊有序排列。所謂“分塊有序”指的是后一塊表中所有記錄的關(guān)鍵字均大于前一塊表中的最大關(guān)鍵字。7.2.4 分塊查找24 七月 2022 分塊查找可以分為兩步：首先在索引表中確定待查記錄所在塊(可以用順序或折半查找法)，然后在塊內(nèi)順序查找給定值(只能用順序查找法)。 主表被分成3塊，每塊都含有6個記錄，其中每塊的最大關(guān)鍵字分

14、別為23、50、84，索引表是按關(guān)鍵字非遞減有序排列的。假設(shè)給定值key=38，首先在索引表中順序查找，因為第一個索引項的關(guān)鍵字2338，此時可判斷若關(guān)鍵字為38的記錄存在，必定在第二塊中，第二塊的起始位置為7，則接著從主表的第7個記錄向后順序查找，直到找到關(guān)鍵字為38的記錄為止。如果此塊中沒有關(guān)鍵字為38的記錄（自第7個記錄起至第12個記錄的關(guān)鍵字和key比較都不等），則查找失敗。24 七月 2022 需要注意的是，由于索引表是按關(guān)鍵字值有序排列的，所以確定塊的查找既可以用順序查找，也可以用折半查找；而塊中的記錄是任意排列的，則在塊內(nèi)的查找只能是順序查找。 由于分塊查找的算法即為這兩種查找算

15、法的簡單合并，所以分塊查找的平均查找長度為：ASLsb=ASLb+ASLw 其中，ASLb是在索引表中確定待查記錄所在塊的平均查找長度，ASLw是在塊中查找待查記錄的平均查找長度。24 七月 2022 假設(shè)長度為n的線性表被分成m塊，每塊含有s個記錄，即m= ，并且每個記錄的查找概率都相等，則在索引表中確定塊的概率為1/m，在塊中查找待查記錄的概率為1/s。若采用順序查找的方法確定待查記錄所在塊，則分塊查找的平均查找長度為：24 七月 2022 當(dāng)采用折半查找的方法確定待查記錄所在的塊時，則分塊查找的平均查找長度為：24 七月 20227.3 動態(tài)查找表 靜態(tài)查找表一旦生成之后，所含記錄在查找

16、過程中一般是固定不變的。而動態(tài)查找表在查找過程中經(jīng)常進(jìn)行插入和刪除操作，所含記錄一直是在變化的。 動態(tài)查找表能更好地解決在查找過程中表的動態(tài)變化問題，此類表常見的有二叉排序樹、平衡二叉樹、B-樹和B+樹等。24 七月 20227.3.1 二叉排序樹 1. 二叉排序樹的定義 二叉排序樹是一種特殊的二叉樹，它的每個結(jié)點的值都大于它的左子樹上的所有結(jié)點的值，并且小于它的右子樹上的所有結(jié)點的值，同時它的左、右子樹也是二叉排序樹。特別地，空樹也是二叉排序樹。例如，對應(yīng)于關(guān)鍵字集合L=100，60，40，80，70，90，150，120，110，130，180，160，200的二叉排序樹如下圖所示。24

17、七月 2022 二叉排序樹的操作中，使用二叉鏈表作為存儲結(jié)構(gòu)，其結(jié)點結(jié)構(gòu)說明如下：typedef strict nodeKeyType key; /關(guān)鍵字的值Strict node *lchild, *rchild; /左右指針BSTNode, *BSTree;24 七月 2022 2. 二叉排序樹的查找 在二叉排序樹中查找一個關(guān)鍵字值為k的結(jié)點的基本思想是： 用給定值k與根結(jié)點關(guān)鍵字比較，如果k小于根結(jié)點關(guān)鍵字的值，則要找的結(jié)點只可能在左子樹中，所以繼續(xù)在左子樹中查找，否則將繼續(xù)在右子樹中查找，依此方法，查找下去直到查找成功或者查找失敗為止。 24 七月 2022 二叉排序樹查找的過程如下：

18、 （1）若二叉排序樹為空樹，則查找失敗。 （2）將給定的值k與根結(jié)點的關(guān)鍵字值比較，如果相等，則查找成功。 （3）若給定的值k小于根結(jié)點的關(guān)鍵字值，則在左子樹中繼續(xù)查找。 （4）否則，在右子樹中繼續(xù)查找。 其遞歸算法如算法7.3所示。 24 七月 2022BSTree SearchBST(BSTree bst, KeyType key) /在根指針bst所指的二叉排序樹中，遞歸查找某關(guān)鍵字等于key的元素，若查找/成功，則返回指向該元素的指針，否則返回空指針if (!bst)retirn NiLL;else if (bst-key = = key)retirn bst; /查找成功else i

19、f (key key)/在左子樹中繼續(xù)查找retirn SearchBST(bst-lchild, key); elseretirn SearchBST(bst-rchild, key); /在右子樹中繼續(xù)查找算法7.324 七月 2022 1.二叉排序樹中插入結(jié)點 (1)若該值小于根結(jié)點的值，則應(yīng)插入左子樹中，因此可以通過調(diào)用相同的算法（即遞歸調(diào)用插入算法）來實現(xiàn)插入左子樹的操作。 (2)若該值大于根結(jié)點的值，則可以通過遞歸調(diào)用插入算法來實現(xiàn)插入右子樹的操作。 按照這樣的方式遞歸調(diào)用若干次后，總是可以搜索到一個空子樹位置，這就是要插入的位置，可以將該結(jié)點放在該子樹上，作為該子樹的根結(jié)點并連接

20、到其父結(jié)點上。7.3.2 二叉排序樹中插入結(jié)點和構(gòu)造二叉排序樹24 七月 2022【例7-2】 要在如7.3.1中圖所示的二叉排序樹中插入值為75的結(jié)點，所執(zhí)行的操作過程如下：(1) 首先和根結(jié)點（即值為100的結(jié)點）比較，由于75比100小，故要遞歸調(diào)用插入算法將其插入左子樹（根為60）中。(2) 由于75比60大，故要遞歸調(diào)用插入算法將其插入右子樹（根為80）中。(3) 由于75比80小，故要遞歸調(diào)用插入算法將其插入左子樹（根為70）中。24 七月 2022 (4) 由于75比70大，故要遞歸調(diào)用插入算法將其插入右子樹中。此時右子樹為空，因此可以將該結(jié)點直接插入到70的右邊，作為其右孩子，

21、到此插入操作完畢。根據(jù)上面的描述，插入結(jié)點的遞歸算法，如算法7.4所示。24 七月 2022 2.構(gòu)造二叉排序樹 二叉排序樹的構(gòu)造的算法思想： 首先將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就建立一個新的結(jié)點，并插入到當(dāng)前已經(jīng)生成的二叉排序樹中，即通過多次調(diào)用二叉排序樹的插入結(jié)點的算法實現(xiàn)，這里需要注意的是，插入時比較結(jié)點的順序始終是從二叉排序樹的根結(jié)點開始的。24 七月 2022 例如，對于關(guān)鍵字集合L=45，24，53，45，12，24，90，建立一棵二叉排序樹。那么建立的過程如下圖所示。24 七月 2022 二叉排序樹的構(gòu)造算法如算法7.5所示。void Creat

22、eBST(BSTree *bst) /從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹KeyType key;*bst = NiLL;scanf (“%d”, &key);while (key != ENDKEY) /ENDKEY為自定義常量InsertBST(bst, key); /在二叉排序樹bst中插入結(jié)點key scanf (“%d”, &key);算法7.524 七月 2022 在二叉排序樹中刪除一個結(jié)點相當(dāng)于刪除有序序列中的一個結(jié)點。 二叉排序樹的刪除的算法基本思想是： 首先查找要刪除的結(jié)點，看它是否在二叉排序樹中，若不在則不做任何操作；否則，假設(shè)要刪除的結(jié)點為P，結(jié)點P的雙親結(jié)點為F，并

23、假設(shè)結(jié)點P是結(jié)點F的左孩子（右孩子的情況類似）。7.3.3 二叉排序樹中刪除結(jié)點24 七月 2022 下面分三種情況討論：(1) 若P為葉子，則可直接刪除：F-lchild = NiLL; free(P);(2)若P結(jié)點只有左子樹，或者只有右子樹，則可將P 的左子樹（或者右子樹）直接改為其雙親結(jié)點F的左子樹（或者右子樹）。即F-lchild = P-lchild (或F-rchild = P-rchild);free(P);(3)若P既有左子樹，又有右子樹，如下圖(a)所示。24 七月 2022此時有兩種處理方法： 方法1：首先找到P結(jié)點在中序遍歷序列中的直接前驅(qū)結(jié)點S，如下圖(b)所示。24

24、 七月 2022然后將P的左子樹改為F的左子樹，而將P的右子樹改為S的右子樹。結(jié)果如下圖 (c)所示。24 七月 2022 方法2：首選找到P結(jié)點在中序遍歷序列中的直接前驅(qū)結(jié)點S，然后用S結(jié)點的值替代P結(jié)點的值，再將S結(jié)點刪除，原S結(jié)點的左子樹改為S的雙親結(jié)點Q的右子樹。結(jié)果如下圖 (d)所示。24 七月 2022 二叉排序樹的刪除結(jié)點的算法如算法7.6所示。 二叉排序樹的查找效率和折半查找的效率相差不大，并且在二叉排序樹上實現(xiàn)插入和刪除結(jié)點也很簡單。 對于那些需要經(jīng)常進(jìn)行插入、刪除和查找操作的表，適宜采用二叉排序樹結(jié)構(gòu)。 二叉排序樹的平均查找長度難以確定，因為它不僅和結(jié)點的個數(shù)n有關(guān)，而且和

25、樹的形態(tài)有關(guān)。24 七月 2022 二叉排序樹越勻稱，樹的層次越少，平均查找深度越小，該樹的查找效率就越高；反之，二叉排序樹不是很勻稱，樹的層次越多，平均查找難度越大，樹的查找效率就越低。 例如一個記錄集合中有7個記錄，如果由它們組成的二叉排序樹是一棵滿二叉排序樹，如下圖(a)所示，則當(dāng)每個結(jié)點的查找概率相等的時候，平均查找長度為(1+2*2+3*4)/7=17/72.4324 七月 2022如果它們組成的二叉排序樹是一棵單支樹，如下圖(b)所示。則當(dāng)每個結(jié)點的查找概率相等的情況下，平均查找長度為(1+2+3+4+5+6+7)/7=28/7=4。在隨機(jī)的情況下，對于一個具有n個結(jié)點的二叉排序樹

26、，平均查找長度為O(log2n)，在最壞的情況下為(n+1)/2。24 七月 20227.4 哈希表 如果能在記錄的存儲位置和它的關(guān)鍵字之間建立起某種直接聯(lián)系，那么在查找時就能不進(jìn)行比較或者只進(jìn)行很少次數(shù)的比較就能找到所要查找的結(jié)點。哈希表查找就是基于這種思想提出來的。7.4.1 哈希表與哈希方法24 七月 2022 在查找過程中，最理想的情況是不經(jīng)過任何比較，一次存取便能夠得到所查的記錄，則必須在記錄的存儲位置和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系f，使每個關(guān)鍵字和結(jié)構(gòu)中一個唯一的存儲位置相對應(yīng)。 查找時，只要根據(jù)這個對應(yīng)關(guān)系f找到給定值k的象f (k)。24 七月 2022 若結(jié)構(gòu)中存在關(guān)

27、鍵字和k相等的記錄，則必定在f (k)的存儲位置上，那么不需要進(jìn)行比較就可以直接取得所查記錄。 這個對應(yīng)關(guān)系f為哈希（hash）函數(shù)。 例如，一組關(guān)鍵字序列為25，22，36，40，43，26，57，選取哈希函數(shù)h (k) = k mod 13，從而可得到每個記錄所對應(yīng)的哈希地址分別如下：24 七月 2022h(25) = 25 mod 13 = 12 h(22) = 22 mod 13 = 9h(36) = 36 mod 13 = 10 h(40) = 40 mod 13 = 1h(43) = 43 mod 13 = 4 h(26) = 26 mod 13 = 0h(57) = 57 mod

28、 13 = 5現(xiàn)在則可以將這些關(guān)鍵字散列存儲到一個表長為13的哈希表中，如下表所示。24 七月 2022 要從哈希表中檢索某關(guān)鍵字所對應(yīng)的記錄，只要依據(jù)哈希函數(shù)h(k)求出函數(shù)值，然后以該值作為存儲單元的地址，從對應(yīng)的存儲單元中取得該記錄即可，可以不用進(jìn)行關(guān)鍵字的比較操作。 在實際應(yīng)用中，通?？赡艹霈F(xiàn)不同的關(guān)鍵字值的哈希函數(shù)計算出的哈希地址相同的情況，這種情況稱為沖突。24 七月 2022 發(fā)生沖突的關(guān)鍵字稱為哈希函數(shù)的同義詞，由同義詞引起的沖突叫做同義詞沖突。 沖突是不可避免的，因為通常關(guān)鍵字的取值集合遠(yuǎn)遠(yuǎn)大于表空間的地址集，只能盡量地減少沖突的發(fā)生。 在構(gòu)造哈希表的時候，就面臨兩個問題：

29、一是構(gòu)造較好的哈希函數(shù)，使關(guān)鍵字集合中的元素盡可能均勻地分布到地址空間中，減少沖突的發(fā)生。 一是研究解決沖突的方法。24 七月 2022 1. 除留余數(shù)法 除留余數(shù)法是用數(shù)據(jù)元素關(guān)鍵字k除以哈希表長度m所得到的余數(shù)作為哈希地址的方法。除留余數(shù)法的哈希函數(shù)h(k)為：h(k) = kmod m 這種方法的關(guān)鍵是選好哈希表長度m，使得數(shù)據(jù)元素集合中的每一個關(guān)鍵字通過該哈希函數(shù)映射到m個內(nèi)存單元的任意地址上的概率相等，從而盡可能減少發(fā)生沖突的可能性。7.4.2 常用的構(gòu)造哈希函數(shù)的方法24 七月 2022 2. 直接定址法 當(dāng)關(guān)鍵字是整型數(shù)時，可以取關(guān)鍵字本身或者它的線性函數(shù)作為它的哈希地址。即：H

30、(k) = k 或者H(k) = ak+b (a, b為常數(shù))例如，某社區(qū)對所轄范圍內(nèi)的居民家庭進(jìn)行適齡學(xué)前教育情況普查，統(tǒng)計得出的調(diào)查表中詳細(xì)記錄了學(xué)前兒童的出生年月、性別等信息，若以出生年月作為關(guān)鍵字，哈希函數(shù)就可以取關(guān)鍵字本身。 24 七月 2022 3. 數(shù)字分析法 數(shù)字分析法是取數(shù)據(jù)元素關(guān)鍵字中某些取值較均勻的數(shù)字位作為哈希地址的方法。它只適用于所有關(guān)鍵字值已知的情況。由于此時所有數(shù)據(jù)元素的關(guān)鍵字都已知，可以對關(guān)鍵字中每一位的取值分布情況作出分析，從而可以把一個很大的關(guān)鍵字取值區(qū)間轉(zhuǎn)化為一個較小的關(guān)鍵字取值區(qū)間。 24 七月 2022例如，要構(gòu)造一個數(shù)據(jù)元素個數(shù)n = 80、哈希表長

31、度m = 100的哈希表。這里只給出其中8個關(guān)鍵字進(jìn)行分析，8個關(guān)鍵字值如下所示：k1 = 61317602 k2 = 61326875 k3 = 62739628k4 = 61343634 k5 = 62706816 k6 = 62774638k7 = 61381262 k8 = 6139422024 七月 2022分析上述8個關(guān)鍵字可知，關(guān)鍵字從左到右的第1、2、3、6位取值較集中，不宜作為哈希地址，剩余的第4、5、7、8位較均勻，可選取其中的兩位作為哈希地址。設(shè)選取最后兩位作為哈希地址，則這8個關(guān)鍵字的哈希地址分別為：2，75，28，34，16，38，62，20。24 七月 2022 通

32、常處理沖突的方法可以分為兩大類：開放定址法鏈地址法。 1. 開放定址法 基本思想： 當(dāng)沖突發(fā)生時，使用某種方法在表中形成一個搜索序列，沿著這個序列逐一搜尋各個存儲單元，直到找到給定的關(guān)鍵字或者搜尋到一個空位置為止。7.4.3 處理沖突的方法24 七月 2022 描述： Hi(k) = (H(k) + di) mod m (i = 1,2, , k(km-1) 其中，H(k)為哈希函數(shù)，m為哈希表長度，di為再次搜尋時的增量序列。 使用該種方法時，首先要計算出直接哈希地址H(k)，如果發(fā)現(xiàn)該單元已經(jīng)被占用，繼續(xù)向下搜尋地址為H(k) + d1的單元，倘若也被占用，再繼續(xù)向下搜尋地址為H(k) +

33、 d2的單元，直到找到空的單元為止，此時可以將關(guān)鍵字k的記錄放入該單元中。24 七月 2022 對于增量di可以有不同的選取方法：(1) di = 1, 2, 3, , m-1(2) di = 12, -12, 22, -22, 32, , k2, -k2 (km/2)(3) di = 隨機(jī)數(shù)序列 當(dāng)增量di采用上面三種不同的方法取值時，分別稱為線性探測再散列、二次探測再散列和隨機(jī)探測再散列。 線性探測再散列方法的特點是當(dāng)沖突發(fā)生的時候，順序查找表中下一個單元，直到找出一個空單元或查遍全表。24 七月 2022 二次探測再散列方法的特點是當(dāng)沖突發(fā)生時，在表的左右進(jìn)行跳躍式探測，比較靈活。 例如

34、，已知哈希表中已經(jīng)存在關(guān)鍵字47、26、60，哈希表長度m = 11，哈希函數(shù)為H(k) = k % 11，則H(47) = 3，H(26) = 4，H(60) = 5，如圖(a)所示。24 七月 2022 假設(shè)下一個關(guān)鍵字為69，則H(69) = 3，與47沖突。 如果用線性探測再散列方法處理沖突，下一個哈希地址為H1 = (3+1) % 11 = 4，仍然沖突；再找下一個哈希地址為H2 = (3+2) % 11 = 5，還是沖突；繼續(xù)找下一個哈希地址為H3 = (3+3) % 11 = 6，此時不再沖突，將69填入6號單元，如圖 (b)所示。 24 七月 2022 用二次探測再散列方法構(gòu)造

35、哈希表時，下一個哈希地址為H1 = (3+12) % 11 = 4，仍然沖突；再找下一個哈希地址為H2 = (3-12) % 11 = 2，此時不再沖突，將69填入2號單元，如圖 (c)所示。24 七月 2022 如果用隨機(jī)探測再散列方法處理沖突，且隨機(jī)序列為2, 5, 9, ，則下一個哈希地址為H1 = (3+2) % 11 = 5，仍然沖突；再找下一個哈希地址為H2 = (3+5) % 11 = 8，此時不再沖突，將69填入8號單元，如圖(d)所示。24 七月 2022 2.鏈地址法 鏈地址法是將具有相同哈希地址的記錄放在同一個線性鏈表中，哈希地址為i的記錄組成的單鏈表的頭指針將被存放在哈

36、希表中的第i個元素中。 例如，已知一組關(guān)鍵字為25, 6, 82, 21, 71, 36, 47, 17, 58, 14, 79，則按照哈希函數(shù)H(k ) = k mod 13和鏈地址法處理沖突構(gòu)造所得到的哈希表如右圖所示。24 七月 2022 與開放定址法相比，鏈地址法不會產(chǎn)生堆積現(xiàn)象，從而能夠使得平均查找長度較短。 當(dāng)表長無法確定時，能夠通過采用這種方法，達(dá)到動態(tài)申請存儲空間、節(jié)省空間消耗的目的，并且在單鏈表上進(jìn)行刪除結(jié)點的操作很容易實現(xiàn)。 但這種方法中的指針需要分配空間，故而當(dāng)沖突現(xiàn)象不太嚴(yán)重、結(jié)點規(guī)模較小的時候，采用開放定址法將較為節(jié)省空間。24 七月 2022 在哈希表上查找關(guān)鍵字k

37、的記錄方法： 由建立哈希表時的哈希函數(shù)H(k)根據(jù)關(guān)鍵字k值求出直接哈希地址，若該地址記錄為空，則查找失敗；若該地址記錄不為空，將關(guān)鍵字k值與該地址的記錄的關(guān)鍵字相比較，二者相等查找成功，否則就按照哈希表建立時采用的解決沖突的辦法，繼續(xù)在下一個哈希存儲地址中查找。7.4.4 哈希表的查找分析24 七月 2022 由于沖突的存在，哈希法仍然需要進(jìn)行關(guān)鍵字比較，因此仍需要用平均查找長度來評價哈希法的查找性能。 哈希法中影響關(guān)鍵字比較次數(shù)的因素有3個： 哈希函數(shù) 處理沖突的方法 哈希表的裝填因子 哈希表的裝填因子的定義如下：= 表中的記錄數(shù)/哈希表的長度24 七月 2022其中，標(biāo)志著表的裝滿程度。

38、越小，發(fā)生沖突的可能性就越?。辉酱?，表就越滿，從而發(fā)生沖突的可能性就越大，查找進(jìn)行得就越慢。 對同樣一組關(guān)鍵字，設(shè)定相同的哈希函數(shù)，則不同的處理沖突的方法得到的哈希表不同，它們的平均查找長度也不同。24 七月 2022 線性探測法在處理沖突的過程中容易產(chǎn)生記錄的二次聚集，使得哈希地址不相同的記錄又產(chǎn)生新的沖突。 鏈地址法處理沖突不會產(chǎn)生類似的情況，因為哈希地址不同的記錄在不同的鏈表中。 一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。24 七月 2022線性探測法哈希表查找長度成功時的平均查找長度為：隨機(jī)探測法、二次探測再散列和再哈希的哈希表查找成功時的平均查找長度為：24 七月 2022 鏈地址法處理沖突的哈希表查找成功時的平均查找長度為： 哈希表在查找不成功時的平均查找長度為：查找不成功時需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值。 不同的處理沖突方法構(gòu)成的哈希表查找不成功時的平均查找長度也不相同。24 七月 20227.5 實例解析【例