1、1、靜態查找表、靜態查找表2、動態查找表、動態查找表3、哈希查找表哈希查找表查找查找查找查找查找在某種數據結構中找出滿足條件的結點：找到查找成功找不到查找失敗關鍵字（鍵）能唯一確定結點的一個或多個域平均查找長度查找一個結點所作的平均比較次數（衡量一個查找算法優劣的主要標準）順序表的查找順序表的查找靜態查找表靜態查找表算法思想：從表的一端開始，用給定值k與表中各個結點的鍵值逐個比較： 查找成功-找出相等鍵盤值； 查找失敗-已到達表的另一端（可在此設置一個監視哨，作為下標越界的條件），即表中所有結點的鍵值都不等于k。012n-3n-2n-1nkey 8100100713i012n-3n-2n-1n

2、i數組數組 ST.elem key查找查找 key = 8 的結點所在的數組元素的下標。的結點所在的數組元素的下標。 8100100713順序表的查找順序表的查找key 8100100713i順序表的查找順序表的查找靜態查找表靜態查找表監視哨的作用：作為越界（即已查完）的檢測條件，省去在循環中每次均要判定是否越界，從而節省比較的時間。順序表的查找順序表的查找結點類型定義：typedef struct int key; /*關鍵字*/ folat info; /*其它域*/JD;int search(JD r , int n, int k)int i = n; /*從表尾開始向前查找*/r0.k

3、ey = k; /*設置監視哨*/While(ri.key! = k) i-;return(i) ;順序表查找算法：性能分析：性能分析： 平均查找長度平均查找長度ASL（Average Search Length ）成功查找情況下：設每個結點的查找概率相等成功查找情況下：設每個結點的查找概率相等一般查找情況下一般查找情況下( (包括成功、不成功兩種情況包括成功、不成功兩種情況) )：設成功與不成功兩種情況可能性相等，每個結點的查找概設成功與不成功兩種情況可能性相等，每個結點的查找概率也相等。率也相等。 順序表的查找順序表的查找順序表的查找順序表的查找順序查找的特點：（1）算法簡單，對線性表的邏

4、輯次序無要求（即不必按關鍵字值不增或不減的次序排列）（2）存儲結構可采用順序或鏈式存儲結構均可，但其平均查找長度較大(（n+1)/2)有序表的查找有序表的查找折半查找（或二分查找法）折半查找（或二分查找法）二分法的特點：（1）線性表的表中結點必須按關鍵字有序；（2）線性表須采用順序存儲結構。二分法思想：（1）用給定的k與有序表的中間位置mid上的結 點的關鍵字比較，若相等，查完（2）若rmid.key k)，則執行（3）（3）在右子表中繼續進行二分查找。查找查找 key = 9 的結點所在的數組元素的下標地址。的結點所在的數組元素的下標地址。數組數組 ST.elem 如下圖所示有序如下圖所示有

5、序數組數組 ST.elem ：遞增序：遞增序 ST.elemi. Key = ST.elemi+1. Key; i= 1, 2 ,n-1查找范圍查找范圍 ：low（低下標）低下標）= 1; high（高下標）高下標）= 7 （初始時為最大下標（初始時為最大下標 n ）;比較對象：中點元素，其下標地址為比較對象：中點元素，其下標地址為 mid = （low+high）/ 2 =4 4 8 9 10 11 13 19有序表的查找有序表的查找012mid=4 但但 key=9 8, 向右向右key 4 8 9 10 11 13 1934567high=3（mid-1）low=1012mid=3; k

6、ey 4 8 9 10 11 13 1934567high=3low=3查找查找 key = 5 的結點所在的數組元素的下標地址。的結點所在的數組元素的下標地址。數組數組 ST.elem 如下圖所示有序如下圖所示有序數組數組 ST.elem ：遞增序：遞增序 ST.elemi. Key = ST.elemI+1. Key; i= 1,2,n-1查查找范圍找范圍 ：low（低下標）低下標）= 1; high（高下標）高下標）= 3 ;比較對象：中點元素，其下標地址為比較對象：中點元素，其下標地址為 mid =(low+high)/ 2 = 2有序表的查找有序表的查找012mid=4key 4 8

