數(shù)據(jù)結(jié)構(gòu) 第8章 查找(作業(yè))

1、第8章 查找 第第8章章 查找查找 8.1 查找的基本概念查找的基本概念8.2 靜態(tài)查找表靜態(tài)查找表 8.3 動(dòng)態(tài)查找表動(dòng)態(tài)查找表 8.4 哈希表哈希表 第8章 查找 8.1 查找的基本概念查找的基本概念 關(guān)鍵字關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素。如果一個(gè)關(guān)鍵字可以唯一標(biāo)識(shí)列表中的一個(gè)數(shù)據(jù)元素，中的一個(gè)數(shù)據(jù)元素， 則稱其為則稱其為主關(guān)鍵字主關(guān)鍵字，否則為，否則為次關(guān)鍵字次關(guān)鍵字。當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)，當(dāng)數(shù)據(jù)元素僅有一個(gè)數(shù)據(jù)項(xiàng)時(shí)， 數(shù)據(jù)元素的值就是關(guān)鍵字。

2、數(shù)據(jù)元素的值就是關(guān)鍵字。 第8章 查找 查找查找：根據(jù)給定的關(guān)鍵字值，在查找表中確定一個(gè)其關(guān)鍵：根據(jù)給定的關(guān)鍵字值，在查找表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在查找表中的字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在查找表中的位置。若找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查位置。若找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時(shí)應(yīng)返回空地址及失敗信息，并可根據(jù)要求插找是失敗的，此時(shí)應(yīng)返回空地址及失敗信息，并可根據(jù)要求插入這個(gè)不存在的數(shù)據(jù)元素。入這個(gè)不存在的數(shù)據(jù)元素。 第8章 查找 8.2 靜態(tài)查找表靜態(tài)查找表 8.2.1 順序查找法順序查找法 順序查找

3、法的過程是：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)順序查找法的過程是：從表中最后一個(gè)記錄開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定行記錄的關(guān)鍵字和給定值的比較，若某個(gè)記錄的關(guān)鍵字和給定值比較相等，則查找成功，否則查找失敗。存儲(chǔ)結(jié)構(gòu)通常為順值比較相等，則查找成功，否則查找失敗。存儲(chǔ)結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。 第8章 查找 /靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)靜態(tài)查找表的順序存儲(chǔ)結(jié)構(gòu)typedef struct ElemType *elem; /數(shù)據(jù)元素存儲(chǔ)空間基址，建數(shù)據(jù)元素存儲(chǔ)空間基址，建 /表時(shí)按實(shí)際長(zhǎng)度分配，表時(shí)按實(shí)際長(zhǎng)度分配，0號(hào)單元留空號(hào)單元留空

4、 int length; /表長(zhǎng)度表長(zhǎng)度 SSTable; 第8章 查找 基于順序結(jié)構(gòu)的算法如下：基于順序結(jié)構(gòu)的算法如下： int Search_Seq(SSTable ST, KeyType key) / 在順序表在順序表ST中順序查找其關(guān)鍵字等于中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若的數(shù)據(jù)元素。若 找到，則函數(shù)值為該元素在表中的位置，否則為找到，則函數(shù)值為該元素在表中的位置，否則為0。算法。算法9.1 int i; ST.elem0.key=key; / 哨兵哨兵 for(i=ST.length;!EQ(ST.elemi.key,key);-i); / 從后往前找從后往前找 retur

5、n i; / 找不到時(shí)，找不到時(shí)，i為為0 其中其中ST.elem0稱為監(jiān)視哨，可以起到防止越界的作用。稱為監(jiān)視哨，可以起到防止越界的作用。第8章 查找 8.2.2 有序表的查找有序表的查找 折半查找法又稱二分法查找法，這種方法適用于有序表。折半查找法又稱二分法查找法，這種方法適用于有序表。其基本過程是其基本過程是：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個(gè)子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，前、后兩個(gè)子表，如果中間位置記錄

6、的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時(shí)查找不成功。存在為止，此時(shí)查找不成功。 第8章 查找 圖圖8.1 折半查找示意圖折半查找示意圖 第8章 查找 折半查找的算法如下：折半查找的算法如下： int Search_Bin(SSTable ST, KeyType key) / 在有序表在有序表ST中折半查找其關(guān)鍵字等于中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若的數(shù)據(jù)元素。若找到，則函數(shù)

