第7章 查找技術(shù)

1、數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社第第 7 章章 查找技術(shù)查找技術(shù)本章的主要內(nèi)容是本章的主要內(nèi)容是:查找的基本概念查找的基本概念線性表的查找技術(shù)線性表的查找技術(shù)樹表的查找技術(shù)樹表的查找技術(shù)散列表的查找技術(shù)散列表的查找技術(shù) 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社查找的基本概念查找的基本概念關(guān)鍵碼關(guān)鍵碼：可以標識一個記錄的某個數(shù)據(jù)項。：可以標識一個記錄的某個數(shù)據(jù)項。 鍵值鍵值：關(guān)鍵碼的值。：關(guān)鍵碼的值。主關(guān)鍵碼主關(guān)鍵碼：可以唯一地標識一個記錄的關(guān)鍵碼。：可以唯一地標識一個記錄的關(guān)鍵碼。次關(guān)鍵碼次關(guān)鍵碼：不能：不能唯一地標識一個記錄的關(guān)鍵碼。唯一地標識

2、一個記錄的關(guān)鍵碼。7.1 概述概述50女女李爽李爽000525女女齊梅齊梅000447女女劉楠劉楠000325男男張亮張亮000238男男王剛王剛0001年齡年齡性別性別姓名姓名職工號職工號1972年年9月月2003年年7月月1979年年9月月2003年年7月月1990年年4月月參加工作參加工作數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社查找的基本概念查找的基本概念查找查找 ：在具有相同類型的記錄構(gòu)成的：在具有相同類型的記錄構(gòu)成的集合集合中找出滿足中找出滿足給給定條件定條件的記錄。的記錄。 7.1 概述概述查找的結(jié)果查找的結(jié)果 ：若在查找集合中找到了與給定值相匹配：若在查找集合

3、中找到了與給定值相匹配的記錄，則稱的記錄，則稱查找成功查找成功；否則，稱；否則，稱查找查找失敗失敗。 50女女李爽李爽000525女女齊梅齊梅000447女女劉楠劉楠000325男男張亮張亮000238男男王剛王剛0001年齡年齡性別性別姓名姓名職工號職工號1972年年9月月2003年年7月月1979年年9月月2003年年7月月1990年年4月月參加工作參加工作數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社靜態(tài)查找靜態(tài)查找 ：不涉及插入和刪除操作的查找：不涉及插入和刪除操作的查找 。動態(tài)查找動態(tài)查找 ：涉及插入和刪除操作的查找。：涉及插入和刪除操作的查找。 7.1 概述概述查找的

4、基本概念查找的基本概念靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對其進行靜態(tài)查找適用于：查找集合一經(jīng)生成，便只對其進行查找，而不進行插入和刪除操作，或經(jīng)過一段時間的查找，而不進行插入和刪除操作，或經(jīng)過一段時間的查找之后，集中地進行插入和刪除等修改操作；查找之后，集中地進行插入和刪除等修改操作；動態(tài)查找適用于：查找與插入和刪除操作在同一個階動態(tài)查找適用于：查找與插入和刪除操作在同一個階段進行，例如當查找成功時，要刪除查找到的記錄，段進行，例如當查找成功時，要刪除查找到的記錄，當查找不成功時，要插入被查找的記錄。當查找不成功時，要插入被查找的記錄。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學

5、出版社7.1 概述概述查找的基本概念查找的基本概念查找結(jié)構(gòu)查找結(jié)構(gòu) ：面向查找操作的數(shù)據(jù)結(jié)構(gòu)面向查找操作的數(shù)據(jù)結(jié)構(gòu) ，即查找基于的，即查找基于的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)。查找結(jié)構(gòu)查找結(jié)構(gòu) 查找方法查找方法 集合中元素之間不存在明顯的組織規(guī)律，不便查找。集合中元素之間不存在明顯的組織規(guī)律，不便查找。集合集合 線性表線性表 樹樹 表表 散列表散列表 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社本章討論的查找結(jié)構(gòu)本章討論的查找結(jié)構(gòu) ：線性表線性表：適用于靜態(tài)查找，主要采用順序查找技術(shù)、：適用于靜態(tài)查找，主要采用順序查找技術(shù)、折半查找技術(shù)。折半查找技術(shù)。樹表樹表：適用于動態(tài)查找，主要采用二叉

6、排序樹的查找：適用于動態(tài)查找，主要采用二叉排序樹的查找技術(shù)。技術(shù)。散列表散列表：靜態(tài)查找和動態(tài)查找均適用，主要采用散列：靜態(tài)查找和動態(tài)查找均適用，主要采用散列技術(shù)。技術(shù)。 7.1 概述概述查找結(jié)構(gòu)查找結(jié)構(gòu) ：面向查找操作的數(shù)據(jù)結(jié)構(gòu)面向查找操作的數(shù)據(jù)結(jié)構(gòu) ，即查找基于的，即查找基于的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)。查找的基本概念查找的基本概念數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社查找算法的性能查找算法的性能 查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？算法；算法；問題規(guī)模；問

7、題規(guī)模；待查關(guān)鍵碼在查找集合中的位置；待查關(guān)鍵碼在查找集合中的位置；查找頻率。查找頻率。7.1 概述概述查找頻率與算法無關(guān)，取決于具體應用。查找頻率與算法無關(guān)，取決于具體應用。通常假設(shè)通常假設(shè)pi是已知的。是已知的。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社查找算法的性能查找算法的性能 查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。查找算法時間性能通過關(guān)鍵碼的比較次數(shù)來度量。查找算法的時間復雜度是問題規(guī)模查找算法的時間復雜度是問題規(guī)模n和待查關(guān)鍵碼和待查關(guān)鍵碼在查找集合中的位置在查找集合中的位置k的函數(shù)，記為的函數(shù)，記為T(n，k)。 同一查找集合、同一查找算法，關(guān)鍵碼的比較同

