大學(xué)數(shù)據(jù)結(jié)構(gòu)課件--第9章 查找

1、1 基本概念基本概念 靜態(tài)查找表靜態(tài)查找表 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 哈希表哈希表第第9章章 查找查找2基本概念基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄或位置；若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄或位置；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表 查 找查找成功查找不成功靜態(tài)查找動(dòng)態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。查詢查詢(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改變集合內(nèi)的數(shù)據(jù)元素。只查找，不改變集合內(nèi)的數(shù)據(jù)元

2、素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素。記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄可以可以唯一唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字識(shí)別若干記錄的關(guān)鍵字識(shí)別若干記錄的關(guān)鍵字3明確：明確：查找的過程就是將給定的查找的過程就是將給定的K K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu)劣。稱為較的過程。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu)劣。稱為平均查找平均查找長(zhǎng)度長(zhǎng)度（ASLASL：average search lengthaverage sea

3、rch length）。）。其中：其中： n n是記錄個(gè)數(shù)；是記錄個(gè)數(shù)； P Pi i是查找第是查找第i i個(gè)記錄的查找概率（通常取等概率個(gè)記錄的查找概率（通常取等概率, ,即即P Pi i =1/n =1/n）; ; C Ci i是找到第是找到第i i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。物理意義：物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為的比較次數(shù)之總和再取平均，即為ASLASL。顯然，顯然，ASLASL值越小，時(shí)間效率越高。值越小，時(shí)間效率越高。 如何評(píng)估查找方法的優(yōu)劣？1iini

4、ASLPC基本概念基本概念4針對(duì)靜態(tài)查找表的查找算法主要有：針對(duì)靜態(tài)查找表的查找算法主要有： 一、順序查找（線性查找）一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┒?、折半查找（二分或?qū)Ψ植檎遥┤㈧o態(tài)樹表的查找三、靜態(tài)樹表的查找四、分塊查找（索引順序查找）四、分塊查找（索引順序查找）9.1 靜態(tài)查找表靜態(tài)查找表5（1）順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：順序表的機(jī)內(nèi)存儲(chǔ)結(jié)構(gòu)：typedef struct ElemType *elem; /表基址，表基址，0 0號(hào)單元留空。表容量為全部元素號(hào)單元留空。表容量為全部元素 int length; /表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)表長(zhǎng)，即表中數(shù)據(jù)元素個(gè)數(shù)SSTa

5、ble;Linear search，又稱線性查找，又稱線性查找，即用逐一比較的辦法順即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。序查找關(guān)鍵字，這顯然是最直接的辦法。 9.1.1 順序查找順序查找6（2）算法的實(shí)現(xiàn)：算法的實(shí)現(xiàn)：技巧：技巧：把待查關(guān)鍵字把待查關(guān)鍵字keykey存入表頭或表尾（俗稱存入表頭或表尾（俗稱“哨兵哨兵”），）， 若將待查找的特定值若將待查找的特定值keykey存入存入順序表的順序表的首部首部（如（如0 0號(hào)單元），則號(hào)單元），則順序查找的實(shí)現(xiàn)方案為：順序查找的實(shí)現(xiàn)方案為：從后向前從后向前逐個(gè)比較！逐個(gè)比較！int Search_Seq( SSTable ST

6、, KeyType key ) ST.elem0.key =key; /設(shè)立哨兵，可免去查找過程中每一步都要檢設(shè)立哨兵，可免去查找過程中每一步都要檢測(cè)是否查找完畢。當(dāng)測(cè)是否查找完畢。當(dāng)n1000n1000時(shí)，查找時(shí)間將減少一半。時(shí)，查找時(shí)間將減少一半。 for( i=ST.length; ST.elem i .key!=key; - - i ); /從后往前找從后往前找 return i; /若到達(dá)若到達(dá)0 0號(hào)單元才結(jié)束循環(huán)，說明不成功，返回號(hào)單元才結(jié)束循環(huán)，說明不成功，返回0 0值值(i=0)(i=0)。成功。成功時(shí)則返回找到的元素位置時(shí)則返回找到的元素位置i i。 / Search_Se

