數(shù)據(jù)結(jié)構(gòu)(C語言版)第9章查找

1、教學(xué)內(nèi)容教學(xué)內(nèi)容 靜態(tài)查找表及查找算法靜態(tài)查找表及查找算法 動(dòng)態(tài)查找表及查找算法動(dòng)態(tài)查找表及查找算法 哈希表及查找算法哈希表及查找算法 基本概念基本概念 查找表：查找表：由一些具有相同可辨認(rèn)特性的數(shù)據(jù)元素由一些具有相同可辨認(rèn)特性的數(shù)據(jù)元素 （或記錄）構(gòu)成的集合。（或記錄）構(gòu)成的集合。 對(duì)查找表經(jīng)常進(jìn)行的操作：對(duì)查找表經(jīng)常進(jìn)行的操作： 1、某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素是否在查找表中；數(shù)據(jù)元素是否在查找表中； 2、某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素的各種屬性；數(shù)據(jù)元素的各種屬性； 3、在查找表中、在查找表中插入插入一個(gè)數(shù)據(jù)元素；一個(gè)數(shù)據(jù)元素； 4、刪除刪除查找表中的某個(gè)數(shù)據(jù)元素。查找表中的某個(gè)數(shù)

2、據(jù)元素。 靜態(tài)查找表：靜態(tài)查找表：作作“”（檢索）操作的查找表。（檢索）操作的查找表。 動(dòng)態(tài)查找表：動(dòng)態(tài)查找表：作作“插入插入”和和“刪除刪除”操作的查找表。操作的查找表。 關(guān)鍵字（關(guān)鍵字（key）：）：數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以（識(shí)別）一個(gè)數(shù)據(jù)元素。（識(shí)別）一個(gè)數(shù)據(jù)元素。主關(guān)鍵字：主關(guān)鍵字：可以可以標(biāo)示一個(gè)數(shù)據(jù)元素的關(guān)鍵字。標(biāo)示一個(gè)數(shù)據(jù)元素的關(guān)鍵字。 不同記錄的主關(guān)鍵字不同。不同記錄的主關(guān)鍵字不同。 次關(guān)鍵字：次關(guān)鍵字：可以標(biāo)示若干個(gè)數(shù)據(jù)元素的關(guān)鍵字?？梢詷?biāo)示若干個(gè)數(shù)據(jù)元素的關(guān)鍵字。 查找（檢索）：查找（檢索）：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)關(guān)

3、鍵根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)關(guān)鍵 字等于給定值的記錄或數(shù)據(jù)元素。字等于給定值的記錄或數(shù)據(jù)元素。例：例：學(xué)號(hào)、身份證號(hào)學(xué)號(hào)、身份證號(hào) 例：例：性別性別 查找成功：查找成功：即找到滿足條件的記錄。即找到滿足條件的記錄。 此時(shí)作為結(jié)果可報(bào)告該記錄在查找表中的位置，此時(shí)作為結(jié)果可報(bào)告該記錄在查找表中的位置， 也可給出該記錄的全部信息。也可給出該記錄的全部信息。 查找不成功查找不成功：即未找到滿足條件的記錄。即未找到滿足條件的記錄。 作為結(jié)果可給出一個(gè)作為結(jié)果可給出一個(gè)“空空”記錄或記錄或“空空”指針。指針。 可以想像的到，如果能有目標(biāo)地進(jìn)行查找肯定比在一大堆可以想像的到，如果能有目標(biāo)地進(jìn)行查

4、找肯定比在一大堆 事物中瞎摸要有效得多，因此為提高查找效率，一個(gè)辦法就是事物中瞎摸要有效得多，因此為提高查找效率，一個(gè)辦法就是 在構(gòu)造查找表時(shí)，在構(gòu)造查找表時(shí)，在集合中的數(shù)據(jù)元素之間人為地加上某種確在集合中的數(shù)據(jù)元素之間人為地加上某種確 定的約束關(guān)系定的約束關(guān)系。本章正是討論查找表的各種組織方法及其查找。本章正是討論查找表的各種組織方法及其查找 過程的實(shí)施。過程的實(shí)施。 由于對(duì)查找表由于對(duì)查找表“集合集合”中的數(shù)據(jù)元素之間的關(guān)系未作中的數(shù)據(jù)元素之間的關(guān)系未作 限定，故在集合中查詢或檢索一個(gè)限定，故在集合中查詢或檢索一個(gè)“特定的特定的”數(shù)據(jù)元素時(shí)，無數(shù)據(jù)元素時(shí)，無 規(guī)律可循，只能對(duì)集合中的元素一

5、一加以辨認(rèn)直至找到為止。規(guī)律可循，只能對(duì)集合中的元素一一加以辨認(rèn)直至找到為止。 而這樣的而這樣的“查詢查詢”或或“檢索檢索”是任何計(jì)算機(jī)應(yīng)用系統(tǒng)中使用頻是任何計(jì)算機(jī)應(yīng)用系統(tǒng)中使用頻 度都很高的操作，因此設(shè)法提高查找表的查找效率，是本章討度都很高的操作，因此設(shè)法提高查找表的查找效率，是本章討 論問題的出發(fā)點(diǎn)。論問題的出發(fā)點(diǎn)。 9.1 靜態(tài)查找表靜態(tài)查找表 靜態(tài)查找表有多種不同的表示方法靜態(tài)查找表有多種不同的表示方法 順順 序序 表表線性鏈表線性鏈表#define LIST_INIT_SIZE 100 / 線性表存儲(chǔ)空間的初始分配量線性表存儲(chǔ)空間的初始分配量 typedef struct Elem

6、Type elemLIST_INIT_SIZE; int length; / 當(dāng)前長度當(dāng)前長度 SqList; typedef struct ElemType * elem; int length; / 表長度表長度 SSTable; 靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu) 當(dāng)靜態(tài)查找表用不同的方法表示時(shí)，實(shí)現(xiàn)查找操作的當(dāng)靜態(tài)查找表用不同的方法表示時(shí)，實(shí)現(xiàn)查找操作的 方法也不同。方法也不同。 9.1.1 順序表的查找（順序查找）順序表的查找（順序查找） 順順 序序 表表線性鏈表線性鏈表表示靜態(tài)查找表表示靜態(tài)查找表 順序查找順序查找 順序查找：順序查找：從表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)

