數(shù)據(jù)結(jié)構(gòu)-用面向?qū)ο笳Z(yǔ)言描述-殷人昆-第七章

1、第七章第七章 搜索結(jié)構(gòu)搜索結(jié)構(gòu)楊同峰楊同峰1第七章 搜索結(jié)構(gòu)2搜索搜索(Search)(Search)的概念的概念靜態(tài)搜索表n所謂所謂搜索搜索，就是在數(shù)據(jù)集合中尋找滿足某種，就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對(duì)象。條件的數(shù)據(jù)對(duì)象。n搜索的結(jié)果通常有兩種可能：搜索的結(jié)果通常有兩種可能：搜索成功搜索成功，即找到滿足條件的數(shù)據(jù)對(duì)象。，即找到滿足條件的數(shù)據(jù)對(duì)象。這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中這時(shí)，作為結(jié)果，可報(bào)告該對(duì)象在結(jié)構(gòu)中 的位置的位置, 還可給出該對(duì)象中的具體信息。還可給出該對(duì)象中的具體信息。搜索不成功搜索不成功，或搜索失敗。作為結(jié)果，應(yīng)，或搜索失敗。作為結(jié)果，應(yīng)報(bào)告一些信息報(bào)告一些信

2、息, 如失敗標(biāo)志、位置等。如失敗標(biāo)志、位置等。3p通常稱用于搜索的數(shù)據(jù)集合為搜索結(jié)構(gòu)，它是由同一數(shù)據(jù)類型的對(duì)象(或記錄)組成。p在每個(gè)對(duì)象中有若干屬性，其中有一個(gè)屬性，其值可唯一地標(biāo)識(shí)這個(gè)對(duì)象。稱為關(guān)鍵碼。使用基于關(guān)鍵碼的搜索，搜索結(jié)果應(yīng)是唯一的。但在實(shí)際應(yīng)用時(shí)，搜索條件是多方面的，可以使用基于屬性的搜索方法，但搜索結(jié)果可能不唯一。p實(shí)施搜索時(shí)有兩種不同的環(huán)境。u靜態(tài)環(huán)境，搜索結(jié)構(gòu)在插入和刪除等操作的前后不發(fā)生改變。 靜態(tài)搜索表 4u動(dòng)態(tài)環(huán)境，為保持較高的搜索效率, 搜索結(jié)構(gòu)在執(zhí)行插入和刪除等操作的前后將自動(dòng)進(jìn)行調(diào)整，結(jié)構(gòu)可能發(fā)生變化。 動(dòng)態(tài)搜索表p在靜態(tài)搜索表中，數(shù)據(jù)元素存放于數(shù)組中，利用數(shù)

3、組元素的下標(biāo)作為數(shù)據(jù)元素的存放地址。搜索算法根據(jù)給定值 k，在數(shù)組中進(jìn)行搜索。直到找到 k 在數(shù)組中的存放位置或可確定在數(shù)組中找不到 k 為止。 靜態(tài)搜索表5p順序搜索主要用于在線性表中搜索。p設(shè)若表中有 CurrentSize 個(gè)元素，則順序搜索從表的先端開始，順序用各元素的關(guān)鍵碼與給定值 x 進(jìn)行比較p若找到與其值相等的元素，則搜索成功，給出該元素在表中的位置。p若整個(gè)表都已檢測(cè)完仍未找到關(guān)鍵碼與 x 相等的元素，則搜索失敗。給出失敗信息。順序搜索（Sequential Search） 6p順序搜索的平均搜索長(zhǎng)度p在等概率情形，pi = 1/n, i = 1, 2, , n。搜索成功的平均

