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

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

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

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

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; / 找不到時(shí)，i為0 / Search_Seq算法 7.124 七月 2022 在查找之前先將ST.elem0的關(guān)鍵字賦值key，則ST.elem0 在此起到了哨兵的作用。目的是避免在查找的每

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

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

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

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

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

11、的關(guān)鍵字個(gè)數(shù)至多為log2n+1。 24 七月 2022 折半查找不成功時(shí)，如該例查找給定值為85，在折半查找的判定樹(shù)上的路徑是從根結(jié)點(diǎn)出發(fā)最后指向空子樹(shù)的過(guò)程，該路徑中給定值與關(guān)鍵字進(jìn)行比較的次數(shù)仍為路徑中的結(jié)點(diǎn)數(shù)，所以折半查找不成功時(shí)，給定值與關(guān)鍵字進(jìn)行比較的次數(shù)也不超過(guò)log2n+1。24 七月 2022 假設(shè)表中每個(gè)記錄的查找概率都相等，即Pi=1/n，則查找成功時(shí)折半查找的平均查找長(zhǎng)度為：24 七月 2022 斐波那契查找是根據(jù)斐波那契序列的特點(diǎn)對(duì)表進(jìn)行分割的。斐波那契序列定義為：F0=0，F(xiàn)1=1，F(xiàn)i=Fi-1+Fi-2（i2）。 設(shè)記錄個(gè)數(shù)比某個(gè)斐波那契數(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中查找，表的元素個(gè)數(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)點(diǎn)在于它只涉及加法和減法運(yùn)算，而不用除法。因?yàn)槌ū燃訙p法要占去更多的機(jī)時(shí)，所以斐波那契查找的平均性能要比折半查找好，但最壞情況下的性能（雖然仍是O(logn)）卻比折半查找差。24 七月 2022 分塊查找又稱(chēng)索引順序查找，

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、鍵字和k相等的記錄，則必定在f (k)的存儲(chǔ)位置上，那么不需要進(jìn)行比較就可以直接取得所查記錄。 這個(gè)對(duì)應(yīng)關(guān)系f為哈希（hash）函數(shù)。 例如，一組關(guān)鍵字序列為25，22，36，40，43，26，57，選取哈希函數(shù)h (k) = k mod 13，從而可得到每個(gè)記錄所對(duì)應(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)鍵字散列存儲(chǔ)到一個(gè)表長(zhǎng)為13的哈希表中，如下表所示。24 七月 2022 要從哈希表中檢索某關(guān)鍵字所對(duì)應(yīng)的記錄，只要依據(jù)哈希函數(shù)h(k)求出函數(shù)值，然后以該值作為存儲(chǔ)單元的地址，從對(duì)應(yīng)的存儲(chǔ)單元中取得該記錄即可，可以不用進(jìn)行關(guān)鍵字的比較操作。 在實(shí)際應(yīng)用中，通?？赡艹霈F(xiàn)不同的關(guān)鍵字值的哈希函數(shù)計(jì)算出的哈希地址相同的情況，這種情況稱(chēng)為沖突。24 七月 2022 發(fā)生沖突的關(guān)鍵字稱(chēng)為哈希函數(shù)的同義詞，由同義詞引起的沖突叫做同義詞沖突。 沖突是不可避免的，因?yàn)橥ǔｊP(guān)鍵字的取值集合遠(yuǎn)遠(yuǎn)大于表空間的地址集，只能盡量地減少?zèng)_突的發(fā)生。 在構(gòu)造哈希表的時(shí)候，就面臨兩個(gè)問(wèn)題：

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

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

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

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

33、 d2的單元，直到找到空的單元為止，此時(shí)可以將關(guān)鍵字k的記錄放入該單元中。24 七月 2022 對(duì)于增量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采用上面三種不同的方法取值時(shí)，分別稱(chēng)為線性探測(cè)再散列、二次探測(cè)再散列和隨機(jī)探測(cè)再散列。 線性探測(cè)再散列方法的特點(diǎn)是當(dāng)沖突發(fā)生的時(shí)候，順序查找表中下一個(gè)單元，直到找出一個(gè)空單元或查遍全表。24 七月 2022 二次探測(cè)再散列方法的特點(diǎn)是當(dāng)沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，比較靈活。 例如

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

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

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

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

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