講義專業(yè)課數(shù)據(jù)結(jié)構(gòu)課件

1、1第九章 查 找精英專升本23何謂查找表 ？ 查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。 由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。4對查找表經(jīng)常進行的操作:1）查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個數(shù)據(jù)元素；4）從查找表中刪去某個數(shù)據(jù)元素。5僅作查詢和檢索操作的查找表。靜態(tài)查找表有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動態(tài)查找表查找表可分為兩類:6是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的

2、值，用以標識（識別）一個數(shù)據(jù)元素（或記錄）。關(guān)鍵字 若此關(guān)鍵字可以識別唯一的一個記錄，則稱之謂“主關(guān)鍵字”。 若此關(guān)鍵字能識別若干記錄，則稱之謂“次關(guān)鍵字”。7 根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或（記錄）。 查找 若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置； 否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。8 由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。 為了提高查找的效率， 需要在查找表中的元素之間人為地 附加某種確定的關(guān)系，換句話說， 用另外一種結(jié)構(gòu)來表示查找表。如何進

3、行查找？查找的方法取決于查找表的結(jié)構(gòu)。99.1 靜態(tài)查找表9.2 動態(tài)查找樹表9.3 哈希表109.1 靜態(tài)查找表順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)順序表線性鏈表11typedef struct / 數(shù)據(jù)元素存儲空間基址，建表時 / 按實際長度分配，0號單元留空 int length; / 表的長度 SSTable;假設(shè)靜態(tài)查找表的順序存儲結(jié)構(gòu)為ElemType *elem;聲明順序查找表變量：SSTable ST12數(shù)據(jù)元素類型的定義為:typedef struct keyType key; / 關(guān)鍵字域 / 其它屬性域 ElemType ; , TElemType ;若有順序查找表ST，則第i個元素

4、的關(guān)鍵字是：ST.elemi.key139.1.1、順序查找表9.1.2、有序查找表9.1.3、靜態(tài)查找樹表(*)9.1.4、索引順序表14ST.elem回顧順序表的查找過程：P26算法2.6假設(shè)給定值 e=64,要求 ST.elemk = e, 問: k = ?k一、順序查找表 以順序表或線性鏈表表示靜態(tài)查找表kk假設(shè)給定值 e=91,要求 ST.elemk = e, 問: k = ?15ST.elemST.elem60ikey=64key=6064算法2.6的改進：iii16int Search_Seq(SSTable ST, KeyType key) / 在順序表ST中順序查找其關(guān)鍵字等

5、于 / key的數(shù)據(jù)元素。若找到，則函數(shù)值為 / 該元素在表中的位置，否則為0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 從后往前找 return i; / 找不到時，i為0 / Search_Seq17關(guān)鍵字的平均比較次數(shù)，也稱平均搜索長度ASL(Average Search Length)n：記錄的個數(shù)pi：查找第i個記錄的概率 ( 通常認為pi =1/n )ci：找到第i個記錄所需的比較次數(shù)（n-i+1）查找算法的評價指標18空間復(fù)雜度：一個輔助空間。時間復(fù)雜度：1) 查找成功時的平均查

6、找長度 設(shè)表中各記錄查找概率相等 ASLs(n)=(1+2+ . +n)/n =(n+1)/22)查找不成功時的查找長度 ASLf =n+1順序查找的性能分析19n個數(shù)存在一維數(shù)組A1.n中，在進行順序查找時，這n個數(shù)的排列有序或無序其平均查找長度ASL不同。 練習(xí):判斷對錯查找概率相等時，ASL相同；查找概率不等時，如果從前向后查找，則按查找概率由小到大排列的順序表其ASL要比無排列的順序表ASL小。 20 上述順序查找表的查找算法簡單， 但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表 若以有序表表示靜態(tài)查找表，則查找過程可以基于“折半”進行。21lowhighmid 1

7、2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid折半查找若k=Rmid.key，查找成功若kRmid.key，則low=mid+122 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3

8、4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid若k=Rmid.key，查找成功若kRmid.key，則low=mid+1231 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid直至lowhigh時，查找失

9、敗24int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low data.key進行比較： 若key等于T-data.key，則查找成功，返回根結(jié)點地址； 若key小于T-data.key，則進一步查找左子樹； 若key大于T-data.key，則進一步查找右子樹?！舅惴ㄋ枷搿?1BSTree SearchBST(BSTree T,KeyType key) if( (!T) | key=T-data.key ) return T; else if (key data.key)

10、 return SearchBST( T-lchild, key); else return SearchBST( T-rchild, key); / SearchBST【算法描述】T為空樹，查找不成功，返回空指針key和樹T的根節(jié)點關(guān)鍵字相等，查找成功，返回根節(jié)點指針T42為方便插入操作，需要在查找時增設(shè)指針1、增設(shè)指針 p 指向查找路徑上訪問的最后一個結(jié)點2、增設(shè)指針 f 指向當(dāng)前查找過程中樹T的雙親3、插入操作在查找不成功時進行，所以在查找成功時返回true，查找不成功時返回false改寫的算法描述 P228 算法9.5（b）二叉排序樹的操作插入根據(jù)動態(tài)查找表的定義，“插入”操作在查找不