4、搜索長(zhǎng)度為：p在搜索不成功情形，ASLunsucc = n+1。.)()(1- nisuccnnnninASL021211117* *常用的查找算法常用的查找算法9.2 9.2 順序查找順序查找struct Recordstruct Record int key; int key; ; ;Record rn;Record rn;無(wú)監(jiān)視哨的順序查找無(wú)監(jiān)視哨的順序查找: int SeqSearch(Record r, int n, int k) int i=0;while (in&ri.key!=k) i+;if (in) return i;else return -1;有監(jiān)視哨的順序查找

5、有監(jiān)視哨的順序查找pint SeqSearch2(Record r, int n, int k)ppint i=0;prn.key=k;pwhile (ri.key!=k) i+;pif (in) return i;pelse return -1;p 順序查找的平均查找長(zhǎng)度為：順序查找的平均查找長(zhǎng)度為：順序查找的特點(diǎn)：算法簡(jiǎn)單，但查找效率低。順序查找的特點(diǎn)：算法簡(jiǎn)單，但查找效率低。2/ ) 1()/(11nnicpASLniniiisq 二分查找又稱為折半查找。二分查找又稱為折半查找。 二分查找要求順序表是有序的。二分查找要求順序表是有序的。 與中間位置比較，若相等，與中間位置比較，若相等，

6、則找到！則找到！ 如果小，如果小，則在前半段查找，則在前半段查找， 否則在后邊段查找。否則在后邊段查找。例例: : 05 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 92 05 13 19 21 3705 13 19 21 37 56 64 75 56 64 75 80 88 9280 88 9205 13 19 05 13 19 21 3721 37 56 64 75 56 64 75 80 88 9280 88 92查找查找K=21K=21的過程（查找成功）的過程（查找成功）05 13 19 21 37 56 64

7、75 05 13 19 21 37 56 64 75 80 88 9280 88 9205 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 9205 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 9280 88 92查找查找K=85K=85的過程（查找失?。┑倪^程（查找失敗）05 13 19 21 37 56 64 75 05 13 19 21 37 56 64 75 80 88 92 80 88 92 二分查找算法二分查找算法(非遞歸非遞歸)二分查找算法二分查找算法(

8、遞歸遞歸) 如果把當(dāng)前查找位置上的結(jié)點(diǎn)作為根，左子如果把當(dāng)前查找位置上的結(jié)點(diǎn)作為根，左子表和右子表的結(jié)點(diǎn)分別作為根的左子樹和右子樹，由表和右子表的結(jié)點(diǎn)分別作為根的左子樹和右子樹，由此得到的二叉樹稱為描述二分查找的判定樹。此得到的二叉樹稱為描述二分查找的判定樹。 借助于判定樹很容易求得二分查找的平均查借助于判定樹很容易求得二分查找的平均查找長(zhǎng)度。查找數(shù)據(jù)的比較次數(shù)最多為該判定樹的樹高找長(zhǎng)度。查找數(shù)據(jù)的比較次數(shù)最多為該判定樹的樹高. . 二分查找的算法復(fù)雜度為：二分查找的算法復(fù)雜度為：O(log n)O(log n)即在最壞情況下，二分查找方法查找成功的比較即在最壞情況下，二分查找方法查找成功的比

9、較次數(shù)不超過判定樹的高度。次數(shù)不超過判定樹的高度。 雖然二分查找的效率較高，但它要求被雖然二分查找的效率較高，但它要求被查找序列查找序列事先按關(guān)鍵字排好序事先按關(guān)鍵字排好序，而排序本身是一，而排序本身是一種很費(fèi)時(shí)的運(yùn)算；另外，二分查找只適用于順序種很費(fèi)時(shí)的運(yùn)算；另外，二分查找只適用于順序存儲(chǔ)結(jié)構(gòu)，因此，二分查找特別適用于那種一經(jīng)存儲(chǔ)結(jié)構(gòu)，因此，二分查找特別適用于那種一經(jīng)建立就很少改動(dòng)、而又需要經(jīng)常查找的線性表。建立就很少改動(dòng)、而又需要經(jīng)常查找的線性表。 二叉排序樹的查找二叉排序樹的查找二叉排序樹的概念二叉排序樹的概念二叉排序樹的建立二叉排序樹的建立二叉排序樹的插入二叉排序樹的插入二叉排序樹的刪

10、除二叉排序樹的刪除二叉排序樹的查找二叉排序樹的查找查找性能分析查找性能分析1. 1. 二叉排序樹的概念二叉排序樹的概念 也稱為二叉查找樹也稱為二叉查找樹. .(1)(1)左子樹的所有結(jié)點(diǎn)的值左子樹的所有結(jié)點(diǎn)的值 根結(jié)點(diǎn)的值根結(jié)點(diǎn)的值(3)(3)左子樹、右子樹都是二叉排序樹。左子樹、右子樹都是二叉排序樹。舉例：舉例：性質(zhì)：性質(zhì)：中序遍歷二叉排序樹得到的是有序序列。中序遍歷二叉排序樹得到的是有序序列。pclass BiSortTreeppBiNode *root;pvoid Insert(BiNode *&ptr, int k); /供插入函數(shù)調(diào)用供插入函數(shù)調(diào)用pBiNode* Searc

11、h(BiNode *ptr, int k); /供查找函數(shù)調(diào)用供查找函數(shù)調(diào)用pvoid Delete (BiNode *&ptr, int k); /供刪除函數(shù)調(diào)用供刪除函數(shù)調(diào)用p void Free(BiNode *ptr); /供析構(gòu)函數(shù)調(diào)用供析構(gòu)函數(shù)調(diào)用ppublic:pBiSortTree(int a , int n); /建立二叉排序樹建立二叉排序樹pBiSortTree(); /析構(gòu)函數(shù)析構(gòu)函數(shù)pvoid Insert(int k); /插入插入pbool Search(int k); /查找查找pvoid Delete (int k); /刪除刪除p;2 2二叉排序樹的插

12、入和建立二叉排序樹的插入和建立在一棵二叉排序樹中插入值為在一棵二叉排序樹中插入值為k k的結(jié)點(diǎn)，步驟如的結(jié)點(diǎn)，步驟如下：下： 若二叉排序樹為空，則生成值為若二叉排序樹為空，則生成值為k k的新結(jié)點(diǎn)的新結(jié)點(diǎn)s s，同時(shí)將新結(jié)點(diǎn)同時(shí)將新結(jié)點(diǎn)s s作為根結(jié)點(diǎn)插入。作為根結(jié)點(diǎn)插入。 若若k k小于根結(jié)點(diǎn)的值，則在根的左子樹中插小于根結(jié)點(diǎn)的值，則在根的左子樹中插入值為入值為k k的結(jié)點(diǎn)。的結(jié)點(diǎn)。 若若k k大于根結(jié)點(diǎn)的值，則在根的右子樹中插大于根結(jié)點(diǎn)的值，則在根的右子樹中插入值為入值為k k的結(jié)點(diǎn)。的結(jié)點(diǎn)。 若若k k等于根結(jié)點(diǎn)的值，表明二叉排序樹中已等于根結(jié)點(diǎn)的值，表明二叉排序樹中已有此關(guān)鍵字，則無(wú)須

13、插入。有此關(guān)鍵字，則無(wú)須插入。 二叉排序樹的建立算法二叉排序樹的建立算法 BiSortTree:BiSortTree(int a , int n) BiSortTree:BiSortTree(int a , int n) root = NULL;root = NULL; for (int i = 0; i n; i+) for (int i = 0; i key) return ptr; if (k=ptr-key) return ptr; else if (kkey) ptr=ptr-lchild;else if (kkey) ptr=ptr-lchild; else ptr=ptr-rch

14、ild; else ptr=ptr-rchild; return NULL;return NULL; bool BiSortTree:Search2(int k) bool BiSortTree:Search2(int k) /查找查找 return Search2(root,k)!=NULL; return Search2(root,k)!=NULL; p分三種情況分三種情況 :（1）刪除葉子結(jié)點(diǎn)）刪除葉子結(jié)點(diǎn)p（2）刪除單支結(jié)點(diǎn)）刪除單支結(jié)點(diǎn)p（3）刪除雙支結(jié)點(diǎn)）刪除雙支結(jié)點(diǎn)遞歸刪除算法的步驟如下：遞歸刪除算法的步驟如下：p 若二叉排序樹為空，則表明不存在刪除的結(jié)點(diǎn)，不若二叉排序樹為空，則

15、表明不存在刪除的結(jié)點(diǎn)，不進(jìn)行刪除操作。進(jìn)行刪除操作。p 若給定值若給定值k小于根結(jié)點(diǎn)的值，則繼續(xù)在根的左子樹小于根結(jié)點(diǎn)的值，則繼續(xù)在根的左子樹中刪除。中刪除。p 若給定值若給定值k大于根結(jié)點(diǎn)的值，則繼續(xù)在根的右子樹大于根結(jié)點(diǎn)的值，則繼續(xù)在根的右子樹中刪除。中刪除。p 若給定值若給定值k等于根結(jié)點(diǎn)的值，則根結(jié)點(diǎn)即為要?jiǎng)h除等于根結(jié)點(diǎn)的值，則根結(jié)點(diǎn)即為要?jiǎng)h除的結(jié)點(diǎn)，此時(shí)需要根據(jù)上述分析的三種結(jié)點(diǎn)情況：葉的結(jié)點(diǎn)，此時(shí)需要根據(jù)上述分析的三種結(jié)點(diǎn)情況：葉子結(jié)點(diǎn)、單支結(jié)點(diǎn)或雙支結(jié)點(diǎn)，執(zhí)行相應(yīng)的刪除操作。子結(jié)點(diǎn)、單支結(jié)點(diǎn)或雙支結(jié)點(diǎn)，執(zhí)行相應(yīng)的刪除操作。7.3 7.3 平衡二叉樹平衡二叉樹p問題的提出問題的提出