7、鍵字和給從表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給 定值的比較。定值的比較。 查找過程：查找過程： 0 1 2 3 4 5 6 7 8 9 10 11找找64 5 37 19 21 13 56 64 92 88 80 75 64 算法描述：算法描述： int Search_Seq(SSTable ST, KeyType key) for (i = ST.length ; ST.elemi.key != key ; - - i ) if (i = 1000 時(shí)，此改進(jìn)能使進(jìn)行時(shí)，此改進(jìn)能使進(jìn)行 一次查找所需的平均一次查找所需的平均 時(shí)間幾乎減少一半。時(shí)間幾乎減少一半。 60 監(jiān)視哨監(jiān)視哨查找方法評(píng)

8、價(jià)：查找方法評(píng)價(jià)： ；空間復(fù)雜度；算法本身復(fù)雜程度。；空間復(fù)雜度；算法本身復(fù)雜程度。 因?yàn)椴檎宜惴ǖ幕静僮鳛椋阂驗(yàn)椴檎宜惴ǖ幕静僮鳛椋簩⒂涗浀年P(guān)鍵字同給定值將記錄的關(guān)鍵字同給定值 進(jìn)行比較，進(jìn)行比較，所以，通常以所以，通常以作為衡量查找算法好壞的依據(jù)。作為衡量查找算法好壞的依據(jù)。 平均查找長度平均查找長度 ASL (Average Search Length)：為確定記為確定記 錄在表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的錄在表中的位置，需要與給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)的 期望值期望值叫做查找算法的叫做查找算法的平均查找長度平均查找長度。 找到第找到第 i 個(gè)記錄個(gè)記錄 需比較的

9、次數(shù)。需比較的次數(shù)。 niiiCPASL1 對(duì)含有對(duì)含有 n 個(gè)記錄的表，查找個(gè)記錄的表，查找時(shí)：時(shí)： 第第 i 個(gè)記錄被個(gè)記錄被 查找的概率。查找的概率。 11 niiP0 1 2 3 4 5 6 7 8 9 10 11 5 37 19 21 13 56 64 92 88 80 75 11 10 9 8 7 6 5 4 3 2 1 順序查找的平均查找長度：順序查找的平均查找長度： ASL=nP1+ (n-1)P2+ 2Pn-1 +Pn 假設(shè)每個(gè)記錄的查找概率相等：假設(shè)每個(gè)記錄的查找概率相等：Pi =1/n 則：則： niniiiSSninnCPASL1121)1(1 查找查找時(shí)，關(guān)鍵字的比較

10、次數(shù)總是時(shí)，關(guān)鍵字的比較次數(shù)總是 n + 1 次。次。 0 1 2 3 4 5 6 7 8 9 10 11 5 37 19 21 13 56 64 92 88 80 75 11 10 9 8 7 6 5 4 3 2 1 假設(shè)：假設(shè)：1、查找成功與不成功的、查找成功與不成功的概率相同概率相同。 2、每個(gè)記錄被查找的、每個(gè)記錄被查找的概率相同概率相同。 則：則：平均查找長度（成功與不成功的平均查找長度之和）為平均查找長度（成功與不成功的平均查找長度之和）為 nnninnASL1iSS4)1(3)1(21)1(21 1、記錄的查找概率不相等時(shí)如何提高查找效率？、記錄的查找概率不相等時(shí)如何提高查找效率

11、？ 查找表存儲(chǔ)記錄原則：查找表存儲(chǔ)記錄原則： 1)、查找概率越高比較次數(shù)越少；查找概率越高比較次數(shù)越少； 2)、查找概率越低，比較次數(shù)較多。、查找概率越低，比較次數(shù)較多。 2、記錄的查找概率無法測定時(shí)如何提高查找效率？、記錄的查找概率無法測定時(shí)如何提高查找效率？ 方法：方法： 1)、在每個(gè)記錄中設(shè)一個(gè)訪問頻度域；在每個(gè)記錄中設(shè)一個(gè)訪問頻度域； 2)、始終保持記錄按非遞增有序的次序排列；、始終保持記錄按非遞增有序的次序排列； 3)、每次查找后均將剛查到的記錄直接移至表頭。、每次查找后均將剛查到的記錄直接移至表頭。 9.1.2 有序表的查找（折半查找）有序表的查找（折半查找） 有序表表示靜態(tài)查找表

12、有序表表示靜態(tài)查找表 折半查找：折半查找：每次將待查記錄所在區(qū)間縮小一半。每次將待查記錄所在區(qū)間縮小一半。 查找過程：查找過程： 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找找21lowhighmidhighmid lowmid 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找找63 lowhighmid lowmidhighmidhighHigh low 折半查找折半查找 算法描述：算法描述： int Search_Bin ( SSTable ST, Key

13、Type key ) / 在有序表在有序表 ST 中折半查找其關(guān)鍵字等于中折半查找其關(guān)鍵字等于 key 的數(shù)據(jù)元素。的數(shù)據(jù)元素。 / 若找到，則函數(shù)值為該元素在表中的位置，否則為若找到，則函數(shù)值為該元素在表中的位置，否則為0。 low = 1 ; high = ST.length ; / 置區(qū)間初值置區(qū)間初值 while (low = high) mid = (low + high) / 2 ; if (ST.elemmid.key = key) return mid ; / 找到待查元素找到待查元素 else if (key ST.elemmid.key) high = mid - 1; /

14、 繼續(xù)在前半?yún)^(qū)間進(jìn)行查找繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1; / 繼續(xù)在后半?yún)^(qū)間進(jìn)行查找繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return 0 ; / 順序表中不存在待查元素順序表中不存在待查元素 / Search_Bin 性能分析：性能分析： 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 1 2 2 3 3 3 3 4 4 4 4 Ci i 6 3 9 1 4 7 10 2 5 8 11 判定樹判定樹 表中一個(gè)記錄表中一個(gè)記錄 比較次數(shù)比較次數(shù) = = 路徑上的結(jié)點(diǎn)數(shù)路徑上的結(jié)點(diǎn)數(shù) 比較次數(shù)比較次數(shù) = = 結(jié)點(diǎn)結(jié)

