沒(méi)有幻燈片標(biāo)題 - 武漢大學(xué)

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

2、查找表可分為兩類查找表可分為兩類:是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素（或記錄）。關(guān)鍵字關(guān)鍵字 若此關(guān)鍵字可以識(shí)別唯一的唯一的一個(gè)記錄，則稱之謂“主關(guān)鍵字主關(guān)鍵字”。 若此關(guān)鍵字能識(shí)別若干若干記錄，則稱之謂“次關(guān)鍵字次關(guān)鍵字”。 根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄） 查找查找 若查找表中存在這樣一個(gè)記錄，則稱“查找成功查找成功”，查找結(jié)果：給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置； 否則稱“查找不成功查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。 由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便

3、于查找。 為了提高查找的效率， 需要在查找表中的元素之間人為地 附加某種確定的關(guān)系，換句話說(shuō)， 用另外一種結(jié)構(gòu)來(lái)表示查找表用另外一種結(jié)構(gòu)來(lái)表示查找表。如何進(jìn)行查找？如何進(jìn)行查找？查找的方法取決于查找表的結(jié)構(gòu)。查找的方法取決于查找表的結(jié)構(gòu)。9.1 靜態(tài)查找表靜態(tài)查找表9.2 動(dòng)態(tài)查找樹(shù)表動(dòng)態(tài)查找樹(shù)表9.3 哈希表哈希表9.1 靜靜 態(tài)態(tài) 查查 找找 表表數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)每個(gè)數(shù)據(jù)元素含有類型相同的據(jù)元素含有類型相同的關(guān)鍵字關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。 數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable Create(&a

4、mp;ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：next ADT StaticSearchTable構(gòu)造一個(gè)含 n 個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。 Create(&ST, n);操作結(jié)果：銷毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；若 ST 中存在其關(guān)鍵字等于 kval 的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。 Search(ST, kval);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，kval 為和查找表中元素的關(guān)鍵字類型相

5、同的給定值；按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST, Visit();初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)；假設(shè)靜態(tài)查找表靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)為typedef struct *elem; / 數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí) / 按實(shí)際長(zhǎng)度分配，0號(hào)單元留空 int length; / 表的長(zhǎng)度 SSTable;ElemType數(shù)據(jù)元素類型的定義為數(shù)據(jù)元素類型的定義為:typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemTy

6、pe ; , TElemType ;一、順序查找表一、順序查找表二、有序查找表二、有序查找表三、靜態(tài)查找樹(shù)表三、靜態(tài)查找樹(shù)表三、索引順序表三、索引順序表 以順序表或線性鏈表表示靜態(tài)查找表一、順序查找表順序查找表21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem回顧順序表的查找過(guò)程：回顧順序表的查找過(guò)程：假設(shè)給定值 e = 64,要求 ST.elemi = e, 問(wèn): i = ?ii66iiint location( SqList L, ElemType& e, Status (*comp

7、are)(ElemType, ElemType) i = 1; p = L.elem; while ( i=L.length & !(*compare)(*p+,e) i+; if ( i= L.length) return i; else return 0; /locationi=L.length21 37 88 19 92 05 64 56 80 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

8、.elemi60ikval = 64kval = 60i64int Search_Seq(SSTable ST, KeyType kval) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = kval; / 設(shè)置“哨兵” for (i=ST.length; -i); / 從后往前找 return i; / 找不到時(shí)，i為0 / Search_SeqST.elemi.key!=kval;分析順序查找的時(shí)間性能。 定義：定義： 查找算法的平均查找長(zhǎng)度平均查找長(zhǎng)度 (Average Search Len

9、gth) 為確定記錄在查找表中的位置，需和給定值 進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值 niiiCPASL1其中: n 為表長(zhǎng)，Pi 為查找表中第i個(gè)記錄的概率， 且 Ci為找到該記錄時(shí)，曾和給定值 比較過(guò)的關(guān)鍵字的個(gè)數(shù)11niiP順序表查找的平均查找長(zhǎng)度為：對(duì)順序表順序表而言，Ci = n-i+121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+PnnPi1在等概率查找的情況下， 若查找概率無(wú)法事先測(cè)定，則查找過(guò)程采取的改進(jìn)辦法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss 在 PnPn-1P2P1時(shí)取極小值

10、上述順序查找表的查找算法簡(jiǎn)單， 但平均查找長(zhǎng)度較大，特別不適用于表長(zhǎng)較大的查找表。二、有序查找表二、有序查找表 若以有序表有序表表示靜態(tài)查找表，則查找過(guò)程可以基于“折半折半”進(jìn)行。05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 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。int Search_Bin ( SSTable ST, KeyType kv

11、al ) low = 1; high = ST.length; / 置區(qū)間初值 while (low = high) mid = (low + high) / 2; if （kval = ST.elemmid.key ) return mid; / 找到待查元素 else if ( kval 50 時(shí)，可得近似結(jié)果 關(guān)鍵字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3三、靜態(tài)查找樹(shù)表三、靜態(tài)查找樹(shù)表 在不等概率查找不等概率查找的情況下，折半查找折半查找不是不是有序表最好的查找方法例如例如:此時(shí) ASL=20.2+30.3+10.05+20

12、.3+30.15=2.4若改變Ci的值 2 1 3 2 3則 ASL=20.2+10.3+30.05+20.3+30.15=1.9 使 達(dá)最小的判定樹(shù)稱為最優(yōu)二叉樹(shù)，其中: 111niiCiqniiCipASL1111niiniiqp定義定義:為計(jì)算方便，令 wi = pi選擇二叉樹(shù)的根結(jié)點(diǎn)，使 達(dá)最小 111ijjhijjiwwP介紹一種次優(yōu)二叉樹(shù)的構(gòu)造方法:為便于計(jì)算，引入累計(jì)權(quán)值和 ijjiwsw1并設(shè) wl-1 = 0 和 swl-1 = 0，11)(iilhiswswswswP則推導(dǎo)可得j01234567wj02153435swjpjkeyA B C D E F G023811 15

13、 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG301311)(iilhiswswswswPECGABDF所得次優(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和折半查找相比較和折半查找相比較DBACFEGStatus SecondOptimal(BiTree &T, ElemType R, float sw, int low, int high

14、) / 由有序表Rlow.high及其累計(jì)權(quán)值表sw / 遞歸構(gòu)造次優(yōu)查找樹(shù)T。 選擇最小的選擇最小的Pi值值 if (!(T = new BiTNode) return ERROR; T-data = Ri; / 生成結(jié)點(diǎn)構(gòu)造次優(yōu)二叉樹(shù)的算法if (i=low) T-lchild = NULL; / 左子樹(shù)空else SecondOptimal(T-lchild, R, sw, low, i-1); / 構(gòu)造左子樹(shù) if (i=high) T-rchild = NULL; / 右子樹(shù)空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 構(gòu)造右

15、子樹(shù) return OK; / SecondOptimal次優(yōu)查找樹(shù)采用二叉鏈表的存儲(chǔ)結(jié)構(gòu)Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表 ST 構(gòu)造一棵次優(yōu)查找樹(shù) T。 / ST 的數(shù)據(jù)元素含有權(quán)域 weight if (ST.length = 0) T = NULL; else FindSW(sw, ST); / 按照有序表 ST 中各數(shù)據(jù)元素 / 的 weight 值求累計(jì)權(quán)值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree四、索引順

16、序表四、索引順序表在建立順序表的同時(shí)，建立一個(gè)索引。在建立順序表的同時(shí)，建立一個(gè)索引。012345678910 11 12 1317 08 21 19 14 31 33 22 25 40 52 61 78 4621 040 578 10例如：例如：索引順序表索引順序表 = = 索引索引 + + 順序表順序表順序表順序表索引索引typedef struct KeyType maxkey; int stadr;indexItem; / 索引項(xiàng)typedef struct indexItem *elem; int stadr;indexTable; / 索引表索引順序表的查找過(guò)程：索引順序表的查找過(guò)

17、程：1）由索引確定記錄所在區(qū)間；2）在順序表的某個(gè)區(qū)間內(nèi)進(jìn)行查找?？梢?jiàn)， 索引順序查找索引順序查找的過(guò)程也是一個(gè)“縮小區(qū)間縮小區(qū)間”的查找過(guò)程。順序表順序表有序表有序表表的特性表的特性無(wú)序有序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序 或 鏈?zhǔn)巾樞虿鍎h操作插刪操作易于進(jìn)行需移動(dòng)元素ASL的值的值大小對(duì)比順序表和有序表的查找性能對(duì)比順序表和有序表的查找性能：索引順序查找的平均查找長(zhǎng)度索引順序查找的平均查找長(zhǎng)度 = 查找查找“索引索引”的平均查找長(zhǎng)度的平均查找長(zhǎng)度 + 查找查找“順序表順序表”的平均查找長(zhǎng)度的平均查找長(zhǎng)度注意：注意： 索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造。索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造。ADT Dynamic

18、SearchTable 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型動(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è)集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字， 可唯一標(biāo)識(shí)數(shù)據(jù)元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();nextADT DynamicSearc

19、hTable操作結(jié)果：操作結(jié)果：構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。InitDSTable(&DT);銷毀動(dòng)態(tài)查找表DT。DestroyDSTable(&DT);初始條件： 操作結(jié)果：動(dòng)態(tài)查找表DT存在；若 DT 中存在其關(guān)鍵字等于 kval的數(shù)據(jù)元素，則函數(shù)值為TRUE，p 指示該元素在表中的位置，否則為函數(shù)值為FALSE，p 指示插入位置。SearchDSTable(DT, kval, p);初始條件：操作結(jié)果： 動(dòng)態(tài)查找表 DT 存在，kval為和關(guān)鍵字類型相同的給定值；動(dòng)態(tài)查找表 DT 存在， e 為待插入的數(shù)據(jù)元素；InsertDSTable(&DT, e);初始條件

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

21、綜合上一節(jié)討論的幾種查找表的特性：綜合上一節(jié)討論的幾種查找表的特性：查找 插入 刪除無(wú)序順序表 無(wú)序線性鏈表有序順序表 有序線性鏈表 靜態(tài)查找樹(shù)表(n)(n) (logn)(n) (logn)(1) (1)(n) (1)(nlogn)1）從查找性能看，最好情況能達(dá) (logn)，此時(shí)要求表有序；2）從插入和刪除的性能看，最好 情況能達(dá) (1)，此時(shí)要求存儲(chǔ) 結(jié)構(gòu)是鏈表?？傻萌缦陆Y(jié)論：可得如下結(jié)論：一、二叉排序樹(shù)（二叉查找樹(shù)）一、二叉排序樹(shù)（二叉查找樹(shù)）二、二叉平衡樹(shù)二、二叉平衡樹(shù)三、三、B - 樹(shù)樹(shù)四、四、B+樹(shù)樹(shù)五、鍵五、鍵 樹(shù)樹(shù)一、二叉排序樹(shù)一、二叉排序樹(shù)（二叉查找樹(shù)）（二叉查找樹(shù)）1定義

22、定義2查找算法查找算法3插入算法插入算法4刪除算法刪除算法5查找性能的分析查找性能的分析（1）若它的左子樹(shù)不空，則左子樹(shù)上 所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；1定義：定義： 二叉排序樹(shù)或者是一棵空樹(shù)；或者是具有如下特性的二叉樹(shù)：（3）它的左、右子樹(shù)也都分別是二叉 排序樹(shù)。（2）若它的右子樹(shù)不空，則右子樹(shù)上 所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；503080209010854035252388例如例如:是二叉排序樹(shù)。是二叉排序樹(shù)。66不不 通常，取二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu) struct BiTNode *lchild, *rchild

23、; / 左右孩子指針 BiTNode, *BSTree;TElemType data;2二叉排序樹(shù)的查找算法：二叉排序樹(shù)的查找算法： 1）若給定值等于等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功查找成功； 2）若給定值小于小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找繼續(xù)在左子樹(shù)上進(jìn)行查找； 3）若給定值大于大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找繼續(xù)在右子樹(shù)上進(jìn)行查找。否則若二叉排序樹(shù)為空為空，則查找不成功查找不成功；50308020908540358832例如例如:二叉排序樹(shù)二叉排序樹(shù)查找關(guān)鍵字查找關(guān)鍵字= 50 ,505035 ,503040355090 ,50809095 ,從上述查找過(guò)程可見(jiàn)，從

24、上述查找過(guò)程可見(jiàn)， 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支遞歸進(jìn)行查詢直至關(guān)鍵字等于給定值的遞歸進(jìn)行查詢直至關(guān)鍵字等于給定值的結(jié)點(diǎn)結(jié)點(diǎn);或者 從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支遞歸進(jìn)行查詢直至子樹(shù)為空樹(shù)止。遞歸進(jìn)行查詢直至子樹(shù)為空樹(shù)止。 查找成功查找成功 查找不成功查找不成功算法描述如下：算法描述如下：Status SearchBST (BiTree T, KeyType kval, BiTree f, BiTree &p ) / 在根指針在根指針 T 所指二叉排序樹(shù)中遞歸地查找其所指二叉排序樹(shù)中遞歸地查找其 / 關(guān)鍵字等于關(guān)鍵字

25、等于 kval 的數(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)前訪問(wèn)指向當(dāng)前訪問(wèn) / 的結(jié)點(diǎn)的雙親，其初始調(diào)用值為的結(jié)點(diǎn)的雙親，其初始調(diào)用值為NULLif (!T)else if ( EQ(kval, T-data.key) ) else if (

26、 LT(kval, T-data.key) ) else p = f; return FALSE; / 查找不成功 p = T; return TRUE; / 查找成功return SearchBST (T-lchild, kval, T, p ); / 返回在左子樹(shù)中繼續(xù)查找的結(jié)果return SearchBST (T-rchild, kval, T, p ); / 返回在右子樹(shù)中繼續(xù)查找的結(jié)果fT設(shè) key = 48fTfT22pfTfTTTTfffp30201040352523 根據(jù)動(dòng)態(tài)查找表的定義，“插入插入”操作在操作在查找不成功查找不成功時(shí)才進(jìn)行時(shí)才進(jìn)行;3二叉排序樹(shù)的插入算法二叉

27、排序樹(shù)的插入算法 若二叉排序樹(shù)為空樹(shù)空樹(shù)，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個(gè)新的葉子結(jié)點(diǎn)新的葉子結(jié)點(diǎn)，其插入位置插入位置由查找過(guò)程得到。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; 否則，不進(jìn)行插入并返回否則，不進(jìn)行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return

28、 FALSE; / Insert BST ps = new BiTNode; / 為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點(diǎn)else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子else p-rchild = s; / 插入 *s 為 *p 的右孩子return TRUE; / 插入成功 （1）被刪除的結(jié)點(diǎn)是葉子； （2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或者只有右子樹(shù)； （3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)。4二