7、 9 10 11 13 1934567high=3 low=1012mid=4key 4 8 9 10 11 13 1934567high=7low=1012mid=2key 4 8 9 10 11 13 1934567high=3low=1有序表的查找有序表的查找012mid=2; 但但 key=5 8, 向左向左key 4 8 9 10 11 13 1934567high=1low=1012key 4 8 9 10 11 13 1934567high=3low=1012mid=2key 4 8 9 10 11 13 1934567high=1（mid-1）low=1有序表的查找有序表的查找

8、mid=1,但但 key=5 high; 處于間隙中處于間隙中的鍵值導致這種情況！的鍵值導致這種情況！表示：表示：typedef struct ElemType * elem; int length; / length = n有序表的查找有序表的查找int halfsearch (JD r , int n, int k)int i, j, mid;i = 1, j = n;While (i = j)mid = ( i+j ) / 2;If ( k = = rmid.key ) return(mid);else if (k rmid.key ) j = mid-1; else i = mid+1

9、;Return(0); 性能分析性能分析 1、最壞情況分析：設、最壞情況分析：設 key 和中點的二次比較的時間代價和中點的二次比較的時間代價 1如果如果 n = 1, 則則 low = high = mid , 則代價為則代價為 1，記為，記為 S（1） 1如果如果 n 是奇數，那么中點元素的左、右段各有是奇數，那么中點元素的左、右段各有 (n-1)/2 個元素個元素如果如果 n 是偶數，中點元素的左段有是偶數，中點元素的左段有 n/2-1 個元素；右段有個元素；右段有 n/2 個元素個元素因此，算法工作的那一段，最多有因此，算法工作的那一段，最多有 n/2 項項 S（n）= 1 + S（

10、n/2 ）= 1 + 1 + S（ n/22 ）= 1 + 1 + 1 + S（ n/23 ） = 1 + 1 + 1 + + 1 + S（ n/2k ）當當 1 = n/2k 2 時；則時；則 n/2k = 1 此時：此時： 2k = n 2k+1 即即 k = log2n k+1注意：注意：k 不可為小數，它是正整數。不可為小數，它是正整數。 k = log2n 故：故： S（n）= 1 + log2n 有序表的查找有序表的查找012mid= 4 4 8 9 10 11 13 1934567high=7low=1012mid= 4 4 8 9 10 11 13 1934567low=1 2

11、0high=88有序表的查找有序表的查找 1、最壞情況分析：、最壞情況分析：定理：在最壞情況下，二分查找法的查找有序表的最大的比較次數為定理：在最壞情況下，二分查找法的查找有序表的最大的比較次數為1+ log2n ，大體上和大體上和 log2n 成正比。也可用判定樹的方法進行推導。成正比。也可用判定樹的方法進行推導。如：如：16735248key = k4?012345678489101113192912345678 當尋找當尋找 key = 8 及小于、大于及小于、大于 8 的鍵值的相應結點時，查找的鍵值的相應結點時，查找次數最大。達到了判定樹的深次數最大。達到了判定樹的深度或高度。度或高度

12、。有序表的查找有序表的查找性能分析性能分析2、平均情況分析（在成功查找的情況下）：設每個、平均情況分析（在成功查找的情況下）：設每個 結點的查找概率相同結點的查找概率相同都為都為1/n。為了簡單起見，設結點個數為為了簡單起見，設結點個數為 n = 2t -1 （t = 1,2,3 ）。）。 經過經過 1 次比較確定的結點個數為次比較確定的結點個數為 1 = 20 個個 ，紅色標識的結點。，紅色標識的結點。 經過經過 2 次比較確定的結點個數為次比較確定的結點個數為 2 = 21 個個 ，綠色標識的結點。，綠色標識的結點。經過經過 3 次比較確定的結點個數為次比較確定的結點個數為 4 = 22

13、個個 ，灰色標識的結點。，灰色標識的結點。經過經過 t 次比較確定的結點個數為次比較確定的結點個數為 2t-1 個個 ，黑色標識的結點。，黑色標識的結點。注意：注意： 20 + 21 + 22 + + 2t-1 = 2t -1 最多經過最多經過 t 次比較可以找到有序表中的任何一個結點次比較可以找到有序表中的任何一個結點e.g: 當當 t = 4 時的例子：最多經過時的例子：最多經過 t=4 次比較找到任何一個結點次比較找到任何一個結點48910 1113192912345678324765778193999101112131415有序表的查找有序表的查找性能分析性能分析 Fibonacci