15、點(diǎn) 4 4 的層數(shù)的層數(shù) 比較次數(shù)比較次數(shù) 樹的深度樹的深度 log2n +1 比較次數(shù)比較次數(shù) = = 路徑上的內(nèi)部結(jié)點(diǎn)數(shù)路徑上的內(nèi)部結(jié)點(diǎn)數(shù) 比較次數(shù)比較次數(shù) log2n +1 -13-46-79-10 1-22-34-55-67-88-910-1111-平均查找長度平均查找長度ASL（成功時(shí)）：（成功時(shí)）： )50(1)1(log1)1(log1211221111 n n nnn jncncpASLhjjniiniiibs：則則 設(shè)表長設(shè)表長 n = 2h 1，則，則 h = log2(n +1)（此時(shí)，判定樹為深度（此時(shí)，判定樹為深度= h 的滿二叉樹），且表中每個(gè)記錄的查找概率相等：的

16、滿二叉樹），且表中每個(gè)記錄的查找概率相等：Pi = 1/n。 第第 j 層的每個(gè)結(jié)點(diǎn)要比較的次數(shù)層的每個(gè)結(jié)點(diǎn)要比較的次數(shù) 第第 j 層層 結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù) 第第 j 層要比層要比 較的總次數(shù)較的總次數(shù) 折半查找折半查找：效率比順序查找高。效率比順序查找高。 折半查找折半查找：只適用于只適用于，且限于，且限于（對(duì)線性鏈表無效）。（對(duì)線性鏈表無效）。 21SSnASL查查389.1.4 索引順序表的查找（分塊查找）索引順序表的查找（分塊查找） 1、將表分成幾塊，且表或者有序，或者將表分成幾塊，且表或者有序，或者； 2、建立、建立“索引表索引表”（每個(gè)結(jié)點(diǎn)含有最大關(guān)鍵字域和指向本（每個(gè)結(jié)點(diǎn)含有最大關(guān)鍵字

17、域和指向本 塊第一個(gè)結(jié)點(diǎn)的指針，且按關(guān)鍵字有序）。塊第一個(gè)結(jié)點(diǎn)的指針，且按關(guān)鍵字有序）。 若若 i j，則第，則第 j 塊中所塊中所 有記錄的關(guān)鍵字均大于有記錄的關(guān)鍵字均大于 第第 i 塊中的最大關(guān)鍵字。塊中的最大關(guān)鍵字。 1 7 1322 48 86索引表索引表 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53查找過程：查找過程：先確定待查記錄所在塊（

18、順序或折半查找），再在塊先確定待查記錄所在塊（順序或折半查找），再在塊 內(nèi)查找（順序查找）。內(nèi)查找（順序查找）。 性能分析：性能分析： 平均查找長度：平均查找長度： ASLbs= Lb + Lw 在塊中查找元素的平均查找長度在塊中查找元素的平均查找長度 在索引表中查找所在塊的平均查找長度在索引表中查找所在塊的平均查找長度 1)(2121211111 ssnsbisjbASLsibjbs 若將長度為若將長度為 n 的表均分成的表均分成 b 塊，每塊含塊，每塊含 s 個(gè)記錄個(gè)記錄 (b = n/s )； 并設(shè)表中每個(gè)記錄的查找概率相等，則每塊查找的概率為并設(shè)表中每個(gè)記錄的查找概率相等，則每塊查找的

19、概率為 1/b， 塊中塊中每個(gè)記錄的查找概率為每個(gè)記錄的查找概率為 1/s。 2)1(log211)1(log22ssnsbASLbs 。取取最最小小值值時(shí)時(shí)，取取可可以以證證明明，當(dāng)當(dāng)1 nASL n s bs(1)、用順序查找確定所在塊：、用順序查找確定所在塊： (2)、用折半查找確定所在塊：、用折半查找確定所在塊： 查找方法比較查找方法比較 順序查找折半查找分塊查找ASL 最大最小中間表結(jié)構(gòu)有序表、無序表有序表分塊有序存儲(chǔ)結(jié)構(gòu)順序表、線性鏈表順序表順序表、線性鏈表9.1.3 靜態(tài)樹表的查找靜態(tài)樹表的查找 折半查找的平均查找長度的前提是查找表中各個(gè)記錄被查找折半查找的平均查找長度的前提是查

20、找表中各個(gè)記錄被查找 的的。如果表中各個(gè)記錄被查找的。如果表中各個(gè)記錄被查找的概率不同概率不同，那么折半查，那么折半查 找是否是在有序表中進(jìn)行查找的最好選擇呢？找是否是在有序表中進(jìn)行查找的最好選擇呢？ 關(guān)鍵字關(guān)鍵字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3 例：例： CADBEBADCEASL=2 0.2+3 0.3+1 0.05+2 0.3+3 0.15= 改變查找順序（即：改變改變查找順序（即：改變 Ci 的值）的值） Ci： 2 1 3 2 3 ASL=2 0.2+1 0.3+3 0.05+2 0.3+3 0.15=1.9 若只

21、考慮查找成功的情況，并為討論方便起見引入常量若只考慮查找成功的情況，并為討論方便起見引入常量 c， 令令 wi = cpi (i = 1, 2, , n)，（，（pi 為結(jié)點(diǎn)被查找的概率），則稱為結(jié)點(diǎn)被查找的概率），則稱 wi 為結(jié)點(diǎn)的為結(jié)點(diǎn)的“權(quán)權(quán)”，并且稱：，并且稱： 為為帶權(quán)內(nèi)路徑長度之和帶權(quán)內(nèi)路徑長度之和。 其中：其中： n 為二叉樹（判定樹）上的結(jié)點(diǎn)個(gè)數(shù)（即：有序表的長為二叉樹（判定樹）上的結(jié)點(diǎn)個(gè)數(shù)（即：有序表的長 度）；度）；hi 為第為第 i 個(gè)結(jié)點(diǎn)在二叉樹上的層次。個(gè)結(jié)點(diǎn)在二叉樹上的層次。 niiihwPH1 稱稱 PH 值取最小的二叉樹為值取最小的二叉樹為“” (Static

22、 Optimal Nearly Search Tree)。 若某個(gè)二叉樹的若某個(gè)二叉樹的 PH 值在所有具有同樣權(quán)值的二叉樹中近似值在所有具有同樣權(quán)值的二叉樹中近似 為最小，則稱它為為最小，則稱它為“” (Nearly Optimal Search Tree)。 （近似近似最優(yōu)查找樹）最優(yōu)查找樹） 假設(shè)按關(guān)鍵字從小到大有序排列的記錄序列為：假設(shè)按關(guān)鍵字從小到大有序排列的記錄序列為： (rl , rl+1, , rh) 其中其中 rl .key rl+1.key data.key) return(T); else if ( key data.key) return(SearchBST (T- l

23、child, key); / 在左子樹中繼續(xù)查找在左子樹中繼續(xù)查找 else return(SearchBST (T- rchild, key); / 在右子樹中繼續(xù)查找在右子樹中繼續(xù)查找 / SearchBST2. 二叉排序樹的插入和刪除二叉排序樹的插入和刪除 1)、若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)；、若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為根結(jié)點(diǎn)； 2)、若二叉排序樹非空，則新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)、若二叉排序樹非空，則新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié) 點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)結(jié)點(diǎn) 的左孩子或右孩子結(jié)點(diǎn)。的左