29、叉排序樹(shù)的刪除算法二叉排序樹(shù)的刪除算法可分三種情況討論： 和插入相反，刪除在查找成功查找成功之后進(jìn)行，并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后，仍仍然保持二叉排序樹(shù)的特性然保持二叉排序樹(shù)的特性。50308020908540358832（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)例如例如:被刪關(guān)鍵字被刪關(guān)鍵字 = 2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空空”50308020908540358832（2）被刪除的結(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ù)

30、或右子樹(shù)”。被刪關(guān)鍵字被刪關(guān)鍵字 = 408050308020908540358832（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)，也有右子樹(shù)既有左子樹(shù)，也有右子樹(shù)4040以其前驅(qū)替代之，然以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)后再刪除該前驅(qū)結(jié)點(diǎn)被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)被刪關(guān)鍵字被刪關(guān)鍵字 = 50Status DeleteBST (BiTree &T, KeyType kval ) / 若二叉排序樹(shù)若二叉排序樹(shù) T 中存在其關(guān)鍵字等于中存在其關(guān)鍵字等于 kval 的的 / 數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回?cái)?shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點(diǎn)，并返回 / 函數(shù)值函數(shù)值 TRUE，否則返回函數(shù)值，否則返回函數(shù)值

31、FALSE if (!T) return FALSE; / 不存在關(guān)鍵字等于kval的數(shù)據(jù)元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (kval, T-data.key) ) / 找到關(guān)鍵字等于key的數(shù)據(jù)元素else if ( LT (kval, T-data.key) ) else Delete (T); return TRUE; return DeleteBST ( T-lchild, kval ); / 繼續(xù)在左子樹(shù)中進(jìn)行查找return DeleteBST ( T-rchild, kval ); / 繼續(xù)在右子樹(shù)中進(jìn)行查找void Delete