16、p什么是平衡二叉樹什么是平衡二叉樹p平衡二叉樹的建立平衡二叉樹的建立 左子樹與右子樹高度之差稱為結(jié)點(diǎn)的左子樹與右子樹高度之差稱為結(jié)點(diǎn)的。由平衡二叉樹定義可知，平衡二由平衡二叉樹定義可知，平衡二叉樹所有結(jié)點(diǎn)的平衡因子只能取叉樹所有結(jié)點(diǎn)的平衡因子只能取 1 1，0 0，1 1三個(gè)值之一。三個(gè)值之一。p如何使建立的一棵二叉排序樹是平衡的呢？如何使建立的一棵二叉排序樹是平衡的呢？p這就要求當(dāng)新結(jié)點(diǎn)插入二叉排序樹時(shí)，必須保持所有結(jié)點(diǎn)這就要求當(dāng)新結(jié)點(diǎn)插入二叉排序樹時(shí)，必須保持所有結(jié)點(diǎn)的平衡因子滿足平衡二叉樹的要求，一旦不滿足要求，就的平衡因子滿足平衡二叉樹的要求，一旦不滿足要求，就必須進(jìn)行必須進(jìn)行調(diào)整調(diào)整

17、。關(guān)鍵！關(guān)鍵！p從插入位置沿著通向根的路徑回溯，逐一檢查每個(gè)節(jié)點(diǎn)的從插入位置沿著通向根的路徑回溯，逐一檢查每個(gè)節(jié)點(diǎn)的平衡因子，當(dāng)發(fā)現(xiàn)不平衡時(shí)，這個(gè)不平衡節(jié)點(diǎn)和向下的兩平衡因子，當(dāng)發(fā)現(xiàn)不平衡時(shí)，這個(gè)不平衡節(jié)點(diǎn)和向下的兩個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn) 構(gòu)成關(guān)鍵的三個(gè)節(jié)點(diǎn)。構(gòu)成關(guān)鍵的三個(gè)節(jié)點(diǎn)。p這三個(gè)節(jié)點(diǎn)的形狀決定了需要采取的操作。這三個(gè)節(jié)點(diǎn)的形狀決定了需要采取的操作。38調(diào)整有調(diào)整有4 4種情況種情況p（1）LL型型p（2）RR型型p（3）LR型型p（4）RL型型9.7 B9.7 B樹與樹與B+B+樹樹p什么是什么是B B樹樹? ? pB B樹的查找樹的查找p什么是什么是B+B+樹樹? ? pB+B+樹的查找樹的查