7、q/不要用不要用for(i=n; i0; - -i) for(i=n; i0; - -i) 或或 for(i=1; i=n; i+)for(i=1; i=n; i+)9.1.1 順序查找順序查找7說明說明 查找效率怎樣計(jì)算？查找效率怎樣計(jì)算？用平均查找長(zhǎng)度用平均查找長(zhǎng)度ASL衡量。衡量。說明說明 如何計(jì)算如何計(jì)算ASL？查找第查找第1個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為1；查找第查找第2個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為2；查找第查找第n個(gè)元素所需的比較次數(shù)為個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：總計(jì)全部比較次數(shù)為：12n = (1+n)n/2這是查找成功的情況這是查

8、找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n，即：即： ASL（1n）/2 ，時(shí)間效率為，時(shí)間效率為 O(n)優(yōu)點(diǎn)：優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：缺點(diǎn)： ASL 太長(zhǎng)，時(shí)間效率太低。太長(zhǎng)，時(shí)間效率太低。說明說明 順序查找的特點(diǎn)：順序查找的特點(diǎn)：8先給數(shù)據(jù)排序先給數(shù)據(jù)排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再將，然后再將keykey與與正中元素相比，若比正中元素相比，若比keykey小，則縮小至右半部?jī)?nèi)查找；再取其中值小，則縮小至右半部?jī)?nèi)查找；再取其中值比

9、較，每次縮小比較，每次縮小1/21/2的范圍，直到查找成功或失敗為止。的范圍，直到查找成功或失敗為止。折半查找舉例：折半查找舉例：LowLow指向待查元素指向待查元素所在區(qū)間的下界所在區(qū)間的下界highhigh指向待查元素所指向待查元素所在區(qū)間的上界在區(qū)間的上界midmid指向待查元素所在指向待查元素所在區(qū)間的中間位置區(qū)間的中間位置 已知如下已知如下11個(gè)元素的個(gè)元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）, 請(qǐng)查找關(guān)鍵字為請(qǐng)查找關(guān)鍵字為21和和85的數(shù)據(jù)元素。的數(shù)據(jù)元素。9.1.2 折半查找折半查找（又稱二分查找或?qū)Ψ植檎矣址Q二分查找或?qū)Ψ植檎遥?

10、 運(yùn)算步驟運(yùn)算步驟： （1） low =1,high =11 ,mid =6 ，待查范圍是，待查范圍是 1,11； （2）若）若 ST.elemmid.key key，說明，說明key low ,mid-1， 則令：則令：high =mid1;重算重算 mid ； （4）若）若 ST.elem mid .key = key，說明查找成功，元素序號(hào)，說明查找成功，元素序號(hào)=mid; 結(jié)束條件：結(jié)束條件： （1）查找成功）查找成功 ： ST.elemmid.key = key （2）查找不成功）查找不成功 ： highlow （意即區(qū)間長(zhǎng)度小于（意即區(qū)間長(zhǎng)度小于0）解：解： 先設(shè)定先設(shè)定3個(gè)輔助標(biāo)

11、志個(gè)輔助標(biāo)志: low,high,midlow,high,mid，顯然有：顯然有：mid= (low+high)/2 9.1.2 折半查找折半查找（又稱二分查找或?qū)Ψ植檎矣址Q二分查找或?qū)Ψ植檎遥?0查找查找21:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhighmidlowhighmid 查找結(jié)果：查找成功，查找結(jié)果：查找成功，21所在位置是所在位置是49.1.2 折半查找折半查找（又稱二分查找或?qū)Ψ植檎矣址Q二分查找或?qū)Ψ植檎遥?1查找查找85:（05 13 19 21 37 56 64 75 80 88 92）lowhighmidlowhi