8、一查找集合、同一查找算法，關(guān)鍵碼的比較次數(shù)與哪些因素有關(guān)呢？次數(shù)與哪些因素有關(guān)呢？7.1 概述概述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社平均查找長度：平均查找長度：將查找算法進行的關(guān)鍵碼的比較次數(shù)將查找算法進行的關(guān)鍵碼的比較次數(shù)的數(shù)學期望值定義為的數(shù)學期望值定義為平均查找長度平均查找長度。計算公式為：。計算公式為： 其中：其中：n：問題規(guī)模，查找集合中的記錄個數(shù)；問題規(guī)模，查找集合中的記錄個數(shù)； pi：查找第查找第i個記錄的概率；個記錄的概率； ci：查找第查找第i個記錄所需的關(guān)鍵碼的比較次數(shù)。個記錄所需的關(guān)鍵碼的比較次數(shù)。結(jié)論結(jié)論：ci取決于算法；取決于算法；pi與算法

9、無關(guān)，取決于具體應用。與算法無關(guān)，取決于具體應用。如果如果pi是已知的，則平均查找長度只是問題規(guī)模的函數(shù)。是已知的，則平均查找長度只是問題規(guī)模的函數(shù)。7.1 概述概述查找算法的性能查找算法的性能 ASL = = =niiicp1數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社順序查找順序查找 （線性查找）（線性查找）基本思想基本思想：從線性表的一端向另一端逐個將關(guān)鍵碼與：從線性表的一端向另一端逐個將關(guān)鍵碼與給定值進行比較，若相等，則查找成功，給出該記錄給定值進行比較，若相等，則查找成功，給出該記錄在表中的位置；若整個表檢測完仍未找到與給定值相在表中的位置；若整個表檢測完仍未找到與給

10、定值相等的關(guān)鍵碼，則查找失敗，給出失敗信息。等的關(guān)鍵碼，則查找失敗，給出失敗信息。 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i7.2 線性表的查找技術(shù)線性表的查找技術(shù)例：查找例：查找k35iii數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社順序查找順序查找 （線性查找）（線性查找）7.2 線性表的查找技術(shù)線性表的查找技術(shù)int SeqSearch1( (int r , int n, int k) )/數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 i=n; while ( (i0 & ri!=k) ) i-; return i

11、;數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社基本思想基本思想：設(shè)置：設(shè)置“哨兵哨兵”。哨兵就是待查值，將它放。哨兵就是待查值，將它放在查找方向的在查找方向的盡頭盡頭處，免去了在查找處，免去了在查找過程中每一次比過程中每一次比較后都要判斷查找位置是否較后都要判斷查找位置是否越界越界，從而提高查找速度，從而提高查找速度。 7.2 線性表的查找技術(shù)線性表的查找技術(shù)改進的順序查找改進的順序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k35iii哨兵哨兵35查找方向查找方向數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版

12、社清華大學出版社基本思想基本思想：設(shè)置：設(shè)置“哨兵哨兵”。哨兵就是待查值，將它放。哨兵就是待查值，將它放在查找方向的在查找方向的盡頭盡頭處，免去了在查找處，免去了在查找過程中每一次比過程中每一次比較后都要判斷查找位置是否較后都要判斷查找位置是否越界越界，從而提高查找速度，從而提高查找速度。 7.2 線性表的查找技術(shù)線性表的查找技術(shù)改進的順序查找改進的順序查找 10 15 24 6 12 35 40 98 550 1 2 3 4 5 6 7 8 9 i例：查找例：查找k25ii25查找方向查找方向iiiiiii數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社int SeqSearch

13、2(int r , int n, int k) /數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 r0=k; i=n; while (ri!=k) i -; return i;7.2 線性表的查找技術(shù)線性表的查找技術(shù)改進的順序查找改進的順序查找ASL= = =niicp1 + +- -= =niiinp1) 1(i= (n+1)/2=O(n)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社7.2 線性表的查找技術(shù)線性表的查找技術(shù)算法簡單而且使用面廣。算法簡單而且使用面廣。對表中記錄的存儲沒有任何要求，順序存儲和鏈接對表中記錄的存儲沒有任何要求，順序存儲和鏈接存儲均可；存儲均可；對表中記

14、錄的有序性也沒有要求，無論記錄是否按對表中記錄的有序性也沒有要求，無論記錄是否按關(guān)鍵碼有序均可。關(guān)鍵碼有序均可。順序查找的優(yōu)點：順序查找的優(yōu)點：平均查找長度較大，特別是當待查找集合中元素較多平均查找長度較大，特別是當待查找集合中元素較多時，查找效率較低。時，查找效率較低。(起始位置起始位置, 步長步長, 規(guī)模規(guī)模)順序查找的缺點：順序查找的缺點：數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社折半查找折半查找使用條件使用條件：線性表中的記錄必須按關(guān)鍵碼線性表中的記錄必須按關(guān)鍵碼有序有序；必須采用必須采用順序順序存儲存儲?；舅枷牖舅枷耄涸谟行虮碇?，?。涸谟行虮碇校≈虚g中間記錄作

15、為比較對象，記錄作為比較對象，若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若若給定值與中間記錄的關(guān)鍵碼相等，則查找成功；若給定值給定值小于小于中間記錄的關(guān)鍵碼，則在中間記錄的中間記錄的關(guān)鍵碼，則在中間記錄的左半左半?yún)^(qū)繼續(xù)查找；若給定值區(qū)繼續(xù)查找；若給定值大于大于中間記錄的關(guān)鍵碼，則在中間記錄的關(guān)鍵碼，則在中間記錄的中間記錄的右半右半?yún)^(qū)繼續(xù)查找。不斷重復上述過程，直區(qū)繼續(xù)查找。不斷重復上述過程，直到查找成功，或所查找的區(qū)域無記錄，查找失敗。到查找成功，或所查找的區(qū)域無記錄，查找失敗。7.2 線性表的查找技術(shù)線性表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社折半查找的基本