24、孩子或右孩子結(jié)點(diǎn)。 例：例： 插入插入 40， 插入插入 50， 40 50 45 12 53 3 37 61 99 24 90 78 二叉排序樹的插入二叉排序樹的插入 是是 37 的右孩子。的右孩子。 是是 53 的左孩子。的左孩子。 查找算法：查找算法：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹中遞歸地查找其關(guān)鍵字等于所指二叉排序樹中遞歸地查找其關(guān)鍵字等于 key / 的數(shù)據(jù)元素，若查找成功，則指針的數(shù)據(jù)元素，若查找成功，則指針 p 指向該數(shù)據(jù)元素結(jié)點(diǎn)，指向該

25、數(shù)據(jù)元素結(jié)點(diǎn)， / 并返回并返回 TRUE，否則指針，否則指針 p 指向查找路徑上訪問的最后一個(gè)指向查找路徑上訪問的最后一個(gè) / 結(jié)點(diǎn)并返回結(jié)點(diǎn)并返回 FALSE，指針，指針 f 指向指向 T 的雙親，其初始調(diào)用值的雙親，其初始調(diào)用值 / 為為NULL。 if (!T) p = f; return FALSE; / 查找不成功查找不成功 else if ( key = T- data.key ) p = T; return TRUE; / 查找成功查找成功 else if ( key data.key ) SearchBST (T - lchild, key, T, p ); / 在左子樹中查

26、找在左子樹中查找 else SearchBST (T- rchild, key, T, p ); / 在右子樹中查找在右子樹中查找 / SearchBST 插入算法：插入算法： Status Insert BST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹當(dāng)二叉排序樹 T 中不存在關(guān)鍵字等于中不存在關(guān)鍵字等于 e.key 的數(shù)據(jù)元素時(shí)，的數(shù)據(jù)元素時(shí)， / 插入插入 e 并返回并返回 TRUE，否則返回，否則返回 FALSEif (!SearchBST ( T, e.key, NULL, p ) / 查找不成功查找不成功 s = (BiTree) malloc (s

27、izeof (BiTNode); s - data = e; s - lchild = s - rchild = NULL; if ( !p ) T = s; / 插入插入 s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn) else if ( e.key data.key ) p - lchild = s; / 插入插入 s 為左孩子為左孩子 else p - rchild = s; / 插入插入 s 為右孩子為右孩子 return TRUE; else return FALSE; / 樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入樹中已有關(guān)鍵字相同的結(jié)點(diǎn)，不再插入 / Insert BST 例：設(shè)查找的關(guān)鍵字序列為例：設(shè)查

28、找的關(guān)鍵字序列為 45, 24, 53, 45, 12, 24, 90，可生成，可生成 二叉排序樹如下：二叉排序樹如下： 中序遍歷中序遍歷二叉排序樹二叉排序樹可得到可得到一個(gè)關(guān)鍵字的一個(gè)關(guān)鍵字的有序序列有序序列。 二叉排序樹生成：二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作從空樹出發(fā)，經(jīng)過一系列的查找、插入操作 之后，可生成一棵二叉排序樹。之后，可生成一棵二叉排序樹。 4553249012 一個(gè)無序序列可通過構(gòu)造二叉排序樹而變成一個(gè)有序序列。一個(gè)無序序列可通過構(gòu)造二叉排序樹而變成一個(gè)有序序列。 構(gòu)造樹的過程就是對(duì)無序序列進(jìn)行排序的過程。構(gòu)造樹的過程就是對(duì)無序序列進(jìn)行排序的過程。 插入

29、的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)，故無需移動(dòng)其他結(jié)點(diǎn)。相當(dāng)于插入的結(jié)點(diǎn)均為葉子結(jié)點(diǎn)，故無需移動(dòng)其他結(jié)點(diǎn)。相當(dāng)于在在 有序序列上插入記錄而無需移動(dòng)其他記錄有序序列上插入記錄而無需移動(dòng)其他記錄。 二叉排序樹既有類似于折半查找的特性，又采用了鏈表作存二叉排序樹既有類似于折半查找的特性，又采用了鏈表作存 儲(chǔ)結(jié)構(gòu)。儲(chǔ)結(jié)構(gòu)。 二叉排序樹的刪除二叉排序樹的刪除 在刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。在刪除某個(gè)結(jié)點(diǎn)之后，仍然保持二叉排序樹的特性。 刪除二叉排序樹中的刪除二叉排序樹中的 p 結(jié)點(diǎn)，分三種情況討論：結(jié)點(diǎn)，分三種情況討論： 1)、 p 為葉子結(jié)點(diǎn)。為葉子結(jié)點(diǎn)。因刪除葉子結(jié)點(diǎn)不破壞樹的結(jié)構(gòu)，因刪除葉子結(jié)點(diǎn)不

30、破壞樹的結(jié)構(gòu)，故故只只 需修改需修改 p 雙親雙親 f 的指針：的指針：f - lchild=NULL 或或 f-rchild=NULL 2)、 p 只有左子樹或右子樹：只有左子樹或右子樹： p 只有左子樹，用只有左子樹，用 p 的左孩子代替的左孩子代替 p； 中序遍歷：中序遍歷：PL S Q 中序遍歷：中序遍歷： PL S Q SPPLQSPLQ中序遍歷：中序遍歷：Q S PL 中序遍歷：中序遍歷： Q S PL SPPLQSPLQ p 只有右子樹，用只有右子樹，用 p 的右孩子代替的右孩子代替 p； SPPRQSPRQ中序遍歷：中序遍歷： PR S Q 中序遍歷：中序遍歷： PR S Q

31、中序遍歷：中序遍歷：Q S PR 中序遍歷：中序遍歷： Q S PR SPPRQSPRQ中序：中序：CL C QL Q SL S PR F 中序：中序：CL C QL Q SL S PR F 3)、 p 左、右子樹均非空：左、右子樹均非空： FPCPRCLQQLSSLFCPRCLQQLSSL 用用 p 的直接前驅(qū)取代的直接前驅(qū)取代 p。 FCPRCLQQLSSL 用用 p 的直接后繼取代的直接后繼取代 p。 若若 p 的左子樹的左子樹無右子樹，無右子樹， 用用 p 的左子樹的左子樹取代取代 p。 中序遍歷：中序遍歷：CL C PR F 中序遍歷：中序遍歷：CL C PR F FPCPRCLFC