7、值為該元素在表中的位置，否則為找到，則函數(shù)值為該元素在表中的位置，否則為0。算法。算法9.2 low=1 ; high=ST.length; / 置區(qū)間初值置區(qū)間初值 while(lowlchild=NULL； free(p)； (2) 若若p結(jié)點(diǎn)只有左子樹，或只有右子樹，則可將結(jié)點(diǎn)只有左子樹，或只有右子樹，則可將p的左的左子樹或右子樹直接改為其雙親結(jié)點(diǎn)子樹或右子樹直接改為其雙親結(jié)點(diǎn)f的左子樹，即：的左子樹，即：f-lchild=p-lchild（或（或f-lchild=p-rchild）；）； free(p)； (3) 若若p既有左子樹，既有左子樹， 又有右子樹，又有右子樹， 如圖如圖8.6

8、 (a) 所示。所示。 此時(shí)有兩種處理方法：此時(shí)有兩種處理方法： 第8章 查找 方法方法1: 首先找到首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，結(jié)點(diǎn)，如圖如圖8.6 (b) 所示，然后將所示，然后將p的左子樹改為的左子樹改為f的左子樹，而將的左子樹，而將p的右子樹改為的右子樹改為s的右子樹：的右子樹：f-lchild=p-lchild；s-rchild= p-rchild； free(p)；結(jié)果如圖；結(jié)果如圖8.6 (c) 所示。所示。 方法方法2 : 首先找到首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，結(jié)點(diǎn)， 如圖如圖8.6 (b) 所示

9、，然后用所示，然后用s結(jié)點(diǎn)的值替代結(jié)點(diǎn)的值替代p結(jié)點(diǎn)的值，再將結(jié)點(diǎn)的值，再將s結(jié)結(jié)點(diǎn)刪除，原點(diǎn)刪除，原s結(jié)點(diǎn)的左子樹改為結(jié)點(diǎn)的左子樹改為s的雙親結(jié)點(diǎn)的雙親結(jié)點(diǎn)q的右子樹：的右子樹：p-data=s-data；q-rchild= s-lchild；free(s)；結(jié)果如圖；結(jié)果如圖8.6 (d) 所示。所示。 第8章 查找 fPLPRPFfp(a) P的左右子樹均不空QLSLCFfp(d) 將原P結(jié)點(diǎn)的值改為S結(jié)點(diǎn)的值，刪除原S結(jié)點(diǎn) 并將原S的左子樹改為Q的右子樹QqCLSPRcSLPRCf(c) 將P的 左子樹改為F的左子樹，將P的右子樹改為S的右子樹SCLFcQLSLCFpQqCLPPRcS

10、s(b) S為P的直接前驅(qū) 圖圖8.6 二叉排序樹刪除示意二叉排序樹刪除示意 第8章 查找 3. 二叉排序樹的查找二叉排序樹的查找 因?yàn)槎媾判驑淇煽醋魇且粋€(gè)有序表，所以在二叉排因?yàn)槎媾判驑淇煽醋魇且粋€(gè)有序表，所以在二叉排序樹上進(jìn)行查找與折半查找類似，也是一個(gè)逐步縮小查找序樹上進(jìn)行查找與折半查找類似，也是一個(gè)逐步縮小查找范圍的過程。范圍的過程。 根據(jù)二叉排序樹的特點(diǎn)，首先將待查關(guān)鍵字根據(jù)二叉排序樹的特點(diǎn)，首先將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果：進(jìn)行比較，如果： (1） k=t， 則返回根結(jié)點(diǎn)地址；則返回根結(jié)點(diǎn)地址； (2） kt， 則進(jìn)一步查右子樹。則進(jìn)一步查右子樹。

11、 第8章 查找 8.3.2 平衡二叉樹平衡二叉樹 平衡二叉樹又稱為平衡二叉樹又稱為AVL樹樹。一棵平衡二叉樹或者是空樹，。一棵平衡二叉樹或者是空樹，或者具有下列性質(zhì)的二叉排序樹：或者具有下列性質(zhì)的二叉排序樹： 左子樹與右子樹的高度之左子樹與右子樹的高度之差的絕對(duì)值小于等于差的絕對(duì)值小于等于1； 左子樹和右子樹也是平衡二叉樹。左子樹和右子樹也是平衡二叉樹。 平衡因子平衡因子：結(jié)點(diǎn)的左子樹深度與右子樹深度之差。：結(jié)點(diǎn)的左子樹深度與右子樹深度之差。 顯然，對(duì)一棵平衡二叉排序樹而言，顯然，對(duì)一棵平衡二叉排序樹而言， 其所有結(jié)點(diǎn)的平衡因其所有結(jié)點(diǎn)的平衡因子只能是子只能是-1、 0，或，或1。當(dāng)我們?cè)谝粋€(gè)

12、平衡二叉排序樹上插入一。當(dāng)我們?cè)谝粋€(gè)平衡二叉排序樹上插入一個(gè)結(jié)點(diǎn)時(shí)，有可能導(dǎo)致失衡，即出現(xiàn)絕對(duì)值大于個(gè)結(jié)點(diǎn)時(shí)，有可能導(dǎo)致失衡，即出現(xiàn)絕對(duì)值大于1的平衡因子，的平衡因子，如如2、-2。圖。圖8.7中給出了一棵平衡二叉排序樹和一棵失去平衡中給出了一棵平衡二叉排序樹和一棵失去平衡的二叉排序樹。的二叉排序樹。 第8章 查找 圖圖8.7 平衡與不平衡的二叉排序樹平衡與不平衡的二叉排序樹 208070302560405011110006030255040120058100(a) 一棵平衡二叉排序樹(b) 一棵失去平衡的二叉排序樹第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.9（