11、成功時才進行4330201040352523fT設(shè) key = 48fTfT22pfTfTTTTfffp插入的元素一定是P的左孩子或右孩子44二叉排序樹的操作插入插入的元素一定在葉結(jié)點上若二叉排序樹為空，則插入結(jié)點應(yīng)為根結(jié)點否則，繼續(xù)在其左、右子樹上查找樹中已有，不再插入樹中沒有，查找直至某個葉子結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)點的左孩子或右孩子45Status Insert BST(BiTree &T, ElemType e ) / 當(dāng)二叉排序樹中不存在關(guān)鍵字等于 e.key 的 / 數(shù)據(jù)元素時，插入元素值為 e 的結(jié)點，并返 / 回 TRUE; 否則，不進行插入并返回F

12、ALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 46s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 為 *p 的左孩子else p-rchild = s; / 插入 *s 為 *p 的右孩子retu

13、rn TRUE; / 插入成功47 10， 18， 3， 8， 12， 2， 7 10101810183101838101838121018381221018381227從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹二叉排序樹的操作生成二叉排序樹48不同插入次序的序列生成不同形態(tài)的二叉排序樹4024551237122437405540，24，12，37，5512，24，37，40，55二叉排序樹的操作生成49（1）被刪除的結(jié)點是葉子；（2）被刪除的結(jié)點只有左子樹或者只有右子樹；（3）被刪除的結(jié)點既有左子樹，也有右子樹。4二叉排序樹的刪除算法可分三種情況討論： 和插入相反，刪除

14、在查找成功之后進行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。5050308020908540358832（1）被刪除的結(jié)點是葉子結(jié)點例如:被刪關(guān)鍵字 = 2088其雙親結(jié)點中相應(yīng)指針域的值改為“空”5150308020908540358832（2）被刪除的結(jié)點只有左子樹或者只有右子樹 其雙親結(jié)點的相應(yīng)指針域的值改為 “指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字 = 40805250308020908540358832（3）被刪除的結(jié)點既有左子樹，也有右子樹4040以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關(guān)鍵字 = 5053第i層結(jié)點需比較i次。在等概

15、率的前提下，上述兩圖的平均查找長度為：40245512371224374055查找的性能分析54平均查找長度和二叉樹的形態(tài)有關(guān)，即，最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似）最壞: （n+1)/2（單支樹）查找的性能分析4024551237122437405555問題：如何提高二叉排序樹的查找效率？盡量讓二叉樹的形狀均衡左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值 1平衡二叉樹平衡因子:該結(jié)點左子樹與右子樹的高度差56 平衡二叉樹（AVL樹）是二叉查找樹的另一種形式，其特點為： 樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1 。例如:548254821是平衡樹不是平

16、衡樹57(a) 平衡樹 (b) 不平衡樹練習(xí)：判斷下列二叉樹是否AVL樹？00011-1-120001-1對于一棵有n個結(jié)點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。58 構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 65424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)59如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。LL平衡旋轉(zhuǎn)RR平衡旋轉(zhuǎn)LR平衡旋轉(zhuǎn)RL平衡旋轉(zhuǎn)保證二叉排序樹的次序不變60若在A的左

17、子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：61若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABCABC3）LR平衡旋轉(zhuǎn)：6201303

18、7024練習(xí)：請將下面序列構(gòu)成一棵平衡二叉排序樹 （ 13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn)，B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053 63 在平衡樹上進行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)不超過平衡 樹的深度。平衡樹的查找性能分析： 問：含 n 個關(guān)鍵字的二叉平衡樹可能達到的最大深度是多少？64n = 0空樹最大深度為 0n = 1最大深度為 1n = 2最大深度為 2n = 4最大深度為 3n = 7最大深度為 4