16、思想折半查找的基本思想7.2 線性表的查找技術(shù)線性表的查找技術(shù) r1 rmid- -1 rmid rmid+1 rn 如果如果krmid 查找左半?yún)^(qū)查找左半?yún)^(qū) 查找右半?yún)^(qū)查找右半?yún)^(qū)k（mid=(1+n)/2）數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社例：查找值為例：查找值為14的記錄的過程：的記錄的過程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 311418147221822low=4mid=

17、4 21high數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社int BinSearch1(int r , int n, int k)/數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 low=1; high=n; while (low=high) mid=(low+high)/2; if (krmid) low=mid+1; else return mid; return 0;7.2 線性表的查找技術(shù)線性表的查找技術(shù)折半查找折半查找非遞歸算法非遞歸算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社int BinSearch2(int r , int low, int h

18、igh, int k)/數(shù)組數(shù)組r1 rn存放查找集合存放查找集合 if (lowhigh) return 0; else mid=(low+high)/2; if (krmid) return BinSearch2(r, mid+1, high, k); else return mid; 7.2 線性表的查找技術(shù)線性表的查找技術(shù)折半查找折半查找遞歸算法遞歸算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社折半查找判定樹折半查找判定樹 判定樹判定樹：折半查找的過程可以用二叉樹來描述，樹中折半查找的過程可以用二叉樹來描述，樹中的每個結(jié)點對應有序表中的一個記錄，結(jié)點的值為該的每個結(jié)點

19、對應有序表中的一個記錄，結(jié)點的值為該記錄在記錄在表中的位置。通常稱這個描述折半查找過程的表中的位置。通常稱這個描述折半查找過程的二叉樹為折半查找判定樹，簡稱二叉樹為折半查找判定樹，簡稱判定樹判定樹。7.2 線性表的查找技術(shù)線性表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社 當當n=0時，折半查找判定樹為空；時，折半查找判定樹為空； 當當n0時，折半查找判定樹的根結(jié)點是有序表中時，折半查找判定樹的根結(jié)點是有序表中序號為序號為mid=( (n+1) )/2的記錄，根結(jié)點的左子樹是與有的記錄，根結(jié)點的左子樹是與有序表序表r1 rmid- -1相對應的折半查找判定樹，根結(jié)相對

20、應的折半查找判定樹，根結(jié)點的點的右子樹是與右子樹是與rmid+1 rn相對應的折半查找判相對應的折半查找判定樹。定樹。 7.2 線性表的查找技術(shù)線性表的查找技術(shù)判定樹的構(gòu)造方法判定樹的構(gòu)造方法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社7.2 線性表的查找技術(shù)線性表的查找技術(shù) 11223344510111191089785667內(nèi)部結(jié)點內(nèi)部結(jié)點外部結(jié)點外部結(jié)點3691011784512判定樹的構(gòu)造方法判定樹的構(gòu)造方法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社具有具有n個結(jié)個結(jié)點的折半查找判定樹的深度為點的折半查找判定樹的深度為 查找成功查找成功：在表中查找任一

21、記錄的過程，即是折半查：在表中查找任一記錄的過程，即是折半查找判定樹中從根結(jié)點到該記錄結(jié)點的路徑，和給定值找判定樹中從根結(jié)點到該記錄結(jié)點的路徑，和給定值的比較次數(shù)等于該記錄結(jié)點在樹中的層數(shù)。的比較次數(shù)等于該記錄結(jié)點在樹中的層數(shù)。查找不成功查找不成功：查找失敗的過程就是走了一條從根結(jié)：查找失敗的過程就是走了一條從根結(jié)點到外部結(jié)點的路徑，和給定值進行的關(guān)鍵碼的比點到外部結(jié)點的路徑，和給定值進行的關(guān)鍵碼的比較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。7.2 線性表的查找技術(shù)線性表的查找技術(shù)。 1log2+ +n折半查找性能分析折半查找性能分析 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）

22、清華大學出版社清華大學出版社如果有序表的長度為如果有序表的長度為n,則外結(jié)點一定有則外結(jié)點一定有n+1個個 查找成功時的平均查找長度即為查找每個內(nèi)部結(jié)點的比較次數(shù)之和除以有序表的長度，如： ASL=(1*1+2*2+3*4+4*4)/11=33/11 查找不成功時的平均查找長度即為查找每個外部結(jié)點的比較次數(shù)之和除以外結(jié)點的個數(shù)，如： ASL=(4*4+8*5)/12=56/127.2 線性表的查找技術(shù)線性表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹二叉排序樹二叉排序樹二叉排序樹（也稱（也稱二叉查找樹二叉查找樹）：或者是一棵空的二）：或者是一棵空的二叉樹，或

23、者是具有下列性質(zhì)的二叉樹：叉樹，或者是具有下列性質(zhì)的二叉樹： 若它的左子樹不空，則左子樹上所有結(jié)點的值均若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；小于根結(jié)點的值； 若它的右子樹不空，則右子樹上所有結(jié)點的值均若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；大于根結(jié)點的值； 它的左右子樹也都是二叉排序樹。它的左右子樹也都是二叉排序樹。7.3 樹表的查找技術(shù)樹表的查找技術(shù)二叉排序樹的定義采用的是遞歸方法。二叉排序樹的定義采用的是遞歸方法。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹二叉排序樹 非二叉排序樹非二叉排序樹二叉排序樹二叉排序樹7.3 樹表