13、a）所示。在）所示。在A的左子樹的左子樹的左子樹上插入的左子樹上插入15后，導(dǎo)致失衡，如圖后，導(dǎo)致失衡，如圖8.9（b）所示。為恢復(fù)）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可將平衡并保持二叉排序樹的特性，可將A改為改為B的右子，的右子，B原來原來的右子改為的右子改為A的左子，如圖的左子，如圖8.9（c）所示。這相當(dāng)于以）所示。這相當(dāng)于以B為軸，為軸，對(duì)對(duì)A做了一次順時(shí)針旋轉(zhuǎn)。做了一次順時(shí)針旋轉(zhuǎn)。 圖圖8.9 不平衡二叉樹的調(diào)整不平衡二叉樹的調(diào)整(1) 6015302025604010000AB(a) 一棵平衡二叉排序樹(b) 插入15后 失去平衡302025604020110AB030152

14、040250000BA01(c) 調(diào)整后的二叉排序樹第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.10（a）所示。在）所示。在A的右子樹的右子樹B的右子樹上插入的右子樹上插入70后，導(dǎo)致失衡，如圖后，導(dǎo)致失衡，如圖8.10（b）所示。為恢復(fù)）所示。為恢復(fù)平衡并保持二叉排序樹的特性，平衡并保持二叉排序樹的特性， 可將可將A改為改為B的左子，的左子，B原來的原來的左子改為左子改為A的右子，如圖的右子，如圖8.10（c）所示。這相當(dāng)于以）所示。這相當(dāng)于以B為軸，為軸， 對(duì)對(duì)A做了一次逆時(shí)針旋轉(zhuǎn)。做了一次逆時(shí)針旋轉(zhuǎn)。 圖圖8.10 不平衡二叉樹的調(diào)整不平衡二叉樹的調(diào)整(2)

15、 30607060302040251000AB(a) 一棵平衡二叉排序樹(b) 插入70后失去平衡204025200AB0202560400000BA0(c) 調(diào)整后的二叉排序樹70111300第8章 查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.11（a）所示。）所示。 在在A的的左子樹左子樹B的右子樹上插入的右子樹上插入45后，導(dǎo)致失衡，如圖后，導(dǎo)致失衡，如圖8.11（b）所示。為恢復(fù)平衡并保持二叉排序樹的特性，可所示。為恢復(fù)平衡并保持二叉排序樹的特性，可首先將首先將B改為改為C的左子，而的左子，而C原來的左子改為原來的左子改為B的右子；然后將的右子；然后將A改改為為C

