數(shù)據(jù)結(jié)構(gòu)liuli查找演示

1、第九章 查找第 九 章 查 找 第九章 查找 9.1 概述 9.2 靜態(tài)表查找表 9.3 動(dòng)態(tài)表查找表 9.4 哈希表第九章 查 找學(xué)習(xí)要點(diǎn)1 掌握順序表和有序表的查找方法；了解二分查找過程的描述方法判定樹；2 掌握二叉排序樹的查找方法；3 掌握哈希表的構(gòu)造方法和查找方法，理解哈希表與其他結(jié)構(gòu)的表的實(shí)質(zhì)性的差異，了解哈希表解決沖突的方法：開放地址法，鏈地址法9.1 概 述本章討論數(shù)據(jù)結(jié)構(gòu)：查找表何謂查找表 ？ 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。 由于“集合中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。對(duì)查找表經(jīng)常進(jìn)行的操作:1查詢某個(gè)“特定的數(shù)據(jù)元素是否在查

2、找表中；2檢索某個(gè)“特定的數(shù)據(jù)元素的各種屬性；3在查找表中插入一個(gè)數(shù)據(jù)元素；4從查找表中刪去某個(gè)數(shù)據(jù)元素。9.1 概 述二 查找的有關(guān)概念1 靜態(tài)查找表、動(dòng)態(tài)查找表僅作查詢和檢索操作的查找表。靜態(tài)查找表有時(shí)在查詢之后，還需要將“查詢結(jié)果為“不在查找表中的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢結(jié)果為“在查找表中的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類:9.1 概 述2 記錄、關(guān)鍵字記錄：由假設(shè)干數(shù)據(jù)項(xiàng)構(gòu)成的數(shù)據(jù)元素稱為記錄是數(shù)據(jù)元素或記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，用以標(biāo)識(shí)識(shí)別一個(gè)數(shù)據(jù)元素或記錄。關(guān)鍵字: 假設(shè)此關(guān)鍵字可以識(shí)別唯一的一個(gè)記錄，那么稱之謂“主關(guān)鍵字。 假設(shè)此關(guān)鍵字能識(shí)別假設(shè)干記錄

3、，那么稱之謂“次關(guān)鍵字。9.1 概 述例：學(xué)生管理系統(tǒng)，假設(shè)想按姓名查找，可將姓名作為關(guān)鍵字，假設(shè)想按學(xué)號(hào)查找，可將學(xué)號(hào)作為關(guān)鍵字，學(xué)號(hào) 姓名 專業(yè) 年齡 01王洪 計(jì)算機(jī) 17 02 孫文 計(jì)算機(jī) 18 03 謝軍 計(jì)算機(jī) 18 04李輝 計(jì)算機(jī) 20 05 沈祥福 計(jì)算機(jī) 25 06 余斌 計(jì)算機(jī) 19 07鞏力 計(jì)算機(jī) 17 08王輝 計(jì)算機(jī) 18說明： 記錄的任何數(shù)據(jù)項(xiàng)都可用為關(guān)鍵字； 假設(shè)此關(guān)鍵字的值能唯一標(biāo)識(shí)記錄，那么稱該關(guān)鍵字為主關(guān)鍵字，否那么次關(guān)鍵字；例：學(xué)號(hào)是主關(guān)鍵字，姓名是次關(guān)鍵字9.1 概 述3 查找 應(yīng)用中有各種各樣的查找，本章討論的查找操作定義如下：查找：給定某個(gè)值，

4、在查找表中查找關(guān)鍵字值等于給定值的記錄，假設(shè)表中存在這樣的記錄，那么稱查找成功，查找結(jié)果為該記錄在表中的位置，否那么稱為查找不成功，查找結(jié)果為“空記錄或“空指針nu11。 查找有內(nèi)查找和外查找之分。假設(shè)整個(gè)查找過程全部在內(nèi)存進(jìn)行，那么稱這樣的查找為內(nèi)查找；反之，假設(shè)在查找過程中還需要訪問外存，那么稱之為外查找。我們僅介紹內(nèi)查找。 要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的平均值來作為衡量一個(gè)查找算法好壞的標(biāo)準(zhǔn)，對(duì)于一個(gè)含有n個(gè)元素的表，查找成功時(shí)的平均查找長(zhǎng)度可表示為ASL= ，其中i為查找第i個(gè)元素的概率，且 =1。一般情形下我們認(rèn)為

