數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言版(嚴(yán)蔚敏版)第9章 查找

1、1065865ABCDEFG學(xué)習(xí)提要學(xué)習(xí)提要第第9章章 查找查找 本章中介紹下列主要內(nèi)容：本章中介紹下列主要內(nèi)容： 靜態(tài)查找表及查找算法：靜態(tài)查找表及查找算法：順序查找順序查找、折半查找折半查找 動(dòng)態(tài)查找表及查找算法：動(dòng)態(tài)查找表及查找算法：二叉排序樹二叉排序樹 哈希表哈希表及查找算法及查找算法學(xué)習(xí)提要（具體來講）學(xué)習(xí)提要（具體來講）.熟練掌握順序表和有序表的查找方法。熟練掌握順序表和有序表的查找方法。.熟練掌握二叉排序樹的構(gòu)造和查找方法。熟練掌握二叉排序樹的構(gòu)造和查找方法。.掌握二叉平衡樹的維護(hù)平衡方法。掌握二叉平衡樹的維護(hù)平衡方法。.理解樹的特點(diǎn)以及它們的建樹過程。理解樹的特點(diǎn)以及它們的建樹

2、過程。.熟練掌握哈希表的構(gòu)造方法，深刻理解哈熟練掌握哈希表的構(gòu)造方法，深刻理解哈希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。希表與其它結(jié)構(gòu)的表的實(shí)質(zhì)性的差別。.掌握描述查找過程的判定樹的構(gòu)造方法，掌握描述查找過程的判定樹的構(gòu)造方法，以及按定義計(jì)算各種查找方法在等概率情況下以及按定義計(jì)算各種查找方法在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。查找成功時(shí)的平均查找長(zhǎng)度?；靖拍罨靖拍?查找表查找表 用于查找的數(shù)據(jù)元素集合稱為查找用于查找的數(shù)據(jù)元素集合稱為查找表。表。查找表由同一類型的數(shù)據(jù)元素（或記錄）查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成。構(gòu)成。 靜態(tài)查找表靜態(tài)查找表 若只對(duì)查找表進(jìn)行如下兩種操若只對(duì)查找表

3、進(jìn)行如下兩種操作：（作：（1）在查找表中查看某個(gè)特定的數(shù)據(jù)元素）在查找表中查看某個(gè)特定的數(shù)據(jù)元素是否在是否在查找表中，（查找表中，（2）檢索某個(gè)特定元素的各）檢索某個(gè)特定元素的各種種屬性屬性，則稱這類查找表為靜態(tài)查找表。靜態(tài)，則稱這類查找表為靜態(tài)查找表。靜態(tài)查找表在查找過程中查找表本身不發(fā)生變化。查找表在查找過程中查找表本身不發(fā)生變化。對(duì)靜態(tài)查找表進(jìn)行的查找操作稱為對(duì)靜態(tài)查找表進(jìn)行的查找操作稱為靜態(tài)查找靜態(tài)查找。 動(dòng)態(tài)查找表：動(dòng)態(tài)查找表：若在查找過程中可以將查找若在查找過程中可以將查找表中不存在的表中不存在的數(shù)據(jù)元素插入數(shù)據(jù)元素插入，或者從查找表中，或者從查找表中刪除某個(gè)數(shù)據(jù)元素刪除某個(gè)數(shù)據(jù)元

4、素，則稱這類查找表為，則稱這類查找表為動(dòng)態(tài)查動(dòng)態(tài)查找表找表。動(dòng)態(tài)查找表在查找過程中查找表可能會(huì)。動(dòng)態(tài)查找表在查找過程中查找表可能會(huì)發(fā)生變化。對(duì)動(dòng)態(tài)查找表進(jìn)行的查找操作稱為發(fā)生變化。對(duì)動(dòng)態(tài)查找表進(jìn)行的查找操作稱為動(dòng)態(tài)查找動(dòng)態(tài)查找。 關(guān)鍵字：關(guān)鍵字：是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。唯是數(shù)據(jù)元素中的某個(gè)數(shù)據(jù)項(xiàng)。唯一能標(biāo)識(shí)數(shù)據(jù)元素（或記錄）的關(guān)鍵字，即每一能標(biāo)識(shí)數(shù)據(jù)元素（或記錄）的關(guān)鍵字，即每個(gè)元素的關(guān)鍵字值互不相同，我們稱這種關(guān)鍵個(gè)元素的關(guān)鍵字值互不相同，我們稱這種關(guān)鍵字為字為主關(guān)鍵字主關(guān)鍵字；若查找表中某些元素的關(guān)鍵字；若查找表中某些元素的關(guān)鍵字值相同，稱這種關(guān)鍵字為值相同，稱這種關(guān)鍵字為次關(guān)鍵字次關(guān)鍵

5、字。例如，銀。例如，銀行帳戶中的帳號(hào)是主關(guān)鍵字，而姓名是次關(guān)鍵行帳戶中的帳號(hào)是主關(guān)鍵字，而姓名是次關(guān)鍵字。字。 查找查找：在數(shù)據(jù)元素集合中查找滿足某種條：在數(shù)據(jù)元素集合中查找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。最簡(jiǎn)單且最常件的數(shù)據(jù)元素的過程稱為查找。最簡(jiǎn)單且最常用的查找條件是用的查找條件是“關(guān)鍵字值等于某個(gè)給定值關(guān)鍵字值等于某個(gè)給定值”，在查找表搜索關(guān)鍵字等于給定值的數(shù)據(jù)元素，在查找表搜索關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。若表中存在這樣的記錄，則稱（或記錄）。若表中存在這樣的記錄，則稱查查找成功找成功，此時(shí)的查找結(jié)果應(yīng)給出找到記錄的全，此時(shí)的查找結(jié)果應(yīng)給出找到記錄的全部信息或指示找到記錄