18、找9.8 Hash9.8 Hash查找查找1. 1. 基本概念基本概念 Hash, Hash, 哈希哈希, ,也稱為也稱為散列散列. . HashHash是一種重要的存儲(chǔ)方法，也是一種常是一種重要的存儲(chǔ)方法，也是一種常見的查找方法。見的查找方法。 它的基本思想是：以數(shù)據(jù)元素的關(guān)鍵字它的基本思想是：以數(shù)據(jù)元素的關(guān)鍵字K K為為自變量，通過一個(gè)確定的函數(shù)關(guān)系，計(jì)算出對(duì)應(yīng)自變量，通過一個(gè)確定的函數(shù)關(guān)系，計(jì)算出對(duì)應(yīng)的函數(shù)值的函數(shù)值f(K)f(K)，把這個(gè)值作為數(shù)據(jù)元素的存儲(chǔ)地，把這個(gè)值作為數(shù)據(jù)元素的存儲(chǔ)地址。查找時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置。址。查找時(shí)也是根據(jù)這個(gè)函數(shù)計(jì)算其存儲(chǔ)位置。 【例】【例】

19、 假設(shè)一組記錄的關(guān)鍵字分別為假設(shè)一組記錄的關(guān)鍵字分別為18，27，1，20，22，6，10，13，41，15，25。選取關(guān)鍵字與。選取關(guān)鍵字與記錄位置間的函數(shù)為記錄位置間的函數(shù)為f(key)=key %11。pHash函數(shù)函數(shù)-關(guān)鍵字與記錄位置間的函數(shù)關(guān)鍵字與記錄位置間的函數(shù).pHash地址地址-據(jù)據(jù)HashHash函數(shù)計(jì)算出的存儲(chǔ)位置函數(shù)計(jì)算出的存儲(chǔ)位置. .pHash表表-存儲(chǔ)記錄的查找表存儲(chǔ)記錄的查找表, ,該表中根據(jù)該表中根據(jù)HashHash函數(shù)計(jì)算出函數(shù)計(jì)算出的存儲(chǔ)位置的存儲(chǔ)位置. .p基于基于Hash表的查找稱為表的查找稱為Hash查找。查找。在建立在建立HashHash表時(shí)，若表