12、ghlow highmidlowhighmid查找結(jié)果：查找失敗查找結(jié)果：查找失敗9.1.2 折半查找折半查找（又稱二分查找或?qū)Ψ植檎遥ㄓ址Q二分查找或?qū)Ψ植檎遥?2折半查找算法折半查找算法int Search_Bin(SSTable ST,KeyType key) low=1; high=ST.length; while(lowlchild=NULLf-lchild=NULL或或 f-rchild=NULLf-rchild=NULL20SQPLP中序遍歷：Q S PL PSQPL中序遍歷：Q S PL(2)SPPLQ中序遍歷：PL P S QSPLQ中序遍歷：PL S Q(1)刪除18634

13、218158634215821中序遍歷：P PR S QSPRQ中序遍歷：PR S Q(3)SPPRQ中序遍歷：Q S P PRSQPR中序遍歷：Q S PR(4)SQPRP刪除12634218121513634218151322F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2: 2: S的左子樹成為的左子樹成為S的雙親的雙親Q的右子樹，的右子樹， 用用S取代取代p；若若C無右子樹，用無右子樹，用C取代取代p F FC CCLS SSLQLPPRQ法法1: 1: P的左子樹成為的左子樹成為f的左子樹，的左子樹， P的右子樹成為的右子樹成為S的右子樹的右子樹

14、例：請(qǐng)從下面的二叉排序樹中刪除結(jié)點(diǎn)例：請(qǐng)從下面的二叉排序樹中刪除結(jié)點(diǎn)P P。S SSL231036241812156342181215刪除104362181215問題：?jiǎn)栴}：如何提高二叉排序樹的查找效率？如何提高二叉排序樹的查找效率？盡量讓二叉樹的形狀均衡盡量讓二叉樹的形狀均衡口訣：用左子樹最大的結(jié)點(diǎn)代替P； 或 用右子樹最小的結(jié)點(diǎn)代替P24平衡二叉樹又稱平衡二叉樹又稱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)的。

15、這個(gè)數(shù)字稱為結(jié)點(diǎn)的平衡因子平衡因子balance。這樣，可以得到這樣，可以得到AVL樹的其它性質(zhì)：樹的其它性質(zhì)：左、右子樹是平衡二叉樹；左、右子樹是平衡二叉樹；所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值所有結(jié)點(diǎn)的左、右子樹深度之差的絕對(duì)值 1 1v任一結(jié)點(diǎn)的平衡因子只能?。喝我唤Y(jié)點(diǎn)的平衡因子只能?。?1-1、0 0 或或 1 1；如果樹中任；如果樹中任意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于意一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1 1，則這棵二叉樹，則這棵二叉樹就失去平衡，不再是就失去平衡，不再是AVLAVL樹；樹；三、平衡二叉樹三、平衡二叉樹25(a) (a) 平衡樹平衡樹 (b) (b) 不是平衡樹不是平衡樹

16、例：例：判斷下列二叉樹是否判斷下列二叉樹是否AVL樹？樹？0001 11 1-1-10001-1三、平衡二叉樹三、平衡二叉樹26如果在一棵如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須此時(shí)必須重新調(diào)整樹的結(jié)構(gòu)重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡過程為平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：平衡旋轉(zhuǎn)可以歸納為四類：v RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v LL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v LR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)v RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)三、平衡二叉樹三、平衡二叉樹27若在A的左子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加

17、至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）（2）LL平衡旋轉(zhuǎn)（1）RR平衡旋轉(zhuǎn)三、平衡二叉樹三、平衡二叉樹28若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）（4）RL平衡旋轉(zhuǎn)若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）（3）LR平衡旋轉(zhuǎn)這種調(diào)整規(guī)則可以保證二叉排序樹的次序不變?nèi)⑵胶舛鏄淙?、平衡二叉?90 013130 03