6、的存儲(chǔ)位置；若表中不部信息或指示找到記錄的存儲(chǔ)位置；若表中不存在關(guān)鍵字等于給定值的記錄，則稱存在關(guān)鍵字等于給定值的記錄，則稱查找不成查找不成功功，此時(shí)查找的結(jié)果可以給出一個(gè)空記錄或空，此時(shí)查找的結(jié)果可以給出一個(gè)空記錄或空指針。若按主關(guān)鍵字查找，查找結(jié)果是唯一的指針。若按主關(guān)鍵字查找，查找結(jié)果是唯一的；若按次關(guān)鍵字查找，結(jié)果可能是多個(gè)記錄，；若按次關(guān)鍵字查找，結(jié)果可能是多個(gè)記錄，即結(jié)果可能不唯一。即結(jié)果可能不唯一。 查找表的存儲(chǔ)結(jié)構(gòu)查找表的存儲(chǔ)結(jié)構(gòu)：查找表是一種非常靈活的：查找表是一種非常靈活的數(shù)據(jù)結(jié)構(gòu)，對(duì)于不同的存儲(chǔ)結(jié)構(gòu)，其查找方法數(shù)據(jù)結(jié)構(gòu)，對(duì)于不同的存儲(chǔ)結(jié)構(gòu)，其查找方法不同。為了提高查找速度

7、，有時(shí)會(huì)采用一些特不同。為了提高查找速度，有時(shí)會(huì)采用一些特殊的存儲(chǔ)結(jié)構(gòu)。本章將介紹以殊的存儲(chǔ)結(jié)構(gòu)。本章將介紹以線性結(jié)構(gòu)線性結(jié)構(gòu)、樹型樹型結(jié)構(gòu)結(jié)構(gòu)及及哈希表結(jié)構(gòu)哈希表結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)的各種查找算法為存儲(chǔ)結(jié)構(gòu)的各種查找算法。 查找算法的時(shí)間效率查找算法的時(shí)間效率：查找過程的主要操作：查找過程的主要操作是關(guān)鍵字的比較，所以通常以是關(guān)鍵字的比較，所以通常以“平均比較次數(shù)平均比較次數(shù)”來衡量查找算法的時(shí)間效率。來衡量查找算法的時(shí)間效率。9.1.1. 順序查找（線性查找）順序查找（線性查找） 靜態(tài)查找是指在靜態(tài)查找表上進(jìn)行的查找靜態(tài)查找是指在靜態(tài)查找表上進(jìn)行的查找操作，在查找表中查找滿足條件的數(shù)據(jù)元素的操作

8、，在查找表中查找滿足條件的數(shù)據(jù)元素的存儲(chǔ)位置或各種屬性。本節(jié)將討論以線性結(jié)構(gòu)存儲(chǔ)位置或各種屬性。本節(jié)將討論以線性結(jié)構(gòu)表示的靜態(tài)查找表及相應(yīng)的查找算法。表示的靜態(tài)查找表及相應(yīng)的查找算法。9.1 靜態(tài)查找表靜態(tài)查找表順序查找的基本思想順序查找的基本思想： 順序查找是一種最簡(jiǎn)單的查找方法。其基本順序查找是一種最簡(jiǎn)單的查找方法。其基本思想是將查找表作為一個(gè)線性表，可以是順序思想是將查找表作為一個(gè)線性表，可以是順序表，也可以是鏈表，依次用查找條件中給定的表，也可以是鏈表，依次用查找條件中給定的值與查找表中數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較，值與查找表中數(shù)據(jù)元素的關(guān)鍵字值進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字值與給定值相等

9、，則查找若某個(gè)記錄的關(guān)鍵字值與給定值相等，則查找成功，返回該記錄的存儲(chǔ)位置，反之，若直到成功，返回該記錄的存儲(chǔ)位置，反之，若直到最后一個(gè)記錄，其關(guān)鍵字值與給定值均不相等最后一個(gè)記錄，其關(guān)鍵字值與給定值均不相等，則查找失敗，返回查找失敗標(biāo)志。，則查找失敗，返回查找失敗標(biāo)志。 可以采用從前向后查，也可采用從后向前查的方法?？梢圆捎脧那跋蚝蟛?，也可采用從后向前查的方法。 在平均情況下，大約要與表中一半以上元素進(jìn)行比較在平均情況下，大約要與表中一半以上元素進(jìn)行比較效率較低。平均查找長(zhǎng)度較大。效率較低。平均查找長(zhǎng)度較大。 在下面兩種情況下只能采取順序查找：在下面兩種情況下只能采取順序查找： a. 線性表