16、的右子，的右子， C原來的右子改為原來的右子改為A的左子，的左子， 如圖如圖8.11（c）所示。所示。這相當(dāng)于對(duì)這相當(dāng)于對(duì)B做了一次逆時(shí)針旋轉(zhuǎn)，做了一次逆時(shí)針旋轉(zhuǎn)， 對(duì)對(duì)A做了一次做了一次順時(shí)針旋轉(zhuǎn)。順時(shí)針旋轉(zhuǎn)。 第8章 查找 圖圖8.11 不平衡二叉樹的調(diào)整不平衡二叉樹的調(diào)整(3) (a) 一棵平衡二叉排序樹507000103095204090801000B06085AC0000(b) 插入45后失去平衡507010103095204090802101B06085AC00000458595(c) 調(diào)整后的二叉排序樹45103090204080600001B05070C00001A00第8章

17、查找 u 已知一棵平衡二叉排序樹如圖已知一棵平衡二叉排序樹如圖8.12（a）所示。）所示。 在在A的右的右子樹的左子樹上插入子樹的左子樹上插入55后，導(dǎo)致失衡，如圖后，導(dǎo)致失衡，如圖8.12（b）所示。）所示。 為恢復(fù)平衡并保持二叉排序樹的特性，可首先將為恢復(fù)平衡并保持二叉排序樹的特性，可首先將B改為改為C的的右子，右子， 而而C原來的右子改為原來的右子改為B的左子；然后將的左子；然后將A改為改為C的左子，的左子，C原來的左子改為原來的左子改為A的右子，如圖的右子，如圖8.12（c）所示。這相當(dāng)于）所示。這相當(dāng)于對(duì)對(duì)B做了一次順時(shí)針旋轉(zhuǎn)，做了一次順時(shí)針旋轉(zhuǎn)， 對(duì)對(duì)A做了一次逆時(shí)針旋轉(zhuǎn)。做了一次

18、逆時(shí)針旋轉(zhuǎn)。 第8章 查找 圖8.12 不平衡二叉樹的調(diào)整(4) (c) 調(diào)整后的二叉排序樹(a) 一棵平衡二叉排序樹(b) 插入55后失去平衡859550709010208040100003060A00B0000C859550709010208040200003060A11B000C15508595551030902040806000A05070C0001B00100第8章 查找 1） LL型型 圖圖8.13 二叉排序樹的二叉排序樹的LL型平衡旋轉(zhuǎn)型平衡旋轉(zhuǎn) (a) 插入新結(jié)點(diǎn)S后 失去平衡(b) 調(diào)整后恢復(fù)平衡ABBLBRARS21BABLARBRS00第8章 查找 2） LR型型 圖8.

19、14 二叉排序樹的LR型平衡旋轉(zhuǎn) (a) 插入新結(jié)點(diǎn) S后失去平衡(b) 調(diào)整后恢復(fù)平衡ABCLARS2 1CCR1BLCACLARCRS0 1B0BL第8章 查找 圖8.15 二叉排序樹的RR型平衡旋轉(zhuǎn) (a) 插入新結(jié)點(diǎn) S后失去平衡(b) 調(diào)整后恢復(fù)平衡ABBRBLALS 2 1BABRALBLS003） RR型型第8章 查找 4） RL型型 圖8.16 二叉排序樹的RL型平衡旋轉(zhuǎn) (b) 調(diào)整后恢復(fù)平衡(a) 插入新結(jié)點(diǎn) S后失去平衡ABBRCRS 2 1CCL1ALCACRALCLS01B0BR第8章 查找 8.4 哈希表哈希表 哈希法又稱散列法、雜湊法或關(guān)鍵字地址計(jì)算法哈希法又稱散

20、列法、雜湊法或關(guān)鍵字地址計(jì)算法等，相應(yīng)等，相應(yīng)的表稱為哈希表。這種方法的基本思想：首先在元素的關(guān)鍵字的表稱為哈希表。這種方法的基本思想：首先在元素的關(guān)鍵字k和元素的存儲(chǔ)位置和元素的存儲(chǔ)位置p之間建立一個(gè)對(duì)應(yīng)關(guān)系之間建立一個(gè)對(duì)應(yīng)關(guān)系H，使得，使得p=H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為稱為哈希函數(shù)。創(chuàng)建哈希表時(shí)，把關(guān)鍵字為k的元素直接存的元素直接存入地址為入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為的單元；以后當(dāng)查找關(guān)鍵字為k的元素時(shí)，再利的元素時(shí)，再利用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置用哈希函數(shù)計(jì)算出該元素的存儲(chǔ)位置p=H(k)，從而達(dá)到按關(guān)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。鍵字

