數(shù)據結構課件：第9章 查找1靜態(tài)查找表

1、第9章 查找查找的基本概念靜態(tài)查找表動態(tài)查找表哈希表查找的基本概念9.1 查找的基本概念查找表：是由同一類型的具有相同可辨認特性的 數(shù)據元素（或記錄）構成的集合。 對查找表經常進行的操作： 1. 查詢某個“特定的”數(shù)據元素是否在查找表中； 2. 查詢某個“特定的”數(shù)據元素的各種屬性； 3. 在查找表中插入一個數(shù)據元素； 4. 刪除查找表中的某個數(shù)據元素。 查找表的分類9.1 查找的基本概念靜態(tài)查找表動態(tài)查找表：僅作“查詢”（檢索）操作的查找表，只查找，不改變數(shù)據元素集內的數(shù)據元素。作“插入”和“刪除”操作的查找表既查找，又改變(增減)集合內的數(shù)據元素。關鍵字9.1 查找的基本概念 在實際應用問

2、題中，每個記錄一般包含有多個數(shù)據域，查找是根據其中某一個指定的域進行的，這個作為查找依據的域稱關鍵字(key)。主關鍵字 可唯一標識一個記錄的關鍵字。例：學號次關鍵字 可識別若干記錄的關鍵字。例：性別關鍵字9.1 查找的基本概念姓名學號性別年齡健康情況王小林790631男18健康陳 紅790632女20一般劉建平790633男21健康張立立790634男17健康 查找9.1 查找的基本概念 根據給定的某個值，在查找表中確定一個其關鍵字等于給定值的記錄或數(shù)據元素。 若表中存在這樣的一個記錄，則稱查找是成功的，若表中不存在關鍵字等于給定值的記錄，則稱查找不成功。靜態(tài)查找如何進行查找 取決于查找表的

3、結構，如字典，電話本平均查找長度(Average Search Length)9.1 查找的基本概念 為確定記錄在查找表中的位置，需和給定值進行比較的關鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度(ASL)。 對于含有n個記錄的表，查找成功時的平均查找長度為查找表中第i個記錄的概率，且找表中關鍵字與給定值相等的第i個記錄時，和給定值已進行過比較的關鍵字個數(shù)靜態(tài)查找表順序表的查找有序表的查找索引順序表的查找9.2 靜態(tài)查找表順序表的查找9.2 靜態(tài)查找表順序查找：從表的一端開始，逐個進行記錄的關鍵 字和給定值的比較。 查找過程： 找645371921135664928880750123

4、456789101164順序查找的算法9.2 靜態(tài)查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 53719211356649288807501234567891011找60找不到時，i為0&(i=0)順序查找的算法9.2 靜態(tài)查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 5371

5、9211356649288807501234567891011找60&(i=0)60順序查找的算法9.2 靜態(tài)查找表int Search_seq(SSTable ST , int n, int key) ST0.key=key; int i=n; while(STi.key!=key) i-; return i; 53719211356649288807501234567891011找6060監(jiān)視哨監(jiān)視哨作用：避免每步都去判斷是否查找結束順序查找的算法分析9.2 靜態(tài)查找表 對于n個數(shù)據元素的表，若給定值key與表中第i個元素的關鍵字相等，則需要n-i+1次關鍵字比較，即Ci=n-i+1。 例

6、如，當?shù)趎個元素的關鍵字為key時，需要進行1次比較(n-n+1=1)，又如，當?shù)谝粋€元素為所求時，需要進行n次比較(n-1+1=n)。因此，查找成功時，順序查找的平均查找長度為 Pi每個元素的查找概率，假設所有元素的查找概率均相等。順序查找的算法分析9.2 靜態(tài)查找表 對于n個數(shù)據元素的表，若給定值key與表中第i個元素的關鍵字相等，則需要n-i+1次關鍵字比較，即Ci=n-i+1。 例如，當?shù)趎個元素的關鍵字為key時，需要進行1次比較(n-n+1=1)，又如，當?shù)谝粋€元素為所求時，需要進行n次比較(n-1+1=n)。因此，查找成功時，順序查找的平均查找長度為 順序查找的算法分析9.2 靜

