數(shù)據(jù)結(jié)構(gòu)-第九章

1、數(shù) 據(jù) 結(jié) 構(gòu)第九章 查找引言查找表：由同一類型的數(shù)據(jù)元素構(gòu)成的集合。對查找表的操作:查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；檢索某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一個數(shù)據(jù)元素；從查找表中刪去某個數(shù)據(jù)元素引言靜態(tài)查找表：僅作查詢和檢索操作的查找表。動態(tài)查找表：在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素,此類表為動態(tài)查找表。引言關(guān)鍵字：是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用以標(biāo)識一個數(shù)據(jù)元素（或記錄）。若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。如：學(xué)號，身份證。若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。如：姓名。引言

2、查找： 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。 若查找表中存在這樣一個記錄，則稱“查找成功”，查找結(jié)果：給出整個記錄的信息，或指示該記錄在查找表中的位置；否則稱“查找不成功”，查找結(jié)果：給出“空記錄”或“空指針”。9.1 靜態(tài)查找表查找的方法取決于查找表的結(jié)構(gòu)。由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。9.1 靜態(tài)查找表ADT StaticSearchTable 數(shù)據(jù)對象D:是具有相同特性的數(shù)據(jù)元素的集 合。每個數(shù)據(jù)元素含有類型

3、相同 的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個集合?；静僮?P： Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit(); ADT StaticSearchTable9.1.1 順序表的查找以順序表或線性表表示靜態(tài)查找表，則查找可以用順序的方式進(jìn)行。我們以線性表的順序存儲為例來學(xué)習(xí)順序表的查找。 typedef struct ElemType *elem; int length; SSTable;9.1.1 順序表的查找在線性表中查找一個元素是非常容易的。為了程序編寫簡單，我們采用從后往前查找的

4、方式，并且在第一個位置上設(shè)置一個“監(jiān)視哨”。10 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464監(jiān)視哨5432比較次數(shù)=5比較次數(shù)：查找第n個元素： 1查找第n-1個元素：2查找第i個元素： n+1-i 查找第1個元素： n查找失?。?n+1查找過程：從表的一端開始逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較。例如：9.1.1 順序表的查找int Search_Seq(SSTable ST, KeyType key) ST.elem0.key = key; for (i=ST.length; ST.elemi.key!=key;

5、-i); return i;9.1.1 順序表的查找查找算法的平均查找長度ASL( Average Search Length)： 為確定記錄在查找表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值。 9.1.1 順序表的查找通過分析，我們可以得到順序表查找成功：9.1.2 有序表的查找順序表的查找算法簡單，但平均查找長度較大，不適用于表長較大的查找表。若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進(jìn)行。9.1.2 有序表的查找折半查找查找過程：每次將待查記錄所在區(qū)間縮小一半。適用條件：采用順序存儲結(jié)構(gòu)的有序表。ST.elemST.length例如: key = 64 的查找過程如下lo

6、whighmidlow mid high midlow 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。ST.elemST.length例如: key = 70 的查找過程如下lowhighmidlow mid high midlow 指示查找區(qū)間的下界;high 指示查找區(qū)間的上界;mid = (low+high)/2。lowmidhighint Search_Bin ( SSTable ST, KeyType kval ) low = 1; high = ST.length; while (low = high) mid = (low + high)

7、 / 2; if （key = ST.elemmid.key ) return mid; else if ( key ST.elemmid.key) ) high = mid - 1; else low = mid + 1; return 0;先看一個具體的情況，假設(shè)查找表：n=11分析折半查找的平均查找長度6391425781011判定樹12233334444 查找表: A B C D E F G H I J K log 2 n +1ASL = 33/11最大次數(shù)9.1.4 索引順序表的查找索引順序表：在建立順序表的同時，建立一個索引項，包括兩項：關(guān)鍵字項（每塊中的最大值）和指針項（每塊的起

8、始地址）。索引表按關(guān)鍵字有序。表則為分塊有序（每塊中的元素都要求大于前一塊的元素）。01234567891011121317821191431332225405261784621 040 578 10索引順序表 = 索引 + 順序表順序表索引表9.1.4 索引順序表的查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例如9.1.4 索引順序表的查找9.2 動態(tài)查找表動態(tài)查找表的特點(diǎn):表結(jié)構(gòu)本身是在查找過程中動態(tài)生

9、成。若表中存在其關(guān)鍵字等于給定值key的記錄,表明查找成功；否則插入關(guān)鍵字等于key的記錄。ADT見P2279.2.1 二叉排序樹和二叉平衡樹二叉排序樹：二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹；若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；它的左、右子樹也都分別是二叉排序樹。9.2.1 二叉排序樹和二叉平衡樹503080209010854035252388669.2.1 二叉排序樹和二叉平衡樹二叉排序樹的查找算法若二叉排序樹為空，則查找不成功；否則1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；2）若給定值小于根結(jié)

10、點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹上進(jìn)行查找；3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹上進(jìn)行查找。注意：因?yàn)槭莿討B(tài)查找表，則在查找不成的情況下，需要插入該結(jié)點(diǎn)。在二叉排序樹中查找關(guān)鍵字值等于50,35,90,9550308020908540358832505050304035505080909.2.1 二叉排序樹和二叉平衡樹二叉排序樹的插入算法：根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進(jìn)行；若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一個新的葉子結(jié)點(diǎn)，其插入位置由查找過程得到。9.2.1 二叉排序樹和二叉平衡樹例如：45，24，53，45，12，37，9345