32、 ( BiTree &p ) / 從二叉排序樹(shù)中刪除結(jié)點(diǎn) p， / 并重接它的左子樹(shù)或右子樹(shù) if (!p-rchild) else if (!p-lchild) else / Delete其中刪除操作刪除操作過(guò)程如下所描述： p / 右子樹(shù)為空樹(shù)時(shí)只需重接它的左子樹(shù)q = p; p = p-lchild; delete(q);pqq/ 左子樹(shù)為空樹(shù)時(shí)只需重接它的右子樹(shù)q = p; p = p-rchild; delete(q);ppqqq = p; s = p-lchild;while (s-rchild) q = s; s = s-rchild; / s 指向被刪結(jié)點(diǎn)的前驅(qū)/ 左右

33、子樹(shù)均不空p-data = s-data; q-rchild = s-lchild;delete(s);pqsif (q != p ) else q-lchild = s-lchild; / 重接*q的左子樹(shù)5查找性能的分析查找性能的分析 對(duì)于每一棵特定的二叉排序樹(shù)，均可按照平均查找長(zhǎng)度的定義來(lái)求它的 ASL 值，顯然，由值相同的 n 個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹(shù)的平均查找長(zhǎng)度的值不同，甚至可能差別很大。由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹(shù)由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹(shù)，例如：例如：2134535412ASL =（1+2+3+4+5）/ 5