5、查找每個(gè)元素的概率相等，i為查找第i個(gè)元素所用到的比較次數(shù)。查找算法的效率用平均查找長(zhǎng)度度量設(shè)查找不成功的可能性很小，可忽略不計(jì)4 平均查找長(zhǎng)度平均查找長(zhǎng)度ASL = 在查找過程中與給定值比較的關(guān)鍵字個(gè)數(shù)的數(shù)學(xué)期望值 PiCiCi為在查找表中查找第i個(gè)記錄所需的比較次數(shù)，Pi為在查找表中查找第i個(gè)記錄的概率 i=1,2n9.1 概 述三 查找表的組織與查找如何在查找表中查找？取決于如何組織查找表例1： 查找索引號(hào)為的圖書1 假設(shè)圖書館中的圖書無序地?cái)[放，那么只能順序查找；2 假設(shè)圖書按索引號(hào)順序擺放，那么可先找到TP類圖書，再找到TP3 例2 在詞典中查找單詞 are1 先找到a打頭的單詞，再

6、在a打頭的單詞中找2 假設(shè)詞典中無序排列，那么只能順序查找；本章介紹： 靜態(tài)查找表的組織方法與查找 動(dòng)態(tài)查找表的組織方法與查找 哈希表的組織方法與查找 本章介紹： 靜態(tài)查找表的組織方法與查找 動(dòng)態(tài)查找表的組織方法與查找9.1 概 述約定：假設(shè)1) 本章查找是關(guān)于主關(guān)鍵字查找；2假設(shè)本章涉及的關(guān)鍵字為整型類型；3為使查找的圖示簡(jiǎn)潔，對(duì)于查找表中的每一記錄，只寫出其關(guān)鍵字；關(guān)鍵字類型定義為 typedef int KeyType; 記錄類型定義為： stypedef struct KeyType key; /關(guān)鍵字域 /其它域 ElemType;9.1 概 述 R= 01,02,03,04,05,

7、06,07,084) 本章所討論的查找方法，只要稍加修改即可用于其他類型的查找例學(xué)號(hào) 姓名 專業(yè) 年齡 01 王洪 計(jì)算機(jī) 17 02 孫文 計(jì)算機(jī) 18 03 謝軍 計(jì)算機(jī) 18 04 李輝 計(jì)算機(jī) 20 05 沈祥福 計(jì)算機(jī) 25 06 余斌 計(jì)算機(jī) 19 07 鞏力 計(jì)算機(jī) 17 08 王輝 計(jì)算機(jī) 189.2 靜態(tài)查找表9.2 靜態(tài)查找表只提供如下兩種查找的查找表，稱為靜態(tài)查找表 1查詢某個(gè)“特定元素是否在表中； 2檢索某個(gè)“特定元素的各種屬性；對(duì)靜態(tài)查找表介紹兩種組織與查找方法 順序表及查找 有序表及查找抽象數(shù)據(jù)類型靜態(tài)查找表的定義為：數(shù)據(jù)對(duì)象D：數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元

8、素的集合。每個(gè)數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。 數(shù)據(jù)元素同屬一個(gè)集合。ADT StaticSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();根本操作 P：next ADT StaticSearchTable構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)元素的靜態(tài)查找表ST。 Create(&ST, n);操作結(jié)果：銷毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；假設(shè) ST 中存在其關(guān)鍵字等于 key 的數(shù)據(jù)元素，那么函數(shù)值為該元素的值或在表中的位置，否那么為“空。 Sea