10、為無序表（元素排列是無序的）；線性表為無序表（元素排列是無序的）； b. 即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。即使是有序線性表，但采用的是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。查找過程：查找過程： 對(duì)給定的一關(guān)鍵字對(duì)給定的一關(guān)鍵字K，從線性表的一端開始，逐個(gè)進(jìn)，從線性表的一端開始，逐個(gè)進(jìn)行記錄的關(guān)鍵字和行記錄的關(guān)鍵字和K的比較，直到找到關(guān)鍵字等于的比較，直到找到關(guān)鍵字等于K的記的記錄或到達(dá)表的另一端。錄或到達(dá)表的另一端。（1）順序查找）順序查找 (線性表在順序存儲(chǔ)結(jié)構(gòu)下的順序查找）線性表在順序存儲(chǔ)結(jié)構(gòu)下的順序查找） 數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：#define MAX_NUM 100 /用于定義表的長(zhǎng)度用于定義表的長(zhǎng)度t

11、ypedef struct int key; float info;SSTableMAX_NUM，SSItem ;每個(gè)結(jié)點(diǎn)包含兩部分每個(gè)結(jié)點(diǎn)包含兩部分內(nèi)容：內(nèi)容：Key 和和info其他其他信息信息 假設(shè)在查找表中，數(shù)據(jù)元素個(gè)數(shù)為假設(shè)在查找表中，數(shù)據(jù)元素個(gè)數(shù)為n（nMAX_NUM），并分別存放在數(shù)組的下標(biāo)變），并分別存放在數(shù)組的下標(biāo)變量量ST1STn中。中。下面我們給出順序查找的完整算法。下面我們給出順序查找的完整算法。int seq_search (SSTable ST，int key)/在順序表中查找關(guān)鍵字值等于在順序表中查找關(guān)鍵字值等于key的記錄，的記錄， /若查找成功，返回該記錄的位

12、置下標(biāo)序號(hào)，若查找成功，返回該記錄的位置下標(biāo)序號(hào)，否則返回否則返回0 i=1; while (i=n & STi.key != key) i+; if (inext; while (p!=NULL) & (p-key!=k) p=p-next; return p; 9.1.2 折半查找（二分法查找）折半查找（二分法查找） 折半查找要求查找表用順序存儲(chǔ)結(jié)構(gòu)存放且折半查找要求查找表用順序存儲(chǔ)結(jié)構(gòu)存放且各數(shù)據(jù)元素各數(shù)據(jù)元素按關(guān)鍵字有序按關(guān)鍵字有序（升序或隆序）排列（升序或隆序）排列，也就是說折半查找只適用于對(duì)有序順序表進(jìn)，也就是說折半查找只適用于對(duì)有序順序表進(jìn)行查找。行查找。 1.

13、折半查找的基本思想是折半查找的基本思想是： 首先以整個(gè)查找表作為查找范圍，用查找條件中首先以整個(gè)查找表作為查找范圍，用查找條件中給定值給定值k與中間位置結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則與中間位置結(jié)點(diǎn)的關(guān)鍵字比較，若相等，則查找成功，否則，根據(jù)比較結(jié)果縮小查找范圍，如果查找成功，否則，根據(jù)比較結(jié)果縮小查找范圍，如果k的值小于關(guān)鍵字的值，根據(jù)查找表的有序性可知查的值小于關(guān)鍵字的值，根據(jù)查找表的有序性可知查找的數(shù)據(jù)元素只有可能在表的前半部分，即在左半部找的數(shù)據(jù)元素只有可能在表的前半部分，即在左半部分子表中，所以繼續(xù)對(duì)左子表進(jìn)行折半查找；若分子表中，所以繼續(xù)對(duì)左子表進(jìn)行折半查找；若k的的值大于中間結(jié)點(diǎn)的關(guān)

14、鍵字值，則可以判定查找的數(shù)據(jù)值大于中間結(jié)點(diǎn)的關(guān)鍵字值，則可以判定查找的數(shù)據(jù)元素只有可能在表的后半部分，即在右半部分子表中元素只有可能在表的后半部分，即在右半部分子表中，所以應(yīng)該繼續(xù)對(duì)右子表進(jìn)行折半查找。每進(jìn)行一次，所以應(yīng)該繼續(xù)對(duì)右子表進(jìn)行折半查找。每進(jìn)行一次折半查找，要么查找成功，結(jié)束查找，要么將查找范折半查找，要么查找成功，結(jié)束查找，要么將查找范圍縮小一半，如此重復(fù)，直到查找成功或查找范圍縮圍縮小一半，如此重復(fù)，直到查找成功或查找范圍縮小為空即查找失敗為止。小為空即查找失敗為止。 思想：先確定待查找記錄所在的范圍，然后思想：先確定待查找記錄所在的范圍，然后逐步縮小范圍，直到找到或確認(rèn)找不到該

15、記錄逐步縮小范圍，直到找到或確認(rèn)找不到該記錄為止。為止。 前提：必須在前提：必須在具有順序存儲(chǔ)結(jié)構(gòu)的具有順序存儲(chǔ)結(jié)構(gòu)的有序表中有序表中進(jìn)行進(jìn)行。分三種情況：分三種情況：1 1）若中間項(xiàng)的值等于）若中間項(xiàng)的值等于x,x,則說明已查到。則說明已查到。2 2）若）若x x小于中間項(xiàng)的值，則在線性表的前半部分查找；小于中間項(xiàng)的值，則在線性表的前半部分查找；3 3）若）若x x大于中間項(xiàng)的值，則在線性表的后半部分查找。大于中間項(xiàng)的值，則在線性表的后半部分查找。特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比特點(diǎn)：比順序查找方法效率高。最壞的情況下，需要比較較 loglog2 2n n次次。查找查找23和

16、和79的過程如下圖：的過程如下圖：mid=(low+high)/2不進(jìn)位取整不進(jìn)位取整( 08, 14, 23, 37, 46, 55, 68, 79, 91 )( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhigh=mid-1mid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )low=mid+1highmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 3

17、7, 46, 55, 68, 79, 91 )lowhighmid( 08, 14, 23, 37, 46, 55, 68, 79, 91 )lowhighmid2. 折半查找算法折半查找算法 假設(shè)查找表存放在數(shù)組假設(shè)查找表存放在數(shù)組ST的的ST1 STn中，中，且升序，查找關(guān)鍵字值為且升序，查找關(guān)鍵字值為key。 折半查找的主要步驟為：折半查找的主要步驟為： （1）置初始查找范圍：）置初始查找范圍：low=1，high=n; （2）求查找范圍中間項(xiàng)：）求查找范圍中間項(xiàng)：mid=(low+high)/2 （ 3 ） 將 指 定 的 關(guān) 鍵 字 值） 將 指 定 的 關(guān) 鍵 字 值 k e y

18、與 中 間 項(xiàng)與 中 間 項(xiàng)STmid.key比較比較 若相等，查找成功，找到的數(shù)據(jù)元素為此時(shí)若相等，查找成功，找到的數(shù)據(jù)元素為此時(shí)mid 指向的位置；指向的位置； 若小于，查找范圍的低端數(shù)據(jù)元素指針若小于，查找范圍的低端數(shù)據(jù)元素指針low不變，高端數(shù)據(jù)元素指針不變，高端數(shù)據(jù)元素指針high更新為更新為mid-1; 若大于，查找范圍的高端數(shù)據(jù)元素指針若大于，查找范圍的高端數(shù)據(jù)元素指針high不變，低端數(shù)據(jù)元素指針不變，低端數(shù)據(jù)元素指針low更新為更新為mid+1; （4）重復(fù)步驟（）重復(fù)步驟（2）、（）、（3）直到查找成功或）直到查找成功或查找范圍空（查找范圍空（lowhigh），即查找失敗為

19、止。），即查找失敗為止。 （5）如果查找成功，返回找到元素的存放位）如果查找成功，返回找到元素的存放位置，即當(dāng)前的中間項(xiàng)位置指針置，即當(dāng)前的中間項(xiàng)位置指針mid；否則返回；否則返回查找失敗標(biāo)志。查找失敗標(biāo)志。折半查找的折半查找的c語(yǔ)言算法程序：語(yǔ)言算法程序：int Search_Bin( SSTable ST, int n, int key) int low, high,mid; low=1; high=n; while(low=high) mid=(low+high)/2; if(STmid.key= = key) return (mid); /*查找成功查找成功*/ else if( ke

20、y key = k ) return bt; else if (k key) return bt_search ( bt - lchild , k ); /在左子樹中搜索在左子樹中搜索 else return bt_search ( bt - rchild , k ); /在右子在右子樹中搜索樹中搜索 這個(gè)過程也可以用非遞歸算法實(shí)現(xiàn)，算法描述如下：這個(gè)過程也可以用非遞歸算法實(shí)現(xiàn)，算法描述如下：Bin_Sort_Tree_Node *bt_search1(Bin_Sort_Tree bt , keytype k) p = bt; /指針指針p指向根結(jié)點(diǎn)，搜索從根結(jié)點(diǎn)開始指向根結(jié)點(diǎn)，搜索從根結(jié)點(diǎn)開

21、始 while ( p != NULL & p -key != k ) if (k key ) p = p - lchild; else p = p - rchild; return ( p);3. 二叉排序樹的插入和刪除二叉排序樹的插入和刪除 3-1. 二叉排序樹的插入二叉排序樹的插入 在一棵二叉排序樹中插入一個(gè)結(jié)點(diǎn)可以用一在一棵二叉排序樹中插入一個(gè)結(jié)點(diǎn)可以用一個(gè)遞歸的過程實(shí)現(xiàn)，即：若二叉排序樹為空，個(gè)遞歸的過程實(shí)現(xiàn)，即：若二叉排序樹為空，則新結(jié)點(diǎn)作為二叉排序樹的根結(jié)點(diǎn)；否則，若則新結(jié)點(diǎn)作為二叉排序樹的根結(jié)點(diǎn)；否則，若給定結(jié)點(diǎn)的關(guān)鍵字值小于根結(jié)點(diǎn)關(guān)鍵字值，則給定結(jié)點(diǎn)的關(guān)鍵字值小于根結(jié)

22、點(diǎn)關(guān)鍵字值，則插入在左子樹上；若給定結(jié)點(diǎn)的關(guān)鍵字值大于插入在左子樹上；若給定結(jié)點(diǎn)的關(guān)鍵字值大于根結(jié)點(diǎn)的值，則插入在右子樹上。根結(jié)點(diǎn)的值，則插入在右子樹上。 10、18、3、8、12、2、7、3 1010181018310183810183812101838122101838122731018381227下面是二叉排序樹插入操作的遞歸算法。下面是二叉排序樹插入操作的遞歸算法。void bt_insert1(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) /在以在以bt為根的二叉排序樹上插入一個(gè)由指針為根的二叉排序樹上插入一個(gè)由指針pn指向的新的結(jié)點(diǎn)指向的新

23、的結(jié)點(diǎn) if ( *bt =NULL) *bt = pn ; else if ( *bt - key pn-key ) bt_insert 1( &(*bt - lchild) , pn ) ; else if ( *bt - key key ) bt_insert1 ( &(*bt - rchild) , pn) ;這個(gè)算法也可以用非遞歸的形式實(shí)現(xiàn)，如下所示：這個(gè)算法也可以用非遞歸的形式實(shí)現(xiàn)，如下所示：void bt_insert 2(Bin_Sort_Tree *bt , Bin_Sort_Tree_Node *pn) p = bt; while ( p != NULL &

24、amp; p - key!= pn-key) q = p; if ( p -key pn-key ) p = p - lchild; else p = p - rchild; if ( p =NULL ) if ( q -key pn - key ) q -lchild = pn; else q - rchild =pn -key; 利用二叉排序樹的插入算法，可以很容易利用二叉排序樹的插入算法，可以很容易地實(shí)現(xiàn)創(chuàng)建二叉排序樹的操作，其基本思想為地實(shí)現(xiàn)創(chuàng)建二叉排序樹的操作，其基本思想為：由一棵空二叉樹開始，經(jīng)過一系列的查找插：由一棵空二叉樹開始，經(jīng)過一系列的查找插入操作生成一棵二叉排序樹。入操作

25、生成一棵二叉排序樹。 例如，由結(jié)點(diǎn)關(guān)鍵字序列例如，由結(jié)點(diǎn)關(guān)鍵字序列 10、18、3、8、12、2、7、3 構(gòu)造二叉排序樹的過程為：從構(gòu)造二叉排序樹的過程為：從空二叉樹開始，依次將每個(gè)結(jié)點(diǎn)插入到二叉排空二叉樹開始，依次將每個(gè)結(jié)點(diǎn)插入到二叉排序樹中插入，在插入每個(gè)結(jié)點(diǎn)時(shí)都是從根結(jié)點(diǎn)序樹中插入，在插入每個(gè)結(jié)點(diǎn)時(shí)都是從根結(jié)點(diǎn)開始搜索插入位置，找到插入位置后，將新結(jié)開始搜索插入位置，找到插入位置后，將新結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入，經(jīng)過點(diǎn)作為葉子結(jié)點(diǎn)插入，經(jīng)過8次的查找和插入操次的查找和插入操作，建成由這作，建成由這8個(gè)結(jié)點(diǎn)組成的二叉排序樹。個(gè)結(jié)點(diǎn)組成的二叉排序樹。 創(chuàng)建二叉排序樹的算法如下：創(chuàng)建二叉排序樹的算

26、法如下：Bin_Sort_Tree_Node *bt_bulid (Bin_Sort_Tree a , int n) /在數(shù)組在數(shù)組a的的a1an單元中存放著將要構(gòu)成二叉排序樹的單元中存放著將要構(gòu)成二叉排序樹的n個(gè)個(gè)結(jié)點(diǎn)內(nèi)容結(jié)點(diǎn)內(nèi)容bt = NULL ; for ( i =1; i key =ai.key; p - otheritem= ai.otheritem; p - lchile = NULL; p - rchile = NULL; bt_insert1( &bt , p); return ( bt) ; 3-2. 二叉排序樹的刪除二叉排序樹的刪除 下面分四種情況討論一下如何確保

27、從二叉下面分四種情況討論一下如何確保從二叉樹中刪除一個(gè)結(jié)點(diǎn)后，不會(huì)影響二叉排序樹的樹中刪除一個(gè)結(jié)點(diǎn)后，不會(huì)影響二叉排序樹的性質(zhì)：性質(zhì)： （1）若要?jiǎng)h除的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，可以直）若要?jiǎng)h除的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，可以直接進(jìn)行刪除。接進(jìn)行刪除。 （2）若要?jiǎng)h除結(jié)點(diǎn)有右子樹，但無左子樹）若要?jiǎng)h除結(jié)點(diǎn)有右子樹，但無左子樹，可用其右子樹的根結(jié)點(diǎn)取代要?jiǎng)h除結(jié)點(diǎn)的位，可用其右子樹的根結(jié)點(diǎn)取代要?jiǎng)h除結(jié)點(diǎn)的位置。置。 （3）若要?jiǎng)h除結(jié)點(diǎn)有左子樹，但無右子樹，）若要?jiǎng)h除結(jié)點(diǎn)有左子樹，但無右子樹，可用其左子樹的根結(jié)點(diǎn)取代要?jiǎng)h除結(jié)點(diǎn)的位置，可用其左子樹的根結(jié)點(diǎn)取代要?jiǎng)h除結(jié)點(diǎn)的位置，與步驟與步驟類似。類似。 （4）若要?jiǎng)h除結(jié)點(diǎn)

