《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言 查找表 詳細(xì)舉例介紹PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)C語(yǔ)言 查找表 詳細(xì)舉例介紹PPT課件（169頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 查找表是由同一類(lèi)型的數(shù)據(jù)元查找表是由同一類(lèi)型的數(shù)據(jù)元素素(或記錄或記錄)構(gòu)成的集合。構(gòu)成的集合。 由于由于“集合集合”中的數(shù)據(jù)元素之間中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。種應(yīng)用靈便的結(jié)構(gòu)。何謂查找表何謂查找表 ？第1頁(yè)/共169頁(yè)對(duì)查找表經(jīng)常進(jìn)行的對(duì)查找表經(jīng)常進(jìn)行的操作操作: :1. 查詢(xún)查詢(xún)某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素是數(shù)據(jù)元素是否在查找表中；否在查找表中；2. 檢索檢索某個(gè)某個(gè)“特定的特定的”數(shù)據(jù)元素的數(shù)據(jù)元素的各種屬性；各種屬性；3. 在查找表中在查找表中插入插入一個(gè)數(shù)據(jù)元素；一個(gè)數(shù)據(jù)元素；4. 從查找表中從查找表中刪去

2、刪去某個(gè)數(shù)據(jù)元素。某個(gè)數(shù)據(jù)元素。第2頁(yè)/共169頁(yè)僅作僅作查詢(xún)查詢(xún)和和檢索檢索操作的查找表。操作的查找表。有時(shí)在查詢(xún)之后，還需要將有時(shí)在查詢(xún)之后，還需要將“查詢(xún)查詢(xún)”結(jié)結(jié)果為果為“不在查找表中不在查找表中”的數(shù)據(jù)元素的數(shù)據(jù)元素插入插入到到查找表中；或者，從查找表中查找表中；或者，從查找表中刪除刪除其其“查詢(xún)查詢(xún)”結(jié)果為結(jié)果為“在查找表中在查找表中”的數(shù)據(jù)的數(shù)據(jù)元素。元素。查找表可分為兩類(lèi)查找表可分為兩類(lèi):第3頁(yè)/共169頁(yè)是數(shù)據(jù)元素（或記錄）中某個(gè)是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)的值，用以的值，用以標(biāo)識(shí)標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。素（或記錄）。 若此關(guān)鍵字可以識(shí)

3、別若此關(guān)鍵字可以識(shí)別唯一的唯一的一個(gè)記一個(gè)記錄，則稱(chēng)之謂錄，則稱(chēng)之謂 若此關(guān)鍵字能識(shí)別若此關(guān)鍵字能識(shí)別若干若干記錄，則稱(chēng)記錄，則稱(chēng)之謂之謂第4頁(yè)/共169頁(yè) 根據(jù)給定的某個(gè)值，在查找表中根據(jù)給定的某個(gè)值，在查找表中確定一確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）錄） 查找查找 若查找表中存在這樣一個(gè)記錄，則稱(chēng)若查找表中存在這樣一個(gè)記錄，則稱(chēng)“查找成功查找成功”，查找結(jié)果：，查找結(jié)果：給出整個(gè)記錄給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置的信息，或指示該記錄在查找表中的位置； 否則稱(chēng)否則稱(chēng)“查找不成功查找不成功”，查找結(jié)果：，查找結(jié)果：給給出出“空記

4、錄空記錄”或或“空指針空指針”。第5頁(yè)/共169頁(yè) 由于查找表中的數(shù)據(jù)元素之間不存由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。在明顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率，為了提高查找的效率， 需要在查找需要在查找表中的元素之間人為地表中的元素之間人為地 附加某種確定的附加某種確定的關(guān)系，換句話說(shuō)，關(guān)系，換句話說(shuō)， 用另外一種結(jié)構(gòu)來(lái)表用另外一種結(jié)構(gòu)來(lái)表示查找表示查找表。查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。如何進(jìn)行查找？如何進(jìn)行查找？第6頁(yè)/共169頁(yè)9.1 靜態(tài)查找表靜態(tài)查找表9.2 動(dòng)態(tài)查找樹(shù)表動(dòng)態(tài)查找樹(shù)表9.3 哈希表哈希表第7頁(yè)/共1

5、69頁(yè)第8頁(yè)/共169頁(yè)數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)是具有相同特性的數(shù)據(jù)元素的集合。據(jù)元素的集合。每個(gè)數(shù)每個(gè)數(shù)據(jù)元素含有類(lèi)型相同的據(jù)元素含有類(lèi)型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。據(jù)元素。 數(shù)據(jù)元素同屬一個(gè)集合。數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable 第9頁(yè)/共169頁(yè) Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：next ADT StaticSearchTable第10頁(yè)/共169頁(yè)構(gòu)造一個(gè)含構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)

6、元素個(gè)數(shù)據(jù)元素的靜態(tài)查找表的靜態(tài)查找表ST。 Create(&ST, n);操作結(jié)果：操作結(jié)果：第11頁(yè)/共169頁(yè)銷(xiāo)毀表銷(xiāo)毀表ST。Destroy(&ST);初始條件：初始條件：操作結(jié)果：操作結(jié)果：靜態(tài)查找表靜態(tài)查找表ST存在；存在；第12頁(yè)/共169頁(yè)若若 ST 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的數(shù)據(jù)元素，則函數(shù)值的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位為該元素的值或在表中的位置，否則為置，否則為“空空”。 Search(ST, key);初始條件：初始條件：操作結(jié)果：操作結(jié)果：靜態(tài)查找表靜態(tài)查找表ST存在，存在，key 為為和查找表中元素的關(guān)鍵字類(lèi)和查找表中元素的關(guān)鍵字

7、類(lèi)型相同的給定值；型相同的給定值；第13頁(yè)/共169頁(yè)按某種次序?qū)Π茨撤N次序?qū)T的每個(gè)元的每個(gè)元素調(diào)用函數(shù)素調(diào)用函數(shù)Visit()一次且一次且僅一次，一旦僅一次，一旦Visit()失敗，失敗，則操作失敗。則操作失敗。Traverse(ST, Visit();初始條件：初始條件：操作結(jié)果：操作結(jié)果：靜態(tài)查找表靜態(tài)查找表ST存在，存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)；是對(duì)元素操作的應(yīng)用函數(shù)；第14頁(yè)/共169頁(yè)typedef struct / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長(zhǎng)度分配，按實(shí)際長(zhǎng)度分配，0號(hào)單元留空號(hào)單元留空 int length; / 表的長(zhǎng)

