數(shù)據(jù)結(jié)構(gòu)課件：第9章 查找1靜態(tài)查找表VIP

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

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

3、結(jié)構(gòu)，如字典，電話本平均查找長度(Average Search Length)9.1 查找的基本概念 為確定記錄在查找表中的位置，需和給定值進行比較的關(guān)鍵字個數(shù)的期望值稱為查找算法在查找成功時的平均查找長度(ASL)。 對于含有n個記錄的表，查找成功時的平均查找長度為查找表中第i個記錄的概率，且找表中關(guān)鍵字與給定值相等的第i個記錄時，和給定值已進行過比較的關(guān)鍵字個數(shù)靜態(tài)查找表順序表的查找有序表的查找索引順序表的查找9.2 靜態(tài)查找表順序表的查找9.2 靜態(tài)查找表順序查找：從表的一端開始，逐個進行記錄的關(guān)鍵 字和給定值的比較。 查找過程： 找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)視哨作用：避免每步都去判斷是否查找結(jié)束順序查找的算法分析9.2 靜態(tài)查找表 對于n個數(shù)據(jù)元素的表，若給定值key與表中第i個元素的關(guān)鍵字相等，則需要n-i+1次關(guān)鍵字比較，即Ci=n-i+1。 例

6、如，當?shù)趎個元素的關(guān)鍵字為key時，需要進行1次比較(n-n+1=1)，又如，當?shù)谝粋€元素為所求時，需要進行n次比較(n-1+1=n)。因此，查找成功時，順序查找的平均查找長度為 Pi每個元素的查找概率，假設(shè)所有元素的查找概率均相等。順序查找的算法分析9.2 靜態(tài)查找表 對于n個數(shù)據(jù)元素的表，若給定值key與表中第i個元素的關(guān)鍵字相等，則需要n-i+1次關(guān)鍵字比較，即Ci=n-i+1。 例如，當?shù)趎個元素的關(guān)鍵字為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、找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認找不到該記錄為止前提條件 必須在具有順序存儲結(jié)構(gòu)的有序表中進行有序表的查找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二叉樹的性質(zhì)6.2 二叉樹性質(zhì)4：具有n個結(jié)點的完全二叉樹的高度為 log2n + 1證明：設(shè)完全二叉樹的高度為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個結(jié)點，樹的第i層結(jié)點的全部查詢次數(shù)為i*2i-1，在等概率的情況下，Pi=1/n，因此，折半查找的平均查找長度為算法性能分析9.2 靜態(tài)查找表81423374655687991123456789算法性能分析9.2 靜態(tài)查找表 折

12、半查找的效率相當高，在最壞的情況下(即查找失敗時)的關(guān)鍵字比較次數(shù)也不超過判定樹的深度，而且折半查找的最壞性能與平均性能相當接近。 但折半查找只能用于有序表中，而排序本身是一件很費時的事情。折半查找還要求對數(shù)據(jù)元素隨機訪問，因此只能用順序存儲的線性表中，因此適用于查找頻繁，但是有序表元素改動少的應用中。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)查找表 若只考慮查找成功的情況，則使查找性能達最佳的判定樹是其帶權(quán)內(nèi)路徑長度之和PH值取最小值的二叉樹。 其中：n為二叉樹上結(jié)點

14、的個數(shù)(即有序表的長度)；hi為第i個結(jié)點在二叉樹上的層次數(shù)；結(jié)點的權(quán)wi=cpi(i=1，2，n)，其中pi為結(jié)點的查找概率，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ù)據(jù)節(jié)點靜態(tài)樹表的查找9.2 靜態(tài)查找表 由于構(gòu)造靜態(tài)最優(yōu)查找樹花費的時間代價較高，因此在此介紹一種構(gòu)造近似最優(yōu)查找樹的有效算法。靜態(tài)樹表的查找9.2 靜態(tài)查找表 若某個二叉樹的PH

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

16、, ri+2, , rh) 構(gòu)造兩 棵次優(yōu)查找樹，并分別設(shè)為根結(jié)點的左子樹和右子樹。 例： 0123456789ABCDEFGHI112534435 j Keyj Wj Pj 27 25 22 15 7 0 8 15 23 為便于計算，引入累計權(quán) 值和： SWj 0 1 2 4 9 12 16 20 23 28 0 l h 并設(shè) 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 當各關(guān)鍵字 查找概率不 等時，次優(yōu) 查找樹的查 找性能優(yōu)于 折半查找。 索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表普通搜索存在的問題： 當數(shù)據(jù)對象個數(shù)n很大時，如果用無序表形式的靜態(tài)搜索結(jié)構(gòu)存儲，采用順序搜索，則搜索效率極低。如果采用有序表存儲形式的靜態(tài)搜索結(jié)構(gòu)，則插入新記錄進行排序，時間開銷也很可觀。這時可采用索引方法來實現(xiàn)存儲和搜索。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表示例：有一個存放職工信息的數(shù)據(jù)表，每一個職工對象有近1k字節(jié)的信息, 正好占據(jù)一個頁塊的存儲空間。建立一個索引表便于數(shù)據(jù)的搜索。索引順序表的查找（分塊查找） 9.2 靜態(tài)查找表索引的優(yōu)勢：有時數(shù)

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

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