7、態(tài)查找表 若查找失敗，則算法一直遍歷到Elem0，總共比較n+1次。5371921135664928880750123456789101160順序查找的算法分析9.2 靜態(tài)查找表查找成功時的平均查找次數(shù)為： ASL=(1+2+3+4+n)/n = (n+1)/2 查找不成功時的比較次數(shù)為： ASL=(n(n+1)/n = n+1 則順序查找的平均查找長度為： ASL=( + )/2 = 3(n+1)/4優(yōu)點：算法簡單，無需排序，采用順序和鏈式存儲均可。缺點：當n很大時，平均查找長度較大。有序表的查找9.2 靜態(tài)查找表折半查找 又稱為二分法查找，每次將待查記錄所在區(qū)間縮小一半查找思想 先確定待查

8、找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止前提條件 必須在具有順序存儲結構的有序表中進行有序表的查找9.2 靜態(tài)查找表81423374655687991lowhighmid例:查找23high = mid-1keymid keyhigh = nlow = 1mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2有序表的查找9.2 靜態(tài)查找表81423374655687991lowhighmid例:查找79low = mid + 1keymid keyhigh = nlow = 1

9、mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2有序表的查找9.2 靜態(tài)查找表81423374655687991lowhighmid例:查找80low = mid + 1Key=80mid keyhigh = nlow = 1mid = (low+high)/2mid = (low+high)/2mid keylow = mid +1mid = (low+high)/2mid keyhigh = mid - 1折半查找的算法9.2 靜態(tài)查找表int Search_Bin( SSTable ST ,

10、 int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if (STmid.key = key) return mid; else if ( key=1）2k-1個423156789101112131415二叉樹的性質6.2 二叉樹性質4：具有n個結點的完全二叉樹的高度為 log2n + 1證明：設完全二叉樹的高度為k，則有 (2k-1 -1 ) n (2k -1) 或 2k-1 n 2k 兩邊取對數(shù) k-1 log2n k 因為k是整數(shù)，所以k = log2n + 1算法性能分析

11、9.2 靜態(tài)查找表8142337465568799112345678946911468823375579比較次數(shù) log2n +1 查找不成功： 算法性能分析9.2 靜態(tài)查找表8142337465568799112345678946911468823375579查找不成功： 算法性能分析9.2 靜態(tài)查找表 若在樹的高度為k的滿二叉樹n=2k-1中，樹的第i層有2i-1個結點，樹的第i層結點的全部查詢次數(shù)為i*2i-1，在等概率的情況下，Pi=1/n，因此，折半查找的平均查找長度為算法性能分析9.2 靜態(tài)查找表81423374655687991123456789算法性能分析9.2 靜態(tài)查找表 折

12、半查找的效率相當高，在最壞的情況下(即查找失敗時)的關鍵字比較次數(shù)也不超過判定樹的深度，而且折半查找的最壞性能與平均性能相當接近。 但折半查找只能用于有序表中，而排序本身是一件很費時的事情。折半查找還要求對數(shù)據元素隨機訪問，因此只能用順序存儲的線性表中，因此適用于查找頻繁，但是有序表元素改動少的應用中。9.2 靜態(tài)查找表8142337465568799112345678946911468823375579靜態(tài)樹表的查找9.2 靜態(tài)查找表ABCDE12345CADBE0.20.20.20.20.2靜態(tài)樹表的查找9.2 靜態(tài)查找表ABCDE12345CADBE0.10.20.10.40.20.10

13、.20.10.40.2靜態(tài)樹表的查找9.2 靜態(tài)查找表ABCDE12345CBDAE0.10.20.10.40.2靜態(tài)樹表的查找9.2 靜態(tài)查找表ABCDE12345靜態(tài)樹表的查找9.2 靜態(tài)查找表 折半查找的平均查找長度的前提是查找表中各個記錄被查找的概率相同。如果表中各個記錄被查找的概率不同，那么折半查找是否是在有序表中進行查找的最好選擇呢？ 這就說明，當有序表中各記錄的查找概率不等時，折半查找性能未必是優(yōu)的。 那么此時應如何進行查找呢?靜態(tài)樹表的查找9.2 靜態(tài)查找表 若只考慮查找成功的情況，則使查找性能達最佳的判定樹是其帶權內路徑長度之和PH值取最小值的二叉樹。 其中：n為二叉樹上結點

14、的個數(shù)(即有序表的長度)；hi為第i個結點在二叉樹上的層次數(shù)；結點的權wi=cpi(i=1，2，n)，其中pi為結點的查找概率，c為某個常量。稱PH值取最小的二叉樹為靜態(tài)最優(yōu)查找樹(Static Optimal Search Tree)。靜態(tài)樹表的查找9.2 靜態(tài)查找表0.10.20.10.40.2ABCDE12345最優(yōu)查找樹= ？最優(yōu)二叉樹(哈夫曼樹)左兒子比根節(jié)點小，右兒子比根節(jié)點大?哈夫曼樹的節(jié)點不是原始的數(shù)據節(jié)點靜態(tài)樹表的查找9.2 靜態(tài)查找表 由于構造靜態(tài)最優(yōu)查找樹花費的時間代價較高，因此在此介紹一種構造近似最優(yōu)查找樹的有效算法。靜態(tài)樹表的查找9.2 靜態(tài)查找表 若某個二叉樹的PH

15、 值在所有具有同樣權值的二叉樹中近似為最小，則稱它為“次優(yōu)查找樹”(Nearly Optimal Search Tree) 次優(yōu)查找樹（近似最優(yōu)查找樹） 假設按關鍵字從小到大有序排列的記錄序列為： (rl , rl+1, , rh) 其中 rl .key rl+1.key rh.key 與每個記錄相應的權值為 wl , wl+1, , wh 靜態(tài)樹表的查找9.2 靜態(tài)查找表構造次優(yōu)查找樹方法： 從序列 (rl , rl+1, , rh) 中選取第 i (l i h) 個記錄作為次優(yōu) 二叉樹的“根結點”，要求 取最小值。 然后分別對子序列 (rl , rl+1, , ri-1) 和 (ri+1

16、, ri+2, , rh) 構造兩 棵次優(yōu)查找樹，并分別設為根結點的左子樹和右子樹。 例： 0123456789ABCDEFGHI112534435 j Keyj Wj Pj 27 25 22 15 7 0 8 15 23 為便于計算，引入累計權 值和： SWj 0 1 2 4 9 12 16 20 23 28 0 l h 并設 wl -1 = 0 和 swl -1 = 0， 則 i 根 FPj h 11 9 6 1 9 根 i Dl h 8 1 7 i HPj l h 3 1 2 根 i B 0 i E 0 0 i i GI根 Pj 0 0 i i ACEBGACFHDIPH = 71 PH

17、 = 83 當各關鍵字 查找概率不 等時，次優(yōu) 查找樹的查 找性能優(yōu)于 折半查找。 索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表普通搜索存在的問題： 當數(shù)據對象個數(shù)n很大時，如果用無序表形式的靜態(tài)搜索結構存儲，采用順序搜索，則搜索效率極低。如果采用有序表存儲形式的靜態(tài)搜索結構，則插入新記錄進行排序，時間開銷也很可觀。這時可采用索引方法來實現(xiàn)存儲和搜索。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表示例：有一個存放職工信息的數(shù)據表，每一個職工對象有近1k字節(jié)的信息, 正好占據一個頁塊的存儲空間。建立一個索引表便于數(shù)據的搜索。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表索引的優(yōu)勢：有時數(shù)

18、據文件很大不能一次全部裝入內存，所以搜索一個數(shù)據對象無論是順序搜索或對分搜索，都需要多次讀取外存記錄。索引文件比數(shù)據文件要小的多，從外存中把索引表讀入內存，經過搜索索引后確定了職工對象的存儲地址，再經過1次讀取對象操作就可以完成搜索。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表幾個概念：稠密索引：即一個索引項對應數(shù)據表中一個對象的索引結構。此時對象在外存中可不按關鍵碼有序存放。此索引結構叫做索引非順序結構。前面的例子就是一個稠密索引結構。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表幾個概念：稀疏索引：當對象在外存中按關鍵碼有序存放時，可以把所有 n 個對象分為 b 個子表(塊)存放，一

19、個索引項對應數(shù)據表中一組對象(子表)。下圖是一個稀疏索引的例子。這樣的索引結構叫做索引順序結構。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表分塊查找：是順序查找的一種改進方法，就是把被查找的表分成若干塊，每塊中記錄的存放順序是無序的，但塊與塊之間必須按關鍵字有序。即第一塊中任一記錄的關鍵字都小于第二塊中任一記錄的關鍵字，而第二塊中任一記錄的關鍵字都小于第三塊中任一記錄的關鍵字，依此類推。22 12 13 8 9 20 索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表條件：1. 將表分成幾塊，且表或者有序，或者分塊有序； 2. 建立“索引表”（每個結點含有最大關鍵字域和 指向本塊第一個結點的指針，且按關鍵字有序）。 1 7 1322 48 86索引表 1 2 3 4 5 6