典型查找算法ppt課件

1、第第9章章 典型查找算法典型查找算法 順序查找、折半查找和分塊查找的方法順序查找、折半查找和分塊查找的方法和算法，相應(yīng)的平均查找長度和算法，相應(yīng)的平均查找長度二叉排序樹查找方法和算法，二叉平衡二叉排序樹查找方法和算法，二叉平衡樹概念樹概念散列表的概念，散列函數(shù)的構(gòu)造方法，散列表的概念，散列函數(shù)的構(gòu)造方法，處理沖突的方法及散列表各種運算的實處理沖突的方法及散列表各種運算的實現(xiàn)算法現(xiàn)算法 第第9 9章章 典型查找算法典型查找算法 9.1 9.1 實例：學(xué)生分配座位實例：學(xué)生分配座位 9.2 9.2 靜態(tài)查找靜態(tài)查找 9.3 9.3 動態(tài)查找動態(tài)查找 9.4 9.4 散列查找散列查找 本章總結(jié)本章總

2、結(jié)9.1 實例：學(xué)生分配座位實例：學(xué)生分配座位 9.1.1 問題描述問題描述 9.1.2 問題的分析問題的分析 9.1.3 實現(xiàn)算法實現(xiàn)算法 9.1.4 基本概念基本概念 9.1.1 問題描述問題描述 教室中的學(xué)生座位分配是一個最簡單的例子。教室中的學(xué)生座位分配是一個最簡單的例子。假定某教室有假定某教室有3535個座位，如果不加限定任意就坐個座位，如果不加限定任意就坐或按某種規(guī)律就座，則要查找某學(xué)生時就要將待或按某種規(guī)律就座，則要查找某學(xué)生時就要將待查找的學(xué)生與當(dāng)前座位上的學(xué)生進(jìn)行比較。查找的學(xué)生與當(dāng)前座位上的學(xué)生進(jìn)行比較。 9.1.2 問題的分析問題的分析 用計算機(jī)來解決查找學(xué)生問題，通常需

3、要做以下工作： 第一，學(xué)生信息以什么形式表示和存儲； 第二，查找的具體實現(xiàn)方法(算法)。struct student int num1; / 表示座號表示座號int num2; / 表示學(xué)號表示學(xué)號char name12; / 表示姓名表示姓名 ；struct listStudent stusize; /保存學(xué)生記錄保存學(xué)生記錄Int len; /學(xué)生人數(shù)學(xué)生人數(shù); 學(xué)生信息的存儲方式：學(xué)生信息的存儲方式： 從第一個學(xué)生開始，依次與查從第一個學(xué)生開始，依次與查找的學(xué)生進(jìn)行比較。在查找過程中，找的學(xué)生進(jìn)行比較。在查找過程中，若某個學(xué)生的記錄與所查找學(xué)生記若某個學(xué)生的記錄與所查找學(xué)生記錄相等，則查

4、找成功，返回該學(xué)生錄相等，則查找成功，返回該學(xué)生在表中位置；若全部比較完畢，沒在表中位置；若全部比較完畢，沒有符合條件的學(xué)生記錄，則查找不有符合條件的學(xué)生記錄，則查找不成功，前往成功，前往-1。查找學(xué)生的方法：查找學(xué)生的方法：9.1.3 實現(xiàn)算法實現(xiàn)算法 int search ( List &L , int s )/從表從表L.stu0,L.stu1,L.stun-1的的n個個元素中查找關(guān)鍵字為元素中查找關(guān)鍵字為S的元素，若查找成功返回該生學(xué)號，的元素，若查找成功返回該生學(xué)號，否則返回否則返回-1 int i;for (i=0; iL.len; i+)if ( L.stui=s) br