8、度表的長(zhǎng)度 SSTable;假設(shè)靜態(tài)查找表的假設(shè)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)為為ElemType *elem;第15頁(yè)/共169頁(yè)數(shù)據(jù)元素類(lèi)型的定義為數(shù)據(jù)元素類(lèi)型的定義為:typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ; , TElemType ;第16頁(yè)/共169頁(yè)第17頁(yè)/共169頁(yè) 以順序表或線性鏈表以順序表或線性鏈表表示靜態(tài)查找表表示靜態(tài)查找表一、順序查找表一、順序查找表第18頁(yè)/共169頁(yè)21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Leng

9、thST.elem回顧順序表的查找過(guò)程：回顧順序表的查找過(guò)程：假設(shè)給定值假設(shè)給定值 e=64,要求要求 ST.elemk = e, 問(wèn)問(wèn): k = ?kk第19頁(yè)/共169頁(yè)int Location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.elem; while ( k=L.length & compare(*p+,e) k+; if ( k= L.length) return k; else return 0;第20頁(yè)/共169頁(yè)21 37 88 19 92 05 64 56 80

10、75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64第21頁(yè)/共169頁(yè)int Search_Seq(SSTable ST, KeyType key) / 在順序表在順序表ST中順序查找其關(guān)鍵字等于中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為該元素在表中的位置，否則為0。 ST.el

11、em0.key = key; / “哨兵哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找從后往前找 return i; / 找不到時(shí)，找不到時(shí)，i為為0第22頁(yè)/共169頁(yè) 定義：定義： 查找算法的查找算法的平均查找長(zhǎng)度平均查找長(zhǎng)度 (Average Search Length) 為確定記錄在查找表中的位置，需和給定值為確定記錄在查找表中的位置，需和給定值 進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值 其中其中: n 為表長(zhǎng)，為表長(zhǎng)，Pi 為查找表中第為查找表中第i個(gè)記錄的概率，個(gè)記錄的概率， 且且 Ci為找到該記錄時(shí)，曾為

12、找到該記錄時(shí)，曾和給定值和給定值 比較過(guò)的關(guān)鍵字的個(gè)數(shù)。比較過(guò)的關(guān)鍵字的個(gè)數(shù)。分析順序查找的時(shí)間性能。分析順序查找的時(shí)間性能。niiiCPASL111niiP第23頁(yè)/共169頁(yè)在在等概率等概率查找的情況下，查找的情況下， 順序表查找的平均查找長(zhǎng)度順序表查找的平均查找長(zhǎng)度為：為：對(duì)對(duì)順序表順序表而言，而言，Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn第24頁(yè)/共169頁(yè) 若查找概率無(wú)法事先測(cè)定，則查若查找概率無(wú)法事先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，找過(guò)程采取的改進(jìn)辦法是，在每次查找在每次查找之后，將剛剛查找到的記

13、錄直接移至表之后，將剛剛查找到的記錄直接移至表尾的位置上尾的位置上。在在不等概率查找不等概率查找的情況下，的情況下，ASLss 在在 PnPn-1P2P1時(shí)時(shí)取極小值取極小值第25頁(yè)/共169頁(yè) 上述順序查找表的查找算法簡(jiǎn)上述順序查找表的查找算法簡(jiǎn)單，單， 但平均查找長(zhǎng)度較大，特別不但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。適用于表長(zhǎng)較大的查找表。 若以若以有序表有序表表示靜態(tài)查找表，則表示靜態(tài)查找表，則查找過(guò)程可以基于查找過(guò)程可以基于“折半折半”進(jìn)行。進(jìn)行。二、有序查找表二、有序查找表第26頁(yè)/共169頁(yè)05 13 19 21 37 56 64 75 80 88 92 0 1 2 3

14、 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找過(guò)程如下lowhighmidlow mid high midlow 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。第27頁(yè)/共169頁(yè)int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值置區(qū)間初值 while (low 50時(shí)，可得近似結(jié)果時(shí)，可得近似結(jié)果 一般情況下，表長(zhǎng)為一般情況下，表長(zhǎng)為 n 的折半查找的折半查找的判定樹(shù)的深度和含有的判定樹(shù)的深度

15、和含有 n 個(gè)結(jié)點(diǎn)的完全個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相同。二叉樹(shù)的深度相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs第30頁(yè)/共169頁(yè)關(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 在不等概率查找在不等概率查找的情況下，折半查找的情況下，折半查找不是不是有序表最好的查找方法有序表最好的查找方法例如例如:此時(shí)此時(shí) ASL=2 0.2+3 0.3+1 0.05+2 0.3+3 0.15=2.4若改變?nèi)舾淖僀i的值的值 2 1 3 2 3則則 ASL=2 0.2+1 0.3+3

16、 0.05+2 0.3+3 0.15=1.9三、靜態(tài)查找樹(shù)表三、靜態(tài)查找樹(shù)表第31頁(yè)/共169頁(yè) 使使 達(dá)最小的判定樹(shù)稱(chēng)為達(dá)最小的判定樹(shù)稱(chēng)為最優(yōu)二叉樹(shù)最優(yōu)二叉樹(shù)，其中其中: 111niiCiqniiCipASL1111niiniiqp定義定義:第32頁(yè)/共169頁(yè)為計(jì)算方便，令為計(jì)算方便，令 wi = pi選擇二叉樹(shù)的根結(jié)點(diǎn)，選擇二叉樹(shù)的根結(jié)點(diǎn)，使使 達(dá)最小達(dá)最小 111ijjhijjiwwP11)(iilhiswswswswP介紹一種介紹一種次優(yōu)二叉樹(shù)次優(yōu)二叉樹(shù)的構(gòu)造方法的構(gòu)造方法:為便于計(jì)算，引入累計(jì)權(quán)值和為便于計(jì)算，引入累計(jì)權(quán)值和 并設(shè)并設(shè) wl-1 = 0 和和 swl-1 = 0，則

17、推導(dǎo)可得則推導(dǎo)可得ijjiwsw1第33頁(yè)/共169頁(yè)j01234567wj02153435swjpjkeyA B C D E F G023811 15 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013第34頁(yè)/共169頁(yè)ECGABDF所得次優(yōu)二叉樹(shù)如下所示所得次優(yōu)二叉樹(shù)如下所示: 查找比較查找比較“總次數(shù)總次數(shù)” = 3 2+4 1+2 5+3 3 +1 4+3 3+2 5 = 52 查找比較查找比較“總次數(shù)總次數(shù)” = 3 2+2 1+3 5+1 3 +3 4+2 3+3 5 = 59和折半查找相比較和折半查找相比較DBACFEG第35頁(yè)/共1

18、69頁(yè)Status SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表由有序表Rlow.high及其累計(jì)權(quán)值表及其累計(jì)權(quán)值表sw / 遞歸構(gòu)造次優(yōu)查找樹(shù)遞歸構(gòu)造次優(yōu)查找樹(shù)T。 選擇最小的選擇最小的Pi值值 if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成結(jié)點(diǎn)生成結(jié)點(diǎn)第36頁(yè)/共169頁(yè)if (i=low) T-lchild = NULL; / 左子樹(shù)空左子樹(shù)空else SecondOptimal(T-lch

19、ild, R, sw, low, i-1); / 構(gòu)造左子樹(shù)構(gòu)造左子樹(shù) if (i=high) T-rchild = NULL; / 右子樹(shù)空右子樹(shù)空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 構(gòu)造右子樹(shù)構(gòu)造右子樹(shù) return OK; / SecondOptimal第37頁(yè)/共169頁(yè)次優(yōu)查找樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)次優(yōu)查找樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表由有序表 ST 構(gòu)造一棵次優(yōu)查找樹(shù)構(gòu)造一棵次優(yōu)查找樹(shù) T。 / ST 的數(shù)據(jù)元素含有權(quán)域的

20、數(shù)據(jù)元素含有權(quán)域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表按照有序表 ST 中各數(shù)據(jù)元素中各數(shù)據(jù)元素 / 的的 weight 值求累計(jì)權(quán)值表值求累計(jì)權(quán)值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree第38頁(yè)/共169頁(yè)四、索引順序表四、索引順序表以索引順序表表示靜態(tài)查找表，以索引順序表表示靜態(tài)查找表，searchsearch操作可用分塊查找來(lái)實(shí)現(xiàn)。操作可用分塊查找來(lái)實(shí)現(xiàn)。分塊查找又稱(chēng)索引順序查找，這是分塊查找又

21、稱(chēng)索引順序查找，這是順序查找的一種改進(jìn)方法。在此查順序查找的一種改進(jìn)方法。在此查找方法中，除表本身以外，尚需建找方法中，除表本身以外，尚需建立一個(gè)立一個(gè)“索引表索引表”。第39頁(yè)/共169頁(yè)例如 表中含有18個(gè)元素，可分成三個(gè)子表。對(duì)每個(gè)子表（或稱(chēng)塊）建立一個(gè)索引項(xiàng)，其中包括兩項(xiàng)內(nèi)容：關(guān)鍵字項(xiàng)（其值為該子表內(nèi)的最大關(guān)鍵字）和項(xiàng)指針（指示該子表的第一個(gè)元素在表中位置）。索引表索引表最大關(guān)鍵字起始地址 22 48 8617 13221213 8 9 20334244382448605874498653第40頁(yè)/共169頁(yè) 索引表按關(guān)鍵字有序，故表或者有序，或者分塊有序。所謂“分塊有序” 是指一個(gè)子

22、表中所有元素的關(guān)鍵字均大于前一個(gè)子表的最大關(guān)鍵字。 第41頁(yè)/共169頁(yè)1）由索引確定記錄所在區(qū)間；）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造。注意：索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造?？梢?jiàn)，可見(jiàn)， 索引順序查找索引順序查找的過(guò)程也是一個(gè)的過(guò)程也是一個(gè)“縮小區(qū)間縮小區(qū)間”的查找過(guò)程。的查找過(guò)程。第42頁(yè)/共169頁(yè)索引順序查找的平均查找長(zhǎng)度索引順序查找的平均查找長(zhǎng)度 = 查找查找“索引索引”的平均查找長(zhǎng)度的平均查找長(zhǎng)度 + 查找查找“順序表順序表”的平均查找長(zhǎng)度的平均查找長(zhǎng)度第43頁(yè)/共169頁(yè)第44頁(yè)/共169