18、7370 02424例：例：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹： （ 1313，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞B逆轉(zhuǎn)逆轉(zhuǎn),B為根）為根）0 09090-1-12424-1-137370 053531 190903737需要需要RL平衡旋轉(zhuǎn)平衡旋轉(zhuǎn)(繞繞C先順后逆）先順后逆）0 037370 090900 053530 037370 090900 05353三、平衡二叉樹三、平衡二叉樹30B-樹是一種 平衡平衡 的 多路多路 查找查找

19、樹： root 50 15 71 84 3 8 20 26 43 56 62 78 89 96一棵4階B-樹1781501152718432026432382566228996FFFFFFFFFFFFFFF四、四、B-B-樹和樹和B+B+樹樹31平衡樹的特性平衡樹的特性樹中每個(gè)結(jié)點(diǎn)最多含有樹中每個(gè)結(jié)點(diǎn)最多含有 m 棵子樹棵子樹; ;根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹;其余所有非葉子結(jié)點(diǎn)均至少含有其余所有非葉子結(jié)點(diǎn)均至少含有 m/2 棵棵子樹；子樹；樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上;每個(gè)非終

20、端結(jié)點(diǎn)可能含有：每個(gè)非終端結(jié)點(diǎn)可能含有： n 個(gè)個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n 個(gè)個(gè)指向記錄的指針指向記錄的指針 Di（1in） n+1 個(gè)個(gè)指向子樹的指針指向子樹的指針 Ai（0in）;多叉樹的特性多叉樹的特性非葉結(jié)點(diǎn)中的非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)關(guān)鍵字均均自小至大自小至大有序排列，即：有序排列，即：K1 K2 Kn;且且 Ai-1 所指子樹上所有關(guān)鍵字均所指子樹上所有關(guān)鍵字均小于小于Ki;Ai 所指子樹上所有關(guān)鍵字均所指子樹上所有關(guān)鍵字均大于大于Ki; ;查找樹的特性查找樹的特性 一棵m階的B-樹,或?yàn)榭諛?或?yàn)闈M足下列特性的m叉樹:（n,A0,K1,A1,K2Kn,An）32

21、從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)搜索結(jié)點(diǎn)和在結(jié)點(diǎn)內(nèi)進(jìn)行在結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找查找 兩個(gè)過程交叉進(jìn)行。若查找不成功查找不成功，則需要插入關(guān)鍵值需要插入關(guān)鍵值。在B-樹中插入一個(gè)關(guān)鍵值k，不是在樹中添加一個(gè)葉子結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵值。并且要使插入的結(jié)點(diǎn)中的關(guān)鍵值個(gè)數(shù)m1，否則將涉及到結(jié)點(diǎn)的分裂問題。3 3、B-B-樹的插入樹的插入2 2、B-B-樹的查找樹的查找331）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm，不修改指針不修改指針; ; 2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m，則，則需進(jìn)行需進(jìn)行“結(jié)點(diǎn)分結(jié)點(diǎn)分裂裂”，令，

22、令 s = m/2 ， 在原結(jié)點(diǎn)中保留在原結(jié)點(diǎn)中保留A0，K1， Ks-1，As-1）；）； 建新結(jié)點(diǎn)建新結(jié)點(diǎn)（As，Ks+1， ，Kn，An）；）； 將（將（Ks，p）插入雙親結(jié)點(diǎn)）插入雙親結(jié)點(diǎn)；-分裂后提升3）若雙親為空，則若雙親為空，則建新的根結(jié)點(diǎn)建新的根結(jié)點(diǎn)。3 3、B-B-樹的插入樹的插入34例如例如:下列為下列為 3 階階B-樹，分別插入樹，分別插入60、90、30。5020 408060 80 60 80 90906050 8020906030 50 804080 30 503 3、B-B-樹的插入樹的插入35 和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，