34、 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面討論平均情況下面討論平均情況: 不失一般性，假設(shè)長(zhǎng)度為 n 的序列中有 k 個(gè)關(guān)鍵字小于小于第一個(gè)關(guān)鍵字，則必有 n-k-1 個(gè)關(guān)鍵字大于大于第一個(gè)關(guān)鍵字,由它構(gòu)造的二叉排序樹(shù)n-k-1k的平均查找長(zhǎng)度是 n 和 k 的函數(shù)P(n, k) ( 0 k n-1 ) 假設(shè) k 從 0 到 n-1 的可能性相同，則含 n 個(gè)關(guān)鍵字的二叉排序樹(shù)的平均查找長(zhǎng)度10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在等概率查找等概率查找的情況下，RiLirootniiCCCnCnknP11),(1)1)1()(1()1

35、)(11knPknkPkn)1()1()(11knPknkPkn由此可類似于解差分方程，此遞歸方程得解為:10) 1() 1()(111)(nkknPknkPknnnP112)(21nkkPkn2ln)11 (2)(nnnnP二、二叉平衡樹(shù)二、二叉平衡樹(shù) 何謂何謂“二叉平衡樹(shù)二叉平衡樹(shù)”？ 二叉平衡樹(shù)的查找性能分析二叉平衡樹(shù)的查找性能分析 如何構(gòu)造如何構(gòu)造“二叉平衡樹(shù)二叉平衡樹(shù)” 二叉平衡樹(shù)二叉平衡樹(shù)是二叉查找樹(shù)的另一種形式，其特點(diǎn)為： 樹(shù)中每個(gè)結(jié)點(diǎn)的樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度左、右子樹(shù)深度之差的絕對(duì)值不大于之差的絕對(duì)值不大于1 。例如例如:1RLhh548254821是平衡樹(shù)是平衡樹(shù)不是平

36、衡樹(shù)不是平衡樹(shù) 構(gòu)造二叉平衡（查找）樹(shù)的方法是：在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)426589426895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字 9 在平衡樹(shù)上進(jìn)行查找的過(guò)程和二叉排序樹(shù)相同，因此，查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過(guò)平衡 樹(shù)的深度。平衡樹(shù)的查找性能分析：平衡樹(shù)的查找性能分析： 問(wèn)：含 n 個(gè)關(guān)鍵字的二叉平衡樹(shù)可能達(dá)到的最大深度最大深度是多少？n = 0空樹(shù)空樹(shù)最大深度為最大深度為 0n = 1最大深度為最大深度為

37、1n = 2最大深度為最大深度為 2n = 4最大深度為最大深度為 3n = 7最大深度為最大深度為 4先看幾個(gè)具體情況:反過(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 因此，在二叉平衡樹(shù)二叉平衡樹(shù)上進(jìn)行查找時(shí)，查找過(guò)程中和給定值進(jìn)行比較的關(guān)鍵字進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)和的個(gè)數(shù)和 log(n) 相當(dāng)。 由此推得，深度為深度為 h 的二叉

38、平衡樹(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 三、三、 B - 樹(shù)樹(shù)1定義定義2查找過(guò)程查找過(guò)程3插入操作插入操作4刪除操作刪除操作5查找性能的分析查找性能的分析1B-樹(shù)的定義樹(shù)的定義B-樹(shù)是一種 平衡平衡 的 多路多路 查找查找 樹(shù)： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 階的B-樹(shù)上，每個(gè)非終端結(jié)點(diǎn)可能含有： n 個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)指向