23、頁(yè) (n) (1) (n) (1) (nlogn)綜合上一節(jié)討論的幾種查找表的特性：綜合上一節(jié)討論的幾種查找表的特性：查找查找 插入插入 刪除刪除無(wú)序順序表無(wú)序順序表 無(wú)序線性鏈表無(wú)序線性鏈表有序順序表有序順序表 有序線性鏈表有序線性鏈表 靜態(tài)查找樹(shù)表靜態(tài)查找樹(shù)表 (n) (n) (logn) (n) (logn) (1) (1) (n) (1) (nlogn)第45頁(yè)/共169頁(yè)1）從）從查找查找性能看，最好情況能達(dá)性能看，最好情況能達(dá) (logn)，此時(shí)要求表，此時(shí)要求表有序有序；2）從）從插入插入和和刪除刪除的性能看，最好的性能看，最好 情況能達(dá)情況能達(dá) (1)，此時(shí)要求存儲(chǔ)，此時(shí)要求存

24、儲(chǔ) 結(jié)構(gòu)是結(jié)構(gòu)是鏈表鏈表。第46頁(yè)/共169頁(yè)ADT DynamicSearchTable 抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型動(dòng)態(tài)查找表動(dòng)態(tài)查找表的定義如下：的定義如下：數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R： 數(shù)據(jù)元素同屬一個(gè)集合。數(shù)據(jù)元素同屬一個(gè)集合。D是具有相同特性的數(shù)據(jù)是具有相同特性的數(shù)據(jù)元素的集合。元素的集合。每個(gè)數(shù)據(jù)元素含有類(lèi)型相每個(gè)數(shù)據(jù)元素含有類(lèi)型相同的關(guān)鍵字，同的關(guān)鍵字， 可唯一標(biāo)可唯一標(biāo)識(shí)數(shù)據(jù)元素。識(shí)數(shù)據(jù)元素。第47頁(yè)/共169頁(yè)InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTab

25、le(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();nextADT DynamicSearchTable第48頁(yè)/共169頁(yè)操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。InitDSTable(&DT);第49頁(yè)/共169頁(yè)銷(xiāo)毀動(dòng)態(tài)查找表銷(xiāo)毀動(dòng)態(tài)查找表DT。DestroyDSTable(&DT);初始條件：初始條件： 操作結(jié)果：操作結(jié)果：動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT存在；存在；第50頁(yè)/共169頁(yè)若若DT中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key的數(shù)據(jù)元素，則函數(shù)值的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在

26、表中的位為該元素的值或在表中的位置，否則為置，否則為“空空”。SearchDSTable(DT, key);初始條件：初始條件：操作結(jié)果：操作結(jié)果：動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT存在，存在，key為和關(guān)鍵字類(lèi)型相同的給為和關(guān)鍵字類(lèi)型相同的給定值；定值；第51頁(yè)/共169頁(yè)動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT存在，存在， e 為待插入的數(shù)據(jù)元素；為待插入的數(shù)據(jù)元素；InsertDSTable(&DT, e);初始條件：初始條件：操作結(jié)果：操作結(jié)果：若若DT中不存在其關(guān)鍵字中不存在其關(guān)鍵字等于等于 e.key 的的 數(shù)據(jù)元素，數(shù)據(jù)元素，則插入則插入 e 到到DT。第52頁(yè)/共169頁(yè)動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT存在，存

27、在，key為和關(guān)鍵字類(lèi)型相同的給為和關(guān)鍵字類(lèi)型相同的給定值；定值；DeleteDSTable(&T, key);初始條件：初始條件：操作結(jié)果：操作結(jié)果：若若DT中存在其關(guān)鍵字等中存在其關(guān)鍵字等于于key的數(shù)據(jù)元素，則刪的數(shù)據(jù)元素，則刪除之。除之。第53頁(yè)/共169頁(yè)動(dòng)態(tài)查找表動(dòng)態(tài)查找表DT存在，存在，Visit是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；是對(duì)結(jié)點(diǎn)操作的應(yīng)用函數(shù)；TraverseDSTable(DT, Visit();初始條件：初始條件：操作結(jié)果：操作結(jié)果：按某種次序?qū)Π茨撤N次序?qū)T的每個(gè)結(jié)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)點(diǎn)調(diào)用函數(shù) Visit() 一次且至一次且至多一次。一旦多一次。一旦 Visit() 失敗

28、，失敗，則操作失敗。則操作失敗。第54頁(yè)/共169頁(yè)一、二叉排序樹(shù)（二叉查找樹(shù)）一、二叉排序樹(shù)（二叉查找樹(shù)）二、二叉平衡樹(shù)二、二叉平衡樹(shù)三、三、B - 樹(shù)樹(shù)四、四、B+樹(shù)樹(shù)五、鍵五、鍵 樹(shù)樹(shù)第55頁(yè)/共169頁(yè)1定義定義2查找算法查找算法3插入算法插入算法4刪除算法刪除算法5查找性能的分析查找性能的分析一、二叉排序樹(shù)一、二叉排序樹(shù)（二叉查找樹(shù)）（二叉查找樹(shù)）第56頁(yè)/共169頁(yè)（1）若它的左子樹(shù)不空，則左子樹(shù)上）若它的左子樹(shù)不空，則左子樹(shù)上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均小于均小于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值； 二叉排序樹(shù)二叉排序樹(shù)或者是一棵空樹(shù)；或者或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：是具有如

29、下特性的二叉樹(shù)：（3）它的左、右子樹(shù)）它的左、右子樹(shù)也都也都分別分別是二叉是二叉 排序樹(shù)排序樹(shù)。（2）若它的右子樹(shù)不空，則右子樹(shù)上）若它的右子樹(shù)不空，則右子樹(shù)上 所有所有結(jié)點(diǎn)的值結(jié)點(diǎn)的值均大于均大于根結(jié)點(diǎn)的值；根結(jié)點(diǎn)的值；1 1定義：定義：第57頁(yè)/共169頁(yè)503080209010854035252388例如例如:是二叉排序樹(shù)是二叉排序樹(shù)66不不第58頁(yè)/共169頁(yè) 通常，取二叉鏈表作為通常，取二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild; / 左右孩子指

30、針左右孩子指針 BiTNode, *BiTree;TElemType data;第59頁(yè)/共169頁(yè)1）若給定值）若給定值等于等于根結(jié)點(diǎn)的關(guān)鍵字，根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；則查找成功；2）若給定值）若給定值小于小于根結(jié)點(diǎn)的關(guān)鍵字，根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；則繼續(xù)在左子樹(shù)上進(jìn)行查找；3）若給定值）若給定值大于大于根結(jié)點(diǎn)的關(guān)鍵字，根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。則繼續(xù)在右子樹(shù)上進(jìn)行查找。否則否則若二叉排序樹(shù)若二叉排序樹(shù)為空為空，則查找不成功；，則查找不成功；第60頁(yè)/共169頁(yè)50308020908540358832例如例如:二叉排序樹(shù)二叉排序樹(shù)查找關(guān)鍵字查找關(guān)鍵字=

31、50 ,505035 ,503040355090 ,50809095 第61頁(yè)/共169頁(yè)從上述查找過(guò)程可見(jiàn)，從上述查找過(guò)程可見(jiàn)，在查找過(guò)程中，生成了一條在查找過(guò)程中，生成了一條查找路徑查找路徑: 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn)逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止。逐層向下直至指針指向空樹(shù)為止。 查找成功查找成功 查找不成功查找不成功第62頁(yè)/共169頁(yè)算法描述如下：算法描述如下：Status SearchBST (BiTre

32、e T, KeyType key, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹(shù)中遞歸地查找其所指二叉排序樹(shù)中遞歸地查找其 / 關(guān)鍵字等于關(guān)鍵字等于 key 的數(shù)據(jù)元素，若的數(shù)據(jù)元素，若查找成功查找成功， / 則返回指針則返回指針 p 指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回指向該數(shù)據(jù)元素的結(jié)點(diǎn)，并返回 / 函數(shù)值為函數(shù)值為 TRUE; / SearchBST 否則表明否則表明查找不成功查找不成功，返回，返回 / 指針指針 p 指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)，指向查找路徑上訪問(wèn)的最后一個(gè)結(jié)點(diǎn)， / 并返回函數(shù)值為并返回函數(shù)值為FALSE, 指針指針 f 指向當(dāng)前訪