32、PRCLFPCPRCLQQLSSLFCPRCLQQLSSL中序：中序：CL C QL Q SL S PR F 中序：中序：CL C QL Q SL S PR F 3、二叉排序樹的查找分析 二叉排序樹上查找某關(guān)鍵字二叉排序樹上查找某關(guān)鍵字 等于給定值的結(jié)點(diǎn)過程，其等于給定值的結(jié)點(diǎn)過程，其 實(shí)就是走了一條從根到該結(jié)實(shí)就是走了一條從根到該結(jié) 點(diǎn)的路徑。點(diǎn)的路徑。 30802090854035883250查找關(guān)鍵字：查找關(guān)鍵字：35 35比較的關(guān)鍵字次數(shù)比較的關(guān)鍵字次數(shù) 此結(jié)點(diǎn)所在層次數(shù)此結(jié)點(diǎn)所在層次數(shù) 最多的比較次數(shù)最多的比較次數(shù) 樹的深度樹的深度 二叉排序樹的平均查找長度：二叉排序樹的平均查找長度

33、： 452412375393(45, 24, 53, 12, 37, 93) 614)333221 (61 ASL534512243793614)333221 (61 ASL折半查找折半查找 判定樹判定樹 (12, 24, 37, 45, 53, 93) 371245245393二叉排序樹二叉排序樹 452412375393621)654321 (61 ASL最壞情況：最壞情況：插入的插入的 n 個(gè)元素從一開始就有序，個(gè)元素從一開始就有序， 變成單支樹的形態(tài)！變成單支樹的形態(tài)！ 此時(shí)樹的深度為此時(shí)樹的深度為 n; ASL = (n + 1) / 2 查找效率與順序查找情況相同查找效率與順序查找

34、情況相同。 含有含有 n 個(gè)結(jié)點(diǎn)的二叉排序樹的個(gè)結(jié)點(diǎn)的二叉排序樹的平均查找長度平均查找長度和樹的和樹的形態(tài)形態(tài)有關(guān)有關(guān) 最好情況： ASL=log 2(n + 1) 1; 樹的深度為：log 2n + 1; 與折半查找中的判定樹相同。 （形態(tài)比較均衡）。 452412375393452412375393有有 n 個(gè)關(guān)鍵字的二叉排序樹的平均查找長度個(gè)關(guān)鍵字的二叉排序樹的平均查找長度 不失一般性，假設(shè)某個(gè)序列中有不失一般性，假設(shè)某個(gè)序列中有 k 個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵個(gè)關(guān)鍵字小于第一個(gè)關(guān)鍵 字，即有字，即有 n k 1 個(gè)關(guān)鍵字大于第一個(gè)關(guān)鍵字，由它構(gòu)造的二叉?zhèn)€關(guān)鍵字大于第一個(gè)關(guān)鍵字，由它構(gòu)造的二

35、叉 排序樹如下所示：排序樹如下所示： n-k-1k其平均查找長度是其平均查找長度是 n 和和 k 的函數(shù)：的函數(shù)： P(n, k) (0kn 1) 設(shè)每種樹態(tài)出現(xiàn)概率相同（即：設(shè)每種樹態(tài)出現(xiàn)概率相同（即： n 個(gè)關(guān)鍵字可能出現(xiàn)的個(gè)關(guān)鍵字可能出現(xiàn)的 n! 種排列的可能性相同），則含種排列的可能性相同），則含 n 個(gè)關(guān)鍵字的二叉排序樹的平均查個(gè)關(guān)鍵字的二叉排序樹的平均查 找長度為：找長度為： 10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在在每個(gè)關(guān)鍵字每個(gè)關(guān)鍵字等概率查找等概率查找的情況下，的情況下， RiLirootniiCCCnCnknP11),(1 )1)1(

36、)(1()1)(11 knPknkPkn )1()1()(11 knPknkPkn由此由此 10) 1() 1()(111)(nkknPknkPknnnP 112)(21nkkPknCnnnnP log12)(可類似于解差分方程，可類似于解差分方程， 此遞歸方程有解：此遞歸方程有解： 有有 n 個(gè)關(guān)鍵字的二叉排序樹的平均查找長度個(gè)關(guān)鍵字的二叉排序樹的平均查找長度 設(shè)每種樹態(tài)出現(xiàn)概率相同，查找每個(gè)關(guān)鍵字也是等概率的，設(shè)每種樹態(tài)出現(xiàn)概率相同，查找每個(gè)關(guān)鍵字也是等概率的， 則二叉排序樹的則二叉排序樹的 nnASLlog)11(2 由此可見，在由此可見，在隨機(jī)隨機(jī)的情況下，二叉排序樹的的情況下，二叉排

37、序樹的 ASL 和和 log n 是是 等數(shù)量級(jí)等數(shù)量級(jí)的。的。 如何提高如何提高形態(tài)不均衡的形態(tài)不均衡的二叉排序樹的查找效率？二叉排序樹的查找效率？ 做做“平衡化平衡化”處理，即盡量讓二叉樹的形狀均衡！處理，即盡量讓二叉樹的形狀均衡！ 4、平衡二叉樹 平衡二叉樹平衡二叉樹又稱又稱 AVL 樹，它是具有如下性質(zhì)的二叉樹：樹，它是具有如下性質(zhì)的二叉樹： 為了方便起見，給每個(gè)結(jié)點(diǎn)附加一個(gè)為了方便起見，給每個(gè)結(jié)點(diǎn)附加一個(gè)數(shù)字?jǐn)?shù)字 = 該結(jié)點(diǎn)左子樹與該結(jié)點(diǎn)左子樹與 右子樹的深度差右子樹的深度差。這個(gè)數(shù)字稱為結(jié)點(diǎn)的。這個(gè)數(shù)字稱為結(jié)點(diǎn)的。這樣，可以得。這樣，可以得 到到 AVL 樹的其它性質(zhì)（可以證明）：

38、樹的其它性質(zhì)（可以證明）： 即：即： |左子樹深度右子樹深度左子樹深度右子樹深度| 1 左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹； 所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值 1。 任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1、0 或或 1；如果樹中任意一個(gè)；如果樹中任意一個(gè) 結(jié)點(diǎn)的平衡因子的絕對(duì)值大于結(jié)點(diǎn)的平衡因子的絕對(duì)值大于 1，則這棵二叉樹就失去平衡。，則這棵二叉樹就失去平衡。 對(duì)于一棵有對(duì)于一棵有 n 個(gè)結(jié)點(diǎn)的個(gè)結(jié)點(diǎn)的 AVL 樹，其樹，其深度深度和和 log n 同數(shù)量級(jí)，同數(shù)量級(jí)， ASL 也和也和 log n 同數(shù)量級(jí)。同數(shù)量級(jí)。