24、的查找技術(shù)樹表的查找技術(shù)6390554258104567837063605582581045678370中序遍歷二叉排序樹可以得到一個按關(guān)鍵碼有序的序列中序遍歷二叉排序樹可以得到一個按關(guān)鍵碼有序的序列 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的存儲結(jié)構(gòu)二叉排序樹的存儲結(jié)構(gòu)以二叉鏈表形式存儲，類聲明如下：以二叉鏈表形式存儲，類聲明如下：class BiSortTree public: BiSortTree( (int a , int n) ); BiSortTree( )( ); void InsertBST( (BiNode *root , BiNode *s)

25、); void DeleteBST( (BiNode *p, BiNode *f ) ); BiNode *SearchBST( (BiNode *root, int k) ); private: BiNode *root; ;7.3 樹表的查找技術(shù)樹表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的插入二叉排序樹的插入分析：分析：若二叉排序樹為空樹，則新插入的結(jié)點為新若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。結(jié)點，其插入位置由查找過程得到。7.

26、3 樹表的查找技術(shù)樹表的查找技術(shù)void InsertBST(BiNode *root , BiNode *s);數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社例：插入值為例：插入值為98的結(jié)點的結(jié)點7.3 樹表的查找技術(shù)樹表的查找技術(shù)63559058 70985563root90587098sroot數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社void BiSortTree:InsertBST(BiNode *root, BiNode *s) if (root=NULL) root=s; else if (s-datadata) InsertBST(root-l

27、child, s); else InsertBST(root-rchild, s);7.3 樹表的查找技術(shù)樹表的查找技術(shù)二叉排序樹的插入算法二叉排序樹的插入算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的構(gòu)造二叉排序樹的構(gòu)造從空的二叉排序樹開始，依次插入一個個結(jié)點從空的二叉排序樹開始，依次插入一個個結(jié)點 。例：關(guān)鍵碼集合為例：關(guān)鍵碼集合為63，90，70，55，58，二二叉排序樹的構(gòu)造過程為：叉排序樹的構(gòu)造過程為： 7.3 樹表的查找技術(shù)樹表的查找技術(shù)63559058 70數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社BiSortTree:BiSort

28、Tree(int r , int n) for (i=0; in; i+) s=new BiNode; s-data=ri; s-lchild=s-rchild=NULL; InsertBST(root, s); 7.3 樹表的查找技術(shù)樹表的查找技術(shù)二叉排序樹的構(gòu)造算法二叉排序樹的構(gòu)造算法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社 一個無序序列可以通過構(gòu)造一棵二叉排序樹而一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列變成一個有序序列; 每次插入的新結(jié)點都是二叉排序樹上新的葉子每次插入的新結(jié)點都是二叉排序樹上新的葉子結(jié)點結(jié)點; 找到插入位置后，不必移動其它結(jié)點，僅需修

29、找到插入位置后，不必移動其它結(jié)點，僅需修改某個結(jié)點的指針；改某個結(jié)點的指針； 在左子樹在左子樹/右子樹的查找過程與在整棵樹上查右子樹的查找過程與在整棵樹上查找過程相同；找過程相同； 新插入的結(jié)點沒有破壞原有結(jié)點之間的關(guān)系。新插入的結(jié)點沒有破壞原有結(jié)點之間的關(guān)系。小小 結(jié)：結(jié)：7.3 樹表的查找技術(shù)樹表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的刪除二叉排序樹的刪除在二叉排序樹上刪除某個結(jié)點之后，仍然保持二叉排在二叉排序樹上刪除某個結(jié)點之后，仍然保持二叉排序樹的特性。序樹的特性。分三種情況討論：分三種情況討論：被刪除的結(jié)點是葉子；被刪除的結(jié)點是葉子；被刪除的

30、結(jié)點只有左子樹或者只有右子樹；被刪除的結(jié)點只有左子樹或者只有右子樹；被刪除的結(jié)點既有左子樹，也有右子樹被刪除的結(jié)點既有左子樹，也有右子樹。7.3 樹表的查找技術(shù)樹表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社情況情況1被刪除的結(jié)點是葉子結(jié)點被刪除的結(jié)點是葉子結(jié)點7.3 樹表的查找技術(shù)樹表的查找技術(shù)50302080908588403532503020809085403532操作：操作：將雙親結(jié)點中相應指針域的值改為空。將雙親結(jié)點中相應指針域的值改為空。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社情況情況2被刪除的結(jié)點只有左子樹或者只有右子被刪除的結(jié)點只有

31、左子樹或者只有右子樹樹操作：操作：將雙親結(jié)點的相應指針域的值指向被刪除將雙親結(jié)點的相應指針域的值指向被刪除結(jié)點的左子樹（或右子樹）。結(jié)點的左子樹（或右子樹）。7.3 樹表的查找技術(shù)樹表的查找技術(shù)50302080908588403532503020908588403532數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社情況情況3被刪除的結(jié)點既有左子樹也有右子樹被刪除的結(jié)點既有左子樹也有右子樹操作：操作：以其前驅(qū)（左子樹中的最大值）替代之，然后再刪除以其前驅(qū)（左子樹中的最大值）替代之，然后再刪除該前驅(qū)結(jié)點；或者該前驅(qū)結(jié)點；或者以其后繼（右子樹中的最小值）替代之，以其后繼（右子樹中的最小