14、數數定義：定義：F0 = 0，F1 = 1，Fn = Fn-1 + Fn-2 如：如：0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 Fibonacci Fibonacci 查找查找 實現實現 設結點的總數為設結點的總數為 n = Fu - 1，查找鍵值為查找鍵值為 key 的結點的結點 首先比較首先比較 key STFu1.key 如果如果 key STFu1.key ，則比較則比較 key 與與 STFu1+ Fu3.key Fibonacci Fibonacci 查找查找 注意：注意：設根結點（或子樹的根結點）同它的左、右兒子的下標之設根結點

15、（或子樹的根結點）同它的左、右兒子的下標之差為差為Fu3 那么，那么，根結點（或子樹的根結點）的左兒子同它的兒子的下根結點（或子樹的根結點）的左兒子同它的兒子的下標之差為標之差為Fu4 根結點（或子樹的根結點）的右兒子同它的兒子的下標之差根結點（或子樹的根結點）的右兒子同它的兒子的下標之差為為Fu5 可以設計類似于二分查找的算法。但先要把可以設計類似于二分查找的算法。但先要把 Fu3 、 Fu4 、 Fu5計算出來，它們也構成計算出來，它們也構成 Fibonacci 數數 Fibonacci Fibonacci 查找查找 n = F6 - 1 = 13 - 1 = 12個結點的查找過程個結點的

16、查找過程 Fu1 = 8 Fu3 = 3 Fu4 = 2 Fu5 = 1 311127105826419STFu1.key差為差為 Fu3 = 3 差為差為 Fu4 = 2差為差為 Fu5 = 1共共 Fu1 1817個結點個結點共共 Fu2 1514個結點個結點 Fibonacci Fibonacci 查找查找 優點：優點：只用只用 、法，不用除法。平均查找速度更快。、法，不用除法。平均查找速度更快。O(log2n)級。級。缺點：缺點：最壞情況下比二分查找法差。必須先給出最壞情況下比二分查找法差。必須先給出Fibonacci 數。數。 Fibonacci Fibonacci 查找查找除中點下

