講義專業(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)常進(jìn)行的操作:1）查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；2）檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；3）在查找表中插入一個(gè)數(shù)據(jù)元素；4）從查找表中刪去某個(gè)數(shù)據(jù)元素。5僅作查詢和檢索操作的查找表。靜態(tài)查找表有時(shí)在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素。動(dòng)態(tài)查找表查找表可分為兩類:6是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)的

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

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

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的改進(jìn)：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; / 找不到時(shí)，i為0 / Search_Seq17關(guān)鍵字的平均比較次數(shù)，也稱平均搜索長度ASL(Average Search Length)n：記錄的個(gè)數(shù)pi：查找第i個(gè)記錄的概率 ( 通常認(rèn)為pi =1/n )ci：找到第i個(gè)記錄所需的比較次數(shù)（n-i+1）查找算法的評(píng)價(jià)指標(biāo)18空間復(fù)雜度：一個(gè)輔助空間。時(shí)間復(fù)雜度：1) 查找成功時(shí)的平均查

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

9、敗24int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置區(qū)間初值 while (low data.key進(jìn)行比較： 若key等于T-data.key，則查找成功，返回根結(jié)點(diǎn)地址； 若key小于T-data.key，則進(jìn)一步查找左子樹； 若key大于T-data.key，則進(jìn)一步查找右子樹?！舅惴ㄋ枷搿?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é)點(diǎn)關(guān)鍵字相等，查找成功，返回根節(jié)點(diǎn)指針T42為方便插入操作，需要在查找時(shí)增設(shè)指針1、增設(shè)指針 p 指向查找路徑上訪問的最后一個(gè)結(jié)點(diǎn)2、增設(shè)指針 f 指向當(dāng)前查找過程中樹T的雙親3、插入操作在查找不成功時(shí)進(jìn)行，所以在查找成功時(shí)返回true，查找不成功時(shí)返回false改寫的算法描述 P228 算法9.5（b）二叉排序樹的操作插入根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在查找不

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

12、ALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST 46s = (BiTree) malloc (sizeof (BiTNode); / 為新結(jié)點(diǎn)分配空間s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入 s 為新的根結(jié)點(diǎn)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é)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；（3）被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。4二叉排序樹的刪除算法可分三種情況討論： 和插入相反，刪除

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

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

16、衡樹57(a) 平衡樹 (b) 不平衡樹練習(xí)：判斷下列二叉樹是否AVL樹？00011-1-120001-1對于一棵有n個(gè)結(jié)點(diǎn)的AVL樹，其高度保持在O(log2n)數(shù)量級(jí)，ASL也保持在O(log2n)量級(jí)。58 構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5, 4, 2, 8, 65424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)59如果在一棵AVL樹中插入一個(gè)新結(jié)點(diǎn)，就有可能造成失衡，此時(shí)必須重新調(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é)點(diǎn)，使A的平衡因子從1增加至2，需要進(jìn)行一次順時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC若在A的右子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時(shí)針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABC1）LL平衡旋轉(zhuǎn)：61若在A的右子樹的左子樹上插入結(jié)點(diǎn)，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時(shí)針旋轉(zhuǎn)，再逆時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABCABCABC若在A的左子樹的右子樹上插入結(jié)點(diǎn)，使A的平衡因子從1增加至2，需要先進(jìn)行逆時(shí)針旋轉(zhuǎn)，再順時(shí)針旋轉(zhuǎn)。(以插入的結(jié)點(diǎn)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 在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個(gè)數(shù)不超過平衡 樹的深度。平衡樹的查找性能分析： 問：含 n 個(gè)關(guān)鍵字的二叉平衡樹可能達(dá)到的最大深度是多少？64n = 0空樹最大深度為 0n = 1最大深度為 1n = 2最大深度為 2n = 4最大深度為 3n = 7最大深度為 4

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

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

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

22、字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功。哈希函數(shù)(雜湊函數(shù))：哈希方法中使用的轉(zhuǎn)換函數(shù)有關(guān)術(shù)語73沖 突：不同的關(guān)鍵碼映射到同一個(gè)哈希地址哈希表(雜湊表)：按上述思想構(gòu)造的表有關(guān)術(shù)語14119內(nèi)容地址3925242314119232539同義詞：具有相同函數(shù)值的兩個(gè)關(guān)鍵字key1key2，但H(key1)=H(key2)74（14，23，39，9，25，11）哈希函數(shù)：H(k)=k mod 72539239146個(gè)元素用7個(gè)地址應(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沖突是不可能避免的如何減少?zèng)_突構(gòu)造好的哈希函數(shù)制定一個(gè)好的解決沖突方案76哈希函數(shù)的構(gòu)造方法根據(jù)元素集合的特性構(gòu)造地址空間盡量小均勻直接定址法 數(shù)字分析法平方取中法折疊法除留余數(shù)法隨機(jī)數(shù)法 77Hash(key) = akey + b (a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突。缺點(diǎ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 的素?cái)?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三、處理沖突的方法 “處理沖突” 的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。1.

25、 開放定址法2. 鏈地址法81基本思想：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。 1.開放定址法（開地址法）線性探測法二次探測法偽隨機(jī)探測法82Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m為哈希表長度 di 為增量序列 1，2，m-1，且di=i一旦沖突，就找下一個(gè)空地址存入線性探測法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ù)移動(dòng)了兩次線性探測法84線性探測法的特點(diǎn)優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素。缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，產(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要求是某個(gè)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偽隨機(jī)探測法Hi=(Hash(key)+di) mod m ( 1i m ) 其中：m為哈希表長度 di 為隨機(jī)數(shù)87將所有哈希地址相同的記錄都鏈接在同一鏈表中。 2. 鏈地址法0123456140136198223116855ASL=(61+22+3)/9=13/9例如:同前例的關(guān)鍵字，哈希函數(shù)為 H(key)=key MOD 788哈希表的查找給定k值計(jì)算H(k)此地