20、時(shí)，若HashHash函數(shù)是一個(gè)一對(duì)一的函數(shù)，函數(shù)是一個(gè)一對(duì)一的函數(shù)， 則在查找時(shí)，只需根據(jù)散列函數(shù)對(duì)給定值進(jìn)行某種運(yùn)則在查找時(shí)，只需根據(jù)散列函數(shù)對(duì)給定值進(jìn)行某種運(yùn) 算，即可得到待查數(shù)據(jù)的存儲(chǔ)位置。算，即可得到待查數(shù)據(jù)的存儲(chǔ)位置。在一般情況下，在一般情況下， HashHash表的空間必須比數(shù)據(jù)的集合大，表的空間必須比數(shù)據(jù)的集合大， 此時(shí)雖然浪費(fèi)了一定的空間，但換取的是查找效率。此時(shí)雖然浪費(fèi)了一定的空間，但換取的是查找效率。 設(shè)散列表的空間大小為設(shè)散列表的空間大小為m m，填入表中的數(shù)據(jù)個(gè)數(shù)為，填入表中的數(shù)據(jù)個(gè)數(shù)為n n，則稱則稱=n/m=n/m為散列表的為散列表的裝填因子裝填因子。HashHa

21、sh函數(shù)的選取原則是：運(yùn)算盡可能簡(jiǎn)單；函數(shù)的值函數(shù)的選取原則是：運(yùn)算盡可能簡(jiǎn)單；函數(shù)的值 域必須在表長(zhǎng)的范圍內(nèi)；盡可能使得關(guān)鍵字不同時(shí)，域必須在表長(zhǎng)的范圍內(nèi)；盡可能使得關(guān)鍵字不同時(shí)， 其散列函數(shù)值亦不相同。其散列函數(shù)值亦不相同。若某個(gè)若某個(gè)HashHash函數(shù)對(duì)于不相等的關(guān)鍵字計(jì)算出了相同的函數(shù)對(duì)于不相等的關(guān)鍵字計(jì)算出了相同的 HashHash地址，則稱該現(xiàn)象為地址，則稱該現(xiàn)象為hashhash沖突沖突，發(fā)生沖突的兩個(gè)，發(fā)生沖突的兩個(gè)關(guān)鍵字該關(guān)鍵字該HashHash函數(shù)的函數(shù)的同義詞同義詞。在實(shí)際應(yīng)用中，不產(chǎn)生沖。在實(shí)際應(yīng)用中，不產(chǎn)生沖突的突的HashHash函數(shù)極少存在。函數(shù)極少存在。直接定