33、問(wèn)指向當(dāng)前訪問(wèn) / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULL第63頁(yè)/共169頁(yè)if (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找不成功查找不成功 p = T; return TRUE; / 查找成功查找成功SearchBST (T-lchild, key, T, p ); / 在左子樹(shù)中繼續(xù)查找在左子樹(shù)中繼續(xù)查找SearchBST (T-rchild, key, T, p ); / 在右子樹(shù)中繼續(xù)查找在右子樹(shù)中繼續(xù)查找

34、第64頁(yè)/共169頁(yè)30201040352523fT設(shè)設(shè) key = 48fTfT22pfTfTTTTfffp第65頁(yè)/共169頁(yè)根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不成功時(shí)才進(jìn)行; 若二叉排序樹(shù)為空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過(guò)程得到。第66頁(yè)/共169頁(yè)Status Insert BST(BiTree &T, ElemType e) / 當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于當(dāng)二叉排序樹(shù)中不存在關(guān)鍵字等于 e.key 的的 / 數(shù)據(jù)元素時(shí)，插入元素值為數(shù)據(jù)元素時(shí)，插入元素值為 e 的結(jié)點(diǎn)，并返的結(jié)點(diǎn)，并返 / 回回 TRUE; 否則，

35、不進(jìn)行插入并返回否則，不進(jìn)行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 第67頁(yè)/共169頁(yè)s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)分配空間為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 s 為新的根結(jié)點(diǎn)為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入插入 *s 為為

36、*p 的左孩子的左孩子else p-rchild = s; / 插入插入 *s 為為 *p 的右孩子的右孩子return TRUE; / 插入成功插入成功第68頁(yè)/共169頁(yè)（1）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)是葉子是葉子；（2）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)只有左子樹(shù)只有左子樹(shù)或者或者只有右子樹(shù)只有右子樹(shù)；（3）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)既有左子樹(shù)，也有右子樹(shù)?？煞挚煞秩N情況三種情況討論：討論： 和插入相反，刪除在和插入相反，刪除在查找成功查找成功之后進(jìn)行，并之后進(jìn)行，并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍仍然保持二叉排序樹(shù)的特性然保

37、持二叉排序樹(shù)的特性。第69頁(yè)/共169頁(yè)50308020908540358832（1）被刪除的結(jié)點(diǎn)是）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)例如例如:被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”第70頁(yè)/共169頁(yè)50308020908540358832（2）被刪的結(jié)點(diǎn)）被刪的結(jié)點(diǎn)只有左子樹(shù)只有左子樹(shù)或或只有右子樹(shù)只有右子樹(shù) 其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為 “指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字被刪關(guān)鍵字 = 4080第71頁(yè)/共169頁(yè)50308020908540358832

38、（3）被刪除的結(jié)點(diǎn)）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)既有左子樹(shù)，也有右子樹(shù)4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字被刪關(guān)鍵字 = 50以中序遍歷排好，20-30-32-35-40-50-80-85-88-90第72頁(yè)/共169頁(yè)Status DeleteBST (BiTree &T, KeyType key ) / 若二叉排序樹(shù)若二叉排序樹(shù) T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 key 的的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回?cái)?shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返

39、回函數(shù)值，否則返回函數(shù)值 FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于key的數(shù)據(jù)元素 else / DeleteBST算法描述如下：算法描述如下： 第73頁(yè)/共169頁(yè)if ( EQ (key, T-data.key) ) / 找到關(guān)鍵字等于找到關(guān)鍵字等于key的數(shù)據(jù)元素的數(shù)據(jù)元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 繼續(xù)在左子樹(shù)中進(jìn)行查找繼續(xù)在左子樹(shù)中進(jìn)行查找DeleteBST ( T-rchild, key

40、); / 繼續(xù)在右子樹(shù)中進(jìn)行查找繼續(xù)在右子樹(shù)中進(jìn)行查找第74頁(yè)/共169頁(yè)void Delete ( BiTree &p ) / 從從二叉排序樹(shù)中刪除結(jié)點(diǎn)二叉排序樹(shù)中刪除結(jié)點(diǎn) p， / 并重接它的左子樹(shù)或右子樹(shù)并重接它的左子樹(shù)或右子樹(shù) if (!p-rchild) else if (!p-lchild) else / Delete其中其中刪除操作刪除操作過(guò)程如下所描述：過(guò)程如下所描述： 第75頁(yè)/共169頁(yè) / 右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)右子樹(shù)為空樹(shù)則只需重接它的左子樹(shù)q = p; p = p-lchild; free(q);pp此處p應(yīng)該換為f的左孩子或右，根據(jù)p為f左還是右而定第76

41、頁(yè)/共169頁(yè)/ 左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)左子樹(shù)為空樹(shù)只需重接它的右子樹(shù)q = p; p = p-rchild; free(q);pp第77頁(yè)/共169頁(yè)q = p; s = p-lchild;while (!s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右子樹(shù)均不空左右子樹(shù)均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接重接*q的左子樹(shù)的左子樹(shù)free(s);pqs第78頁(yè)/共169頁(yè) 對(duì)于每一棵特定的二

42、叉排序樹(shù)，對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它均可按照平均查找長(zhǎng)度的定義來(lái)求它的的 ASL 值，顯然，由值相同的值，顯然，由值相同的 n 個(gè)關(guān)個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹(shù)的平均查找長(zhǎng)叉排序樹(shù)的平均查找長(zhǎng) 度的值不同，度的值不同，甚至可能差別很大。甚至可能差別很大。第79頁(yè)/共169頁(yè)由關(guān)鍵字序列由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹(shù)構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)，構(gòu)造而得的二叉排序樹(shù)，2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL

43、 =（1+2+3+2+3）/ 5 = 2.2第80頁(yè)/共169頁(yè) 下面討論平均情況下面討論平均情況: 不失一般性，假設(shè)長(zhǎng)度為不失一般性，假設(shè)長(zhǎng)度為 n 的序列中有的序列中有 k 個(gè)關(guān)鍵字個(gè)關(guān)鍵字小于小于第一個(gè)關(guān)鍵字，則必有第一個(gè)關(guān)鍵字，則必有 n-k-1 個(gè)關(guān)鍵字個(gè)關(guān)鍵字大于大于第一個(gè)關(guān)鍵字第一個(gè)關(guān)鍵字,由它構(gòu)造的二由它構(gòu)造的二叉排序樹(shù)叉排序樹(shù)n-k-1k的平均查找長(zhǎng)度是的平均查找長(zhǎng)度是 n 和和 k 的函數(shù)的函數(shù)P(n, k) ( 0 k n-1 )第81頁(yè)/共169頁(yè) 假設(shè)假設(shè) n 個(gè)關(guān)鍵字可能出現(xiàn)的個(gè)關(guān)鍵字可能出現(xiàn)的 n! 種排列種排列的可能性相同，則含的可能性相同，則含 n 個(gè)關(guān)鍵字的