21、直接存取元素的目的。 第8章 查找 當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象當(dāng)關(guān)鍵字集合很大時(shí)，關(guān)鍵字值不同的元素可能會(huì)映象到哈希表的同一地址上，到哈希表的同一地址上，即即 k1k2，但，但 H（k1）=H（k2），），這種現(xiàn)象稱為沖突，此時(shí)稱這種現(xiàn)象稱為沖突，此時(shí)稱k1和和k2為同義詞。為同義詞。實(shí)際中，沖突實(shí)際中，沖突是不可避免的，是不可避免的， 只能通過改進(jìn)哈希函數(shù)的性能來減少?zèng)_突。只能通過改進(jìn)哈希函數(shù)的性能來減少?zèng)_突。 綜上所述，綜上所述， 哈希法主要包括以下兩方面的內(nèi)容：哈希法主要包括以下兩方面的內(nèi)容： (1） 如何構(gòu)造哈希函數(shù)；如何構(gòu)造哈希函數(shù)； (2） 如何處理沖突。如何

22、處理沖突。 第8章 查找 8.4.1 哈希函數(shù)的構(gòu)造方法哈希函數(shù)的構(gòu)造方法 1. 直接定址法直接定址法 哈希函數(shù)為關(guān)鍵字的線性函數(shù)，即哈希函數(shù)為關(guān)鍵字的線性函數(shù)，即H(key)=key或者或者H(key)=akey+b (a和和b為常數(shù)為常數(shù))。 此方法適合于此方法適合于地址集合的大小地址集合的大小=關(guān)鍵字集合的大小關(guān)鍵字集合的大小。 例：例：P253 解放后出生的人口調(diào)查表解放后出生的人口調(diào)查表第8章 查找 2. 數(shù)字分析法數(shù)字分析法 如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希如果事先知道關(guān)鍵字集合，并且每個(gè)關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干表的

23、地址碼位數(shù)多時(shí)，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。位，構(gòu)成哈希地址。第8章 查找 例如有例如有80個(gè)記錄，關(guān)鍵字為個(gè)記錄，關(guān)鍵字為8位十進(jìn)制整數(shù)位十進(jìn)制整數(shù)d1d2d3d7d8，如哈，如哈希表長(zhǎng)取希表長(zhǎng)取100，則哈希表的地址空間為：，則哈希表的地址空間為： 0099。假設(shè)經(jīng)過分。假設(shè)經(jīng)過分析，各關(guān)鍵字中析，各關(guān)鍵字中d4和和d7的取值分布較均勻，的取值分布較均勻， 則哈希函數(shù)為：則哈希函數(shù)為：H(key)=H(d1d2d3d7d8)=d4d7。例如，。例如， H(81346532)=43，H(81301367)=06。 8 1 3 4 6 5 3 28 1 3 7 2 2

24、4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 78 1 3 3 8 9 6 78 1 3 5 4 1 5 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5 數(shù)字分布近乎隨機(jī)數(shù)字分布近乎隨機(jī),可取其中任意兩位或取其中可取其中任意兩位或取其中兩位與另兩位的疊加求和后兩位與另兩位的疊加求和后舍去進(jìn)位作哈希地址舍去進(jìn)位作哈希地址第8章 查找 3. 平方取中法平方取中法 當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí)，當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時(shí)， 可以先求出關(guān)鍵可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。字的平方值，然

25、后按需要取平方值的中間幾位作為哈希地址。這這是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵是因?yàn)椋浩椒胶笾虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會(huì)以較高的概率產(chǎn)生不同的哈希地址。字會(huì)以較高的概率產(chǎn)生不同的哈希地址。 第8章 查找 例：我們把英文字母在字母表中的位置序號(hào)作為該英文字母的內(nèi)例：我們把英文字母在字母表中的位置序號(hào)作為該英文字母的內(nèi)部編碼。例部編碼。例K的內(nèi)部編碼為的內(nèi)部編碼為11，E的內(nèi)部編碼為的內(nèi)部編碼為05，Y的內(nèi)部編的內(nèi)部編碼為碼為25，A的內(nèi)部編碼為的內(nèi)部編碼為01, B的內(nèi)部編碼為的內(nèi)部編碼為02。 由此組成關(guān)鍵字由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為的內(nèi)部代