39、非平衡二叉樹非平衡二叉樹 例：例：判斷下列二叉樹是否判斷下列二叉樹是否 AVL 樹？樹？ 1-100-110平衡二叉樹平衡二叉樹 0012-10 如果在一棵如果在一棵 AVL 樹中插入一個(gè)新結(jié)點(diǎn)后造成失衡，則樹中插入一個(gè)新結(jié)點(diǎn)后造成失衡，則 必須必須，使之恢復(fù)平衡。，使之恢復(fù)平衡。 我們稱此調(diào)整平衡的過程為我們稱此調(diào)整平衡的過程為。 平衡旋轉(zhuǎn)的類別平衡旋轉(zhuǎn)的類別 LL 平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) RR 平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) LR 平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) RL 平衡旋轉(zhuǎn)平衡旋轉(zhuǎn) 若在若在 C 的的左子樹的左子樹上插入左子樹的左子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 C 的平衡因子從的平衡因子從 1 增加增加 至至 2， 需要

40、進(jìn)行一次需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)。 (以以 B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） A若在若在 A 的的右子樹的右子樹上插入右子樹的右子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 A 的平衡因子從的平衡因子從 -1 改變改變?yōu)闉?-2，需要進(jìn)行一次，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)。(以以 B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸）2) RR 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： C1) LL 平衡旋轉(zhuǎn)： CBCABA若在若在 A 的的右子樹的左子樹上插入右子樹的左子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 A 的平衡因子從的平衡因子從 -1 改變改變 為為 -2，需要，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)以插入的結(jié)

41、點(diǎn) B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） 4) RL 平衡旋轉(zhuǎn)：平衡旋轉(zhuǎn)： B若在若在 C 的的左子樹的右子樹上插入左子樹的右子樹上插入 結(jié)點(diǎn)，使結(jié)點(diǎn)，使 C 的平衡因子從的平衡因子從 1 增加增加 至至 2， 需要需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，先進(jìn)行逆時(shí)針旋轉(zhuǎn)， 再順時(shí)針旋轉(zhuǎn)。再順時(shí)針旋轉(zhuǎn)。 (以插入的結(jié)點(diǎn)以插入的結(jié)點(diǎn) B 為旋轉(zhuǎn)軸）為旋轉(zhuǎn)軸） B3) LR 平衡旋轉(zhuǎn)： 調(diào)整必須保證二叉排序樹的特性不變調(diào)整必須保證二叉排序樹的特性不變 CAABCCABACBACCBA013037024例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹： (13, 24, 37, 90, 53) 013037-113024-124-2130

42、90-124-137053190-237需要需要 RR 平衡平衡 旋轉(zhuǎn)旋轉(zhuǎn) (繞繞 24 逆逆轉(zhuǎn)，轉(zhuǎn)，24 為根為根) 需要需要 RL 平衡平衡旋轉(zhuǎn)（繞旋轉(zhuǎn)（繞 53 先順后逆）先順后逆） -224037090053053037090-1249.2.2 B- 樹和樹和 B+ 樹樹 1. B- 樹的定義樹的定義 一棵一棵 m 階的階的 B- 樹，或?yàn)榭諛浠驗(yàn)闈M足下列特性的樹，或?yàn)榭諛浠驗(yàn)闈M足下列特性的 m 叉樹：叉樹： F111271FF391991F6453473FFFFFFF a b c d e f g h (1)、樹中每個(gè)結(jié)點(diǎn)至多有、樹中每個(gè)結(jié)點(diǎn)至多有 m 棵子樹

43、；棵子樹； (2)、若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；、若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；(3)、除根之外的所有非終端結(jié)點(diǎn)至少有、除根之外的所有非終端結(jié)點(diǎn)至少有 m/2 棵子樹；棵子樹； 階階 m 可以事先任意指定，可以事先任意指定， 一旦指定后就固定不變。一旦指定后就固定不變。 (4)、所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)為：（、所有的非終端結(jié)點(diǎn)的結(jié)構(gòu)為：（n, A0, K1, A1, K2, A2, , Kn, An） 其中，其中，Ki ( i = 1, , n ) 為按升序排列的關(guān)鍵字；為按升序排列的關(guān)鍵字； Ai (i = 0, , n) 為指向子樹為指向子樹 根結(jié)點(diǎn)的指針，且根結(jié)點(diǎn)的指

44、針，且 Ai 所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于所指子樹中所有結(jié)點(diǎn)的關(guān)鍵字均小于 ki，An 所指子樹所指子樹 中所有結(jié)點(diǎn)的關(guān)鍵字均大于中所有結(jié)點(diǎn)的關(guān)鍵字均大于 kn，n ( 對(duì)于根結(jié)點(diǎn)對(duì)于根結(jié)點(diǎn) 1nm 1, 對(duì)于其它結(jié)點(diǎn)對(duì)于其它結(jié)點(diǎn) m/2 1 n m 1) 為關(guān)鍵字的個(gè)數(shù)（或?yàn)殛P(guān)鍵字的個(gè)數(shù)（或 n +1 為子樹個(gè)數(shù)）。為子樹個(gè)數(shù)）。 (5)、所有葉子結(jié)點(diǎn)在同一個(gè)層次上，且不含有任何信息。（可、所有葉子結(jié)點(diǎn)在同一個(gè)層次上，且不含有任何信息。（可 以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不以看作是外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不 存在，指向這些結(jié)點(diǎn)的指針為空）。存在，指向這些

45、結(jié)點(diǎn)的指針為空）。 B- 樹特點(diǎn)樹特點(diǎn) 平衡平衡 多路多路 查找查找 樹中所有葉子結(jié)點(diǎn)均不帶信息且在樹的同一層次上； 根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹； 所有非葉子結(jié)點(diǎn)均含有 n （m/2 nm）棵子樹。 在在 m 階的階的 B- 樹上，每個(gè)非終端結(jié)點(diǎn)可能含有：樹上，每個(gè)非終端結(jié)點(diǎn)可能含有： n 個(gè)關(guān)鍵字個(gè)關(guān)鍵字 Ki（1in）n m n 個(gè)指向記錄的指針個(gè)指向記錄的指針 Di（1in） n+1 個(gè)指向子樹的指針個(gè)指向子樹的指針 Ai（0in）非葉子結(jié)點(diǎn)中的均有序排列； Ai -1 所指子樹上所有關(guān)鍵字均小于 Ki ； Ai 所指子樹上所有關(guān)鍵字均大于 Ki 。 2. B- 樹的查找樹的