44、二叉排個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度序樹(shù)的平均查找長(zhǎng)度10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在在等概率查找等概率查找的情況下，的情況下，第82頁(yè)/共169頁(yè)RiLirootniiCCCnCnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn第83頁(yè)/共169頁(yè)由此可類(lèi)似于解差分方程，此遞歸方程有解：可類(lèi)似于解差分方程，此遞歸方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn第84頁(yè)/共169頁(yè)何謂何謂“二叉平衡樹(shù)二叉平衡樹(shù)”

45、？ 二叉平衡樹(shù)的查找性能分析二叉平衡樹(shù)的查找性能分析 如何構(gòu)造如何構(gòu)造“二叉平衡樹(shù)二叉平衡樹(shù)”二、二叉平衡樹(shù)第85頁(yè)/共169頁(yè) 二叉平衡樹(shù)二叉平衡樹(shù)是二叉查找樹(shù)的另一種形式，是二叉查找樹(shù)的另一種形式，其特點(diǎn)為：其特點(diǎn)為： 樹(shù)中每個(gè)結(jié)點(diǎn)的樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度左、右子樹(shù)深度之差的絕對(duì)值不大于之差的絕對(duì)值不大于1 。例如例如:1RLhh548254821是平衡樹(shù)是平衡樹(shù)不是平衡樹(shù)不是平衡樹(shù)第86頁(yè)/共169頁(yè) 構(gòu)造二叉平衡（查找）樹(shù)的方法是：構(gòu)造二叉平衡（查找）樹(shù)的方法是：在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。例如例如:依次插入的關(guān)鍵字為依次插入的關(guān)鍵字為5, 4

46、, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)向右旋轉(zhuǎn)一次一次先向右旋轉(zhuǎn)先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)再向左旋轉(zhuǎn)第87頁(yè)/共169頁(yè)426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字繼續(xù)插入關(guān)鍵字 9第88頁(yè)/共169頁(yè) 在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉排序樹(shù)相同，因此，排序樹(shù)相同，因此，查找過(guò)程中和給定查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡 樹(shù)的深度。樹(shù)的深度。平衡樹(shù)的查找性能分析：平衡樹(shù)的查找性能分析： 問(wèn)：含 n 個(gè)關(guān)鍵字的二叉平衡樹(shù)可能達(dá)到的最大深度最大深度是多少？第89頁(yè)/共169頁(yè)n = 0空樹(shù)最大深度為最

47、大深度為 0n = 1最大深度為最大深度為 1n = 2最大深度為最大深度為 2n = 4最大深度為最大深度為 3n = 7最大深度為最大深度為 4先看幾個(gè)具體情況:第90頁(yè)/共169頁(yè)反過(guò)來(lái)問(wèn)，反過(guò)來(lái)問(wèn)，深度為深度為 h 的二叉平衡樹(shù)中的二叉平衡樹(shù)中所所含結(jié)點(diǎn)的最小值含結(jié)點(diǎn)的最小值 Nh 是多少？是多少？h = 0N0 = 0h = 1h = 2h = 3一般情況下，一般情況下，N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用歸納法可證得，利用歸納法可證得， Nh = Fh+2 - 1第91頁(yè)/共169頁(yè) 因此，在二叉平衡樹(shù)上進(jìn)行查找時(shí)，因此，在二叉平衡樹(shù)上進(jìn)

48、行查找時(shí)，查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和的個(gè)數(shù)和 log(n) 相當(dāng)相當(dāng)。 由此推得，深度為由此推得，深度為 h 的二叉平衡樹(shù)的二叉平衡樹(shù)中所含結(jié)點(diǎn)的最小值中所含結(jié)點(diǎn)的最小值 Nh = h+2/5 - 1 反之，含有反之，含有 n 個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能個(gè)結(jié)點(diǎn)的二叉平衡樹(shù)能達(dá)到的最大深度達(dá)到的最大深度 hn = log ( 5 (n+1) - 2 第92頁(yè)/共169頁(yè)1定義定義2查找過(guò)程查找過(guò)程3插入操作插入操作4刪除操作刪除操作5查找性能的分析查找性能的分析三、三、 B - 樹(shù)樹(shù)第93頁(yè)/共169頁(yè)1B-樹(shù)的定義樹(shù)的定義B-樹(shù)是一種樹(shù)是一種 平衡

49、的的 多路 查找 樹(shù)：樹(shù)： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96第94頁(yè)/共169頁(yè) 在在 m 階的階的B-樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能含有：含有： n 個(gè)個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)個(gè)指向記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)個(gè)指向子樹(shù)的指針指向子樹(shù)的指針 Ai（0in）;多叉樹(shù)的特性第95頁(yè)/共169頁(yè)typedef struct BTNode int keynum; / 結(jié)點(diǎn)中結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)關(guān)鍵字個(gè)數(shù)，結(jié)點(diǎn)大小，結(jié)點(diǎn)大小 struct BTNode *parent; / 指向指向雙親

50、雙親結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針 KeyType keym+1; / 關(guān)鍵字（關(guān)鍵字（0號(hào)單元不用）號(hào)單元不用） struct BTNode *ptrm+1; / 子樹(shù)子樹(shù)指針向量指針向量 Record *recptrm+1; / 記錄記錄指針向量指針向量 BTNode, *BTree; / B樹(shù)結(jié)點(diǎn)和樹(shù)結(jié)點(diǎn)和B樹(shù)的類(lèi)型樹(shù)的類(lèi)型B-樹(shù)結(jié)構(gòu)的樹(shù)結(jié)構(gòu)的C語(yǔ)言描述如下語(yǔ)言描述如下: :第96頁(yè)/共169頁(yè)非葉結(jié)點(diǎn)中的非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)關(guān)鍵字均均自小至大自小至大有序排列，即：有序排列，即：K1 K2 keynum; i=Search(p, K); / 在在p-key1.keynum中查找中查找 i ，

51、 / p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的雙親 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功第102頁(yè)/共169頁(yè)在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入插入的位置位置必定在最下最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：3插入插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nsymbol 其中其中: p 指向雙鏈樹(shù)中某個(gè)結(jié)點(diǎn)，指向雙鏈樹(shù)中某個(gè)結(jié)點(diǎn)， 0 i K.num-1第124頁(yè)/共169頁(yè)初始狀態(tài)初始

