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

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

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

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

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

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

8、找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止前提條件 必須在具有順序存儲(chǔ)結(jié)構(gòu)的有序表中進(jìn)行有序表的查找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個(gè)423156789101112131415二叉樹的性質(zhì)6.2 二叉樹性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的高度為 log2n + 1證明：設(shè)完全二叉樹的高度為k，則有 (2k-1 -1 ) n (2k -1) 或 2k-1 n 2k 兩邊取對(duì)數(shù) k-1 log2n k 因?yàn)閗是整數(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個(gè)結(jié)點(diǎn)，樹的第i層結(jié)點(diǎn)的全部查詢次數(shù)為i*2i-1，在等概率的情況下，Pi=1/n，因此，折半查找的平均查找長(zhǎng)度為算法性能分析9.2 靜態(tài)查找表81423374655687991123456789算法性能分析9.2 靜態(tài)查找表 折

12、半查找的效率相當(dāng)高，在最壞的情況下(即查找失敗時(shí))的關(guān)鍵字比較次數(shù)也不超過(guò)判定樹的深度，而且折半查找的最壞性能與平均性能相當(dāng)接近。 但折半查找只能用于有序表中，而排序本身是一件很費(fèi)時(shí)的事情。折半查找還要求對(duì)數(shù)據(jù)元素隨機(jī)訪問(wèn)，因此只能用順序存儲(chǔ)的線性表中，因此適用于查找頻繁，但是有序表元素改動(dòng)少的應(yīng)用中。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)查找表 折半查找的平均查找長(zhǎng)度的前提是查找表中各個(gè)記錄被查找的概率相同。如果表中各個(gè)記錄被查找的概率不同，那么折半查找是否是在有序表中進(jìn)行查找的最好選擇呢？ 這就說(shuō)明，當(dāng)有序表中各記錄的查找概率不等時(shí)，折半查找性能未必是優(yōu)的。 那么此時(shí)應(yīng)如何進(jìn)行查找呢?靜態(tài)樹表的查找9.2 靜態(tài)查找表 若只考慮查找成功的情況，則使查找性能達(dá)最佳的判定樹是其帶權(quán)內(nèi)路徑長(zhǎng)度之和PH值取最小值的二叉樹。 其中：n為二叉樹上結(jié)點(diǎn)

14、的個(gè)數(shù)(即有序表的長(zhǎng)度)；hi為第i個(gè)結(jié)點(diǎn)在二叉樹上的層次數(shù)；結(jié)點(diǎn)的權(quán)wi=cpi(i=1，2，n)，其中pi為結(jié)點(diǎn)的查找概率，c為某個(gè)常量。稱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é)點(diǎn)小，右兒子比根節(jié)點(diǎn)大?哈夫曼樹的節(jié)點(diǎn)不是原始的數(shù)據(jù)節(jié)點(diǎn)靜態(tài)樹表的查找9.2 靜態(tài)查找表 由于構(gòu)造靜態(tài)最優(yōu)查找樹花費(fèi)的時(shí)間代價(jià)較高，因此在此介紹一種構(gòu)造近似最優(yōu)查找樹的有效算法。靜態(tài)樹表的查找9.2 靜態(tài)查找表 若某個(gè)二叉樹的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 與每個(gè)記錄相應(yīng)的權(quán)值為 wl , wl+1, , wh 靜態(tài)樹表的查找9.2 靜態(tài)查找表構(gòu)造次優(yōu)查找樹方法： 從序列 (rl , rl+1, , rh) 中選取第 i (l i h) 個(gè)記錄作為次優(yōu) 二叉樹的“根結(jié)點(diǎn)”，要求 取最小值。 然后分別對(duì)子序列 (rl , rl+1, , ri-1) 和 (ri+1

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

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

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