22、址法直接定址法除留余數(shù)法除留余數(shù)法數(shù)字分析法數(shù)字分析法平方取中法平方取中法折疊法折疊法直接定址法直接定址法 Hash Hash函數(shù)是關(guān)鍵字的線性函數(shù)。即：函數(shù)是關(guān)鍵字的線性函數(shù)。即： H(key) = aH(key) = akeykeyb例例1 1：已知一個(gè)含有：已知一個(gè)含有7070個(gè)數(shù)據(jù)的線性表，其關(guān)個(gè)數(shù)據(jù)的線性表，其關(guān)鍵字是兩位十進(jìn)制數(shù)字組成，則可將線性表存鍵字是兩位十進(jìn)制數(shù)字組成，則可將線性表存儲(chǔ)在如下說明的散列表中：儲(chǔ)在如下說明的散列表中： int HT100;int HT100;其中，其中，HTiHTi存放關(guān)鍵字為存放關(guān)鍵字為i i的結(jié)點(diǎn)，即散列函的結(jié)點(diǎn)，即散列函數(shù)為：數(shù)為： H(k

23、ey)=keyH(key)=key除留余數(shù)法除留余數(shù)法 選擇一個(gè)適當(dāng)?shù)恼麛?shù)選擇一個(gè)適當(dāng)?shù)恼麛?shù)P，用，用P去除關(guān)鍵字，取去除關(guān)鍵字，取所得得余數(shù)作為散列地址，即：所得得余數(shù)作為散列地址，即： H(key) = key%P這個(gè)方法的關(guān)鍵是選取適當(dāng)?shù)倪@個(gè)方法的關(guān)鍵是選取適當(dāng)?shù)腜。選擇。選擇P最好不要是最好不要是偶數(shù)，也不要是基數(shù)的冪。一般地選偶數(shù)，也不要是基數(shù)的冪。一般地選P為小于或等于為小于或等于散列表長(zhǎng)度散列表長(zhǎng)度m的某個(gè)最大的某個(gè)最大質(zhì)數(shù)質(zhì)數(shù)比較好。例如：比較好。例如： m = 8，16，32，64，128，256，512，1024 P = 7，13，31，61，127，251，503，1

24、019除余法的地址計(jì)算公式簡(jiǎn)單，而且在很多情況下效除余法的地址計(jì)算公式簡(jiǎn)單，而且在很多情況下效果較好，因此是一種常用的構(gòu)造散列函數(shù)的方法。果較好，因此是一種常用的構(gòu)造散列函數(shù)的方法。數(shù)字分析法數(shù)字分析法 若事先知道關(guān)鍵字集合，且關(guān)鍵字的位數(shù)比散列表若事先知道關(guān)鍵字集合，且關(guān)鍵字的位數(shù)比散列表的地址位數(shù)多，則可選取數(shù)字分布比較均勻的若干位作的地址位數(shù)多，則可選取數(shù)字分布比較均勻的若干位作為散列地址。例如，有一組為散列地址。例如，有一組8位數(shù)字組成的關(guān)鍵字：位數(shù)字組成的關(guān)鍵字： 經(jīng)過分析可知，前三位和第五位分布不均勻，所以，經(jīng)過分析可知，前三位和第五位分布不均勻，所以，若表長(zhǎng)為若表長(zhǎng)為1000，則

25、可取，則可取4、6、7位的數(shù)字作為散列地址，位的數(shù)字作為散列地址，若表長(zhǎng)為若表長(zhǎng)為100，則可取，則可取4、6與與7、8位之和并舍去進(jìn)位作位之和并舍去進(jìn)位作為散列地址。為散列地址。平方取中法平方取中法 通常，要預(yù)先估計(jì)關(guān)鍵字的數(shù)字分布并不容易，通常，要預(yù)先估計(jì)關(guān)鍵字的數(shù)字分布并不容易，要找數(shù)字均勻分布的位數(shù)更難。此時(shí)可采用平方取要找數(shù)字均勻分布的位數(shù)更難。此時(shí)可采用平方取中法：即先通過求關(guān)鍵字的平方來擴(kuò)大差別，再取中法：即先通過求關(guān)鍵字的平方來擴(kuò)大差別，再取其中的幾位或其組合作為散列地址。其中的幾位或其組合作為散列地址。 例如：一組關(guān)鍵字：例如：一組關(guān)鍵字： (0100，0110，1010，1

26、001，0111)平方結(jié)果為：平方結(jié)果為：(0010000，0012100，1020100，1002001，0012321)若表長(zhǎng)為若表長(zhǎng)為3位，則可取中間三位作為散列地址集：位，則可取中間三位作為散列地址集： (100，121，201，020，123)折疊法折疊法 若關(guān)鍵字位數(shù)較多，可將關(guān)鍵字分割成位數(shù)相若關(guān)鍵字位數(shù)較多，可將關(guān)鍵字分割成位數(shù)相同的幾段（最后一段的位數(shù)可以不同），段的長(zhǎng)度同的幾段（最后一段的位數(shù)可以不同），段的長(zhǎng)度取決于散列表的地址位數(shù)，然后將各段的迭加和取決于散列表的地址位數(shù)，然后將各段的迭加和（舍去進(jìn)位）作為散列地址。（舍去進(jìn)位）作為散列地址。 例如，對(duì)于例如，對(duì)于key