52、狀態(tài): p=T-first; i = 0;若若 ( p & p-symbol = K.chi & ifirst; i+;若若 ( p & p-symbol != K.chi )則繼續(xù)在鍵樹(shù)的同一層上進(jìn)行查找則繼續(xù)在鍵樹(shù)的同一層上進(jìn)行查找 p=p-next;若若 ( p & p-symbol=K.chi & i=K.num-1)則則 查找成功，查找成功，返回指向相應(yīng)記錄的指針?lè)祷刂赶蛳鄳?yīng)記錄的指針 p-infoptr 若若 ( p = NULL)則表明查找不成功，返回則表明查找不成功，返回“空指針空指針”;第125頁(yè)/共169頁(yè)3. Trie樹(shù)樹(shù) 以多重鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的鍵樹(shù)結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):

53、分支結(jié)點(diǎn)分支結(jié)點(diǎn)葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)指向記錄指向記錄的指針的指針0 1 2 3 4 5 24 25 26關(guān)鍵字指向下層結(jié)點(diǎn)的指針指向下層結(jié)點(diǎn)的指針每個(gè)域?qū)?yīng)一個(gè)每個(gè)域?qū)?yīng)一個(gè)“字母字母”第126頁(yè)/共169頁(yè)0 1(A) 3 4 5(E) 9(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)分支結(jié)點(diǎn)分支結(jié)點(diǎn)指向記錄指向記錄的指針的指針第127頁(yè)/共169頁(yè)typedef struct TrieNode NodeKind kind; / 結(jié)點(diǎn)類(lèi)型結(jié)點(diǎn)類(lèi)型 union struct

54、KeyType K; Record *infoptr lf; / 葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)(關(guān)鍵字和指向記錄的指針關(guān)鍵字和指向記錄的指針) struct TrieNode *ptr27; int num bh; / 分支結(jié)點(diǎn)分支結(jié)點(diǎn)(27個(gè)指向下一層結(jié)點(diǎn)的指針個(gè)指向下一層結(jié)點(diǎn)的指針) TrieNode, *TrieTree; / 鍵樹(shù)類(lèi)型鍵樹(shù)類(lèi)型結(jié)點(diǎn)結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)的 C 語(yǔ)言描述語(yǔ)言描述:第128頁(yè)/共169頁(yè)在在 Trie 樹(shù)中查找記錄的過(guò)程樹(shù)中查找記錄的過(guò)程:假設(shè)假設(shè): T 為指向?yàn)橹赶?Trie 樹(shù)根結(jié)點(diǎn)的指針，樹(shù)根結(jié)點(diǎn)的指針， K.ch0.K.num-1 為待查關(guān)鍵字為待查關(guān)鍵字(給定值給定值

55、)。則查找過(guò)程中的基本操作為：則查找過(guò)程中的基本操作為： 搜索和對(duì)應(yīng)字母相應(yīng)的指針?biāo)阉骱蛯?duì)應(yīng)字母相應(yīng)的指針:若若 p 不空，且不空，且 p 所指為分支結(jié)點(diǎn)，所指為分支結(jié)點(diǎn)，則則 p = p-bh.Ptrord(K.Chi) ; ( 其中其中: 0 i K.num-1 )第129頁(yè)/共169頁(yè)初始狀態(tài)初始狀態(tài): p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，其中，ord 為求字符在字母表中序號(hào)的函數(shù)為求字符在字母表中序號(hào)的函數(shù)若若 ( p & p-kind=LEAF & p-lf.K=K)則則查找成功查找成功，返回指

56、向相應(yīng)記錄的指針?lè)祷刂赶蛳鄳?yīng)記錄的指針 p-lf.infoptr 反之，即反之，即 ( !p | p-kind=LEAF & p-lf.K!=K )則表明則表明查找不成功查找不成功，返回，返回“空指針空指針”;第130頁(yè)/共169頁(yè) 一、哈希表是什么？一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法二、哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法處理沖突的方法 四、哈希表的查找四、哈希表的查找 五、哈希表的刪除操作五、哈希表的刪除操作 六、對(duì)靜態(tài)查找表，。六、對(duì)靜態(tài)查找表，。9.3 哈哈 希希 表表第131頁(yè)/共169頁(yè) 以上兩節(jié)討論的表示查找表的各種以上兩節(jié)討論的表示查找表的各種結(jié)結(jié)構(gòu)構(gòu)的共同的共同特點(diǎn)特

57、點(diǎn)：記錄在表中的位置和它的記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，關(guān)鍵字之間不存在一個(gè)確定的關(guān)系， 查找的過(guò)程查找的過(guò)程為給定值依次和關(guān)鍵字集為給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字進(jìn)行合中各個(gè)關(guān)鍵字進(jìn)行比較比較， 查找的效率查找的效率取決于和給定值取決于和給定值進(jìn)行比較進(jìn)行比較的關(guān)鍵字個(gè)數(shù)。的關(guān)鍵字個(gè)數(shù)。第132頁(yè)/共169頁(yè) 用這類(lèi)方法表示的查找表，用這類(lèi)方法表示的查找表，其其平均查找長(zhǎng)度都不為零平均查找長(zhǎng)度都不為零 不同的表示方法，其差別僅在于：不同的表示方法，其差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同。關(guān)鍵字和給定值進(jìn)行比較的順序不同。第133頁(yè)/共169頁(yè) 只有一個(gè)辦法

58、：預(yù)先知道所查關(guān)鍵只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在表中的位置，字在表中的位置， 對(duì)于頻繁使用的查找表，對(duì)于頻繁使用的查找表，希望希望 ASL = 0。 即，要求：即，要求：記錄在表中位置和其關(guān)記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系鍵字之間存在一種確定的關(guān)系。第134頁(yè)/共169頁(yè)若若以下標(biāo)為以下標(biāo)為000 999 的順序表的順序表表示之。表示之。例如：例如：為每年招收的為每年招收的 1000 名新生建立名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為范圍為 xx000 xx999 (前兩位為年份前兩位為年份)。則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值則查找

59、過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，（學(xué)號(hào)）的后三位，不需要經(jīng)過(guò)比較便不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字?？芍苯訌捻樞虮碇姓业酱殛P(guān)鍵字。第135頁(yè)/共169頁(yè)但是，對(duì)于但是，對(duì)于動(dòng)態(tài)查找表動(dòng)態(tài)查找表而言，而言，因此在一般情況下，需在關(guān)鍵字與記錄因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，系，以以 f(key) 作為關(guān)鍵字為作為關(guān)鍵字為 key 的記錄的記錄在表中的位置在表中的位置，通常通常稱(chēng)稱(chēng)這個(gè)函數(shù)這個(gè)函數(shù) f(key) 為哈希函數(shù)。為哈希函數(shù)。1) 表長(zhǎng)不確定；表長(zhǎng)不確定；2) 在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字