32、值）替代之，然后再刪除該前驅(qū)結(jié)點。然后再刪除該前驅(qū)結(jié)點。7.3 樹表的查找技術(shù)樹表的查找技術(shù)50302080908588403532403020809085883532數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社1. 若結(jié)點若結(jié)點p是葉子，則直接刪除結(jié)點是葉子，則直接刪除結(jié)點p；2. 若結(jié)點若結(jié)點p只有左子樹，則只需重接只有左子樹，則只需重接p的左子樹；的左子樹； 若結(jié)點若結(jié)點p只有右子樹，則只需重接只有右子樹，則只需重接p的右子樹；的右子樹； 3. 若結(jié)點若結(jié)點p的左右子樹均不空，則的左右子樹均不空，則 3.1 查找結(jié)點查找結(jié)點p的右子樹上的最左下結(jié)點的右子樹上的最左下結(jié)點s

33、及其雙親結(jié)點及其雙親結(jié)點par； 3.2 將結(jié)點將結(jié)點s數(shù)據(jù)域替換到被刪結(jié)點數(shù)據(jù)域替換到被刪結(jié)點p的數(shù)據(jù)域；的數(shù)據(jù)域； 3.3 若結(jié)點若結(jié)點p的右孩子無左子樹，的右孩子無左子樹， 則將則將s的右子樹接到的右子樹接到par的右子樹上；的右子樹上； 否則，將否則，將s的右子樹接到結(jié)點的右子樹接到結(jié)點par的左子樹上；的左子樹上； 3.4 刪除結(jié)點刪除結(jié)點s；7.3 樹表的查找技術(shù)樹表的查找技術(shù)二叉排序樹的刪除算法二叉排序樹的刪除算法偽代碼偽代碼數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的查找二叉排序樹的查找在二叉排序樹中查找給定值在二叉排序樹中查找給定值k的過程是：的過

34、程是： 若若root是空樹，則查找失??；是空樹，則查找失??； 若若kroot-data，則查找成功；否則則查找成功；否則 若若kroot-data，則在則在root的左子樹上查找；否則的左子樹上查找；否則 在在root的右子樹上查找。的右子樹上查找。 上述過程一直持續(xù)到上述過程一直持續(xù)到k被找到或者待查找的子樹為被找到或者待查找的子樹為空，如果待查找的子樹為空，則查找失敗?？?，如果待查找的子樹為空，則查找失敗。二叉排序樹的查找效率在于只需查找二個子樹之一。二叉排序樹的查找效率在于只需查找二個子樹之一。7.3 樹表的查找技術(shù)樹表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版

35、社例：在二叉排序樹中查找關(guān)鍵字值為例：在二叉排序樹中查找關(guān)鍵字值為35，95的過程：的過程：7.3 樹表的查找技術(shù)樹表的查找技術(shù)50302080908588403532二叉排序樹的查找二叉排序樹的查找50302080908588403532數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社BiNode *BiSortTree:SearchBST( (BiNode *root, int k) ) if ( (root=NULL) ) return NULL； else if ( (root-data=k) ) return root; else if (k(k-data) ) retu

36、rn SearchBST( (root-lchild, k) ); else return SearchBST( (root-rchild, k) );7.3 樹表的查找技術(shù)樹表的查找技術(shù)二叉排序樹的查找二叉排序樹的查找數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社二叉排序樹的查找性能分析二叉排序樹的查找性能分析由序列由序列3, 1, 2, 5, 4得到二叉排序樹：得到二叉排序樹：由序列由序列1, 2, 3, 4, 5得到二叉排序樹：得到二叉排序樹：ASL =（1+2+3+4+5）/ 5= 3ASL =（1+2+3+2+3）/ 5 = 2.2二叉排序樹的查找性能取決于二叉排序樹的

37、形狀，二叉排序樹的查找性能取決于二叉排序樹的形狀，在在O( (log2n) )和和O( (n) )之間。之間。 7.3 樹表的查找技術(shù)樹表的查找技術(shù)1234531254數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社平衡二叉樹：平衡二叉樹：或者是一棵空的二叉排序樹，或者是具或者是一棵空的二叉排序樹，或者是具有下列性質(zhì)的二叉排序樹：有下列性質(zhì)的二叉排序樹： 根結(jié)點的左子樹和右子樹的深度最多相差根結(jié)點的左子樹和右子樹的深度最多相差1; 根結(jié)點的左子樹和右子樹也都是平衡二叉樹。根結(jié)點的左子樹和右子樹也都是平衡二叉樹。 平衡因子：平衡因子：結(jié)點的平衡因子是該結(jié)點的左子樹的深度結(jié)點的平衡因子

38、是該結(jié)點的左子樹的深度與右子樹的深度之差。與右子樹的深度之差。 平衡二叉樹平衡二叉樹7.3 樹表的查找技術(shù)樹表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社548254821是平衡樹是平衡樹 非平衡樹非平衡樹7.3 散列表的查找技術(shù)散列表的查找技術(shù)平衡二叉樹平衡二叉樹在平衡樹中，結(jié)點的平衡因子可以是在平衡樹中，結(jié)點的平衡因子可以是1，0，-1。結(jié)點的平衡因子結(jié)點的平衡因子HL-HR數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社最小不平衡子樹：最小不平衡子樹：在平衡二叉樹的構(gòu)造過程中，在平衡二叉樹的構(gòu)造過程中，以距以距離離插入結(jié)點插入結(jié)點最近的、且平衡因子的

39、絕對值大于最近的、且平衡因子的絕對值大于1的結(jié)的結(jié)點為點為根根的子樹。的子樹。 7.3 樹表的查找技術(shù)樹表的查找技術(shù)542814平衡二叉樹平衡二叉樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社基本思想基本思想：在構(gòu)造二叉排序樹的過程中，每插入一個：在構(gòu)造二叉排序樹的過程中，每插入一個結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，結(jié)點時，首先檢查是否因插入而破壞了樹的平衡性，若是，則找出最小不平衡子樹，在保持二叉排序樹特若是，則找出最小不平衡子樹，在保持二叉排序樹特性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈性的前提下，調(diào)整最小不平衡子樹中各結(jié)點之間的鏈接關(guān)系，進行相應的旋轉(zhuǎn)，