39、記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)指向子樹(shù)的指針指向子樹(shù)的指針 Ai（0in）;多叉樹(shù)的特性typedef struct BTNode int keynum; / 結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)，結(jié)點(diǎn)大小 struct BTNode *parent; / 指向雙親結(jié)點(diǎn)的指針 KeyType keym+1; / 關(guān)鍵字（0號(hào)單元不用） struct BTNode *ptrm+1; / 子樹(shù)指針向量 Record *recptrm+1; / 記錄指針向量 BTNode, *BTree; / B樹(shù)結(jié)點(diǎn)和B樹(shù)的類型B-樹(shù)結(jié)構(gòu)的樹(shù)結(jié)構(gòu)的 C 語(yǔ)言描述如下語(yǔ)言描述如下: : 非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)

40、關(guān)鍵字均自小至大自小至大有序排列，即：K1 K2 keynum; i=Search(p, K); / 在p-key1.keynum中查找 i ， 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); / 查找不成功在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入插入的位置位置必定在最下最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：3插入插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nsym

41、bol 其中: p 指向雙鏈樹(shù)中某個(gè)結(jié)點(diǎn)， 0 i K.num-1初始狀態(tài): p=T-first; i = 0;若 ( p & p-symbol = K.chi & ifirst; i+;若 ( p & p-symbol != K.chi )則繼續(xù)在鍵樹(shù)的同一層上進(jìn)行查找 p=p-next;若 ( p & p-symbol=K.chi & i=K.num-1)則 查找成功，返回指向相應(yīng)記錄的指針 p-infoptr 若 ( p = NULL)則表明查找不成功，返回“空指針”;3. Trie樹(shù)樹(shù) 以多重鏈表作存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的鍵樹(shù)結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu):分支結(jié)點(diǎn)分支

42、結(jié)點(diǎn)葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)指向記錄的指針0 1 2 3 4 5 24 25 26關(guān)鍵字關(guān)鍵字指向下層結(jié)點(diǎn)的指針每個(gè)域?qū)?yīng)一個(gè)“字母”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)指向記錄指向記錄的指針的指針typedef struct TrieNode NodeKind kind; / 結(jié)點(diǎn)類型 union struct KeyType K; Record *infoptr lf; / 葉子結(jié)點(diǎn)(關(guān)鍵字和指向記錄的指針) str

43、uct TrieNode *ptr27; int num bh; / 分支結(jié)點(diǎn)(27個(gè)指向下一層結(jié)點(diǎn)的指針) TrieNode, *TrieTree; / 鍵樹(shù)類型結(jié)點(diǎn)結(jié)構(gòu)的結(jié)點(diǎn)結(jié)構(gòu)的 C 語(yǔ)言描述語(yǔ)言描述:在在 Trie 樹(shù)中查找記錄的過(guò)程樹(shù)中查找記錄的過(guò)程:假設(shè)假設(shè): T 為指向 Trie 樹(shù)根結(jié)點(diǎn)的指針， K.ch0.K.num-1 為待查關(guān)鍵字(給定值)。則則查找過(guò)程中的基本操作為： 搜索和對(duì)應(yīng)字母相應(yīng)的指針?biāo)阉骱蛯?duì)應(yīng)字母相應(yīng)的指針:若若 p 不空，且 p 所指為分支結(jié)點(diǎn)，則則 p = p-bh.Ptrord(K.Chi) ; ( 其中: 0 i K.num-1 )初始狀態(tài)初始狀態(tài):

44、p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，ord 為求字符在字母表中序號(hào)的函數(shù)若若 ( p & p-kind=LEAF & p-lf.K=K)則則 查找成功查找成功，返回返回指向相應(yīng)記錄的指針 ptr 反之，反之，即 ( !p | p-kind=LEAF & p-lf.K!=K )則則表明查找不成功查找不成功，返回返回“空指針”; 一、一、什么是哈希表？什么是哈希表？二、哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法三、處理沖突的方法處理沖突的方法 四、哈希表的查