5、eak;if (i0 i0， 從而節(jié)省比較的時間。從而節(jié)省比較的時間。 順序查找的平均查找長度為：順序查找的平均查找長度為： 有時，表中各結(jié)點的查找概率并不相等。因有時，表中各結(jié)點的查找概率并不相等。因 此若事先知道表中各結(jié)點查找概率的分布情此若事先知道表中各結(jié)點查找概率的分布情 況，則可將表中結(jié)點按查找概率從大到小排況，則可將表中結(jié)點按查找概率從大到小排 列，以便提高順序查找的效率。列，以便提高順序查找的效率。 順序查找的特點：算法簡單，但查找效率低。順序查找的特點：算法簡單，但查找效率低。111(1)/2nnsqiiiiASLpcinn 折半查找又稱為二分查找。折半查找又稱為二分查找。 折

6、半要求查找表是有序的。折半要求查找表是有序的。 折半查找的基本思想是：折半查找的基本思想是： 首先將待查的首先將待查的K值與有序表值與有序表R0到到Rn-1的中間位的中間位置置mid上的結(jié)點的關(guān)鍵字進(jìn)行比較，若相等，則查上的結(jié)點的關(guān)鍵字進(jìn)行比較，若相等，則查找完成；找完成； 否則，若否則，若Rmid.keyK，則說明待查找的結(jié)點只，則說明待查找的結(jié)點只可能在左表可能在左表R0到到Rmid-1中，只需在左子表中繼中，只需在左子表中繼續(xù)查找；否則在右子表中繼續(xù)查找。這樣，經(jīng)過一續(xù)查找；否則在右子表中繼續(xù)查找。這樣，經(jīng)過一次鍵字的比較就縮小了一半的查找區(qū)間。次鍵字的比較就縮小了一半的查找區(qū)間。 重復(fù)

7、執(zhí)行，直到找到關(guān)鍵字為重復(fù)執(zhí)行，直到找到關(guān)鍵字為K的元素或當(dāng)前查找的元素或當(dāng)前查找區(qū)間為空區(qū)間為空(即表明查找失敗即表明查找失敗)為止。為止。9.2.2 9.2.2 折半查找折半查找05 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=21K=21的過程查找成功）的過程查找成功）midhighlowlowhighmidlowhighmid05 13 19 21 37 56 64 75 80 88 9205 13 19 21 37 56 64 75

8、 80 88 9205 13 19 21 37 56 64 75 80 88 92查找查找K=85K=85的過程查找失?。┑倪^程查找失敗）05 13 19 21 37 56 64 75 80 88 92 lowhighmidmidlowhighmidlowhighlowhigh折半查找算法折半查找算法low和和high分別表示當(dāng)前查找區(qū)分別表示當(dāng)前查找區(qū)間的下界和上界）間的下界和上界）int BINSEARCH(SSTable ST,keytype K) int low,mid,high; low0; highn-1; while (low=high) mid(low+high)/2; /整除

9、整除 if (K=ST.Rmid.key) return mid; if (KST.Rmid.key) highmid-1; else lowmid+1; return -1; /查找失敗查找失敗 雖然折半查找的效率較高，但它要求被查找雖然折半查找的效率較高，但它要求被查找序列事先按關(guān)鍵字排好序，而排序本身是一種很序列事先按關(guān)鍵字排好序，而排序本身是一種很費時的運算；另外，折半查找只適用于順序存儲費時的運算；另外，折半查找只適用于順序存儲結(jié)構(gòu)，因此，折半查找特別適用于那種一經(jīng)建立結(jié)構(gòu)，因此，折半查找特別適用于那種一經(jīng)建立就很少改動、而又需要經(jīng)常查找的線性表。就很少改動、而又需要經(jīng)常查找的線性表

10、。二叉判定樹：表示折半查找的查找過程。樹中的每個結(jié)點表示表中一個元素，每棵子樹的根結(jié)點表示當(dāng)前查找區(qū)間的中間點元素，它的左子樹和右子樹分別對應(yīng)該區(qū)間的左子表和右子表。 二叉判定樹是一棵二叉排序樹。 二分查找的平均查找長度為： )21()2(11111hhiinnhiASL9.2.3 分塊查找分塊查找 分塊查找分塊查找(索引順序查找索引順序查找) 基本思想：基本思想： 首先把一個線性表首先把一個線性表(即主表即主表)按照一定的函數(shù)關(guān)按照一定的函數(shù)關(guān)系或條件劃分成若干個邏輯子表，為每個子表分系或條件劃分成若干個邏輯子表，為每個子表分別建立一個索引項，由所有子表的索引項構(gòu)成一別建立一個索引項，由所有

11、子表的索引項構(gòu)成一個索引表。當(dāng)進(jìn)行分塊查找時，先根據(jù)所給的關(guān)個索引表。當(dāng)進(jìn)行分塊查找時，先根據(jù)所給的關(guān)鍵字查找索引表，從中查找出給定值鍵字查找索引表，從中查找出給定值K剛好小于剛好小于等于索引值的那個索引項，找到待查塊，然后再等于索引值的那個索引項，找到待查塊，然后再到主表中查找該塊，從中查找待查的記錄。到主表中查找該塊，從中查找待查的記錄。 實現(xiàn)算法：實現(xiàn)算法： （略）（略） 索引表是有序的，所以在索引表上既可以采用索引表是有序的，所以在索引表上既可以采用順序查找，也可以采用折半查找，而每個塊中的順序查找，也可以采用折半查找，而每個塊中的記錄排列是任意的，所以在塊內(nèi)只能采用順序查記錄排列是任

12、意的，所以在塊內(nèi)只能采用順序查找。找。 平均查找長度為：平均查找長度為： 設(shè)將長度為設(shè)將長度為n n的表均勻分成的表均勻分成b b塊，每塊有塊，每塊有s s個記錄，則個記錄，則b=n/sb=n/s，查找表中每條記錄的概，查找表中每條記錄的概率相等，則每塊查找的概率為率相等，則每塊查找的概率為1/b1/b，塊中每條，塊中每條記錄的查找概率為記錄的查找概率為1/s1/s。則順序查找索引表時：。則順序查找索引表時： 1)(21212111L1121ssnsbisjbLASLsibj 分塊有序表的索引存儲表示 索引表結(jié)點的數(shù)據(jù)類型定義如下：索引表結(jié)點的數(shù)據(jù)類型定義如下： #define MaxInde

13、x typedef struct KeyType key; int addr(link); IdxType; 在這種結(jié)構(gòu)下，查找過程要分為兩步：首先查找索在這種結(jié)構(gòu)下，查找過程要分為兩步：首先查找索引表。因為索引表是有序表，所以可采用二分查找或順引表。因為索引表是有序表，所以可采用二分查找或順序查找，以確定給定值所在的塊。因為塊中的記錄可以序查找，以確定給定值所在的塊。因為塊中的記錄可以是任意排列的，所以再在已確定的塊中進(jìn)行順序查找。是任意排列的，所以再在已確定的塊中進(jìn)行順序查找。 分塊查找算法如下：分塊查找算法如下：int IdxSerch(SeqList A,IdxType index,i

14、nt b,KeyType k,int n) /分塊查找關(guān)鍵字為分塊查找關(guān)鍵字為k的記錄，索引表為的記錄，索引表為index0.b-1 int low=0,high=b-1,mid,i; int s=n/b; /每塊記錄個數(shù)每塊記錄個數(shù) while(low=high) /在索引表中進(jìn)行二分查找，找到的位置放在在索引表中進(jìn)行二分查找，找到的位置放在low中中 mid=(low+high)/2; if(indexmid.keyk) low=mid+1 else high=mid-1; if(lowb) /在塊中順序查找在塊中順序查找 for(i=indexlow.addr;i=indexlow.ad

15、dr+s-1 & i(*q)-elem.key)/*kx大于當(dāng)前結(jié)點*q的元素關(guān)鍵碼*/*p=*q;*q=(*q)-rc;/*將當(dāng)前結(jié)點*q的右子女置為新根*/elseif(kxelem.key) /*kx小于當(dāng)前結(jié)點*q的元素關(guān)鍵碼*/*p=*q;*q=(*q)-lc; /*將當(dāng)前結(jié)點*q的左子女置為新根*/elseflag=1;break;/*查找成功，前往*/ /*while*/ return flag;時間復(fù)雜度：時間復(fù)雜度： 分析：在二叉排序樹上進(jìn)行查找的分析：在二叉排序樹上進(jìn)行查找的過程中，根結(jié)點為待查結(jié)點時，給定值過程中，根結(jié)點為待查結(jié)點時，給定值同樹中結(jié)點的比較次數(shù)僅為

16、一次，待查同樹中結(jié)點的比較次數(shù)僅為一次，待查結(jié)點位于最后一層時，比較的次數(shù)為樹結(jié)點位于最后一層時，比較的次數(shù)為樹的深度。的深度。 普通情況下，對二叉排序樹進(jìn)行查普通情況下，對二叉排序樹進(jìn)行查找的時間復(fù)雜度為找的時間復(fù)雜度為O( )O( )； 最差情況下最差情況下( (二叉排序樹為一棵單支二叉排序樹為一棵單支樹樹) )，其時間復(fù)雜度為，其時間復(fù)雜度為O(n)O(n)。 n2log45245312371001224374553100(a) 深度為3的二叉排序樹(b) 深度為6的二叉排序樹 為使得由任何初始序列構(gòu)成的二叉排序樹的平均查找長度是對數(shù)級的，所以我們可使得構(gòu)造的二叉排序樹是一個平衡二叉樹。

17、三.二叉排序樹插入操作和構(gòu)造一棵二叉排序樹 向二叉排序樹中插入一個結(jié)點的過程：設(shè)待插入結(jié)點的關(guān)鍵碼為kx，為將其插入，先要在二叉排序樹中進(jìn)行查找，若查找成功，按二叉排序樹定義，待插入結(jié)點已存在，不用插入；查找不成功時，則插入之。因此，新插入結(jié)點一定是作為葉子結(jié)點添加上去的。 構(gòu)造一棵二叉排序樹則是逐個插入結(jié)點的過程。 圖9.5 從空樹開始建立二叉排序樹的過程 【算法9.5】int InsertNode (NodeType *t,KeyType kx) /*在二叉排序樹*t上插入關(guān)鍵碼為kx的結(jié)點*/ NodeType *q, *s , *p=*t; int flag=0;if(!SearchE

18、lem(*t,&p,&q,kx); /*在*t為根的子樹上查找*/s=(NodeType *)malloc(sizeof(NodeType);/*申請結(jié)點,并賦值*/s-elem.key=kx;s-lc=NULL;s-rc=NULL;flag=1; /*設(shè)置插入成功標(biāo)志*/ if(!p) t=s; /*向空樹中插入時*/elseif(kxp-elem.key)p-rc=s; /*插入結(jié)點為p的右子女*/elsep-lc=s; /*插入結(jié)點為p的左子女*/return flag; 9.3.2 二叉平衡樹二叉平衡樹 二叉平衡樹二叉平衡樹(AVL(AVL樹樹) )： 或者是一棵空樹，

19、或者是一棵具有如下性或者是一棵空樹，或者是一棵具有如下性質(zhì)的非空二叉樹：質(zhì)的非空二叉樹： 它的左子樹和右子樹都是二叉平衡樹，且它的左子樹和右子樹都是二叉平衡樹，且左子樹和右子樹的深度之差的絕對值不大于左子樹和右子樹的深度之差的絕對值不大于1 1。二叉平衡樹中結(jié)點的左子樹的深度減去它的右二叉平衡樹中結(jié)點的左子樹的深度減去它的右子樹的深度的值定義為平衡因子子樹的深度的值定義為平衡因子BFBF，則，則BFBF的值的值只可能為只可能為1 1、0 0和和1 1。 對二叉排序樹插入結(jié)點而構(gòu)造平衡二叉樹的規(guī)律：對二叉排序樹插入結(jié)點而構(gòu)造平衡二叉樹的規(guī)律： 設(shè)最小子樹根結(jié)點的指針為設(shè)最小子樹根結(jié)點的指針為a，

20、則失去平衡后進(jìn)，則失去平衡后進(jìn)行調(diào)整的規(guī)律：行調(diào)整的規(guī)律： LL型：單向右旋平衡處理型：單向右旋平衡處理 RR型：單向左旋平衡處理型：單向左旋平衡處理 LR型：雙向旋轉(zhuǎn)型：雙向旋轉(zhuǎn)(先左后右先左后右)平衡處理平衡處理 RL型：雙向旋轉(zhuǎn)型：雙向旋轉(zhuǎn)(先右后左先右后左)平衡處理平衡處理時間復(fù)雜度：時間復(fù)雜度： 在查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)在查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)不超過樹的深度，所以，在二叉平衡樹上進(jìn)行查找不超過樹的深度，所以，在二叉平衡樹上進(jìn)行查找的時間復(fù)雜度為的時間復(fù)雜度為O(log2n)。 平衡二叉樹和非平衡二叉樹平衡二叉樹和非平衡二叉樹/p>

21、21513111214151617(a)(b)1-1-10100-2-1-30-2-10圖9.9 圖9.9給出了兩棵二叉排序樹，每個結(jié)點旁邊所注數(shù)字是以該結(jié)點為根的樹中，左子樹與右子樹高度之差，這個數(shù)字稱為結(jié)點的平衡因子。由平衡二叉樹定義，所有結(jié)點的平衡因子只能取-1，0，1三個值之一。若二叉排序樹中存在這樣的結(jié)點，其平衡因子的絕對值大于1，這棵樹就不是平衡二叉樹。如圖9.9 （a所示的二叉排序樹。 在平衡二叉樹上插入或刪除結(jié)點后，可能使樹失去平衡，因此，需要對失去平衡的樹進(jìn)行平衡化調(diào)整。設(shè)a結(jié)點為失去平衡的最小子樹根結(jié)點，對該子樹進(jìn)行平衡化調(diào)整歸納起來有以下四種情況： 對二叉排序樹插入結(jié)點而

22、構(gòu)造平衡二叉樹的規(guī)律：對二叉排序樹插入結(jié)點而構(gòu)造平衡二叉樹的規(guī)律： 設(shè)最小子樹根結(jié)點的指針為設(shè)最小子樹根結(jié)點的指針為a，則失去平衡后進(jìn)，則失去平衡后進(jìn)行調(diào)整的規(guī)律：行調(diào)整的規(guī)律： LL型：單向右旋平衡處理型：單向右旋平衡處理 RR型：單向左旋平衡處理型：單向左旋平衡處理 LR型：雙向旋轉(zhuǎn)型：雙向旋轉(zhuǎn)(先左后右先左后右)平衡處理平衡處理 RL型：雙向旋轉(zhuǎn)型：雙向旋轉(zhuǎn)(先右后左先右后左)平衡處理平衡處理時間復(fù)雜度：時間復(fù)雜度： 在查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)在查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)不超過樹的深度，所以，在二叉平衡樹上進(jìn)行查找不超過樹的深度，所以，在二叉平衡樹上進(jìn)行查找