23、結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)借調(diào)關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字)，則必須進(jìn)行結(jié)點(diǎn)的合并 。4 4、B-B-樹的刪除樹的刪除36例：請(qǐng)?jiān)谙旅娴?階B-樹上依次刪除關(guān)鍵字12、50（或100）、37 。53 9053 90454524243 123 123737505010010061 7061 7053 9053 90454524243 33737505010010061 7061 7061 9061 90454524243 3373753531001007070刪除12刪除5053 7053 70454524243 3

24、3737505090906161刪除100從鄰近兄弟結(jié)點(diǎn)中取一個(gè)放到雙親中，從雙親中取一個(gè)下移到被刪除結(jié)點(diǎn)中。3770 9070 90454524243 33737616110010061 9061 90454524243 3373753531001007070刪除539090454524243 3373710010061 7061 70從雙親結(jié)點(diǎn)中取一個(gè)與其鄰近兄弟合并389090454524243 3373710010061 7061 70909045453 243 2410010061 7061 7045 9045 903 243 2410010061 7061 70刪除3739前面介紹

25、的所有查找都是基于待查關(guān)鍵字與表中元素進(jìn)行比較而實(shí)現(xiàn)的查找方法，查找的效率依賴于查找過程中所進(jìn)行的比較次數(shù)。理想的情況是希望不經(jīng)過任何比較，一次便能得到所查記錄。哈希表哈希表它既是一種查找方法，它既是一種查找方法，又是一種存儲(chǔ)方法又是一種存儲(chǔ)方法40一、哈希表的概念一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法三、沖突處理方法四、哈希表的查找及分析四、哈希表的查找及分析9.4 哈希查找表哈希查找表41哈希表：哈希表：即散列即散列(Hash)存儲(chǔ)結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)。 散列法存儲(chǔ)的基本思想：散列法存儲(chǔ)的基本思想：建立關(guān)鍵字與其存儲(chǔ)位置的建立關(guān)鍵字與其存儲(chǔ)位置的對(duì)應(yīng)關(guān)系，對(duì)

26、應(yīng)關(guān)系， 或者說，由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址?；蛘哒f，由關(guān)鍵字的值決定數(shù)據(jù)的存儲(chǔ)地址。 例例1 1：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：若將學(xué)生信息按如下方式存入計(jì)算機(jī)，如：將將20010118102200101181020101的所有信息存入的所有信息存入V01V01單元；單元；將將20010118102200101181020202的所有信息存入的所有信息存入V02V02單元；單元；將將20010118102200101181023131的所有信息存入的所有信息存入V31V31單元。單元。欲查找學(xué)號(hào)為欲查找學(xué)號(hào)為20010118102200101181021616的信息，便可直接訪問

27、的信息，便可直接訪問V16V16單元單元優(yōu)點(diǎn)：優(yōu)點(diǎn)：查找速度極快（查找速度極快（ (1)(1)）, ,查找效率與元素個(gè)數(shù)查找效率與元素個(gè)數(shù)n n無關(guān)！無關(guān)！9.4 哈希查找表哈希查找表42解：解：根據(jù)散列函數(shù)根據(jù)散列函數(shù)H H（k k）k k ，可知元素，可知元素1414應(yīng)當(dāng)存入地址為應(yīng)當(dāng)存入地址為 1414的單元，元素的單元，元素2323應(yīng)當(dāng)存入地址為應(yīng)當(dāng)存入地址為2323的單元，的單元， 對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：對(duì)應(yīng)散列存儲(chǔ)表（哈希表）如下：地址地址9111423242539內(nèi)容內(nèi)：有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個(gè)元素k的存儲(chǔ)地