9、rch(ST, key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key 為和查找表中元素的關(guān)鍵字類型相同的給定值；按某種次序?qū)T的每個(gè)元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，那么操作失敗。Traverse(ST, Visit();初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對(duì)元素操作的應(yīng)用函數(shù)；9.2.1 順序表的查找一 順序表及查找線性表及查找 查找表組織：查找表用線性表表示。即將查找表的記錄排成一個(gè)記錄序列。L1=(45,53,12,3,37,24,100,61,90,78) 順序查找法 1根本思想：從表的最后一個(gè)記錄或第一個(gè)記錄開始，依次將記錄的關(guān)鍵字

10、與給定值比較，假設(shè)相等：查找成功，否那么，繼續(xù)查找。設(shè)查找表用順序表存儲(chǔ)，其類型定義如下：Tyypedef struct ElemType *elem; int length; SSTableint Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等于 / key的數(shù)據(jù)元素。假設(shè)找到，那么函數(shù)值為 / 該元素在表中的位置，否那么為0。 ST.elem0.key = key; / “哨兵 for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時(shí)，i為0 / Sea

11、rch_Seq 在上面的程序中，我們首先將關(guān)鍵字的值送到0號(hào)存儲(chǔ)單元，其目的在于免去查找過程中每一步都要檢測(cè)整個(gè)表是否查找完畢。在此，0號(hào)存儲(chǔ)單元起到了監(jiān)視哨的作用。3)說明：1算法簡(jiǎn)單；2順序查找法對(duì)于查找表的存儲(chǔ)結(jié)構(gòu)沒有特別的要求，既可用順序表也可用線性鏈表存儲(chǔ)；假設(shè)用順序表，查找可從前往后掃描，也可從后往前掃描，但假設(shè)采用單鏈表，那么只能從前往后掃描。另外，順序查找的表中元素可以是無序的。3) 平均查找長(zhǎng)度ASLSS=n+1/2ST.elemiST.elemi60ikey=64key=60i64 定義： 查找算法的平均查找長(zhǎng)度 (Average Search Length) 為確定記錄在

12、查找表中的位置，需和給定值 進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值 其中: n 為表長(zhǎng)，Pi 為查找表中第i個(gè)記錄的概率， 且 Ci為找到該記錄時(shí)，曾和給定值 比較過的關(guān)鍵字的個(gè)數(shù)分析順序查找的時(shí)間性能。在等概率查找的情況下， 順序表查找的平均查找長(zhǎng)度為：對(duì)順序表而言，Ci = n-i+1ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 假設(shè)查找概率無法事先測(cè)定，那么查找過程采取的改進(jìn)方法是，在每次查找之后，將剛剛查找到的記錄直接移至表尾的位置上。在不等概率查找的情況下，ASLss 在 PnPn-1P2P1時(shí)取極小值 如果再考慮查找成功與不成功的可能性相同，對(duì)每個(gè)記錄的查找概率也相等，那么

13、Pi=1/2n,平均查找長(zhǎng)度為： 順序查找缺點(diǎn)是當(dāng)n很大時(shí)，平均查找長(zhǎng)度較大，效率低；優(yōu)點(diǎn)是對(duì)表中數(shù)據(jù)元素的存儲(chǔ)沒有要求。另外，對(duì)于線性鏈表，只能進(jìn)行順序查找。有序表的查找有序表及查找 有序表：假設(shè)線性表中的記錄按關(guān)鍵字有序，那么稱為有序表 查找表組織：查找表用有序表表示。即將查找表的記錄排成 按關(guān)鍵字有序的序列。 二分查找法也稱為折半查找法1根本思想：將查找范圍中間位置的記錄關(guān)鍵字與給定值比較： ：繼續(xù)在前半個(gè)表中用二分查找法查找 = ：查找成功，返回記錄位置 ：繼續(xù)在后半個(gè)表中中用二分查找法查找有序表的查找 例1 L2=( 3,12,24,37,45,53,61,78,90,100 )，查

14、找 Key=24的記錄 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100lowmid high 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100lowmid high 24 45 繼續(xù)在前半個(gè)表中用二分查找法查找 1 2 3 4 5 6 7 8 9 10 3 12 24 37 45 53 61 78 90 100Low mid high 24 12 繼續(xù)在后半個(gè)表中用二分查找法查找查找成功int Search_Bin ( SSTable ST, KeyType key ) /在有序表ST中折

15、半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。假設(shè)找到，那么函數(shù)值為/該元素在表中的位置，否那么為0。; / 置區(qū)間初值 while (low 50時(shí)，可得近似結(jié)果 一般情況下，表長(zhǎng)為 n 的折半查找的判定樹的深度和含有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度相同。有序表的查找說明：折半查找法效率比順序查找高;平均查找長(zhǎng)度ASLbs=log2n+1-1要求表中的記錄按關(guān)鍵字有序；3) 表中的記錄要用順序結(jié)構(gòu)存儲(chǔ)；例 在有1000個(gè)記錄的查找表查找，順序查找法平均要比較500次，折半查找法平均要比較9次，可見折半查找法效率比順序查找高。9.2.2、有序表的查找 Fibonacci 查找 1、Fibonacci 數(shù)定