27、=58242324169 582 582 423 423 241 241 + 69 + 69 1315 1315H(key)=315H(key)=315移位迭加移位迭加 582 582 324 324 241 241 + 96 + 96 1243 1243H(key)=243H(key)=243邊界迭加邊界迭加3. 3. 處理處理hashhash沖突的方法沖突的方法(1)(1)開放地址法開放地址法 線性探察法線性探察法 二次探察法二次探察法 雙散列函數(shù)法雙散列函數(shù)法(2)(2)鏈地址法鏈地址法 用開放地址法解決沖突的基本思想是：用開放地址法解決沖突的基本思想是：當(dāng)沖突發(fā)生時(shí)，使用某種方法在散列

28、表中當(dāng)沖突發(fā)生時(shí)，使用某種方法在散列表中形成一個(gè)探查序列，按此序列逐個(gè)單元的形成一個(gè)探查序列，按此序列逐個(gè)單元的查找，直到找到一個(gè)指定的關(guān)鍵字或碰到查找，直到找到一個(gè)指定的關(guān)鍵字或碰到一個(gè)開放的地址（單元為空）為止。插入一個(gè)開放的地址（單元為空）為止。插入時(shí)碰到開放的地址，即可將待插入新結(jié)點(diǎn)時(shí)碰到開放的地址，即可將待插入新結(jié)點(diǎn)放到該地址單元中；查找時(shí)碰到開放的地放到該地址單元中；查找時(shí)碰到開放的地址，則說明表中沒有待查的關(guān)鍵字。址，則說明表中沒有待查的關(guān)鍵字。 形成探測(cè)的方法不同，所得到的解決形成探測(cè)的方法不同，所得到的解決沖突的方法也不同。沖突的方法也不同。線性探測(cè)法線性探測(cè)法 將散列表看成

29、是一個(gè)環(huán)形表。若地址為將散列表看成是一個(gè)環(huán)形表。若地址為d（即（即H(key)=d）的單元發(fā)生沖突，則依次探查下述地址）的單元發(fā)生沖突，則依次探查下述地址單元：?jiǎn)卧?d+1，d+2，.，m-1，0，1，.，d-1直到找到一個(gè)空單元或查找到關(guān)鍵字為直到找到一個(gè)空單元或查找到關(guān)鍵字為key的結(jié)點(diǎn)為的結(jié)點(diǎn)為止。當(dāng)然，若沿著該探查序列查找一遍之后，又回止。當(dāng)然，若沿著該探查序列查找一遍之后，又回到了地址到了地址d，則無(wú)論是做插入操作還是做查找操作，則無(wú)論是做插入操作還是做查找操作，都意味著失敗。都意味著失敗。 例例: 有關(guān)鍵字序列為有關(guān)鍵字序列為3636，7 7，4040，1111，1616，8181，2222，8 8，1414，HashHash表表長(zhǎng)為表表長(zhǎng)為1111，Hash(key)=key % 11Hash(key)=key % 11，用線性探測(cè)法處理沖突，建立的用線性探測(cè)法處理沖突，建立的HashHash表。表。 板書板書二次探查法二次探查法 二次探查法的探查序列依次為：二次探查法的探查序列依次為：12，-12，22，-22，.，等，也就是說，發(fā)生沖突時(shí)，將同義詞，等，也就是說，發(fā)生沖突時(shí)，將同義詞來回散列在第一個(gè)地址的兩端。求下一個(gè)開放地來回散列在第一個(gè)地址的兩端。求下一個(gè)開放地址的公式為：址的公式為： d2i