28、址H（k）k，請(qǐng)畫出存儲(chǔ)結(jié)構(gòu)圖。 注：H（k）k稱為散列函數(shù)）9.4 哈希查找表哈希查找表43討論：如何進(jìn)行散列查找？ 根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)根據(jù)存儲(chǔ)時(shí)用到的散列函數(shù)H(k)H(k)表達(dá)式，即可查到結(jié)果！表達(dá)式，即可查到結(jié)果！ 例如，查找例如，查找key=9,key=9,則訪問則訪問H(9)=9H(9)=9號(hào)地址，若內(nèi)容為號(hào)地址，若內(nèi)容為9 9則成則成 功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或功；若查不到，應(yīng)當(dāng)設(shè)法返回一個(gè)特殊值，例如空指針或 空記錄?？沼涗?。 缺點(diǎn)：空間效率低！9.4 哈希查找表哈希查找表44選取某個(gè)函數(shù)，該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)選取某個(gè)函數(shù)，該函數(shù)按關(guān)鍵字計(jì)

29、算元素的存儲(chǔ)位置，并按此存放；位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)查找時(shí)，由同一個(gè)函數(shù)對(duì)給對(duì)給定值定值k k計(jì)算地址，將計(jì)算地址，將k k與地址單元中元素關(guān)鍵字進(jìn)與地址單元中元素關(guān)鍵字進(jìn)行比較，確定查找是否成功。行比較，確定查找是否成功。通常關(guān)鍵字的集合比哈希地址集合大得多，因而通常關(guān)鍵字的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵字映射可能將不同的關(guān)鍵字映射到同一個(gè)哈希地址上到同一個(gè)哈希地址上，這種現(xiàn)象稱為，這種現(xiàn)象稱為沖突沖突。哈希方法哈希方法哈希函數(shù)哈希函數(shù) 哈希表哈希表 沖沖 突突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希

30、函數(shù)哈希函數(shù)按上述思想構(gòu)造的表稱為按上述思想構(gòu)造的表稱為哈希表哈希表哈希表的若干術(shù)語哈希表的若干術(shù)語45有有6個(gè)元素的關(guān)鍵碼分別為：（個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。）。選取關(guān)鍵碼與元素位置間的函數(shù)為選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=k mod 7，地址編地址編號(hào)從號(hào)從0-6。通過哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 6沖突現(xiàn)象舉例沖突現(xiàn)象舉例46所以，所以，哈希方法必須解決以下兩個(gè)問題哈希方法必須解決以下兩個(gè)問題：1）構(gòu)造好的哈希函數(shù) （a a）所

31、選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度； （b b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集 中致均勻分布，以減少空間浪費(fèi)。中致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案 查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵 碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相 關(guān)單元。關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。47常用的哈

32、希函數(shù)構(gòu)造方法有：常用的哈希函數(shù)構(gòu)造方法有：1.1. 直接定址法直接定址法 2.2. 除留余數(shù)法除留余數(shù)法 3.3. 乘余取整法乘余取整法4.4. 數(shù)字分析法數(shù)字分析法 5.5. 平方取中法平方取中法 6.6. 折疊法折疊法 7.7. 隨機(jī)數(shù)法隨機(jī)數(shù)法 要求一：要求一：n n個(gè)數(shù)據(jù)原僅占用個(gè)數(shù)據(jù)原僅占用n n個(gè)地址，個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。希望散列的地址空間盡量小。要求二：要求二：無論用什么方法存儲(chǔ)，目無論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免的都是盡量均勻地存放元素，以避免沖突。沖突。二、哈希函數(shù)的構(gòu)造方法

33、哈希函數(shù)的構(gòu)造方法48Hash(key) = akey + b ( (a、b為常數(shù)為常數(shù)) )優(yōu)點(diǎn)：優(yōu)點(diǎn)：以關(guān)鍵碼以關(guān)鍵碼keykey的某個(gè)線性函數(shù)值為哈希地址，的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突不會(huì)產(chǎn)生沖突. .缺點(diǎn)：缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。要占用連續(xù)地址空間，空間效率低。 例：例：關(guān)鍵碼集合為關(guān)鍵碼集合為100，300，500，700，800，900， 選取哈希函數(shù)為選取哈希函數(shù)為Hash(key)=key/100， 則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：0 1 2 3 4 5 6 7 8 99008007005003001001 1、直接定址法、直接定址