17、標的選擇和二分查找不同外，除中點下標的選擇和二分查找不同外，其余類似。用于其余類似。用于關鍵字值均勻的情況，平均特性更好。關鍵字值均勻的情況，平均特性更好。實現實現設設 mid 為中點的下標。為中點的下標。low 為具有最小關鍵字值結點的下為具有最小關鍵字值結點的下標，標，high為具有最大關鍵字值結點的下標。為具有最大關鍵字值結點的下標。mid =(high-low+1)(key-ST.elemlow.key)/ (ST.elemhigh.key - ST.elemlow.key） 差值查找差值查找分塊查找分塊查找存儲方式：存儲方式：線性表分成若干塊，每個塊內的元素的關鍵字不線性表分成若干塊

18、，每個塊內的元素的關鍵字不一定有序（一定有序（“塊內無序塊內無序”）塊與塊之間必須按鍵值有序，即前一塊中的最大塊與塊之間必須按鍵值有序，即前一塊中的最大鍵值小于后一塊中的最小鍵值（鍵值小于后一塊中的最小鍵值（“分塊有序分塊有序”）。）。附加索引表：附加索引表：索引表的一塊索引表結點由鍵域、鏈域組成。索引表的一塊索引表結點由鍵域、鏈域組成。存放相應塊的最大鍵值。存放指向本塊第一個結點的指針。查找查找 key = 47 的結點索引。查索引表，確定在第三塊內進的結點索引。查索引表，確定在第三塊內進行順序查找行順序查找387363521406012345678947索引索引順序表順序表83660147

19、塊最大關鍵字塊最大關鍵字塊起始地址塊起始地址索引表索引表塊最大關鍵字有序塊最大關鍵字有序塊內關鍵字無序（也可有序）塊內關鍵字無序（也可有序）分塊查找分塊查找 應用范圍：有序表、查找概率不等。應用范圍：有序表、查找概率不等。EBDAC 舉例：已知舉例：已知 A、B、C、D、E；查找概率分別為：查找概率分別為：0.1、0.2、0.1、0.4、0.2 求成功查找時的平均查找長度？求成功查找時的平均查找長度？AECBD平均查找長度平均查找長度 10.1+20.1+ 20.2+ 30.2+ 30.4 2.5平均查找長度平均查找長度10.4+20.2+ 20.2+ 30.1+ 30.1 1.8靜態樹表的查

20、找靜態樹表的查找 例子說明越接近根結點，例子說明越接近根結點， 那么代價之和將越小。那么代價之和將越小。 n PH = Wi Hi j=1 PH 值最小的二叉樹為最優查找樹。值最小的二叉樹為最優查找樹。靜態樹表的查找靜態樹表的查找 次最優查找樹：次最優查找樹：HEGDF 舉例：已知舉例：已知 A、B、C、D、E、F、G、H、I；查找概率分別為：查找概率分別為：1、 1、2、 5、3、 4、4、 3、5 建造次最優查找樹。建造次最優查找樹。ADEBCDECABBIA建造方法：建造方法：1、兩邊權值等、兩邊權值等 2、根結點或子樹的根結點應盡量大。、根結點或子樹的根結點應盡量大。A、B、C、D、E

21、1 30 2 29 3靜態樹表的查找靜態樹表的查找定義：定義：或是空樹，或是具有如下性質的二叉樹：（1）若它的lc非空，則lc上所有結點的key 根的key（3）它的lc、rc本身又是一棵二叉排序樹二叉排序樹二叉排序樹性質：性質：對二叉排序樹按中序遍歷所得到的中序序列是一個遞增的有序序列。特點：特點：用非線性結構表示一個線性有序表。二叉排序樹二叉排序樹45125333724100619078按中序遍歷：按中序遍歷：3，12，24，37，45，53，61，78，90，100遞增二叉排序樹二叉排序樹Typedef struct nodeint key;struct node *lc, *rc;JD

22、;采用二叉鏈表作存儲結構采用二叉鏈表作存儲結構，它是一種動態數據結構，這種上結構的插入、刪除操作非常方便方便，無需移動大量的元素。結點類型定義結點類型定義在一棵給定的二叉排序樹中插入新結點，只要保證插入仍符合二叉排序樹的定義即可。插入的方法是：插入的方法是：若二叉排序樹（以r為根）為空，則待插入結點*s作為根結點插入空樹中，否則（非空），在二叉排序樹中查找給定的結點，若找到（即：將待插入結點的關鍵字（前者）和樹根的關鍵字（后者）比較，兩者相等），則無須插入，否則（查找必停止在左指針或右指針處）：若前者后者，插入到右子樹中。插入運算插入運算在一棵給定的二叉排序樹中插入新結點，只要保證插入仍符合二

23、叉排序樹的定義即可。插入結點時，不需要遍歷樹，僅需走一條從根到某個有空子樹的結點的路徑。而插入的結點作為葉子結點。插入運算插入運算在下圖給定的二叉排序樹中插入結點20。4512533372410061907820插入運算插入運算Status Inset BST ( BiTree &T，Element e ) / 在二叉分類樹中不存在 e.key 時，插入并返回 TRUE，否則返回 FALSE。 if ( ! SearchBST ( T，e.key，NULL，p ) s = ( Bitree ) malloc ( sizeof ( BitNode ) ); s-data = e; s-l

24、child = s-rchild = NULL; if ( ! p ) T = s; else if ( LT( e.key , p -data. key ) ) p - lchild = s; else p - rchild = s; return TRUE; return FALSE; / Insert BST 程序實現程序實現 插入算法插入算法在一棵給定的二叉排序樹中查找鍵值為k的結點的方法是：若樹為空，返回空指針，否則：若k key，在左子樹檢索k，否則：若k r-key，在右子樹檢索k，否則：k = r-key，找到，返回k的指針；若找到某個結點的左子樹或右子樹是空，則查找失敗并返回

25、空指針。查找運算查找運算顯然，在二叉排序樹中查找某結點其實是從根結點出發走了一條從根到待查結點的路徑?？紤]如下兩種不同插入次序的序列構成的二叉排序樹，插入次序分別為：4024551237122437405540，24，12，37，55 12，24，37，40，55查找運算查找運算插入次序分別為：4024551237122437405540，24，12，37，55 12，24，37，40，55顯然，第 i 層結點需比較 i 次。在等概率的前提下，上述兩圖的平均查找長度為：)(35/ )54321 ()(2 . 25/ )23221 (11右圖左圖niiiniiicpcp查找運算查找運算由上例分析易知：由上例分析易知：在二叉排序樹中進行查找的平均查找長度和二叉樹的在二叉排序樹中進行查找的平均查找長度和二叉樹的