28、的左右子樹均非空，則首）若要?jiǎng)h除結(jié)點(diǎn)的左右子樹均非空，則首先找到要?jiǎng)h除結(jié)點(diǎn)的右子樹中關(guān)鍵字值最小的結(jié)先找到要?jiǎng)h除結(jié)點(diǎn)的右子樹中關(guān)鍵字值最小的結(jié)點(diǎn)（即子樹中最左結(jié)點(diǎn)），利用上面的方法將該點(diǎn)（即子樹中最左結(jié)點(diǎn)），利用上面的方法將該結(jié)點(diǎn)從右子樹中刪除，并用它取代要?jiǎng)h除結(jié)點(diǎn)的結(jié)點(diǎn)從右子樹中刪除，并用它取代要?jiǎng)h除結(jié)點(diǎn)的位置，這樣處理的結(jié)果一定能夠保證刪除結(jié)點(diǎn)后位置，這樣處理的結(jié)果一定能夠保證刪除結(jié)點(diǎn)后二叉樹的性質(zhì)不變。二叉樹的性質(zhì)不變。9.2.1 .2平衡二叉樹平衡二叉樹 何謂何謂“二叉平衡樹二叉平衡樹”？ 如何構(gòu)造如何構(gòu)造“平衡二叉樹平衡二叉樹”平衡二叉樹平衡二叉樹是二叉查找樹的另一種形式，其特點(diǎn)為：