60、所在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所 屬范圍，而不知道確切的關(guān)鍵字。屬范圍，而不知道確切的關(guān)鍵字。第136頁(yè)/共169頁(yè)Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Du 例如：例如：對(duì)于如下對(duì)于如下 9 個(gè)關(guān)鍵字個(gè)關(guān)鍵字設(shè)設(shè) 哈希函數(shù)哈希函數(shù) f(key) = (Ord(第一個(gè)字母第一個(gè)字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 10 11 12 13ChenZhaoQianSunLiWuHanYeDu問(wèn)題問(wèn)題: 若添加關(guān)鍵字 Zhou , 怎么辦？怎么辦？能否找到能否找到另一個(gè)哈希函數(shù)？第137頁(yè)/共169頁(yè)1) 哈希函數(shù)是一個(gè)哈

61、希函數(shù)是一個(gè)映象映象，即：，即： 將關(guān)鍵字的集合映射到某個(gè)地址集合上，將關(guān)鍵字的集合映射到某個(gè)地址集合上， 它的設(shè)置很靈活，只要這個(gè)地址集合的它的設(shè)置很靈活，只要這個(gè)地址集合的 大小不超出允許范圍即可大小不超出允許范圍即可;從這個(gè)例子可見(jiàn)，從這個(gè)例子可見(jiàn)，2) 由于哈希函數(shù)是一個(gè)由于哈希函數(shù)是一個(gè)壓縮映象壓縮映象，因此，因此，在一般情況下，很容易產(chǎn)生在一般情況下，很容易產(chǎn)生“沖突沖突”現(xiàn)象，現(xiàn)象，即：即： key1 key2，而，而 f(key1) = f(key2)。第138頁(yè)/共169頁(yè)3) 很難很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，一般情況下，只能選

62、擇恰當(dāng)?shù)墓：瘮?shù)，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的因此，在構(gòu)造這種特殊的“查找表查找表” 時(shí)，除了需要選擇一個(gè)時(shí)，除了需要選擇一個(gè)“好好”( (盡可能盡可能少產(chǎn)生沖少產(chǎn)生沖突突) )的哈希函數(shù)之外的哈希函數(shù)之外;還需要找還需要找到到一種一種“處理沖突處理沖突” 的方法的方法。第139頁(yè)/共169頁(yè)哈希表的定義: 根據(jù)設(shè)定的根據(jù)設(shè)定的哈希函數(shù)哈希函數(shù) H(key) 和所選和所選中的中的處理沖突的方法處理沖突的方法，將一組關(guān)鍵字，將一組關(guān)鍵字映象映象到到一個(gè)有限的、地址連續(xù)的地址集一個(gè)有限的、地址連續(xù)的地址集 (區(qū)間區(qū)間) 上，并以關(guān)鍵字

63、在地址集中的上，并以關(guān)鍵字在地址集中的“象象”作為作為相應(yīng)記錄在表中的相應(yīng)記錄在表中的存儲(chǔ)位置存儲(chǔ)位置，如此構(gòu)造所，如此構(gòu)造所得的查找表稱(chēng)之為得的查找表稱(chēng)之為“哈希表哈希表”。第140頁(yè)/共169頁(yè) 對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法: 若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。數(shù)字化處理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)法除留余數(shù)法4. 折疊法折疊法6. 隨機(jī)數(shù)法隨機(jī)數(shù)法2. 數(shù)字分析法數(shù)字分析法二、二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法第141頁(yè)/共169頁(yè)哈希函數(shù)為關(guān)鍵字的線性函數(shù)哈希函數(shù)為關(guān)

64、鍵字的線性函數(shù) H(key) = key 或者或者 H(key) = a key + b1. 直接定址法直接定址法此法僅適合于：此法僅適合于：地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小第142頁(yè)/共169頁(yè)此方法僅適合于：此方法僅適合于： 能預(yù)先估計(jì)出預(yù)先估計(jì)出全體關(guān)鍵字的每一位上每一位上各種數(shù)字出現(xiàn)的頻度數(shù)字出現(xiàn)的頻度。2. 數(shù)字分析法數(shù)字分析法 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由由 s 位數(shù)字組成位數(shù)字組成 (u1, u2, , us)，分析關(guān)，分析關(guān)鍵字集中的全體，鍵字集中的全體， 并并從中提取分布均勻從中提取分布均勻的若干位的

65、若干位或或它們的組合它們的組合作為地址。作為地址。第143頁(yè)/共169頁(yè) 以以關(guān)鍵字的平方值的中間幾位關(guān)鍵字的平方值的中間幾位作為存作為存儲(chǔ)地址。求儲(chǔ)地址。求“關(guān)鍵字的平方值關(guān)鍵字的平方值” 的目的的目的是是“擴(kuò)大差別擴(kuò)大差別” ，同時(shí)平方值的中間各，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。位又能受到整個(gè)關(guān)鍵字中各位的影響。3. 平方取中法平方取中法 此方法適合于此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。出現(xiàn)頻度很高的現(xiàn)象。第144頁(yè)/共169頁(yè) 將關(guān)鍵字分割成若干部分，然后取它將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈

66、希地址。們的疊加和為哈希地址。有兩種疊加處有兩種疊加處理的方法：移位疊加和間界疊加。理的方法：移位疊加和間界疊加。4. 折疊法折疊法 此方法適合于此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。關(guān)鍵字的數(shù)字位數(shù)特別多。第145頁(yè)/共169頁(yè)5. 除留余數(shù)法除留余數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中其中， pm ( (表長(zhǎng)表長(zhǎng)) ) 并且并且 p 應(yīng)為不大于應(yīng)為不大于 m 的素?cái)?shù)的素?cái)?shù) 或是或是 不含不含 20 以下的質(zhì)因子以下的質(zhì)因子第146頁(yè)/共169頁(yè) 給定一組關(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 加限制？加限制？ 可見(jiàn)，若可見(jiàn)，若 p 中含質(zhì)因子中含質(zhì)因子 3, 則所有含質(zhì)因則所有含質(zhì)因子子 3 的關(guān)鍵字均映射到的關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的地的地址上址上，從而增加了，從而增加了“沖突沖突”的可能。的可能。第147頁(yè)/共169頁(yè)6.隨機(jī)數(shù)法隨機(jī)數(shù)法設(shè)定哈希函