34、法49Hash(key)=key mod p (p (p是一個(gè)整數(shù)是一個(gè)整數(shù)) )特點(diǎn)：特點(diǎn)：以關(guān)鍵碼除以以關(guān)鍵碼除以p的余數(shù)作為哈希地址。的余數(shù)作為哈希地址。關(guān)鍵：關(guān)鍵：如何選取合適的如何選取合適的p？技巧：技巧：若設(shè)計(jì)的哈希表長(zhǎng)為若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取，則一般取pm且為且為質(zhì)數(shù)質(zhì)數(shù) 2、除留余數(shù)法50Hash(key)= B*( A*key mod 1 ) ( (A、B均為常數(shù)，且均為常數(shù)，且0A 724+518+69 = 724+518+69 =13111311法法1 1：移位法移位法 將各部分的最后一位對(duì)齊相加。將各部分的最后一位對(duì)齊相加。法法2 2：間界疊加法間界疊加法從一端

35、向另一端沿分割界來回折疊后，從一端向另一端沿分割界來回折疊后， 最后一位對(duì)齊相加。最后一位對(duì)齊相加。 6、折疊法54Hash(key) = random ( key ) (random (random為偽隨機(jī)函數(shù)為偽隨機(jī)函數(shù)) )適用于：適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。 執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）； 關(guān)鍵字的長(zhǎng)度；關(guān)鍵字的長(zhǎng)度； 哈希表的大小；哈希表的大??； 關(guān)鍵字的分布情況；關(guān)鍵字的分布情況； 查找頻率。查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：7、隨機(jī)數(shù)法55三、沖突處理方法沖突處理方法56設(shè)

36、計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 具體實(shí)現(xiàn)：Hi=(Hash(key)+di) mod m ( 1i m )其中： Hash(key)為哈希函數(shù) m為哈希表長(zhǎng)度 di 為增量序列 1，2，m-1，且di=i 1.線性探測(cè)法1 1、開放定址法（開地址法）、開放定址法（開地址法）57例：關(guān)鍵碼集為關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，哈希表表，哈希表表長(zhǎng)為長(zhǎng)為m=m=11；哈希函數(shù)為；哈希函數(shù)為Hash(key)=key mod 11；擬用；擬用處處理沖突。建哈希表如下：理沖突。建哈希表如下：解釋：解釋：

37、47、7均是由哈希函數(shù)得到的沒有沖突的哈希地址；均是由哈希函數(shù)得到的沒有沖突的哈希地址；0 1 2 3 4 5 6 7 8 9 10 Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由由H1=(Hash(29)+1) mod 11=8，哈希地址哈希地址8為空，因此將為空，因此將29存入。存入。另外，另外，22、8、3同樣在哈希地址上有沖突，也是由同樣在哈希地址上有沖突，也是由H1找到空找到空 的哈希地址的。的哈希地址的。 平均查找長(zhǎng)度ASL=(1+2 +1 +1 +1 +4 +1 +2 +2)/9=1.6747729111692228

38、3 11、16、92均是由哈希函數(shù)得到的沒有沖突的哈希地址；均是由哈希函數(shù)得到的沒有沖突的哈希地址；58基本思想：基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)個(gè) 哈希地址就設(shè)哈希地址就設(shè)m個(gè)單鏈表個(gè)單鏈表，然后用一個(gè)數(shù)組將，然后用一個(gè)數(shù)組將m個(gè)個(gè) 單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。 設(shè)設(shè) 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 的哈希函數(shù)為：的哈希函數(shù)為：Hash(key)=key mod 11，用用處理沖突，則建表如處理沖突，則建表如右圖

39、所示。右圖所示。 例：例：注：注：有沖突的元素可以插有沖突的元素可以插在表尾在表尾, ,也可以插在表頭也可以插在表頭平均查找長(zhǎng)度ASL=(1*8 +2 *4)/12=1.334730 1 2 3 4 5 6 7 8 9107291116922285037892 2、鏈地址法、鏈地址法( (拉鏈法）拉鏈法）591 1、采用順序查找方法查找長(zhǎng)度為、采用順序查找方法查找長(zhǎng)度為n n的線性表時(shí)的線性表時(shí), ,每個(gè)元素的平均每個(gè)元素的平均 查找長(zhǎng)度為查找長(zhǎng)度為 。 （A A）n n （B B）n/2n/2（C C）(n+1)/2(n+1)/2（D D）(n-1)/2(n-1)/22 2、對(duì)線性表進(jìn)行二分

40、查找時(shí)、對(duì)線性表進(jìn)行二分查找時(shí), ,要求線性表必須要求線性表必須 。 （A A）以順序方式存儲(chǔ)）以順序方式存儲(chǔ) （B B）以鏈接方式存儲(chǔ)）以鏈接方式存儲(chǔ) （C C）以順序方式存儲(chǔ)）以順序方式存儲(chǔ), ,且結(jié)點(diǎn)按關(guān)鍵字有序排序且結(jié)點(diǎn)按關(guān)鍵字有序排序 （D D）以鏈接方式存儲(chǔ)）以鏈接方式存儲(chǔ), ,且結(jié)點(diǎn)按關(guān)鍵字有序排序且結(jié)點(diǎn)按關(guān)鍵字有序排序 3 3、己知一個(gè)有序表為、己知一個(gè)有序表為(12,18,20,25,29,32,40,62,83,90,95,98),(12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為當(dāng)二分查找值為2929和和9090的元素時(shí)的元素時(shí),

41、,分別需要分別需要( )( )次和次和( )( )次比較才次比較才能查找成功；若采用順序查找時(shí)能查找成功；若采用順序查找時(shí), ,分別需要分別需要( )( )次和次和( )( )次比較次比較才能查找成功。才能查找成功。 練 習(xí)604 4、折半查找有序表（、折半查找有序表（4 4，6 6，1212，2020，2828，3838，5050，7070，8888，100100），若查找表中元素），若查找表中元素2020，它將依次與表中元素，它將依次與表中元素 比較大小。比較大小。 5 5、有一個(gè)長(zhǎng)度為、有一個(gè)長(zhǎng)度為1212的有序表，按二分查找法對(duì)其查找，在表內(nèi)各的有序表，按二分查找法對(duì)其查找，在表內(nèi)各元

42、素等概率情況下，查找成功的平均比較次數(shù)為（元素等概率情況下，查找成功的平均比較次數(shù)為（ ）。）。（A A）35/12 35/12 （B B）37/12 37/12 （C C）39/12 39/12 （D D）43/1243/12 6 6、對(duì)下列數(shù)據(jù)進(jìn)行分塊查找。、對(duì)下列數(shù)據(jù)進(jìn)行分塊查找。最大關(guān)鍵字起始地址72189276 1 610207694172172104189150201276211271練 習(xí)617、已知序列50，72，43，85，75，20，35，45，65，30，請(qǐng)構(gòu)造二叉排序樹，并依次給出插入結(jié)點(diǎn)58和刪除結(jié)點(diǎn)20、72之后的二叉排序樹。 插入插入58：437220456585

43、5035307558436545588550353075刪除刪除72：4375456585503530或者或者5843724565855035307558刪除刪除20：練 習(xí)628 8、請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹：請(qǐng)將下面序列構(gòu)成一棵平衡二叉排序樹： （ 3939，5858，2727，1212，6464，8888，4747，9696）39395858272712126464888858586464888847479696練 習(xí)639、請(qǐng)?jiān)谙旅娴?階B_樹上依次插入關(guān)鍵字22、66、88，80；再依次刪除 89，88。37 7337 7317 2917 29575779 8979 8937 7337 7317 17 2222 29 29575779 8979