29、 樹中每個(gè)結(jié)點(diǎn)的樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之左、右子樹深度之差（平衡因子）的絕對(duì)值不大于差（平衡因子）的絕對(duì)值不大于1 1 。例如例如:548254821是平衡樹是平衡樹不是平衡樹不是平衡樹1RLhh 一般地， 假設(shè)由于在二叉樹上插入結(jié)點(diǎn)而失去平衡的最小子樹的根結(jié)點(diǎn)指針為a（即a是離插入結(jié)點(diǎn)最近，且平衡因子絕對(duì)值超過1的祖先結(jié)點(diǎn)），則失去平衡后進(jìn)行調(diào)整的規(guī)律可歸納為歸納為下列四種情況：下列四種情況：（1 1）單向右旋平衡處理：）單向右旋平衡處理：由于在由于在* *a a的的左子樹的左子樹上插入結(jié)點(diǎn)，使左子樹的左子樹上插入結(jié)點(diǎn)，使* *a a的的平衡因子由平衡因子由1 1增至增至2 2而失去平

30、衡，需進(jìn)而失去平衡，需進(jìn)行一次順時(shí)針旋轉(zhuǎn)操作；行一次順時(shí)針旋轉(zhuǎn)操作；(L-L(L-L型）型）（2 2）單向左旋平衡處理：）單向左旋平衡處理：由于在由于在* *a a的的右子樹的右子樹上插入結(jié)點(diǎn)，使右子樹的右子樹上插入結(jié)點(diǎn)，使* *a a的的平衡因子由平衡因子由-1-1減至減至-2-2而失去平衡，需而失去平衡，需進(jìn)行一次逆時(shí)針旋轉(zhuǎn)操作；進(jìn)行一次逆時(shí)針旋轉(zhuǎn)操作； (R-R(R-R型）型）798798（3 3）雙向旋轉(zhuǎn)（先左后右）平衡處理：）雙向旋轉(zhuǎn)（先左后右）平衡處理：由于在由于在* *a a的左子樹的右子樹上插入結(jié)點(diǎn)，的左子樹的右子樹上插入結(jié)點(diǎn)，使使* *a a的平衡因子由的平衡因子由1 1增至

31、增至2 2而失去平衡，而失去平衡，需進(jìn)行兩次旋轉(zhuǎn)操作需進(jìn)行兩次旋轉(zhuǎn)操作（先逆時(shí)針，后順（先逆時(shí)針，后順時(shí)針）時(shí)針）； (L-R(L-R型）型）（4 4）雙向旋轉(zhuǎn)（先右后左）平衡處理）雙向旋轉(zhuǎn)（先右后左）平衡處理: :由由于在于在* *a a的右子樹的左子樹上插入結(jié)點(diǎn)，使的右子樹的左子樹上插入結(jié)點(diǎn)，使* *a a的平衡因子由的平衡因子由-1-1減至減至-2-2而失去平衡，需而失去平衡，需進(jìn)行兩次旋轉(zhuǎn)操作進(jìn)行兩次旋轉(zhuǎn)操作（先順時(shí)針，后逆時(shí)（先順時(shí)針，后逆時(shí)針）針）；(R-L(R-L型）型） 構(gòu)造二叉平衡（查找）樹的方法是：構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。在插入過程中

32、，采用平衡旋轉(zhuǎn)技術(shù)。例如1:依次插入的關(guān)鍵字為5, 4, 2, 8, 6, 95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字 9 例例2：試求按關(guān)鍵字序列（：試求按關(guān)鍵字序列（36，23，18，42，29，25，13，21，15，19）插入生成的平衡二）插入生成的平衡二叉樹。叉樹。 3623362318362318362318423623184229362318422925362318422925362318422925133623184229251321362318422925132136231842292513211515362

33、31842292513211519362318422925131521199.2.2.1 B - 樹樹1定義定義2查找過程查找過程3插入操作插入操作4刪除操作刪除操作1 1B-B-樹的定義樹的定義B-樹是一種 平衡平衡 的 多路多路 查找查找 樹,主要用作文件的索引 root 50 15 71 84 3 8 20 26 43 56 62 78 89 96 在 m 階的B-樹上，每個(gè)非終端結(jié)點(diǎn)可能含有： n 個(gè)關(guān)鍵字關(guān)鍵字 Ki（1 in） nm n+1 個(gè)指向子樹的指針指向子樹的指針 Ai（0in）;B-樹的特性非葉結(jié)點(diǎn)中的多個(gè)關(guān)鍵字多個(gè)關(guān)鍵字均自小至大自小至大有序排列，即：K1 K2 Kn;

34、且 Ai-1 所指子樹上所有關(guān)鍵字均小于小于Ki; Ai 所指子樹上所有關(guān)鍵字均大于大于Ki; 樹中所有葉子結(jié)點(diǎn)均不帶信息，且在樹中的同一層次上; 根結(jié)點(diǎn)或?yàn)槿~子結(jié)點(diǎn)，或至少含有兩棵子樹; 其余所有非葉結(jié)點(diǎn)均至少含有m/2棵子樹，至多含有 m 棵子樹; 從根結(jié)點(diǎn)出發(fā)，沿指針?biāo)阉鹘Y(jié)點(diǎn)搜索結(jié)點(diǎn)和在在結(jié)點(diǎn)內(nèi)進(jìn)行結(jié)點(diǎn)內(nèi)進(jìn)行順序（或折半）查找查找 兩個(gè)過程交叉進(jìn)行。2.查找過程：查找過程： 若查找成功查找成功，則返回指向返回指向被查關(guān)鍵字所在結(jié)點(diǎn)的指針結(jié)點(diǎn)的指針和關(guān)鍵字在結(jié)點(diǎn)中的位置關(guān)鍵字在結(jié)點(diǎn)中的位置；若查找不成功查找不成功，則返回插入位置返回插入位置。在查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入插

35、入的位置位置必定在最下最下層的非葉結(jié)點(diǎn)層的非葉結(jié)點(diǎn)，有下列幾種情況：3插入插入1）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)nm， 不修改指針; 2）插入后，該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) n=m， 則需進(jìn)行“結(jié)點(diǎn)分裂”，令 s = m/2， 在原結(jié)點(diǎn)中保留 （A0，K1，。， Ks-1，As-1）； 建新結(jié)點(diǎn) （As，Ks+1，。 ，Kn，An）； 將Ks插入雙親結(jié)點(diǎn)；3）若雙親為空，則建新的根結(jié)點(diǎn)。例如:下列為 3 階B-樹50 20 40 80 插入關(guān)鍵字 = 60, 60 80 90, 60 80 90 90 50 80 60 30, 40 20 30 50 808030 50 和插入的考慮相反，首先必須找到待刪

36、關(guān)鍵字所在結(jié)點(diǎn)，并且要求刪除之后，結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)不能小于m/2-1，否則，要從其左(或右)兄弟結(jié)點(diǎn)“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點(diǎn)均無關(guān)鍵字可借(結(jié)點(diǎn)中只有最少量的關(guān)鍵字),則必須進(jìn)行結(jié)點(diǎn)的“合并”。4刪除刪除是是B-樹的一種變型樹的一種變型9.2.2.2 B+樹樹1一棵一棵m階的階的B+樹的結(jié)構(gòu)特點(diǎn)：樹的結(jié)構(gòu)特點(diǎn)： 有n棵子樹的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字。 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息及指向含這些關(guān)鍵字記錄的指針；并且，所有葉子葉子結(jié)點(diǎn)彼此相鏈接鏈接構(gòu)成一個(gè)有序鏈表，其頭指針指向含最小關(guān)鍵字的結(jié)點(diǎn)； 每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵字 Ki 即為其相應(yīng)指針 Ai 所指子樹中關(guān)鍵字的最大值； 所

37、有葉子結(jié)點(diǎn)都處在同一層次上，每個(gè)葉子結(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)均介于 m/2和 m 之間。 50 96 15 5062 78 96 71 788 4 8 9 96 56 6220 26 43 50 3 8 15sqroot2查找過程查找過程 在查找時(shí)，不管成功與否，都必須查到葉子結(jié)點(diǎn)才能結(jié)束；即每次查找都是走了一條從根到葉子結(jié)點(diǎn)的路徑 在結(jié)點(diǎn)內(nèi)查找時(shí)，若給定值Ki， 則 應(yīng)繼續(xù)在 Ai 所指子樹中進(jìn)行查找；3插入和刪除的操作插入和刪除的操作類似于類似于B-樹進(jìn)行，即必要時(shí)，樹進(jìn)行，即必要時(shí)，也需要進(jìn)行結(jié)點(diǎn)的也需要進(jìn)行結(jié)點(diǎn)的“分裂分裂”或或“歸并歸并”。9.3.1 基本概念基本概念哈希函數(shù)，沖突哈希函數(shù)

38、，沖突9.3 哈希（哈希（HSAE）表（散列查找）表（散列查找） 哈希表技術(shù)的主要目標(biāo)是提高查找效率，哈希表技術(shù)的主要目標(biāo)是提高查找效率，即縮短查表和填表的時(shí)間。即縮短查表和填表的時(shí)間。 前面介紹的靜態(tài)查找表和動(dòng)態(tài)查找表的特前面介紹的靜態(tài)查找表和動(dòng)態(tài)查找表的特點(diǎn)是：為了從查找表中找到關(guān)鍵字值等于某個(gè)點(diǎn)是：為了從查找表中找到關(guān)鍵字值等于某個(gè)值的記錄，都要經(jīng)過一系列的關(guān)鍵字值的記錄，都要經(jīng)過一系列的關(guān)鍵字比較比較，以，以確定待查記錄的存儲(chǔ)位置或查找失敗，查找所確定待查記錄的存儲(chǔ)位置或查找失敗，查找所需時(shí)間總是與需時(shí)間總是與比較次數(shù)比較次數(shù)有關(guān)。有關(guān)。 如果將記錄的存儲(chǔ)位置與它的關(guān)鍵字之間如果將記錄

39、的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的關(guān)系建立一個(gè)確定的關(guān)系H，使每個(gè)關(guān)鍵字和一個(gè)使每個(gè)關(guān)鍵字和一個(gè)唯一的存儲(chǔ)位置對(duì)應(yīng)，唯一的存儲(chǔ)位置對(duì)應(yīng)，在查找時(shí)，只需要根據(jù)在查找時(shí)，只需要根據(jù)對(duì)應(yīng)關(guān)系計(jì)算出給定的關(guān)鍵字值對(duì)應(yīng)關(guān)系計(jì)算出給定的關(guān)鍵字值k對(duì)應(yīng)的值對(duì)應(yīng)的值H(k)，就可以得到記錄的存儲(chǔ)位置，就可以得到記錄的存儲(chǔ)位置，這就是本這就是本節(jié)將要介紹的哈希表查找方法的基本思想。節(jié)將要介紹的哈希表查找方法的基本思想。 哈希函數(shù)：哈希函數(shù)：我們將記錄的關(guān)鍵字值與記錄我們將記錄的關(guān)鍵字值與記錄的存儲(chǔ)位置對(duì)應(yīng)起來的關(guān)系的存儲(chǔ)位置對(duì)應(yīng)起來的關(guān)系H稱為哈希函數(shù)，稱為哈希函數(shù)，H(k)的結(jié)果稱為的結(jié)果稱為哈希地址哈

40、希地址。 哈希表：哈希表：是根據(jù)哈希函數(shù)建立的表，其基是根據(jù)哈希函數(shù)建立的表，其基本思想是：以記錄的關(guān)鍵字值為自變量，根據(jù)本思想是：以記錄的關(guān)鍵字值為自變量，根據(jù)哈希函數(shù)，計(jì)算出對(duì)應(yīng)的哈希地址，并在此存哈希函數(shù)，計(jì)算出對(duì)應(yīng)的哈希地址，并在此存儲(chǔ)該記錄的內(nèi)容。當(dāng)對(duì)記錄進(jìn)行查找時(shí)，再根儲(chǔ)該記錄的內(nèi)容。當(dāng)對(duì)記錄進(jìn)行查找時(shí)，再根據(jù)給定的關(guān)鍵字值，用同一個(gè)哈希函數(shù)計(jì)算出據(jù)給定的關(guān)鍵字值，用同一個(gè)哈希函數(shù)計(jì)算出給定關(guān)鍵字值對(duì)應(yīng)的存儲(chǔ)地址，隨后進(jìn)行訪問給定關(guān)鍵字值對(duì)應(yīng)的存儲(chǔ)地址，隨后進(jìn)行訪問。所以哈希表即是一種。所以哈希表即是一種存儲(chǔ)形式存儲(chǔ)形式，又是一種，又是一種查查找方法找方法，通常將這種查找方法稱為，

41、通常將這種查找方法稱為哈希查找哈希查找。 沖突：沖突：有時(shí)可能會(huì)出現(xiàn)不同的關(guān)鍵字值其有時(shí)可能會(huì)出現(xiàn)不同的關(guān)鍵字值其哈希函數(shù)計(jì)算的哈希地址相同的情況，然而同哈希函數(shù)計(jì)算的哈希地址相同的情況，然而同一個(gè)存儲(chǔ)位置不可能存儲(chǔ)兩個(gè)記錄，我們將這一個(gè)存儲(chǔ)位置不可能存儲(chǔ)兩個(gè)記錄，我們將這種情況稱為沖突，具有相同函數(shù)值的關(guān)鍵字值種情況稱為沖突，具有相同函數(shù)值的關(guān)鍵字值稱為稱為同義詞同義詞。在實(shí)際應(yīng)用中沖突是不可能完全。在實(shí)際應(yīng)用中沖突是不可能完全避免的，人們通過實(shí)踐總結(jié)出了多種減少?zèng)_突避免的，人們通過實(shí)踐總結(jié)出了多種減少?zèng)_突及解決沖突的方法。下面我們將簡(jiǎn)要地介紹一及解決沖突的方法。下面我們將簡(jiǎn)要地介紹一下。下

42、。312726211916130911050102H(K)=int(K/3)+1121110987654321表項(xiàng)序號(hào)根據(jù)關(guān)鍵字直接計(jì)算出元素所在位置的函數(shù)。根據(jù)關(guān)鍵字直接計(jì)算出元素所在位置的函數(shù)。例如：設(shè)哈希函數(shù)為：例如：設(shè)哈希函數(shù)為： int(K/3)+1 int(K/3)+1則構(gòu)造則構(gòu)造 0101、0202、0505、0909、1111、1313、1616、1919、2121、2626、2727、3131、的散列表的散列表( (哈希表）為：哈希表）為：哈希函數(shù)：哈希函數(shù)：沖突：沖突：兩個(gè)不同的關(guān)鍵字具有相同的存儲(chǔ)位置。兩個(gè)不同的關(guān)鍵字具有相同的存儲(chǔ)位置。 為了有效地使用散列技術(shù)，需要解決

43、兩方為了有效地使用散列技術(shù)，需要解決兩方面的問題：面的問題： （1）構(gòu)造）構(gòu)造好的哈希函數(shù)好的哈希函數(shù)，使沖突的現(xiàn)象，使沖突的現(xiàn)象盡可能的少；盡可能的少； （2）設(shè)計(jì)有效的）設(shè)計(jì)有效的解決沖突的方法解決沖突的方法。二、構(gòu)造哈希函數(shù)的方法構(gòu)造哈希函數(shù)的方法 好的哈希函數(shù)應(yīng)能使任意一個(gè)關(guān)鍵字得到好的哈希函數(shù)應(yīng)能使任意一個(gè)關(guān)鍵字得到一個(gè)隨機(jī)的地址，以便使一組關(guān)鍵字的哈希一個(gè)隨機(jī)的地址，以便使一組關(guān)鍵字的哈希地址均勻分布在整個(gè)地址區(qū)間中，從而減少地址均勻分布在整個(gè)地址區(qū)間中，從而減少?zèng)_突。沖突。對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法對(duì)數(shù)字的關(guān)鍵字可有下列構(gòu)造方法: 若是非數(shù)字關(guān)鍵字非數(shù)字關(guān)鍵字，則需先需先對(duì)其

44、進(jìn)行進(jìn)行數(shù)字化處理數(shù)字化處理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余數(shù)除留余數(shù)法法4. 折疊法折疊法6. 隨機(jī)數(shù)法隨機(jī)數(shù)法2. 數(shù)字分析法數(shù)字分析法哈希函數(shù)為關(guān)鍵字的線性函數(shù) H(key) = key 或者 H(key) = a key + b例見例見P253 。 此法中：此法中：地址集合的大小地址集合的大小 = = 關(guān)鍵字集合的大小關(guān)鍵字集合的大小不會(huì)產(chǎn)生沖突。但實(shí)際使用很少。不會(huì)產(chǎn)生沖突。但實(shí)際使用很少。1. 直接定址法直接定址法此方法僅適合于：此方法僅適合于： 能預(yù)先估計(jì)出預(yù)先估計(jì)出全體關(guān)鍵字的每一位上每一位上各種數(shù)字出現(xiàn)的頻度數(shù)字出現(xiàn)的頻度。2. 數(shù)字分析法數(shù)

45、字分析法 假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由 s 位數(shù)字組成 (u1, u2, , us)，分析關(guān)鍵字集中的全體， 并從中提取分布均勻的若干位或它們的組合作為地址。例見例見P254。關(guān)鍵字為。關(guān)鍵字為8位十位十進(jìn)制數(shù)進(jìn)制數(shù) 以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值” 的目的是“擴(kuò)大差別” ，同時(shí)平方值的中間各位又能受到整個(gè)關(guān)鍵字中各位的影響。3. 平方取中法平方取中法 此方法適合于此方法適合于: 關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。例見例見P255圖圖9.23 將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加移位疊加和間界疊

46、加間界疊加。4. 折疊法折疊法 此方法適合于此方法適合于: 關(guān)鍵字的數(shù)字位數(shù)特別多。國(guó)際標(biāo)準(zhǔn)圖書編號(hào)：國(guó)際標(biāo)準(zhǔn)圖書編號(hào)：0-442-20586-4以其為關(guān)鍵字建立哈希表。以其為關(guān)鍵字建立哈希表。5864422004+10088H(key)=00885864022404+6092H(key)=6092間界疊加間界疊加移位疊加移位疊加5. 除留余數(shù)法除留余數(shù)法 設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = key MOD p 其中其中， pm ( (表長(zhǎng)表長(zhǎng)) ) 并且并且 p 應(yīng)為不大于應(yīng)為不大于 m 的素?cái)?shù)的素?cái)?shù)以減少?zèng)_突的發(fā)生。以減少?zèng)_突的發(fā)生。 給定一組關(guān)鍵字為: 12, 39, 18

