【正文】 Data Structure Page 113 2022/1/4 ?所有順序結構的表和查找樹的平均查找長度都是隨之查找表中記錄數(shù)的增加而增大，而哈希表的平均查找長度是裝填因子的函數(shù)，因此有 可能設計出使平均查找長度不超過某個期望值的哈希表 。 ? 表 中 添 入 的 記 錄 數(shù)裝 填 因 子 = 表 的 長 度Data Structure Page 110 2022/1/4 ?在等概率查找的情況下，可以證明： ? 線性探測再散列的哈希表查找成功 的平均查找長度為 ? 隨機探測再散列、二次探測再散列和再哈希的哈希表查找成功 的平均查找長度為 ? 鏈地址處理沖突的哈希表查找成功 的平均查找長度為 11(1 )21nlS ??? ?1 l n ( 1 )nrS ??? ? ?1 2ncS ???Data Structure Page 111 2022/1/4 ? 線性探測再散列的哈希表查找不成功 的平均查找長度為 ? 隨機探測再散列、二次探測再散列和再哈希的哈希表查找不成功的平均查找長度為 ? 鏈地址處理沖突的哈希表查找不成功 的平均查找長度為 211( 1 )2 ( 1 )nlU ??? ?11nrU ?? ?ncUe ?? ???Data Structure Page 112 2022/1/4 本章小結 ?查找表即為集合結構 ，表中記錄之間本不存在約束條件，但為了提高查找速度，在計算機中構建查找表時，應人為地在記錄的關鍵字之間加上某些約束條件，即以其它結構表示之。 ? 沖突不可避免， 發(fā)生沖突的次數(shù)與表的裝填程度有關 ，表越滿，發(fā)生沖突的可能性就越大，查找也越慢。（哈希表長 16） 14 1 68 27 55 19 20 84 79 23 11 10 1 H(19)=6 H(14)=1 H(23)=10 H(1)=1 H(68)=3 H(20)=7 H(84)=6 1 1 沖突， H1=(1+1) MOD16=2 2 1 1 沖突， H1=(6+1)MOD16=7 沖突， H2=(6+2)MOD16=8 3 H(27)=1 沖突， H3=(1+3)MOD16=4 沖突， H1=(1+1)MOD16=2 沖突， H2=(1+2)MOD16=3 4 Data Structure Page 106 2022/1/4 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 已知一組關鍵字 (19,14,23,1,68,20,84,27,55,11,10,79)，按哈希函數(shù) H(key)=key MOD 13和 線性探測再散列處理沖突 構造哈希表， 設每個記錄的查找概率相等，求平均查找長度。 ? ? ? ? ? ? ? 6 5 4 3 2 1 0 56 ? 19 ? 23 ? ? 14 ? 68 ? 82 ? 70 36 ? ? 91 Data Structure Page 103 2022/1/4 ?再哈希法 ? 思想 ? 構造若干個哈希函數(shù)， 當發(fā)生沖突時，用另一個哈希函數(shù)計算另一個哈希地址 ，直至不發(fā)生沖突為止。) MOD 11=4 不沖突 Data Structure Page 100 2022/1/4 38 例如：表長為 11的哈希表中已填有關鍵字為 1 60、 29的記 錄， H(key)=key MOD 11， 現(xiàn)有第 4條記錄，其 關鍵字 為 38，按三種處理沖突的方法，將它填入表中。(k?m/2) ? 偽隨機探測再散列 ： di=偽隨機數(shù)序列 Data Structure Page 98 2022/1/4 線性探測再散列 H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突 38 例如：表長為 11的哈希表中已填有關鍵字為 1 60、 29的記 錄， H(key)=key MOD 11， 現(xiàn)有第 4條記錄，其 關鍵字 為 38，按三種處理沖突的方法，將它填入表中。,2178。 Data Structure Page 96 2022/1/4 ?選取哈希函數(shù)，考慮以下因素： ?計算哈希函數(shù)所需時間 ?關鍵字長度 ?哈希表長度（哈希地址范圍） ?關鍵字分布情況 ?記錄的查找頻率 Data Structure Page 97 2022/1/4 處理沖突的方法 ?開放定址法 ? 思想 ? 當沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中。 ? p的選取很重要； p選的不好，容易產(chǎn)生同義詞。 Data Structure Page 92 2022/1/4 例如：關鍵字為 0442205864，哈希地址位數(shù)為 4。 71 62 61 60 32 03 02 01 9 ? 2 1 0 Z ? C B A 哈希地址 (217~29) （關鍵字） 2 關鍵字 記錄 745 741 734 314 310 370 440 210 010 1 745651 4 741304 4 734741 4 314704 4 310541 1 370400 1 440000 1 210000 0 010000 2163 2162 2161 2062 2061 1160 1200 1100 0100 Q3 Q2 Q1 P2 P1 I0 J I A Data Structure Page 91 2022/1/4 ?折疊法 ? 思想 若 關鍵字的位數(shù)很多，且每一位上數(shù)字分布大致均勻， 則可采用移位疊加或間界疊加。 ? 適用情況 ? 適于不知道全部關鍵字情況 。 ? 適用情況 ? 關鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關鍵字事先知道的情況。 ? 公式 ? H(key)=key 或 H(key)=a*key+b （ a 和 b 均為常數(shù)） ? 特點 ? 該方法所得地址集合與關鍵字集合大小相等， 不會發(fā)生沖突 。 ? 哈希查找 ? 利用哈希函數(shù)進行查找的過程。 ? 哈希表 ? 應用哈希函數(shù)，由記錄的關鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構成的表。 Data Structure Page 82 2022/1/4 關鍵字序列 { Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei} Zhao Ye Wu Sun Qian Li Han Dei Chen 12 13 11 10 9 8 7 6 5 4 3 2 1 0 ( ) ( ( 1 ) ( 39。 13 24 37 13 24 37 RR 90 53 0 0 1 0 1 20 0 0 0 1 1 0 122從最先不平衡結點開始調(diào)整 13 24 37 90 53 13 24 37 90 53 Data Structure Page 81 2022/1/4 哈希表 ?靜態(tài)查找表和動態(tài)查找表的 缺點 ? 為了從查找表中找到關鍵字值等于某個值的記錄，都要 經(jīng)過一系列的關鍵字比較 ， 以確定待查記錄的存儲位置或查找失敗 ， 查找所需時間總是與比較次數(shù)有關 。 ? 處理 ：進行 先左旋、后右旋的兩次旋轉(zhuǎn) 。 ? 處理 ：進行一次 向右的順時針旋轉(zhuǎn) 。 ? 定義 ? 它或是空樹，或具有下列特性：其左子樹和右子樹都是平衡二叉樹，且左右子樹深度之差的絕對值不大于 1。 Data Structure Page 74 2022/1/4 平衡二叉樹 (AVL樹 ) ?平衡二叉樹 ? 結點的平衡因子 ? 結點的左子樹的深度減去它的右子樹的深度。 ?二叉排序樹的平均查找長度與樹的形態(tài)（深度）有關。 } } // Delete Data Structure Page 69 2022/1/4 80 50 120 60 110 150 55 70 53 80 60 120 110 150 55 70 53 80 55 120 110 150 53 70 刪除 50 Data Structure Page 70 2022/1/4 10 4 25 8 13 6 5 8 4 25 6 13 5 8 4 25 5 13 刪除 6 刪除 10 Data Structure Page 71 2022/1/4 二叉排序樹的查找分析 ?n個結點的二叉排序樹不唯一，由關鍵字插入的先后次序決定。 } //轉(zhuǎn)左，然后向右到盡頭 pdata = sdata。 } else { // 左右子樹均不空 q = p。 free(q)。 // 返回在左子樹上查找的結果 else return DeleteBST( Trchild, key )。 CL， C …… QL， Q， SL， S， P， PR， F CL C …… QL Q SL S PR F F P C PR CL Q QL S SL F S C PR CL Q QL SL Data Structure Page 67 2022/1/4 算法 Status DeleteBST (BiTree amp。 ? 設關鍵字序列 {10,18,3,8,12,2,7,3}，初始構造二叉樹。 // 被插結點 *s 為 *p 的左孩子 else prchild = s。 // 存儲分配失敗 sdata = e。 // 在右子樹中繼續(xù)查找 } // SearchBST Data Structure Page 58 2022/1/4 二叉排序樹的插入算法 Status InsertBST(BiTree amp。} // 查找不成功 else if EQ(key, T){ p=T。 45 12 53 3 27 24 100 61 90 78 59 Data Structure Page 57 2022/1/4 二叉排序樹的查找算法的修改 Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree amp。 // 查找結束 else if LT(key, T) return (SearchBST(T))。 Data Structure Page 53 2022/1/4 算法 BiTree SearchBST (BSTree T, KeyType key){ // 根指針 T所指二叉查找樹中遞歸查找關鍵字等于 key的數(shù)據(jù)元素 , // 若查找成功，則返回指向該數(shù)據(jù)元素結點的指針，否則返回空指針。 45 12 53 3 27 24 100 61 90 78 查找關鍵字等于 40的記錄 Data Structure Page 50 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結點的關鍵字，則查找成功； ? 若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找； ? 若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。 45 12 53 3 27 24 100 61 90 78 查找關鍵字等于 100的記錄 Data Structure Page 46 2022/1/4 ? 二叉排序樹的查找 若二叉排序樹為空，則查找不成功；否則 ? 若給定值等于根結點的關鍵字，則查找成功； ? 若給定值小于根結點的關鍵字，則繼續(xù)在左子樹上進行查找； ? 若給定值大于根結點的關鍵字，則繼續(xù)在右子樹上進行查找。 初始條件：動態(tài)查找表 DT存在， Visit 是對結點操作的應用函 數(shù)； 操作結果：按某種次序?qū)?DT的每個結點調(diào)用函數(shù) visit()一次且 至多一次。 DeleteDSTable(amp。 初始條件：動態(tài)查找表 DT存在， kval 為和關鍵字類型相同的