11、24531237939.2.1 二叉排序樹和二叉平衡樹二叉排序樹查找性能的分析 對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的 ASL 值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同。由關(guān)鍵字序列 3，1，2，5，4構(gòu)造而得的二叉排序樹由關(guān)鍵字序列 1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.29.2.1 二叉排序樹和二叉平衡樹平衡二叉樹AVL：二叉平衡樹是二叉排序樹的另一種形式，其特點(diǎn)為：樹中每個結(jié)點(diǎn)的左、右子樹深度之差

12、的絕對值不大于1 。平衡因子BF：某結(jié)點(diǎn)的左子樹的深度減它的右子樹的深度。9.2.1 二叉排序樹和二叉平衡樹5482548219.2.1 二叉排序樹和二叉平衡樹平衡二叉樹AVL性質(zhì)：AVL樹的深度與logn同數(shù)量級，它的平均查找長度ASL也與logn同數(shù)量級。9.2.1 二叉排序樹和二叉平衡樹構(gòu)建AVL樹，需要進(jìn)行旋轉(zhuǎn)。例如：（13, 24, 37, 90, 53)練習(xí)：（5, 4, 3, 8, 19,1,2，25，23）9.2.2 B-樹和B+樹本節(jié)介紹兩種特殊的平衡樹，只需要了解樹的結(jié)構(gòu)，特點(diǎn)。9.2.2 B-樹和B+樹B -樹：一種平衡的多路查找樹 一棵m階的B-樹或?yàn)榭諛?，或?yàn)闈M足下列

13、特性的m叉樹：樹中每個節(jié)點(diǎn)至多有m棵子樹。若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹。除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2 棵子樹所有的非終端結(jié)點(diǎn)中包含下列信息數(shù)據(jù)(n,A0,K1,A1,K2,A2,Kn,An)。其中n為關(guān)鍵字個數(shù)，Ai-1指向子樹的指針，且Ai-1指向的子樹中所有關(guān)鍵字均小于Ki。Ki(i=1,n)為關(guān)鍵字，且KiKi+1,(i=1,n-1)所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上，并且不帶信息（空指針）。135118243781111271393475364199t9.2.2 B-樹和B+樹練習(xí)：一棵m階B-樹每個結(jié)點(diǎn)最多有（ ）棵子樹，（ ）個關(guān)鍵字,最少有（ ）棵子樹( )個

14、關(guān)鍵字。B+樹 B+樹是B-樹的變型，m階的B+樹和m階的B-樹的區(qū)別是：關(guān)鍵字個數(shù)和子樹個數(shù)一樣多所有葉子結(jié)點(diǎn)中包含全部關(guān)鍵字信息及指向含這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。所有非終端結(jié)點(diǎn)可看成索引，節(jié)點(diǎn)中僅含有其子樹中的最大（或最小）關(guān)鍵字。9.2.2 B-樹和B+樹59 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt9.3 哈希表以上兩節(jié)討論的表示查找表的各種結(jié)構(gòu)的共同特點(diǎn)：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系。查找的過程為給定值依次和關(guān)鍵字集合中各個關(guān)鍵字進(jìn)行比較

15、。查找的效率取決于和給定值進(jìn)行比較的關(guān)鍵字個數(shù)。9.3 哈希表 哈希查找：基本思想：在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。9.3 哈希表哈希函數(shù)：在記錄的關(guān)鍵字與記錄的存儲地址之間建立的一種對應(yīng)關(guān)系。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲地址空間的一種映象。可寫成，addr(ai)=H(ki)其中：ai是表中的一個元素 addr(ai)是ai的存儲地址 ki是ai的關(guān)鍵字9.3 哈希表例如：建立一張全國30個地區(qū)的各民族人口統(tǒng)計表。Key BeijingTianjinHebeiShanxiShanghaif1(key)0

16、220081919f2(key)0904172828f3(key)04260213239.3 哈希表哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可。沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象9.3 哈希表哈希函數(shù)的構(gòu)造方法:直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法9.3 哈希表直接定址法：哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a *key + b此法僅適合于：地址集合的大小 = = 關(guān)鍵字集合的大小例如：按照學(xué)號存放記錄。 數(shù)字分析法假設(shè)關(guān)鍵字集合中的每個關(guān)鍵字都

17、是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。此法適于能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。例 有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī)所以：取任意兩位或兩位 與另兩位的疊加作

18、哈希地址 以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。平方取中法 除留余數(shù)法 設(shè)定哈希函數(shù)為: H(key) = key MOD p ( pm ) 其中， m為表長 例如：（28，35，63，77，105） p=3632835012349.3 哈希表“處理沖突” 的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。開放定址法再哈希法鏈地址法為產(chǎn)生沖突的地址 H(key) 求得一個地址序列： H0, H1, H2, , Hs 1sm-1Hi = ( H(key) + di ) MOD m 其中： i=1, 2, , sH(key)為哈希函數(shù);m為哈希表長;di為增量序列,有下列三種取法:開放定址法對增量 di 的三種取法：1)線性探測再散列 di = 1,2,3,m-1 2) 二次探測再散列 di = 12, -12, 22, -22, ,3) 隨機(jī)探測再散列 di 是一組偽隨機(jī)數(shù)列例如: 給定關(guān)鍵字集合構(gòu)造哈希表 19, 01, 23, 14, 55, 68, 11, 82, 36 設(shè)定哈希函數(shù) H(key) = key MOD 11 ( 表長=11 )1901231455681901231468若采用線性探測再