47、, 24, 33, 21，若取 p=9, 則他們對(duì)應(yīng)的哈希函數(shù)值將為: 3, 3, 0, 6, 6, 3例如：例如：為什么要對(duì) p 加限制？ 可見，因 p 可被 3整除, 所以所有含所以所有含3的的倍數(shù)的關(guān)鍵字均映射到倍數(shù)的關(guān)鍵字均映射到“3 的倍數(shù)的倍數(shù)”的地的地址上址上，從而增加了“沖突”的可能。6.隨機(jī)數(shù)法隨機(jī)數(shù)法設(shè)定哈希函數(shù)為設(shè)定哈希函數(shù)為: H(key) = Random(key)其中，其中，Random 為偽隨機(jī)函數(shù)為偽隨機(jī)函數(shù) 通常，此方法用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。 實(shí)際造表時(shí)，采用何種采用何種構(gòu)造哈希函數(shù)的方法方法取決于建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài))

48、，總的原則是使產(chǎn)生沖突的可能性降到的原則是使產(chǎn)生沖突的可能性降到盡可能地小盡可能地小。三、處理沖突的方法處理沖突的方法 “處理沖突處理沖突” 的實(shí)際含義是：為產(chǎn)生沖突的地址尋找下一個(gè)尋找下一個(gè)哈希地址2. 再哈希法再哈希法 3. 鏈地址法鏈地址法1. 開放定址法開放定址法 4. 建立一個(gè)公共溢出區(qū)建立一個(gè)公共溢出區(qū) 為產(chǎn)生沖突的地址 H(key) 求得一個(gè)地址序列地址序列： H0, H1, H2, , , Hs 1 sm-1其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, , s1. 開放定址法開放定址法對(duì)增量 di 有三種取法： 1) 1)