40、使之成為新的平衡子樹。接關(guān)系，進行相應的旋轉(zhuǎn)，使之成為新的平衡子樹。7.3 樹表的查找技術(shù)樹表的查找技術(shù)平衡二叉樹平衡二叉樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社例：設(shè)序列例：設(shè)序列20，35，40，15，30，25 ，構(gòu)造平衡樹。，構(gòu)造平衡樹。2035407.3 樹表的查找技術(shù)樹表的查找技術(shù)352040153025數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社例：設(shè)序列例：設(shè)序列20，35，40，15，30，25 ，構(gòu)造平衡樹。，構(gòu)造平衡樹。7.3 樹表的查找技術(shù)樹表的查找技術(shù)352040153025202515354030354030202515數(shù)據(jù)結(jié)構(gòu)

41、（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社設(shè)結(jié)點設(shè)結(jié)點A為為最小不平衡子樹最小不平衡子樹的根結(jié)點，對該子樹進行的根結(jié)點，對該子樹進行平衡調(diào)整歸納起來有以下四種情況：平衡調(diào)整歸納起來有以下四種情況： 1. LL型型 2. RR型型 3. LR型型 4. RL型型7.3 樹表的查找技術(shù)樹表的查找技術(shù)平衡二叉樹平衡二叉樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社插入前插入前 插入后，調(diào)整前插入后，調(diào)整前 調(diào)整后調(diào)整后7.3 樹表的查找技術(shù)樹表的查找技術(shù)平衡二叉樹平衡二叉樹LL型型A1BLhBRh0ARhBh2BLhBRh1ARABXh+1BLhARBRh00BAX旋轉(zhuǎn)：扁

42、擔原理；沖突：旋轉(zhuǎn)優(yōu)先旋轉(zhuǎn)：扁擔原理；沖突：旋轉(zhuǎn)優(yōu)先數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社612例例: :LL型型 7.3 樹表的查找技術(shù)樹表的查找技術(shù)108791291012876數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社平衡二叉樹平衡二叉樹RR型型7.3 樹表的查找技術(shù)樹表的查找技術(shù)插入前插入前 插入后，調(diào)整前插入后，調(diào)整前 調(diào)整后調(diào)整后A-1BLhBRh0ALhBXA-2BLhBRh0ALhBBALhBLh0BRh+1AX0數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社插入后，調(diào)整前插入后，調(diào)整前 先先逆逆順時針旋轉(zhuǎn)順時針旋轉(zhuǎn) 再再順

43、順時針時針旋轉(zhuǎn)旋轉(zhuǎn)7.3 樹表的查找技術(shù)樹表的查找技術(shù)平衡二叉樹平衡二叉樹LR型型A2CLh-1BLh-1ARhBCCRh-1XXACLh-1CBCRh-1ARhBLhARhCACRh-1BCLh-1X0-10BLh數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社插入后，調(diào)整前插入后，調(diào)整前 先順時針旋轉(zhuǎn)先順時針旋轉(zhuǎn) 再逆時針旋轉(zhuǎn)再逆時針旋轉(zhuǎn)7.3 樹表的查找技術(shù)樹表的查找技術(shù)平衡二叉樹平衡二叉樹RL型型XACLh-1BRhCBCRh-1ALhA-2CLh-1BRh1ALhBCCRh-1XBRhCBCRh-1AALhCLh-1X001數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清

44、華大學出版社課堂練習：設(shè)有關(guān)鍵碼序列課堂練習：設(shè)有關(guān)鍵碼序列5, 4, 2, 8, 6, 9，構(gòu)造平衡樹，構(gòu)造平衡樹5427.3 樹表的查找技術(shù)樹表的查找技術(shù)LL型型42586數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社864256842585642課堂練習：設(shè)有關(guān)鍵碼序列課堂練習：設(shè)有關(guān)鍵碼序列5, 4, 2, 8, 6, 9，構(gòu)造平衡樹，構(gòu)造平衡樹7.3 樹表的查找技術(shù)樹表的查找技術(shù)RL型型旋轉(zhuǎn)旋轉(zhuǎn)1次次RL型型旋轉(zhuǎn)旋轉(zhuǎn)2次次數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社856429RR型型8465297.3 樹表的查找技術(shù)樹表的查找技術(shù)課堂練習：設(shè)有關(guān)鍵碼序

45、列課堂練習：設(shè)有關(guān)鍵碼序列5, 4, 2, 8, 6, 9，構(gòu)造平衡樹，構(gòu)造平衡樹數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社7.3 散列表的查找技術(shù)散列表的查找技術(shù)順序查找、折半查找、二叉排序樹查找等。順序查找、折半查找、二叉排序樹查找等。這些查找技術(shù)都是通過一系列的給定值與關(guān)鍵碼的這些查找技術(shù)都是通過一系列的給定值與關(guān)鍵碼的比較，查找效率依賴于查找過程中進行的給定值與比較，查找效率依賴于查找過程中進行的給定值與關(guān)鍵碼的比較次數(shù)。關(guān)鍵碼的比較次數(shù)。查找操作要完成什么任務(wù)？查找操作要完成什么任務(wù)？待查值待查值k確定確定k在存儲結(jié)構(gòu)中的位置在存儲結(jié)構(gòu)中的位置我們學過哪些查找技術(shù)？