26、碼為11052501，同理我，同理我們可以得到關(guān)鍵字們可以得到關(guān)鍵字“KYAB”、“AKEY”、 “BKEY”的內(nèi)部編的內(nèi)部編碼。之后對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第碼。之后對(duì)關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第7到第到第9位作為該關(guān)鍵位作為該關(guān)鍵字哈希地址，字哈希地址， 如表如表8 - 1所示。所示。 第8章 查找 表表8-1 平方取中法求得的哈希地址平方取中法求得的哈希地址 關(guān)鍵字關(guān)鍵字 內(nèi)部編碼內(nèi)部編碼 內(nèi)部編碼的平方值內(nèi)部編碼的平方值 H(k)關(guān)鍵字的哈希地址關(guān)鍵字的哈希地址 KEYA 11052501 122157778355001 778 KYAB 11250102 126564795010

27、404 795AKEY 01110525 001233265775625 265BKEY 02110525 004454315775625 315第8章 查找 4. 折疊法折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分將關(guān)鍵字分割成位數(shù)相同的幾部分(最后一部分位數(shù)可不最后一部分位數(shù)可不同同)，然后取這幾部分的疊加和，然后取這幾部分的疊加和(舍去進(jìn)位舍去進(jìn)位)作為哈希地址。作為哈希地址。圖圖8.23 由疊加法求哈希地址由疊加法求哈希地址 2 30 34 71 20 2 0+)1 1 0 52 33 0 64 72 1 10 2 0+) 9 0 7(a) 移位疊加移位疊加 (b) 間界疊加間界疊加 第8章

28、 查找 5. 除留余數(shù)法除留余數(shù)法 假設(shè)哈希表長(zhǎng)為假設(shè)哈希表長(zhǎng)為m，p為小于等于為小于等于m的最大素?cái)?shù)，則哈希函的最大素?cái)?shù)，則哈希函數(shù)為：數(shù)為： H(key)= key % p， 其中其中%為模為模p取余運(yùn)算。取余運(yùn)算。 例如，已知待散列元素為（例如，已知待散列元素為（18，75，60，43，54，90，46），表長(zhǎng)），表長(zhǎng)m=10， p=7， 則有則有H(18)=18 % 7=4 H(75)=75 % 7=5 H(60)=60 % 7=4 H(43)=43 % 7=1 H(54)=54 % 7=5 H(90)=90 % 7=6 H(46)=46 % 7=4 第8章 查找 圖8.24 除留余數(shù)

29、法求哈希地址 此時(shí)沖突較多。此時(shí)沖突較多。 為減少?zèng)_突，為減少?zèng)_突， 可取較大的可取較大的m值和值和p值，值， 如如m=p=13， 結(jié)果如下：結(jié)果如下： H(18)=18 % 13=5 H(75)=75 % 13=10 H(60)=60 % 13=8 H(43)=43 % 13=4 H(54)=54 % 13=2 H(90)=90 % 13=12 H(46)=46 % 13=7 544318466075900 1 2 3 4 5 6 7 8 9 10 11 12 第8章 查找 6. 隨機(jī)數(shù)法隨機(jī)數(shù)法 采用一個(gè)隨機(jī)函數(shù)作哈希函數(shù)，即采用一個(gè)隨機(jī)函數(shù)作哈希函數(shù)，即H(key)=random(key

30、)。 在實(shí)際應(yīng)用中，在實(shí)際應(yīng)用中， 應(yīng)根據(jù)具體情況，采用不同的哈希函數(shù)。應(yīng)根據(jù)具體情況，采用不同的哈希函數(shù)。通常應(yīng)考慮以下五個(gè)因素：通常應(yīng)考慮以下五個(gè)因素： 計(jì)算哈希函數(shù)所需的時(shí)間計(jì)算哈希函數(shù)所需的時(shí)間 關(guān)鍵字的長(zhǎng)度。關(guān)鍵字的長(zhǎng)度。 哈希表的大小。哈希表的大小。 關(guān)鍵字的分布情況。關(guān)鍵字的分布情況。 記錄查找的頻率。記錄查找的頻率。 第8章 查找 8.4.2 處理沖突的方法處理沖突的方法 1. 開放定址法開放定址法 這種方法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字這種方法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的的哈希地址哈希地址p= H（key）出現(xiàn)沖突時(shí)，以）出現(xiàn)沖突時(shí)，以p為基礎(chǔ)，產(chǎn)生另一