23、的時間復(fù)雜度為的時間復(fù)雜度為O(log2n)。 左單旋轉(zhuǎn)RR型） 在圖(a)所示的樹上插入結(jié)點x，如圖(b)所示。結(jié)點x插入在結(jié)點c的右子樹E上，導(dǎo)致結(jié)點a的平衡因子絕對值大于1，以結(jié)點a為根的子樹失去平衡。 【調(diào)整策略】 調(diào)整后的子樹除了各結(jié)點的平衡因子絕對值不超過1，還必須是二叉排序樹。由于結(jié)點c的左子樹D可作為結(jié)點a的右子樹，將結(jié)點a為根的子樹調(diào)整為左子樹是B，右子樹是D，再將結(jié)點a為根的子樹調(diào)整為結(jié)點c的左子樹，結(jié)點c為新的根結(jié)點，如圖(c)?！酒胶饣{(diào)整操作判定】 沿插入路徑檢查三個點a、c、E，若它們處于“”直線上的同一個方向，則要作左單旋轉(zhuǎn)，即以結(jié)點c為軸逆時針旋轉(zhuǎn)。 闡明： 1

24、.旋轉(zhuǎn)操作的正確性可以由二叉排序樹的特性：中序遍歷所得關(guān)鍵字序列自小至大有序證明之。2. 當(dāng)平衡的二叉排序樹因插入結(jié)點而失去平衡時，僅需對最小不平衡子樹進(jìn)行平衡旋轉(zhuǎn)即可。因為經(jīng)過旋轉(zhuǎn)處理之后的子樹深度和插入之前相同，因而不影響插入路徑上所由祖先結(jié)點的平衡度。二. 右單旋轉(zhuǎn) （LL型） 右單旋轉(zhuǎn)與左單旋轉(zhuǎn)類似，沿插入路徑檢查三個點a、c、E，若它們處于“/”直線上的同一個方向，則要作右單旋轉(zhuǎn)，即以結(jié)點c為軸順時針旋轉(zhuǎn)，如圖9.11所示。 如圖9.12為插入前的子樹，根結(jié)點a的左子樹比右子樹高度高1，待插入結(jié)點x將插入到結(jié)點b的右子樹上，并使結(jié)點b的右子樹高度增1，從而使結(jié)點a的平衡因子的絕對值大

25、于1，導(dǎo)致結(jié)點a為根的子樹平衡被破壞，如圖9.12 插入前圖9.13(a)、9.14(d)所示。 圖9.12 插入前三. 先左后右雙向旋轉(zhuǎn) （LR型）圖9.13 沿插入路徑檢查三個點a、b、c，若它們呈“”字形，需要進(jìn)行先左后右雙向旋轉(zhuǎn)： 1. 首先，對結(jié)點b為根的子樹，以結(jié)點c為軸，向左逆時針旋轉(zhuǎn)，結(jié)點c成為該子樹的新根，如圖(b、e)； 2. 由于旋轉(zhuǎn)后，待插入結(jié)點x相當(dāng)于插入到結(jié)點b為根的子樹上，這樣a、c、b三點處于“/”直線上的同一個方向，則要作右單旋轉(zhuǎn)，即以結(jié)點c為軸順時針旋轉(zhuǎn)，如圖(c、f)。 四. 先右后左雙向旋轉(zhuǎn)RL型） 先右后左雙向旋轉(zhuǎn)和先左后右雙向旋轉(zhuǎn)對稱，自行補(bǔ)充整理。

26、 9.4 散列查找散列查找 9.4.1 散列存儲和散列函數(shù)的構(gòu)造方法散列存儲和散列函數(shù)的構(gòu)造方法 9.4.2 解決沖突的方法解決沖突的方法 9.4.3 散列查找實現(xiàn)算法和性能分析散列查找實現(xiàn)算法和性能分析 9.4.1 散列存儲和散列函數(shù)構(gòu)造散列存儲和散列函數(shù)構(gòu)造基本術(shù)語：基本術(shù)語： 散列存儲：以數(shù)據(jù)中每個元素的關(guān)鍵字散列存儲：以數(shù)據(jù)中每個元素的關(guān)鍵字K K為自變量，通過一個函數(shù)為自變量，通過一個函數(shù)f(k)f(k)計算出函數(shù)值，計算出函數(shù)值，把這個值同存儲空間中一個唯一的存儲位置相把這個值同存儲空間中一個唯一的存儲位置相對應(yīng)，將該元素存儲到這個存儲位置中。函數(shù)對應(yīng)，將該元素存儲到這個存儲位置中

27、。函數(shù)f(k)f(k)稱為散列函數(shù)或哈希函數(shù)。稱為散列函數(shù)或哈希函數(shù)。f(k)f(k)的值稱為的值稱為散列地址或哈希地址；進(jìn)行散列存儲的地址空散列地址或哈希地址；進(jìn)行散列存儲的地址空間稱為散列表或哈希表。間稱為散列表或哈希表。 沖突：實際應(yīng)用中，由于散列函數(shù)的沖突：實際應(yīng)用中，由于散列函數(shù)的構(gòu)造方法不同，常會出現(xiàn)多個元素同時占用一構(gòu)造方法不同，常會出現(xiàn)多個元素同時占用一個存儲單元的情況，即散列地址相同，這種現(xiàn)個存儲單元的情況，即散列地址相同，這種現(xiàn)象叫沖突。具有相同函數(shù)值的不同關(guān)鍵字的元象叫沖突。具有相同函數(shù)值的不同關(guān)鍵字的元素，稱為同義詞。素，稱為同義詞。 常用的構(gòu)造散列函數(shù)的方法：常用的構(gòu)

28、造散列函數(shù)的方法：直接定址法直接定址法: :取關(guān)鍵字或關(guān)鍵字的某個現(xiàn)行函數(shù)值為哈希地址。取關(guān)鍵字或關(guān)鍵字的某個現(xiàn)行函數(shù)值為哈希地址。即：即：H(key)=key H(key)=key 或或 H(key)=akey+b H(key)=akey+b。數(shù)字分析法數(shù)字分析法假設(shè)關(guān)鍵字是以假設(shè)關(guān)鍵字是以r r為基的數(shù)為基的數(shù)( (如：以如：以1010為基的十進(jìn)制數(shù)為基的十進(jìn)制數(shù)) )，并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可并且哈希表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成哈希地址。取關(guān)鍵字的若干數(shù)位組成哈希地址。平方取中法：取關(guān)鍵字平方后的中間幾位為哈希地址。平方取中法：取

29、關(guān)鍵字平方后的中間幾位為哈希地址。折疊法折疊法 將關(guān)鍵字分割成位數(shù)相同的幾部分最后一部分的位將關(guān)鍵字分割成位數(shù)相同的幾部分最后一部分的位數(shù)可以不同），然后取這幾部分的疊加和舍去進(jìn)位數(shù)可以不同），然后取這幾部分的疊加和舍去進(jìn)位作為哈希地址。作為哈希地址。除留余數(shù)法除留余數(shù)法 取關(guān)鍵字被某個不大于哈希表表長取關(guān)鍵字被某個不大于哈希表表長m m的數(shù)的數(shù)p p除后所得余除后所得余數(shù)為哈希地址。即數(shù)為哈希地址。即 H(key) = key MOD p , p=m H(key) = key MOD p , p=m該方法是一種最簡單，也最常用的構(gòu)造哈希函數(shù)的方該方法是一種最簡單，也最常用的構(gòu)造哈希函數(shù)的方法

30、。法。 隨機(jī)數(shù)法隨機(jī)數(shù)法選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址。即希地址。即:H(key)=random(key):H(key)=random(key)9.4.2 解決沖突的方法解決沖突的方法 常用的解決沖突的方法有以下幾種：常用的解決沖突的方法有以下幾種：開放定地址開放定地址鏈地址法鏈地址法 再哈希法再哈希法建立一個公共溢出區(qū)建立一個公共溢出區(qū) 從發(fā)生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑存儲單元，把發(fā)生沖突的待插入元素存入到該單元中的一類解決沖突的方法。設(shè)H(key)為散列函數(shù)，m為散列表長度。則開放定址法中找

31、下一個空閑空間的散列函數(shù)為：Hi=(H(key)+ di)%m 其中，i=1,2k； di稱為增量，以di的取值分為以下三種： (1)di=1,2,3m-1,稱線性探測再散列。 (2)di=12,-12，22，-22，k2,(km/2)稱二次探測再散列。 (3)di=隨機(jī)數(shù)序列，稱為隨機(jī)探測再散列。開放定址法：開放定址法： 把具有相同散列地址的關(guān)鍵字放在同一鏈表中，稱為同義詞鏈表。通常把具有相同散列地址的關(guān)鍵字都存放在一個同義詞鏈表中，有m個散列地址就有m個鏈表，同時用數(shù)組tm存放各個鏈表的頭指針,凡是散列地址為i的記錄都以結(jié)點方式插入到以ti為頭指針的單鏈表中。 鏈地址法：鏈地址法：9.4.

32、3 散列查找實現(xiàn)算法和性能分析散列查找實現(xiàn)算法和性能分析散列表的長度表中記錄數(shù)算法思想：在哈希表上進(jìn)行查找的過程和哈希造表算法思想：在哈希表上進(jìn)行查找的過程和哈希造表的過程一致。給定的過程一致。給定K K值，根據(jù)造表時設(shè)定的哈西函數(shù)值，根據(jù)造表時設(shè)定的哈西函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關(guān)鍵字，若何給定值相等，則查不成功；否則比較關(guān)鍵字，若何給定值相等，則查找成功；否則根據(jù)造表時設(shè)定的處理沖突的方法找找成功；否則根據(jù)造表時設(shè)定的處理沖突的方法找“下一地址下一地址”，直至哈希表中某個位置為，直至哈希表中某個位置為“空或空

33、或者表中所填記錄的關(guān)鍵字等于給定值時為止。者表中所填記錄的關(guān)鍵字等于給定值時為止。結(jié)論：結(jié)論： l l 由于產(chǎn)生由于產(chǎn)生“沖突沖突” ” ，查找過程仍是一個給定，查找過程仍是一個給定值和關(guān)鍵字進(jìn)行比較的過程。因此，仍需以平均查值和關(guān)鍵字進(jìn)行比較的過程。因此，仍需以平均查找長度作為衡量散列表的查找效率的量度。找長度作為衡量散列表的查找效率的量度。 l l 查找過程中比較個數(shù)取決于因素：散列函數(shù)、查找過程中比較個數(shù)取決于因素：散列函數(shù)、解決沖突的方法和散列表的裝填因子。解決沖突的方法和散列表的裝填因子。 裝填因子定義：裝填因子定義： = = 越小，發(fā)生沖突的可能性就越小；越小，發(fā)生沖突的可能性就越

34、??；越大，發(fā)生越大，發(fā)生沖突的可能性就越大。沖突的可能性就越大。 本章總結(jié)本章總結(jié) 本章主要介紹了數(shù)據(jù)處理中的幾種典型的查找方法、及實現(xiàn)算法和各種查找方法的性能分析。 查找：指在一個含有眾多數(shù)據(jù)元素(或記錄)的查找表中找出某個“特定的數(shù)據(jù)元素或記錄）。 查找過程：是數(shù)據(jù)處理的一個環(huán)節(jié)，它的下一環(huán)節(jié)是對查找到的結(jié)果進(jìn)行處理，根據(jù)所做的操作的不同，將查找方法分為靜態(tài)查找和動態(tài)查找。靜態(tài)查找方法介紹了順序查找、二分查找和分塊查找三種方法。動態(tài)查找方法介紹了二叉排序樹查找和二叉平衡樹查找。 順序查找既適用于順序表，也適用與單鏈表，時間復(fù)雜度是On），平均查找長度為n+1）/2 。 折半查找只適用于順序存儲的有序表。折半查找的時間復(fù)雜度為Olog2n）。折半查找的查找過程可以畫成一棵二叉判定樹，它是一棵二叉排序樹。 分塊查找過程分為兩部分：先在索引表中查找；然后在主表的對應(yīng)塊中順序查找。 二叉排序樹查找：根據(jù)二叉排序樹的定義，首先訪問根結(jié)點，若其值等于給定值則查找成功；若給定值比根結(jié)點大，繼續(xù)向右子樹中查找；否則給定值比根結(jié)點小，繼續(xù)在左子樹中查找，直到找到該結(jié)點或找不到為止，此時查找失敗。 二叉平衡樹的BF的值只可能為1、0和1。二叉平衡樹的構(gòu)造過程中進(jìn)行調(diào)整的方法共有四種。二叉平衡樹的查找過程也與二叉排序樹類似，從根結(jié)點開始，向左或右子樹進(jìn)行查找。