19、先看幾個具體情況:65反過來問，深度為 h 的二叉平衡樹中所含結(jié)點的最小值 Nh 是多少？h = 0N0 = 0h = 1h = 2h = 3一般情況下N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用歸納法可證得Nh = Fh+2 - 1 因此，在二叉平衡樹上進行查找時，查找過程中和給定值進行比較的關(guān)鍵字的個數(shù)和 log(n) 相當(dāng)。 總之，含有 n 個結(jié)點的二叉平衡樹能達到的最大深度 hn = log(5 (n+1) - 2。 66 一、哈希表是什么？二、哈希函數(shù)的構(gòu)造方法 三、處理沖突的方法 四、哈希表的查找 五、哈希表的刪除操作9.3 哈 希 表67前述查

20、找表的各種結(jié)構(gòu)的共同特點：記錄在表中的位置和它的關(guān)鍵字之間不存在一個確定的關(guān)系，一、哈希表是什么？查找的效率取決于和給定值進行比較的關(guān)鍵字個數(shù)。用這類方法表示的查找表，其平均查找長度都不為零。對于頻繁使用的查找表，希望 ASL = 0。只有一個辦法：預(yù)先知道所查關(guān)鍵字在表中的位置 即，要求：記錄在表中位置和其關(guān)鍵字之間存在一種確定的關(guān)系。68若以下標為000 999 的順序表表示之。例如：為每年招收的 1000 名新生建立一張查找表，其關(guān)鍵字為學(xué)號，其值的范圍為 xx000 xx999 (前兩位為年份)。則查找過程可以簡單進行：取給定值（學(xué)號）的后三位，不需要經(jīng)過比較便可直接從順序表中找到待查

21、關(guān)鍵字。69基本思想：記錄的存儲位置與關(guān)鍵字之間存在對應(yīng)關(guān)系，Loc(i)=H(key) 優(yōu)點：查找速度極快O(1),查找效率與元素個數(shù)n無關(guān)哈希函數(shù)關(guān)鍵字集合存儲地址集合hash70數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）k，請畫出存儲結(jié)構(gòu)圖。14119內(nèi)容地址3925242314119232539例271根據(jù)哈希函數(shù)H（k）k 查找key=9,則訪問H(9)=9號地址，若內(nèi)容為9則成功；若查不到，則返回一個特殊值，如空指針或空記錄。 如何查找14119內(nèi)容地址392524231411923253972哈希方法(雜湊法)選取某個函數(shù)，依該函數(shù)按關(guān)鍵

22、字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進行比，確定查找是否成功。哈希函數(shù)(雜湊函數(shù))：哈希方法中使用的轉(zhuǎn)換函數(shù)有關(guān)術(shù)語73沖 突：不同的關(guān)鍵碼映射到同一個哈希地址哈希表(雜湊表)：按上述思想構(gòu)造的表有關(guān)術(shù)語14119內(nèi)容地址3925242314119232539同義詞：具有相同函數(shù)值的兩個關(guān)鍵字key1key2，但H(key1)=H(key2)74（14，23，39，9，25，11）哈希函數(shù)：H(k)=k mod 72539239146個元素用7個地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7

23、=4同義詞有沖突 0 1 2 3 4 5 6沖突現(xiàn)象舉例75沖突是不可能避免的如何減少沖突構(gòu)造好的哈希函數(shù)制定一個好的解決沖突方案76哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造地址空間盡量小均勻直接定址法 數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機數(shù)法 77Hash(key) = akey + b (a、b為常數(shù))優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突。缺點：要占用連續(xù)地址空間，空間效率低。 直接定址法 例： 100，300，500，700，800，900， 哈希函數(shù)Hash(key)=key/1000 1 2 3 4 5 6 7 8 9900800700500300100此

24、法僅適合于：地址集合的大小 = = 關(guān)鍵字集合的大小78除留余數(shù)法 設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中， pm (表長) 并且 p 應(yīng)為不大于 m 的素數(shù) 或是不含 20 以下的質(zhì)因子79 給定一組關(guān)鍵字為：12, 39, 18, 24, 33, 21，若取 p=9, 則他們對應(yīng)的哈希函數(shù)值將為： 3, 3, 0, 6, 6, 3例如：為什么要對 p 加限制？ 可見，若 p 中含質(zhì)因子 3， 則所有含質(zhì)因子 3 的關(guān)鍵字均映射到“3 的倍數(shù)”的地址上，從而增加了“沖突”的可能。80三、處理沖突的方法 “處理沖突” 的實際含義是：為產(chǎn)生沖突的地址尋找下一個哈希地址。1.

25、 開放定址法2. 鏈地址法81基本思想：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 1.開放定址法（開地址法）線性探測法二次探測法偽隨機探測法82Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m為哈希表長度 di 為增量序列 1，2，m-1，且di=i一旦沖突，就找下一個空地址存入線性探測法83關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)：哈希表表長為m=11； 哈希函數(shù)為Hash(key)=key mod 11 0 1 2 3 4 5 6 7 8 9 10477 291116922283 47、7

26、、11、16、92沒有沖突 Hash(29)=7，有沖突，由H1=(Hash(29)+1) mod 11=8，哈希地址8為空，因此將29存入 3 連續(xù)移動了兩次線性探測法84線性探測法的特點優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素。缺點：可能使第i個哈希地址的同義詞存入第i+1個地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，產(chǎn)生“聚集”現(xiàn)象，降低查找效率。解決方案：二次探測法85二次探測法關(guān)鍵碼集為 47，7，29，11，16，92，22，8，3，設(shè)： 哈希函數(shù)為Hash(key)=key mod 11 Hi=(Hash(key)di)

27、mod m其中：m為哈希表長度，m要求是某個4k+3的質(zhì)數(shù)； di為增量序列 12，-12，22，-22，q2 0 1 2 3 4 5 6 7 8 9 10829716924732211 Hash(3)=3，哈希地址沖突，由H1=(Hash(3)+12) mod 11=4，仍然沖突；H2=(Hash(3)-12) mod 11=2，找到空的哈希地址，存入。 86偽隨機探測法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m為哈希表長度 di 為隨機數(shù)87將所有哈希地址相同的記錄都鏈接在同一鏈表中。 2. 鏈地址法0123456140136198223116855ASL=(61+22+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為 H(key)=key MOD 788哈希表的查找給定k值計算H(k)此地