45、找和插入哈希表的查找和插入 五、哈希表的刪除操作哈希表的刪除操作 六、對(duì)靜態(tài)查找表，。對(duì)靜態(tài)查找表，。9.3 哈哈 希希 表表 以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)結(jié)構(gòu)的共同特點(diǎn)特點(diǎn)：記錄在表中的位置位置和它的關(guān)關(guān)鍵字鍵字之間不存在不存在一個(gè)確定的關(guān)系，一、什么是哈希表？什么是哈希表？ 查找的過(guò)程查找的過(guò)程為給定值給定值依次和關(guān)鍵字集合中各個(gè)關(guān)鍵字關(guān)鍵字進(jìn)行比較比較， 查找的效率查找的效率取決于和給定值進(jìn)行比較進(jìn)行比較的關(guān)鍵字個(gè)數(shù)個(gè)數(shù)。 用這類方法表示的查找表，其平均查找長(zhǎng)度都不為零 不同的表示方法，其差別僅在于：差別僅在于：關(guān)鍵字和給定值進(jìn)行比較的順序不同。 只有一個(gè)辦法：預(yù)先知道所查關(guān)鍵字在

46、表中的位置， 對(duì)于頻繁使用的查找表，希望 ASL = 0。 即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。若以下標(biāo)為以下標(biāo)為000 999 的順序表的順序表表示之。例如：為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學(xué)號(hào)，其值的范圍為 xx000 xx999 (前兩位為年份)。則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定值（學(xué)號(hào)）的后三位，不需要經(jīng)過(guò)比較不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字。但是，對(duì)于動(dòng)態(tài)查找表動(dòng)態(tài)查找表而言，因此在一般情況下，需在關(guān)鍵字與記錄在表中的存儲(chǔ)位置之間建立一個(gè)函數(shù)關(guān)系，以 f(key) 作為關(guān)鍵字為 key 的記錄在表中的位置，通常稱這個(gè)函數(shù) f(

47、key) 為哈希函數(shù)。1) 表長(zhǎng)不確定；2) 在設(shè)計(jì)查找表時(shí)，只知道關(guān)鍵字所 屬范圍，而不知道確切的關(guān)鍵字。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei 例如：對(duì)于如下 9 個(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 1 0 1 1 1 2 1 3ChenZhaoQianSunLiWuHanYeDei問(wèn)題問(wèn)題: 若添加關(guān)鍵字 Zhou , 怎么辦？怎么辦？能否找到能否找到另一個(gè)哈希函數(shù)？1) 哈希(Hash)函數(shù)是一個(gè)映象映象，即： 將關(guān)鍵字的集合

48、映射到某個(gè)地址集合上，將關(guān)鍵字的集合映射到某個(gè)地址集合上， 它的設(shè)置很靈活靈活，只要這個(gè)地址集地址集合的 大小不超出允許范圍不超出允許范圍即可;從這個(gè)例子可見(jiàn)，從這個(gè)例子可見(jiàn)，2) 由于哈希函數(shù)是一個(gè)壓縮映象壓縮映象，因此，在一般情況下，很容易產(chǎn)生“沖突沖突”現(xiàn)象，即： key1 key2，而 f(key1) = f(key2)。3) 很難很難找到一個(gè)不產(chǎn)生沖突的哈希函數(shù)。一般情況下，只能選擇恰當(dāng)?shù)墓：瘮?shù)，使沖突盡可能少地產(chǎn)生。 因此，在構(gòu)造這種特殊的“查找表” 時(shí)，除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外;還需要找到一種“處理沖突” 的方法。哈希表的定義: 根據(jù)設(shè)定的哈希函

49、數(shù)哈希函數(shù) H(key) 和所選中的處理沖突的方法處理沖突的方法，將一組關(guān)鍵字映象映象到到一個(gè)有限的、地址連續(xù)的地址集 (區(qū)間) 上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲(chǔ)位置存儲(chǔ)位置，如此構(gòu)造所得的查找表稱之為“哈希表哈希表”。二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法 對(duì)數(shù)字?jǐn)?shù)字的關(guān)鍵字可有下列構(gòu)造方法: 若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先需先對(duì)其進(jìn)行進(jìn)行數(shù)字化處理數(shù)字化處理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)法除留余數(shù)法4. 折疊法折疊法6. 隨機(jī)數(shù)法隨機(jī)數(shù)法2. 數(shù)字分析法數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者

50、 H(key) = a key + b1. 直接定址法直接定址法此法僅適合于：此法僅適合于：地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小此方法僅適合于：此方法僅適合于： 能預(yù)先估計(jì)出預(yù)先估計(jì)出全體關(guān)鍵字的每一位上每一位上各種數(shù)字出現(xiàn)的頻度數(shù)字出現(xiàn)的頻度。2. 數(shù)字分析法數(shù)字分析法 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。 以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響