16、義： F0 = 0 F1 = 1 Fn = Fn-1 + Fn-2 如：0,1,2,3,5,8,13,21,34,55,89,144,233 2、實(shí)現(xiàn) 設(shè)結(jié)點(diǎn)的總數(shù)為 n = Fu - 1，查找鍵值為 key 的結(jié)點(diǎn) 首先比較 key STFu1.key 如果 key STFu1.key ，那么比較 key = STFu1+ Fu3.key 3、注意： 參照以下圖，設(shè)根結(jié)點(diǎn)或子樹的根結(jié)點(diǎn)同它的左、右兒子的下標(biāo)之差為Fu3 那么，根結(jié)點(diǎn)或子樹的根結(jié)點(diǎn)的左兒子的同它的兒子的下標(biāo)之差為Fu4 根結(jié)點(diǎn)或子樹的根結(jié)點(diǎn)的右兒子的同它的兒子的下標(biāo)之差為Fu5 可以設(shè)計(jì)類似于二分查找的算法。但先要把 Fu3

17、、 Fu4 、 Fu5計(jì)算出來，它們也構(gòu)成 Fibonacci 數(shù)?？9.2、靜態(tài)查找表 Fibonacci 查找 4、e.g: n = F6 - 1 = 13 - 1 = 12個(gè)結(jié)點(diǎn)的查找過程 Fu1 = 8 Fu3 = 3 Fu4 = 2 Fu5 = 1 311127105826419STFu1.key差為 Fu3 = 3 差為 Fu5 = 1差為 Fu2 = 2共 Fu1 1817個(gè)結(jié)點(diǎn)共 Fu2 1514個(gè)結(jié)點(diǎn) 5、優(yōu)點(diǎn)：只用 、法，不用除法。平均查找速度更快。Olog2n級(jí)。 缺點(diǎn)：最壞情況下比二分查找法差。必須先給出 Fibonacci 數(shù)。 插值查找 1、除中點(diǎn)下標(biāo)的選擇和二分查

18、找不同外，其余類似。用于關(guān)鍵字值均勻的情況，平均特性更好。 2、實(shí)現(xiàn) 設(shè) mid 為中點(diǎn)的下標(biāo)。low 為具有最小關(guān)鍵字值結(jié)點(diǎn)的下標(biāo)， high 為具有最大關(guān)鍵字值結(jié)點(diǎn)的下標(biāo)。 mid=(high-low+1)(key-ST.elemlow.key)/ (ST.elemhigh.key - ST.elemlow.key 關(guān)鍵字: A B C D E Pi: Ci: 2 3 1 2 39.2.3 靜態(tài)查找樹表 在不等概率查找的情況下，折半查找不是有序表最好的查找方法例如:此時(shí) ASL=20.2+30.3+10.05+20.3+30.15=假設(shè)改變Ci的值 2 1 3 2 3那么 ASL=20.2

19、+10.3+30.05+20.3+30.15= 使 達(dá)最小的判定樹稱為最優(yōu)二叉樹，其中: 定義:為計(jì)算方便，令 wi = pi選擇二叉樹的根結(jié)點(diǎn)，使 達(dá)最小 介紹一種次優(yōu)二叉樹的構(gòu)造方法:為便于計(jì)算，引入累計(jì)權(quán)值和 并設(shè) wl-1 = 0 和 swl-1 = 0，那么推導(dǎo)可得023811151823例如:lh211812431018h9608EC21Ah53lhG3013ECGABDF所得次優(yōu)二叉樹如下所示: 查找比較“總次數(shù) = 32+41+25+33 +14+33+25 = 52 查找比較“總次數(shù) = 32+21+35+13 +34+23+35 = 59和折半查找相比較DBACFEG但從上面的查找結(jié)果可以看出，該二叉樹并不是最優(yōu)二叉樹，棵可以得到比該二叉樹更優(yōu)的二叉樹。但研究結(jié)果說明，次優(yōu)查找樹和最優(yōu)查找樹的查找性能之差僅