46、這些查找技術(shù)的共性？我們學過哪些查找技術(shù)？這些查找技術(shù)的共性？在存儲位置和關(guān)鍵碼之間建立一個確定的對應關(guān)系在存儲位置和關(guān)鍵碼之間建立一個確定的對應關(guān)系能否不用比較，通過關(guān)鍵碼直接確定存儲位置？能否不用比較，通過關(guān)鍵碼直接確定存儲位置？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社概概 述述散列的基本思想：散列的基本思想：在記錄的存儲地址和它的關(guān)鍵碼之在記錄的存儲地址和它的關(guān)鍵碼之間建立一個確定的對應關(guān)系。這樣，不經(jīng)過比較，一間建立一個確定的對應關(guān)系。這樣，不經(jīng)過比較，一次讀取就能得到所查元素的查找方法。次讀取就能得到所查元素的查找方法。7.3 散列表的查找技術(shù)散列表的查找技術(shù)關(guān)關(guān)

47、鍵鍵碼碼集集合合ki riH( (ki) )H數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列表：散列表：采用散列技術(shù)將記錄存儲在一塊采用散列技術(shù)將記錄存儲在一塊連續(xù)連續(xù)的存的存儲空間中，儲空間中，這塊連續(xù)的存儲空間這塊連續(xù)的存儲空間稱為散列表。稱為散列表。概概 述述7.3 散列表的查找技術(shù)散列表的查找技術(shù)關(guān)關(guān)鍵鍵碼碼集集合合ki riH( (ki) )H散列表散列表數(shù)組數(shù)組數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列函數(shù)：散列函數(shù)：將關(guān)鍵碼映射為散列表中適當存將關(guān)鍵碼映射為散列表中適當存儲位置儲位置的函數(shù)。的函數(shù)。概概 述述7.3 散列表的查找技術(shù)散列表的

48、查找技術(shù)散列表散列表關(guān)關(guān)鍵鍵碼碼集集合合ki riH( (ki) )H散列函數(shù)散列函數(shù)數(shù)組數(shù)組數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列地址：散列地址：由散列函數(shù)由散列函數(shù)所得的存儲位置址所得的存儲位置址 。概概 述述7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列表散列表關(guān)關(guān)鍵鍵碼碼集集合合ki riH( (ki) )H散列函數(shù)散列函數(shù)散列地址散列地址下標下標數(shù)組數(shù)組數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社概概 述述7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列技術(shù)僅僅是一種查找技術(shù)嗎？散列技術(shù)僅僅是一種查找技術(shù)嗎？散列既是一種查找技術(shù)，也是一種存儲技術(shù)。

49、散列既是一種查找技術(shù)，也是一種存儲技術(shù)。散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完散列只是通過記錄的關(guān)鍵碼定位該記錄，沒有完整地表達記錄之間的邏輯關(guān)系，所以，散列主要整地表達記錄之間的邏輯關(guān)系，所以，散列主要是是面向查找面向查找的存儲結(jié)構(gòu)。的存儲結(jié)構(gòu)。散列是一種散列是一種完整的存儲結(jié)構(gòu)完整的存儲結(jié)構(gòu)嗎？嗎？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列技術(shù)一般不適用于允許多個記錄有同樣關(guān)鍵碼散列技術(shù)一般不適用于允許多個記錄有同樣關(guān)鍵碼的情況。散列方法也不適用于范圍查找，換言之，的情況。散列方法也不適用于范圍查找，換言之，在散列表中，我們不可能找到最大或最小關(guān)鍵碼的在散列表中，

50、我們不可能找到最大或最小關(guān)鍵碼的記錄，也不可能找到在某一范圍內(nèi)的記錄。記錄，也不可能找到在某一范圍內(nèi)的記錄。散列技術(shù)最適合回答的問題是：散列技術(shù)最適合回答的問題是：如果有的話，哪個如果有的話，哪個記錄的關(guān)鍵碼等于待查值記錄的關(guān)鍵碼等于待查值。 概概 述述7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列技術(shù)適合于哪種類型的查找？散列技術(shù)適合于哪種類型的查找？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列技術(shù)的關(guān)鍵問題：散列技術(shù)的關(guān)鍵問題： 散列函數(shù)的設(shè)計。如何設(shè)計一個簡單、均勻、存散列函數(shù)的設(shè)計。如何設(shè)計一個簡單、均勻、存儲利用率高的散列函數(shù)。儲利用率高的散列函數(shù)。 沖突的處理。如

51、何采取合適的處理沖突方法來解沖突的處理。如何采取合適的處理沖突方法來解決沖突。決沖突。7.3 散列表的查找技術(shù)散列表的查找技術(shù)概概 述述數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社沖突：沖突：對于兩個不同關(guān)鍵碼對于兩個不同關(guān)鍵碼kikj，有有H( (ki) )H( (kj) )，即兩個不同的記錄即兩個不同的記錄需要存放在同一個存儲位置需要存放在同一個存儲位置, ,ki和和kj相對于相對于H稱做稱做同義詞同義詞。 7.3 散列表的查找技術(shù)散列表的查找技術(shù)概概 述述關(guān)關(guān)鍵鍵碼碼集集合合ki riH(ki)kjH(kj)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列

52、函數(shù)散列函數(shù)7.3 散列表的查找技術(shù)散列表的查找技術(shù)設(shè)計散列函數(shù)一般應遵循以下原則：設(shè)計散列函數(shù)一般應遵循以下原則： 計算計算簡單簡單。散列函數(shù)不應該有很大的計算量，否。散列函數(shù)不應該有很大的計算量，否則會降低查找效率。則會降低查找效率。 函數(shù)值即散列地址分布函數(shù)值即散列地址分布均勻均勻。函數(shù)值要盡量均勻。函數(shù)值要盡量均勻散布在地址空間，這樣才能保證存儲空間的有效利散布在地址空間，這樣才能保證存儲空間的有效利用并減少沖突。用并減少沖突。數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列函數(shù)散列函數(shù)直接定址法直接定址法散列函數(shù)是關(guān)鍵碼的線性函數(shù)散列函數(shù)是關(guān)鍵碼的線性函數(shù)，即：即：H