46、查找 F111271FF391991F6453473FFFFFFF a b c d e f g h 47 47 從根結(jié)點(diǎn)出發(fā)，沿指針從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)搜索結(jié)點(diǎn)和在和在順序（或折順序（或折 半）半）兩個(gè)過程交叉進(jìn)行。兩個(gè)過程交叉進(jìn)行。 若若查找成功查找成功，則，則返回指向返回指向被查關(guān)鍵字所在被查關(guān)鍵字所在結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針和和關(guān)鍵關(guān)鍵 字在結(jié)點(diǎn)中的位置字在結(jié)點(diǎn)中的位置；若若則則9.3 哈希表（散列表）哈希表（散列表） 9.3.1 什么是哈希表什么是哈希表 以上討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：以上討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中記錄在表

47、中 的的位置位置和它的和它的關(guān)鍵字關(guān)鍵字之間不存在一個(gè)確定的關(guān)系。之間不存在一個(gè)確定的關(guān)系。 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 順序表：順序表： 0001 李李 0007 錢錢 0013 孫孫 0019 王王 0025 吳吳 0031 趙趙 0037 鄭鄭 0043 周周 0043 0013 0001 NULL 0037 0007 0019 0025鏈表：鏈表： 45 12 53 3 37 61 99 24 90 78 二叉排序樹（可用二叉鏈表存儲(chǔ)）：二叉排序樹（可用二叉鏈表存儲(chǔ)）： 查找過程：查找過程：給定值依次和

48、關(guān)鍵字集合中各關(guān)鍵字進(jìn)行給定值依次和關(guān)鍵字集合中各關(guān)鍵字進(jìn)行。 查找的效率查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。取決于和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。 用這類方法表示的查找表，用這類方法表示的查找表，。 不同的表示方法，其差別在于：不同的表示方法，其差別在于：1)、關(guān)鍵字和給定值進(jìn)行比關(guān)鍵字和給定值進(jìn)行比較的順序不同。較的順序不同。2)、比較的結(jié)果不同：順序查找有兩種可能比較的結(jié)果不同：順序查找有兩種可能“=”與與“”；其他查找有三種可能其他查找有三種可能“”。 只有一個(gè)辦法：只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置。預(yù)先知道所查關(guān)鍵字在表中的位置。 對(duì)于頻繁使用的查找表，希望對(duì)于頻

49、繁使用的查找表，希望 ASL = 0。 即，要求：即，要求：記錄在表中的位置和其關(guān)鍵字之間存在一種確定記錄在表中的位置和其關(guān)鍵字之間存在一種確定 的關(guān)系。的關(guān)系。 若以下標(biāo)為若以下標(biāo)為000 999 的有序順序表表示之，則查找過程可以的有序順序表表示之，則查找過程可以 簡單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過比較便可直簡單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過比較便可直 接從順序表中找到待查關(guān)鍵字。接從順序表中找到待查關(guān)鍵字。 例如：例如：為每年招收的為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵名新生建立一張查找表，其關(guān)鍵 字為學(xué)號(hào)，其值的范圍為字為學(xué)號(hào)，其值的范圍為 xx0

50、00 xx999 （前兩位為年份）。（前兩位為年份）。 上例表明，記錄的上例表明，記錄的與記錄在表中的與記錄在表中的之間存在之間存在 一種對(duì)應(yīng)（函數(shù)）關(guān)系。若記錄的關(guān)鍵字為一種對(duì)應(yīng)（函數(shù)）關(guān)系。若記錄的關(guān)鍵字為 key，記錄在表中的，記錄在表中的 位置位置（稱為稱為）為為 f (key)，則稱此函數(shù)，則稱此函數(shù) f (key) 為為。 hao, ian, un, i, u, hen, an, e, ai 例如：例如：對(duì)于如下對(duì)于如下 9 個(gè)關(guān)鍵字：個(gè)關(guān)鍵字： 設(shè)哈希函數(shù)設(shè)哈希函數(shù) f (key) = (Ord(關(guān)鍵字首字母關(guān)鍵字首字母) - Ord(A) + 1) / 2 若添加關(guān)鍵字若添加關(guān)

51、鍵字 Zhou，會(huì)出現(xiàn)什么情況，會(huì)出現(xiàn)什么情況 0 1 2 3 4 5 6 7 8 9 10 11 12 13 Dai Chen Zhao Qian Sun Li Wu Han Ye 從這個(gè)例子可見：從這個(gè)例子可見： 1) 哈希函數(shù)是一個(gè)映像，即：哈希函數(shù)是一個(gè)映像，即：將關(guān)鍵字的集合映射到某個(gè)地址將關(guān)鍵字的集合映射到某個(gè)地址 集合上集合上。它的設(shè)置很靈活，只要使得關(guān)鍵字的哈希函數(shù)值都。它的設(shè)置很靈活，只要使得關(guān)鍵字的哈希函數(shù)值都 落在表長允許的范圍之內(nèi)即可；落在表長允許的范圍之內(nèi)即可； 2) 由于哈希函數(shù)是一個(gè)由于哈希函數(shù)是一個(gè)，因此，在一般情況下，很容，因此，在一般情況下，很容 易產(chǎn)生易產(chǎn)

52、生“”現(xiàn)象，即：現(xiàn)象，即：key1 key2，而，而 f (key1) = f (key2)。 這種具有相同函數(shù)值的關(guān)鍵字稱為這種具有相同函數(shù)值的關(guān)鍵字稱為。 3) 很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能 選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。 因此：在構(gòu)造這種特殊的因此：在構(gòu)造這種特殊的“查找表查找表”時(shí)，除了需要選擇一時(shí)，除了需要選擇一個(gè)個(gè) “好好” （其原則是盡可能地使任意一組關(guān)鍵字的哈希地址其原則是盡可能地使任意一組關(guān)鍵字的哈希地址分布在整個(gè)地址空間中，即用任意關(guān)鍵字作為哈希函數(shù)

53、的分布在整個(gè)地址空間中，即用任意關(guān)鍵字作為哈希函數(shù)的自變量其計(jì)算結(jié)果自變量其計(jì)算結(jié)果，以盡可能少產(chǎn)生沖突，以盡可能少產(chǎn)生沖突）的哈希函）的哈希函數(shù)之外；還需要找到一種數(shù)之外；還需要找到一種“處理沖突處理沖突”的方法。的方法。 哈希表的定義：哈希表的定義： 根據(jù)設(shè)定的哈希函數(shù)根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法建立和所選中的處理沖突的方法建立 的的。其基本思想是：以記錄的關(guān)鍵字為自變量，根據(jù)哈希。其基本思想是：以記錄的關(guān)鍵字為自變量，根據(jù)哈希 函數(shù)，計(jì)算出對(duì)應(yīng)的哈希地址，并在此存儲(chǔ)該記錄的內(nèi)容。函數(shù)，計(jì)算出對(duì)應(yīng)的哈希地址，并在此存儲(chǔ)該記錄的內(nèi)容。 這一映像過程稱為這一映像過程稱