51、。3. 平方取中法平方取中法 此方法適合于此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。4. 折疊法折疊法 此方法適合于此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。將關(guān)鍵字分割成若干部分，然后取它們的“疊加和” 為哈希地址。有兩種疊加處理的方法：移位疊加移位疊加和間界疊加間界疊加。例如：key = 110108380428895移位疊加移位疊加 895 428 380 108+) 110 895 824 380 801+) 110間界疊加間界疊加19211301035. 除留余數(shù)法除留余數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中其中， p

52、m ( (表長(zhǎng)表長(zhǎng)) ) 并且并且 p 應(yīng)為不大于應(yīng)為不大于 m 的素?cái)?shù)的素?cái)?shù) 或是或是 不含不含 20 以下的質(zhì)因子以下的質(zhì)因子 給定一組關(guān)鍵字為: 12, 39, 18, 24, 33, 21，若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3例如：例如：為什么要對(duì) p 加限制？ 可見(jiàn)，若 p 中含質(zhì)因子 3, 則所有含質(zhì)因則所有含質(zhì)因子子 3 的關(guān)鍵字均映射到的關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的地的地址上址上，從而增加了“沖突”的可能。6.隨機(jī)數(shù)法隨機(jī)數(shù)法設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = Random(key)其中，其中，Random 為偽隨

53、機(jī)函數(shù)為偽隨機(jī)函數(shù) 通常，此方法用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。 實(shí)際造表時(shí)，采用何種采用何種構(gòu)造哈希函數(shù)的方法方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))，總的原則是使產(chǎn)生沖突的可能性降到的原則是使產(chǎn)生沖突的可能性降到盡可能地小盡可能地小。三、處理沖突的方法處理沖突的方法 “處理沖突處理沖突” 的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)尋找下一個(gè)哈希地址1. 開(kāi)放定址法開(kāi)放定址法2. 鏈地址法鏈地址法 為產(chǎn)生沖突的地址 H(key) 求得一個(gè)地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di

54、 ) MOD m i=1, 2, , s1. 開(kāi)放定址法開(kāi)放定址法對(duì)增量 di 有三種取法： 1) 線性探測(cè)再散列線性探測(cè)再散列 di = c i 最簡(jiǎn)單的情況 c=1 2) 平方探測(cè)再散列平方探測(cè)再散列 di = 12, -12, 22, -22, , , 3) 隨機(jī)探測(cè)再散列隨機(jī)探測(cè)再散列 di 是一組偽隨機(jī)數(shù)列偽隨機(jī)數(shù)列 或者 di=iH2(key) (又稱雙散列函數(shù)探測(cè)又稱雙散列函數(shù)探測(cè))即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的 s(m-1)個(gè)個(gè) Hi 值能覆蓋覆蓋哈希表中所有 地址。則要求： 注意：注意：增量增量 di 應(yīng)具有應(yīng)具有“完備性完備性” 隨機(jī)探測(cè)時(shí)的 m 和 di 沒(méi)有公因

55、子。 平方探測(cè)時(shí)的表長(zhǎng) m 必為形如 4j+3 的素?cái)?shù)（如: 7, 11, 19, 23, 等）； H2(key) 是另設(shè)定的一個(gè)哈希函數(shù)，它的函數(shù)值應(yīng)和 m 互為素?cái)?shù)。若 m 為素?cái)?shù)，則 H2(key) 可以是 1 至 m-1 之間的任意數(shù)任意數(shù); 若 m 為 2 的冪次，則 H2(key) 應(yīng)是 1 至 m-1 之間的任意奇數(shù)任意奇數(shù)。例如，當(dāng) m=11時(shí)， 可設(shè) H2(key)=(3 key) MOD 10+1 0 1 2 3 4 5 6 7 8 9 101901231455681182362 1 1 1 2 1 2 1 3例如例如: 關(guān)鍵字集合 19, 01, 23, 14, 55,

56、68, 11, 82, 36 設(shè)定設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長(zhǎng)=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10190123 145568190123 1468若采用線性探測(cè)再散列線性探測(cè)再散列處理沖突若采用二次探測(cè)再散列二次探測(cè)再散列處理沖突11 8236551182361 1 2 1 3 6 2 5 1將所有哈希地址相同的記錄都鏈接在同一鏈表中。 2. 鏈地址法鏈地址法0123456 11 198268 55 1436 01 23 ASL=(61+22+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為 H(key)=key MOD 7 查找過(guò)程和造表過(guò)程一致。假設(shè)采用開(kāi)放定址