53、(key) = a key + b （a，b為常數(shù)）為常數(shù)）例：關(guān)鍵碼集合為例：關(guān)鍵碼集合為10, 30, 50, 70, 80, 90，選取的散，選取的散列函數(shù)為列函數(shù)為H( (key) )=key/10，則散列表則散列表為：為： 0 1 2 3 4 5 6 7 8 9103050708090適用情況？適用情況？事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。事先知道關(guān)鍵碼，關(guān)鍵碼集合不是很大且連續(xù)性較好。 7.3 散列表的查找技術(shù)散列表的查找技術(shù)數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社散列函數(shù)為：散列函數(shù)為：H( (key) )=key mod p 7.3 散列表的查找

54、技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)除留余數(shù)法除留余數(shù)列地址散列地址56494235282114 關(guān)鍵碼關(guān)鍵碼如何選取合適的如何選取合適的 p，產(chǎn)生較少同義詞？，產(chǎn)生較少同義詞？例：例： p 2137數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)除留余數(shù)法除留余數(shù)法一般情況下，選一般情況下，選p為小于或等于表長（最好接近表長為小于或等于表長（最好接近表長）的最小素數(shù)或不包含小于的最小素數(shù)或不包含小于20質(zhì)因子的合數(shù)。質(zhì)因子的合數(shù)。 除留余數(shù)法是一種最簡單、也是最常用的構(gòu)造散列除留余數(shù)法是一種最簡單、

55、也是最常用的構(gòu)造散列函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。函數(shù)的方法，并且不要求事先知道關(guān)鍵碼的分布。 適用情況？適用情況？數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社根據(jù)關(guān)鍵碼在各個位上的分布情況，選取分布比較根據(jù)關(guān)鍵碼在各個位上的分布情況，選取分布比較均勻均勻的若干位組的若干位組成散列地址。成散列地址。 例：關(guān)鍵碼為例：關(guān)鍵碼為8位十進制數(shù)，散列地址為位十進制數(shù)，散列地址為2位十進制數(shù)位十進制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9

56、6 7 7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)數(shù)字分析法數(shù)字分析法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社適用情況適用情況:能預先估計出全部關(guān)鍵碼的每一位上各種數(shù)字出現(xiàn)能預先估計出全部關(guān)鍵碼的每一位上各種數(shù)字出現(xiàn)的頻度，不同的關(guān)鍵碼集合需要重新分析。的頻度，不同的關(guān)鍵碼集合需要重新分析。7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)數(shù)字分析法數(shù)字分析法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社對關(guān)鍵碼平方后，按散列表大小，取中間的若干位作對關(guān)鍵碼平方后，按散列表大小，取中間的若干位作為散列地址（為散列地址（平方平方后后截取截取）

57、。）。 7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)平方取中法平方取中法事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。適用情況適用情況:例：散列地址為例：散列地址為2位，則關(guān)鍵碼位，則關(guān)鍵碼1234的散列地址為：的散列地址為：(1234)21522756數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社將關(guān)鍵碼從左到右分割成位數(shù)相等的幾部分，將這幾將關(guān)鍵碼從左到右分割成位數(shù)相等的幾部分，將這幾部分疊加求和，取后幾位作為散列地址。部分疊加求和，取后幾位作為散列地址。 7.3 散列表的查找技術(shù)散列表的查找技術(shù)散列函數(shù)散列函數(shù)折疊法

58、折疊法例：設(shè)關(guān)鍵碼為例：設(shè)關(guān)鍵碼為2 5 3 4 6 3 5 8 7 0 5，散列地址為三位。，散列地址為三位。 2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位疊加移位疊加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 間界疊加間界疊加適用情況適用情況:關(guān)鍵碼位數(shù)很多，事先關(guān)鍵碼位數(shù)很多，事先不知道關(guān)鍵碼的分布。不知道關(guān)鍵碼的分布。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社處理沖突的方法處理沖突的方法開放定址法開放定址法由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突，就去尋找下一個空下一個空的散列地

59、址，并將記錄存入。的散列地址，并將記錄存入。 如何尋找下一個空的散列地址如何尋找下一個空的散列地址?7.3 散列表的查找技術(shù)散列表的查找技術(shù)（1）線性探測法）線性探測法（2）二次探測法）二次探測法（3）隨機探測法）隨機探測法數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社線性探測法線性探測法當發(fā)生沖突時，從沖突位置的下一個位置起，依次當發(fā)生沖突時，從沖突位置的下一個位置起，依次尋找空的散列地尋找空的散列地址。址。 對于鍵值對于鍵值key，設(shè)設(shè)H( (key) )=d，閉散列表的長度為閉散列表的長度為m，則發(fā)生沖突時，尋找下一個散列地址的公式為：則發(fā)生沖突時，尋找下一個散列地址的公式

60、為： Hi=( (H( (key) )di) ) % m （di=1，2，m- -1） 7.3 散列表的查找技術(shù)散列表的查找技術(shù)用開放定址法處理沖突得到的散列表叫用開放定址法處理沖突得到的散列表叫閉散列表閉散列表。 數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)（C+版）版）清華大學出版社清華大學出版社例：關(guān)鍵碼集合為例：關(guān)鍵碼集合為 47, 7, 29, 11, 16, 92, 22, 8, 3，散，散列表表長為列表表長為11，散列函，散列函數(shù)為數(shù)為H( (key) )=key mod 11，用用線性探測法處理沖突，則散列表為：線性探測法處理沖突，則散列表為： 0 1 2 3 4 5 6 7 8 9477291116922922228