54、為或或。 當(dāng)對(duì)記錄進(jìn)行查找時(shí)，再根據(jù)給定的關(guān)鍵字，用同一個(gè)哈希當(dāng)對(duì)記錄進(jìn)行查找時(shí)，再根據(jù)給定的關(guān)鍵字，用同一個(gè)哈希 函數(shù)計(jì)算出給定關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)地址，隨后進(jìn)行訪問。所以哈函數(shù)計(jì)算出給定關(guān)鍵字對(duì)應(yīng)的存儲(chǔ)地址，隨后進(jìn)行訪問。所以哈 希表既是一種存儲(chǔ)形式，又是一種查找方法，通常將這種查找方希表既是一種存儲(chǔ)形式，又是一種查找方法，通常將這種查找方 法稱為法稱為。 9.3.2 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 對(duì)對(duì)數(shù)字關(guān)鍵字?jǐn)?shù)字關(guān)鍵字可有下列構(gòu)造方法：可有下列構(gòu)造方法： 若是若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。，則需先對(duì)其進(jìn)行數(shù)字化處理。 1. 直接定址法直接定址法 3. 平方

55、取中法平方取中法 5. 除留余數(shù)法除留余數(shù)法 4. 折疊法折疊法 6. 隨機(jī)數(shù)法隨機(jī)數(shù)法 2. 數(shù)字分析法數(shù)字分析法 哈希函數(shù)為關(guān)鍵字的哈希函數(shù)為關(guān)鍵字的線性函數(shù)線性函數(shù) H(key) = key 或者或者 H(key) = a key + b 1. 直接定址法直接定址法 特點(diǎn)：特點(diǎn)：地址集合的大小地址集合的大小 = 關(guān)鍵字集合的大小。關(guān)鍵字集合的大小。 不同的關(guān)鍵字（不同的關(guān)鍵字（調(diào)整調(diào)整 a 與與 b 的值的值）不發(fā)生沖突。）不發(fā)生沖突。 實(shí)際中能使用這種哈希函數(shù)的情況很少。實(shí)際中能使用這種哈希函數(shù)的情況很少。 2. 數(shù)字分析法（數(shù)字選擇法）數(shù)字分析法（數(shù)字選擇法） 構(gòu)造：構(gòu)造：取關(guān)鍵字的

56、若干位或其組合作哈希地址。取關(guān)鍵字的若干位或其組合作哈希地址。 適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事 先知道的情況。先知道的情況。 例：例：有有 80 個(gè)記錄，關(guān)鍵字為個(gè)記錄，關(guān)鍵字為 8 位十進(jìn)制數(shù)，哈希表長為位十進(jìn)制數(shù)，哈希表長為 100。 則哈希地址可取則哈希地址可取 2 位十進(jìn)制數(shù)。位十進(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 8 1 3 6 8 5 3 7 8

57、 1 4 1 9 3 5 5 分析：分析： 只取只取 8 只取只取 1 只取只取 3、4 只取只取 2、7、5 數(shù)字分布近乎隨機(jī)數(shù)字分布近乎隨機(jī) 所以：取所以：取 任意兩位或兩位任意兩位或兩位 與另兩位的疊加作哈希地址與另兩位的疊加作哈希地址 構(gòu)造：構(gòu)造：以關(guān)鍵字的平方值的中間幾位作為哈希地址。以關(guān)鍵字的平方值的中間幾位作為哈希地址。 求求“關(guān)鍵字的平方值關(guān)鍵字的平方值”的目的是的目的是“擴(kuò)大差別擴(kuò)大差別”，同時(shí)平方值，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。 3. 平方取中法（較常用）平方取中法（較常用） 此方法適合于：此方法適合于：關(guān)鍵

58、字中的每一位都有某些數(shù)字關(guān)鍵字中的每一位都有某些數(shù)字的現(xiàn)象。的現(xiàn)象。4. 折疊法折疊法 構(gòu)造：構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分 的的（舍去進(jìn)位）做哈希地址。（舍去進(jìn)位）做哈希地址。 將分割后的幾部分低位對(duì)齊相加。將分割后的幾部分低位對(duì)齊相加。 從一端沿分割界來回折疊，然后對(duì)齊相加。從一端沿分割界來回折疊，然后對(duì)齊相加。 適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況。適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況。 例：關(guān)鍵字為：例：關(guān)鍵字為：0442205864，哈希地址位數(shù)為，哈希地址位數(shù)為 4。 5 8 6 44

59、2 2 00 41 0 0 8 8H(key)=0088移位疊加移位疊加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092間界疊加間界疊加5. 除留余數(shù)法（最常用）除留余數(shù)法（最常用） 構(gòu)造：構(gòu)造：取關(guān)鍵字被某個(gè)不大于哈希表表長取關(guān)鍵字被某個(gè)不大于哈希表表長 m 的數(shù)的數(shù) p 除后所得除后所得 余數(shù)作哈希地址，即余數(shù)作哈希地址，即 H(key) = key MOD p， p m。 簡單，可與上述幾種方法結(jié)合使用。簡單，可與上述幾種方法結(jié)合使用。 p 的選取很重要；的選取很重要；p 選得不好，容易產(chǎn)生同義詞。選得不好，容易產(chǎn)生同義詞。 p 應(yīng)為不大于應(yīng)為不大于 m 的素?cái)?shù)或

60、不含的素?cái)?shù)或不含 20 以下的質(zhì)因子的合數(shù)。以下的質(zhì)因子的合數(shù)。 給定一組關(guān)鍵字：給定一組關(guān)鍵字：12, 39, 18, 24, 33, 21，若取，若取 p = 9, 則他們則他們 對(duì)應(yīng)的哈希函數(shù)值將為：對(duì)應(yīng)的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3例如：例如：為什么要對(duì)為什么要對(duì) p 加限制？加限制？ 可見，若可見，若 p 中含質(zhì)因子中含質(zhì)因子 3， 則所有含質(zhì)因子則所有含質(zhì)因子 3 的關(guān)鍵字均的關(guān)鍵字均 映射到映射到“3 的倍數(shù)的倍數(shù)”的地址上，從而增加了的地址上，從而增加了“沖突沖突”的可能。的可能。 6. 隨機(jī)數(shù)法隨機(jī)數(shù)法 構(gòu)造：構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即：取關(guān)鍵字的隨機(jī)函數(shù)