49、線性探測(cè)再散列線性探測(cè)再散列 di = c i 最簡(jiǎn)單的情況 c=1 2) 2) 平方探測(cè)再散列平方探測(cè)再散列 di = 12, -12, 22, -22, , 3) 3) 隨機(jī)探測(cè)再散列隨機(jī)探測(cè)再散列 di 是一組偽隨機(jī)數(shù)列是一組偽隨機(jī)數(shù)列即：產(chǎn)生的 Hi 均不相同，且所產(chǎn)生的 Hi 值能覆蓋覆蓋哈希表中所有 地址。注意：注意：增量增量 di 應(yīng)具有應(yīng)具有“完備性完備性”1 . 開放定址法開放定址法 設(shè)散列函數(shù)設(shè)散列函數(shù) H（k）=k MOD m （m為表長(zhǎng)為表長(zhǎng), 設(shè)設(shè)m=11)若發(fā)生沖突，設(shè)發(fā)生沖突的地址為若發(fā)生沖突，設(shè)發(fā)生沖突的地址為 p , 則沿著一個(gè)則沿著一個(gè)探查序列逐個(gè)探查，那么

50、，探查的地址序列為探查序列逐個(gè)探查，那么，探查的地址序列為P+1, P+2, P+3 , m-1 , 0, 1, , P-1. 29 17 600 1 2 3 4 5 6 7 8 9 10 1 . 開放定址法開放定址法 設(shè)散列函數(shù)設(shè)散列函數(shù) H（K）=K MOD m （m為表長(zhǎng)）為表長(zhǎng)） 若發(fā)生沖突，則沿著一個(gè)探查序列逐個(gè)探查，那么，第若發(fā)生沖突，則沿著一個(gè)探查序列逐個(gè)探查，那么，第i次次計(jì)算沖突的散列地址為：計(jì)算沖突的散列地址為：Hi=(H(K)+di)MOD m (di=1,2,m-1，i=1,2,F(F=m-1) 0 1 2 3 4 5 6 7 8 9 10設(shè)設(shè)散列函數(shù)散列函數(shù) H(k)=k MOD 11H(k)=k MOD 11求：求： 6060、1717、2929、3838在散列表中的位置。在散列表中的位置。H(60)= 60 mod 11 = 5 H(60)= 60 mod 11 = 5 H(17)= 17 mod 11 = 6H(17)= 17 mod 11 = 6H(29)= 29 mod 11 = 7H(29)= 29 mod 11 = 7H(38)= 38 mod 11 = 5H(38)= 38 mod 11 = 5（沖突）（沖突）H(38+1)=H(38+1)=（5+15+1） mod 11 = 6 mod 1