31、個(gè)為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址哈希地址p1，如果，如果p1仍然沖突，再以仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個(gè)哈為基礎(chǔ)，產(chǎn)生另一個(gè)哈希地址希地址p2，直到找出一個(gè)不沖突的哈希地址，直到找出一個(gè)不沖突的哈希地址pi，將相應(yīng)，將相應(yīng)元素存入其中。這種方法有一個(gè)通用的再散列函數(shù)形式：元素存入其中。這種方法有一個(gè)通用的再散列函數(shù)形式： ,)%)(mdkeyHHiii=1， 2， ， n 第8章 查找 其中其中H(key)為哈希函數(shù)，為哈希函數(shù)，m為表長(zhǎng)，為表長(zhǎng)，di稱為增量序列。增量稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以

32、下三種：種： 線性探測(cè)再散列線性探測(cè)再散列 di=1，2，3， m-1 這種方法的特點(diǎn)這種方法的特點(diǎn)是：是： 沖突發(fā)生時(shí)，順序查看表中下一單元，沖突發(fā)生時(shí)，順序查看表中下一單元， 直到找出一個(gè)空單元或查遍全表。直到找出一個(gè)空單元或查遍全表。 二次探測(cè)再散列二次探測(cè)再散列 di= 12，-12， 22，-22，k2，-k2 (km/2) 這種方法的特點(diǎn)這種方法的特點(diǎn)是：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探是：沖突發(fā)生時(shí)，在表的左右進(jìn)行跳躍式探測(cè)，測(cè)， 比較靈活。比較靈活。 第8章 查找 偽隨機(jī)探測(cè)再散列偽隨機(jī)探測(cè)再散列 di=偽隨機(jī)數(shù)序列。偽隨機(jī)數(shù)序列。 具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如

33、具體實(shí)現(xiàn)時(shí)，應(yīng)建立一個(gè)偽隨機(jī)數(shù)發(fā)生器，（如i=(i+p) % m），）， 并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。并給定一個(gè)隨機(jī)數(shù)做起點(diǎn)。 第8章 查找 例，已知哈希表長(zhǎng)度例，已知哈希表長(zhǎng)度m=11，哈希函數(shù)為：，哈希函數(shù)為：H(key)= key % 11， 則則H(47)=3，H(26)=4，H(60)=5，假設(shè)下一個(gè)關(guān)鍵字為，假設(shè)下一個(gè)關(guān)鍵字為69，則，則H(69)=3，與，與47沖突。如果用線性探測(cè)再散列處理沖突，沖突。如果用線性探測(cè)再散列處理沖突，下一個(gè)哈希地址為下一個(gè)哈希地址為H1=（3+1）% 11=4， 仍然沖突，再找下一仍然沖突，再找下一個(gè)哈希地址為個(gè)哈希地址為H2=(3+2）% 11=5，

34、還是沖突，繼續(xù)找下一個(gè)哈，還是沖突，繼續(xù)找下一個(gè)哈希地址為希地址為H3=（3+3）% 11=6，此時(shí)不再?zèng)_突，將，此時(shí)不再?zèng)_突，將69填入填入6號(hào)單號(hào)單元，參見圖元，參見圖8.25(a)。 第8章 查找 如果用二次探測(cè)再散列處理沖突，下一個(gè)哈希地址為如果用二次探測(cè)再散列處理沖突，下一個(gè)哈希地址為H1=（3+12）% 11=4， 仍然沖突，再找下一個(gè)哈希地址為仍然沖突，再找下一個(gè)哈希地址為H2=（3-12）% 11=2，此時(shí)不再?zèng)_突，將，此時(shí)不再?zèng)_突，將69填入填入2號(hào)單元，參號(hào)單元，參見圖見圖8.25(b)。 如果用偽隨機(jī)探測(cè)再散列處理沖突，且偽隨機(jī)如果用偽隨機(jī)探測(cè)再散列處理沖突，且偽隨機(jī)數(shù)序列為：數(shù)序列為：2，5，9則下一個(gè)哈希地址為則下一個(gè)哈希地址為H1=（3+2）% 11=5，仍然沖突，再找下一個(gè)哈希地址為，仍然沖突，再找下一個(gè)哈希地址為H2=（3+5）% 11=8，此時(shí)