7.1查找的基本概念

7.2靜態(tài)查找表

7.3動(dòng)態(tài)查找表

7.4哈希表查找

小結(jié)

習(xí)題

實(shí)訓(xùn)指導(dǎo)第7章查找

問(wèn)題引入

查找是我們生活和工作中遇到的非常普遍的事情，例如，在學(xué)生成績(jī)表中查找某位學(xué)生的成績(jī)記錄，在圖書(shū)館的書(shū)目中查找我們需要的書(shū)，在互聯(lián)網(wǎng)上查找關(guān)于某個(gè)問(wèn)題的相關(guān)信息，等等。我們現(xiàn)在將大量的信息存儲(chǔ)在計(jì)算機(jī)中，那么，要使這些信息為我們所用，采用什么方法才能方便、高效、準(zhǔn)確地找到這些信息呢？這是值得研究、探討和學(xué)習(xí)的。

知識(shí)要點(diǎn)

(1)查找的基本概念；

(2)順序查找、二分查找的條件和算法；

(3)索引查找的方法；

(4)二叉排序樹(shù)插入、刪除和查找的算法；

(5)哈希查找的思想方法和解決沖突的方法。

能力要求

能根據(jù)實(shí)際問(wèn)題的需要，結(jié)合應(yīng)用條件，靈活運(yùn)用各種查找算法，高效地解決實(shí)際問(wèn)題。

查找是對(duì)數(shù)據(jù)進(jìn)行操作或處理時(shí)經(jīng)常使用的操作。查找是在一個(gè)數(shù)據(jù)元素集合中查找關(guān)鍵字等于某個(gè)給定值的過(guò)程。在一個(gè)數(shù)據(jù)元素集合中進(jìn)行查找的方法很多，主要有靜態(tài)查找、動(dòng)態(tài)查找和哈希查找等方法。計(jì)算機(jī)應(yīng)用系統(tǒng)中大約有40%的運(yùn)算與查找有關(guān)，因此查找算法的優(yōu)劣對(duì)應(yīng)用系統(tǒng)的效率影響很大。7.1查找的基本概念查找總是在一定的范圍內(nèi)進(jìn)行的。我們把同一類型的數(shù)據(jù)元素的集合稱作查找表。數(shù)據(jù)元素通常由多個(gè)數(shù)據(jù)項(xiàng)組成，數(shù)據(jù)項(xiàng)也叫關(guān)鍵字。在數(shù)據(jù)元素中，有些關(guān)鍵字能夠唯一地標(biāo)識(shí)數(shù)據(jù)元素，這樣的數(shù)據(jù)項(xiàng)稱作主關(guān)鍵字；而不能唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字稱作次關(guān)鍵字。查找就是根據(jù)給定值，在查找表中確定是否存在數(shù)據(jù)元素，該數(shù)據(jù)元素的關(guān)鍵字值等于給定值的過(guò)程。按照主關(guān)鍵字進(jìn)行查找是最經(jīng)常，也是最主要的查找。在一個(gè)查找表上進(jìn)行查找，結(jié)果無(wú)非是兩種：查找成功和查找失敗。查找成功指的是在查找表中找到了要查找的數(shù)據(jù)元素；查找失敗指的是在查找表中沒(méi)有找到要查找的數(shù)據(jù)元素。根據(jù)查找是否涉及外存儲(chǔ)器，可以把查找分為內(nèi)查找和外查找。所謂的內(nèi)查找，指的是整個(gè)查找過(guò)程都在內(nèi)存中進(jìn)行，不涉及外存儲(chǔ)器；反之，如果查找過(guò)程中涉及外存儲(chǔ)器，則稱為外查找。在本章中，我們主要討論內(nèi)查找。根據(jù)查找的目的，查找可以分為靜態(tài)查找和動(dòng)態(tài)查找兩大類。如果查找的目的只是為了確定在查找表中是否存在特定的數(shù)據(jù)元素，而不改動(dòng)數(shù)據(jù)元素，則這樣的查找稱為靜態(tài)查找，相應(yīng)地把以實(shí)現(xiàn)靜態(tài)查找為目的而構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為靜態(tài)查找表。如果查找的目的是為了增加或者刪除某個(gè)數(shù)據(jù)元素，例如查找失敗時(shí)增加數(shù)據(jù)元素，查找成功時(shí)刪除數(shù)據(jù)元素，則這樣的查找稱為動(dòng)態(tài)查找，相應(yīng)地把以實(shí)現(xiàn)動(dòng)態(tài)查找為目的而構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為動(dòng)態(tài)查找表。衡量查找算法效率的指標(biāo)主要是平均查找長(zhǎng)度。平均查找長(zhǎng)度指的是查找過(guò)程所需進(jìn)行的關(guān)鍵字比較的次數(shù)的平均值。平均查找長(zhǎng)度通常記作ASL，它的數(shù)學(xué)定義為其中，n為查找表中數(shù)據(jù)元素的個(gè)數(shù)；Pi為查找第i個(gè)數(shù)據(jù)元素的概率，通常認(rèn)為Pi?=?1/n，即每個(gè)數(shù)據(jù)元素的查找概率都是相同的；Ci為查找第i個(gè)數(shù)據(jù)元素所需要的比較次數(shù)。查找成功和查找失敗的平均查找長(zhǎng)度通常是不一樣的，查找成功時(shí)的平均查找長(zhǎng)度用ASL成功?表示，查找失敗時(shí)的平均查找長(zhǎng)度用ASL失敗?表示。7.2靜?態(tài)?查?找?表

靜態(tài)查找表按照所施加查找算法的不同，采用不同的存儲(chǔ)結(jié)構(gòu)。靜態(tài)查找表適用的查找算法主要有順序查找、折半查找和分塊查找三種。7.2.1順序查找順序查找又稱線性查找，是最基本的查找方法。采用順序查找算法時(shí)，查找表的存儲(chǔ)結(jié)構(gòu)可以是順序表，也可以是單鏈表。

結(jié)構(gòu)7-1

靜態(tài)查找表的順序表存儲(chǔ)描述。#defineMaxsize100typedefintKeytype; //關(guān)鍵字類型typedefstruct{Keytypeelem[Maxsize];intlength; //表長(zhǎng)度，即存放數(shù)據(jù)元素的個(gè)數(shù)}S_TBL；

結(jié)構(gòu)7-2靜態(tài)查找表的單鏈表存儲(chǔ)描述。

typedefintKeytype; //關(guān)鍵字類型

typedefstructnode

{

Keytypeelem;

structnode*next;

}

Nodetype,*L_TBL;順序查找的基本思想是：從表的一端開(kāi)始，用給定數(shù)據(jù)元素的關(guān)鍵字值逐個(gè)和順序表中的每個(gè)數(shù)據(jù)元素的關(guān)鍵字進(jìn)行比較，若與某個(gè)數(shù)據(jù)元素的關(guān)鍵字相等，則查找成功，給出數(shù)據(jù)元素在順序表中的位置；若整個(gè)表中的數(shù)據(jù)元素一一比較完后，仍未找到與給定關(guān)鍵字值相同的數(shù)據(jù)元素，則查找失敗，給出失敗信息。在順序表tbl中查找關(guān)鍵字為key的數(shù)據(jù)元素，若找到，則返回該元素在順序表中的下標(biāo)，否則返回-1，算法如下：

算法7-1

順序表上的順序查找。

ints_search(S_TBLtbl,Keytypekey)

{

inti;

for(i=0;i<tbl.length;i++)

if(tbl.elem[i]==key)

returni;

return-1;

}在單鏈表存儲(chǔ)的查找表tbl中查找關(guān)鍵字為key的數(shù)據(jù)元素，若找到，則返回該元素存儲(chǔ)結(jié)點(diǎn)地址，否則返回null，算法如下：

算法7-2單鏈表上的順序查找。

Nodetype*l_search(L_TBLtbl,Keytypekey)

{

Nodetype*p=tbl;

while(p!=NULL)

{if(p->elem==key)

returnp;

p=p->next;

}

returnNULL;

}對(duì)于有n個(gè)數(shù)據(jù)元素的查找表，設(shè)每個(gè)數(shù)據(jù)元素的查找概率相等，即Pi?=?1/n；給定值key與表中第i個(gè)元素關(guān)鍵字相等，即定位第i個(gè)記錄時(shí)，需進(jìn)行i次關(guān)鍵字比較，即Ci?=?i。則查找成功時(shí)，順序查找的平均查找長(zhǎng)度為查找不成功時(shí)，關(guān)鍵字的比較次數(shù)總是n次。算法中的基本操作就是關(guān)鍵字的比較，因此，查找長(zhǎng)度的量級(jí)就是查找算法的時(shí)間復(fù)雜度，為O(n)。許多情況下，查找表中數(shù)據(jù)元素的查找概率是不相等的。為了提高查找效率，查找表需依據(jù)查找概率越高，比較次數(shù)越少，查找概率越低，比較次數(shù)就越多的原則來(lái)存儲(chǔ)數(shù)據(jù)元素。順序查找的缺點(diǎn)是當(dāng)n很大時(shí)，平均查找長(zhǎng)度較大，效率低；優(yōu)點(diǎn)是對(duì)表中數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)沒(méi)有要求。另外，對(duì)于鏈?zhǔn)酱鎯?chǔ)的靜態(tài)查找表，只能進(jìn)行順序查找。

7.2.2折半查找折半查找是一種效率比較高的的查找算法，但是它對(duì)查找表的存儲(chǔ)結(jié)構(gòu)有特殊的要求：首先要求查找表必須采用順序表存儲(chǔ)結(jié)構(gòu)，其次要求數(shù)據(jù)元素在順序表中必須按照關(guān)鍵字的值升序排列。折半查找的基本思想是：在有序的順序表中，取中間位置的元素作為比較對(duì)象，若給定值與中間元素的關(guān)鍵字相等，則查找成功；若給定值小于中間元素的關(guān)鍵字，則在表的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵字，則在表的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過(guò)程，直到查找成功，或所查找的區(qū)域?yàn)榭諘r(shí)查找失敗。折半查找的步驟如下：

(1)設(shè)置初始查找區(qū)間：low=1，high=length；

(2)當(dāng)low>high時(shí)，查找區(qū)間為空，查找失敗，結(jié)束查找；

(3)當(dāng)low≤high時(shí)，取查找區(qū)間中間位置mid=(low+high)/2，若①?key<tbl.elem[mid]，縮小查找區(qū)間為原區(qū)間的左半?yún)^(qū)，即high=mid-1，轉(zhuǎn)(2)；②?key>tbl.elem[mid]，縮小查找區(qū)間為原區(qū)間的右半?yún)^(qū)，即low=mid+1，轉(zhuǎn)(2)；③?key=tbl.elem[mid]，返回?cái)?shù)據(jù)元素在表中位置，查找成功。

實(shí)例7-1

有序表按關(guān)鍵字排列如下：在表中查找關(guān)鍵字為14和22的數(shù)據(jù)元素。

(1)查找關(guān)鍵字為14的數(shù)據(jù)元素的過(guò)程如圖7-1所示。

(2)查找關(guān)鍵字為22的數(shù)據(jù)元素的過(guò)程如圖7-2所示。圖7-1查找關(guān)鍵字為14的數(shù)據(jù)元素的過(guò)程圖7-2查找關(guān)鍵字為22的數(shù)據(jù)元素的過(guò)程

算法7-3

折半查找法。在表tbl中查找關(guān)鍵字為key的數(shù)據(jù)元素，若找到則返回該元素在表中的位置，否則返回0。

intBinary_Search(S_TBLtbl,Keytypekey)

{intmid,flag=0,low,high;

low=1;high=tbl.length; //設(shè)置初始區(qū)間

while(low<=high) //表空測(cè)試

{ //非空，進(jìn)行比較測(cè)試

mid=(low+high)/2;//得到中點(diǎn)

if(key<tbl.elem[mid]) high=mid-1;//調(diào)整到左半?yún)^(qū)

elseif(key>tbl.elem[mid])low=mid+1; //調(diào)整到右半?yún)^(qū)

else{flag=mid;break;} //查找成功，元素位置設(shè)置到flag中

}returnflag;}從折半查找過(guò)程看，以表的中點(diǎn)為比較對(duì)象，并以中點(diǎn)將表分割為兩個(gè)子表，對(duì)定位到的子表繼續(xù)這種操作。所以，對(duì)表中每個(gè)數(shù)據(jù)元素的查找過(guò)程，可用二叉樹(shù)來(lái)描述，我們稱這個(gè)描述查找過(guò)程的二叉樹(shù)為判定樹(shù)，如圖7-3所示。圖7-3折半查找過(guò)程的判定樹(shù)可以看到，查找表中任一元素的過(guò)程，即是判定樹(shù)中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)鍵字的比較次數(shù)，也即該元素結(jié)點(diǎn)在樹(shù)中的層次數(shù)。對(duì)于n個(gè)結(jié)點(diǎn)的判定樹(shù)，樹(shù)的深度為k，則有2k-1-1<n≤2k-1，即k-1≤log2n<k，所以k=。因此，折半查找在查找成功時(shí)，所進(jìn)行的關(guān)鍵字的比較次數(shù)至多為。接下來(lái)討論折半查找的平均查找長(zhǎng)度。為便于討論，以樹(shù)深度為k的滿二叉樹(shù)(n?=?2k-1)為例。假設(shè)表中每個(gè)元素的查找是等概率的，則樹(shù)的第i層有2i-1個(gè)結(jié)點(diǎn)，因此，折半查找的平均查找長(zhǎng)度為所以，折半查找的時(shí)間效率為O(log2n)。7.2.3分塊查找分塊查找又稱為索引順序查找，其性能介于順序查找和折半查找之間。分塊查找要求把表分成若干塊，每一塊中的關(guān)鍵字值存儲(chǔ)順序是任意的，但要求“分塊有序”，即前一塊中的最大關(guān)鍵字值小于后一塊中最小關(guān)鍵字值。也就是所謂的塊間有序，塊內(nèi)無(wú)序。另外，還需要建立一個(gè)索引表，索引表中的每一項(xiàng)對(duì)應(yīng)表的一塊。索引項(xiàng)由關(guān)鍵字域和鏈域組成，關(guān)鍵字域存放對(duì)應(yīng)塊內(nèi)結(jié)點(diǎn)的最大關(guān)鍵字值，鏈域存放對(duì)應(yīng)塊首結(jié)點(diǎn)的地址。索引表中的索引項(xiàng)按關(guān)鍵字值遞增順序存放。如圖7-4所示為一個(gè)索引順序表。其中包括三個(gè)塊，第一個(gè)塊的起始地址為0，塊內(nèi)最大關(guān)鍵字為25；第二個(gè)塊的起始地址為5，塊內(nèi)最大關(guān)鍵字為58；第三個(gè)塊的起始地址為10，塊內(nèi)最大關(guān)鍵字為99。圖7-4索引順序表分塊查找的基本過(guò)程如下：

(1)首先，將待查關(guān)鍵字key與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。具體的可用順序查找法或折半查找法進(jìn)行。

(2)進(jìn)一步用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為key的元素。例如，在上述索引順序表中查找36。首先，將36與索引表中的關(guān)鍵字進(jìn)行比較，因?yàn)?5<36≤58，所以36在第二個(gè)塊中，進(jìn)一步在第二個(gè)塊中順序查找，最后在8號(hào)單元中找到36。分塊查找的查找過(guò)程包括了在索引表上的查找和在主表上的查找兩部分，所以分塊查找的比較次數(shù)等于在索引表上的查找次數(shù)，再加上在主表的某個(gè)子表中進(jìn)行查找的比較次數(shù)。假設(shè)索引表的長(zhǎng)度為m，主表中每個(gè)子表的長(zhǎng)度為s，并假設(shè)在索引表和主表上均采用順序查找算法，則分塊查找的平均查找長(zhǎng)度為7.3動(dòng)?態(tài)?查?找?表

動(dòng)態(tài)查找就是在查找的過(guò)程中插入或者刪除數(shù)據(jù)元素結(jié)點(diǎn)。為了便于插入和刪除，通常將數(shù)據(jù)元素組織成特定樹(shù)的形式，以鏈表作為其存儲(chǔ)結(jié)構(gòu)。本節(jié)就以二叉排序樹(shù)為例，說(shuō)明動(dòng)態(tài)查找表的應(yīng)用。7.3.1二叉排序樹(shù)二叉排序樹(shù)又稱為二叉查找樹(shù)，它是一種特殊結(jié)構(gòu)的二叉樹(shù)，其定義為：二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：

(1)若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

(2)若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

(3)它的左右子樹(shù)也分別為二叉排序樹(shù)。這是一個(gè)遞歸定義。由定義可以得出二叉排序樹(shù)的一個(gè)重要性質(zhì)：中序遍歷一個(gè)二叉排序樹(shù)時(shí)可以得到一個(gè)遞增有序序列。如圖7-5所示的二叉樹(shù)就是一棵二叉排序樹(shù)，若中序遍歷圖7-5所示的二叉排序樹(shù)，則可得到一個(gè)遞增有序序列：1，2，3，4，5，6，7，8，9。

圖7-5二叉排序樹(shù)在下面討論二叉排序樹(shù)的操作中，使用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，其存儲(chǔ)結(jié)構(gòu)描述如下。

結(jié)構(gòu)7-3

二叉排序樹(shù)結(jié)點(diǎn)及頭指針類型。

typedefintKeytype; //關(guān)鍵字類型

typedefstructnode

{Keytypekey; //關(guān)鍵字的值

structnode*lchild,*rchild; //左右子樹(shù)指針

}BSTNode,*BSTree;7.3.2二叉排序樹(shù)的插入和生成已知一個(gè)關(guān)鍵字值為key的結(jié)點(diǎn)s，要將其插入到二叉排序樹(shù)中，只要保證插入后仍符合二叉排序樹(shù)的定義即可。插入可以用下面的方法進(jìn)行：

(1)若二叉排序樹(shù)是空樹(shù)，則以結(jié)點(diǎn)s作為二叉排序樹(shù)的根；

(2)若二叉排序樹(shù)非空，則將key與二叉排序樹(shù)的根進(jìn)行比較，如果key的值等于根結(jié)點(diǎn)的值，則說(shuō)明二叉排序樹(shù)中已經(jīng)存在該數(shù)據(jù)元素，無(wú)需插入；如果key的值小于根結(jié)點(diǎn)的值，則將結(jié)點(diǎn)s插入左子樹(shù)中；如果key的值大于根結(jié)點(diǎn)的值，則將結(jié)點(diǎn)s插入右子樹(shù)中。相應(yīng)的遞歸算法如下：

算法7-4

二叉排序樹(shù)插入。在以bst為根的二叉排序樹(shù)中，查找關(guān)鍵字為key的結(jié)點(diǎn)，如果查找失敗，則插入關(guān)鍵字為key的結(jié)點(diǎn)，使用遞歸算法。

voidInsertBST(BSTree*bst,Keytypekey)

{BSTrees;

if(*bst==NULL)

{s=(BSTree)malloc(sizeof(BSTNode)); //申請(qǐng)新的結(jié)點(diǎn)s

s->key=key;

s->lchild=NULL;s->rchild=NULL;*bst=s;

}

elseif(key<(*bst)->key)

InsertBST(&((*bst)->lchild),key);//將s插入左子樹(shù)

elseif(key>(*bst)->key)

InsertBST(&((*bst)->rchild),key);//將s插入右子樹(shù)

}可以看出，二叉排序樹(shù)的插入，即構(gòu)造一個(gè)葉子結(jié)點(diǎn)，將其插到二叉排序樹(shù)的合適位置，以保證二叉排序樹(shù)性質(zhì)不變。插入時(shí)不需要移動(dòng)元素。假若給定一個(gè)元素序列，我們可以利用上述算法創(chuàng)建一棵二叉排序樹(shù)。首先，將二叉排序樹(shù)初始化為一棵空樹(shù)，然后逐個(gè)讀入元素，每讀入一個(gè)元素，就將其插入到當(dāng)前已生成的二叉排序樹(shù)中，即調(diào)用上述二叉排序樹(shù)的插入算法將新結(jié)點(diǎn)插入。生成二叉排序樹(shù)的算法如下：

算法7-5生成二叉排序樹(shù)。從鍵盤(pán)輸入若干個(gè)數(shù)據(jù)元素的值，以-1為結(jié)束標(biāo)志，生成二叉排序樹(shù)。

voidCreateBST(BSTree*bst)

{Keytypekey;

*bst=NULL;

printf("輸入若干個(gè)正整數(shù),以-1結(jié)束輸入\n");

scanf("%d",&key);

while(key!=-1)

{InsertBST(&bst,key);

scanf("%d",&key);

}

}

例如，設(shè)關(guān)鍵字的輸入順序?yàn)?5，24，53，12，28，90，按上述算法生成的二叉排序樹(shù)的過(guò)程如圖7-6所示。圖7-6二叉排序樹(shù)的建立過(guò)程對(duì)同樣的一組數(shù)據(jù)元素，如果輸入順序不同，所生成的二叉樹(shù)形態(tài)也不同，如上面的例子。如果輸入順序?yàn)?4，53，90，12，28，45，則生成的二叉排序樹(shù)如圖7-7所示。圖7-7輸入順序不同所建立的不同二叉排序樹(shù)7.3.3二叉排序樹(shù)的刪除從二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)，不能把以該結(jié)點(diǎn)為根的子樹(shù)都刪去，只能刪掉這個(gè)結(jié)點(diǎn)，并且還要保證刪除后所得的二叉樹(shù)仍然滿足二叉排序樹(shù)的性質(zhì)不變。也就是說(shuō)，在二叉排序樹(shù)中刪去一個(gè)結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個(gè)結(jié)點(diǎn)。刪除操作首先要查找，以確定被刪結(jié)點(diǎn)是否在二叉排序樹(shù)中。若不在，則不做任何操作；否則，假設(shè)要?jiǎng)h除的結(jié)點(diǎn)為p，結(jié)點(diǎn)p的雙親結(jié)點(diǎn)為f，并假設(shè)結(jié)點(diǎn)p是結(jié)點(diǎn)f的左孩子(右孩子的情況類似)。下面分三種情況討論：

(1)若p為葉子結(jié)點(diǎn)，則可直接將其刪除：

f->lchild=NULL;free(p);

(2)若p結(jié)點(diǎn)只有左子樹(shù)，或只有右子樹(shù)，則可將p的左子樹(shù)或右子樹(shù)，直接改為其雙親結(jié)點(diǎn)f的左子樹(shù)，即：

f->lchild=p->lchild(或f->lchild=p->rchild);free(p);

(3)若p既有左子樹(shù)，又有右子樹(shù)，如圖7-8(a)所示。此時(shí)有兩種處理方法：方法1：首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，如圖7-8(b)所示，然后將p的左子樹(shù)改為f的左子樹(shù)，而將p的右子樹(shù)改為s的右子樹(shù)：f->lchild=p->lchild;s->rchild=p->rchild;free(p);結(jié)果如圖7-8(c)所示。方法2：首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，如圖7-8(b)所示，然后用s結(jié)點(diǎn)的值，替代p結(jié)點(diǎn)的值，再將s結(jié)點(diǎn)刪除，原s結(jié)點(diǎn)的左子樹(shù)改為s的雙親結(jié)點(diǎn)q的右子樹(shù)：p->data=s->data;q->rchild=s->lchild;free(s);結(jié)果如圖7-8(d)所示。圖7-8二叉排序樹(shù)刪除示意綜上所述，可以得到下面的在二叉排序樹(shù)中刪去一個(gè)結(jié)點(diǎn)的算法；

算法7-6

二叉排序樹(shù)中刪除結(jié)點(diǎn)。在二叉排序樹(shù)t中刪去關(guān)鍵字為k的結(jié)點(diǎn)。

BSTNode*DelBST(BSTreet,Keytypek)

{BSTNode*p,*f,*s,*q;

p=t;f=NULL;

while(p) //查找關(guān)鍵字為k的待刪結(jié)點(diǎn)p

{if(p->key==k)break; //找到，則跳出查找循環(huán)

f=p; //f指向p結(jié)點(diǎn)的雙親結(jié)點(diǎn)

if(p->key>k)p=p->lchild;

elsep=p->rchild;}

if(p==NULL)returnt; //若找不到，返回原來(lái)的二叉排序樹(shù)

if(p->lchild==NULL) //p無(wú)左子樹(shù)

{if(f==NULL)t=p->rchild; //p是原二叉排序樹(shù)的根

elseif(f->lchild==p) //p是f的左孩子

f->lchild=p->rchild; //將p的右子樹(shù)鏈到f的左鏈上

else //p是f的右孩子

f->rchild=p->rchild; //將p的右子樹(shù)鏈到f的右鏈上

free(p); //釋放被刪除的結(jié)點(diǎn)p}else{ //p有左子樹(shù)

q=p;s=p->lchild;while(s->rchild) //在p的左子樹(shù)中查找最右下結(jié)點(diǎn)

{q=s;s=s->rchild;}if(q==p)q->lchild=s->lchild; //將s的左子樹(shù)鏈到q上(方法2)elseq->rchild=s->lchild;p->key=s->key; //將s的值賦給pfree(s);}returnt;}7.3.4二叉排序樹(shù)的查找因?yàn)槎媾判驑?shù)可看做是一個(gè)有序表，所以在二叉排序樹(shù)上進(jìn)行查找，和折半查找類似，也是一個(gè)逐步縮小查找范圍的過(guò)程。根據(jù)二叉排序樹(shù)的特點(diǎn)，首先將待查關(guān)鍵字key與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較。

(1)如果key=t，則返回根結(jié)點(diǎn)地址；

(2)如果key<t，則進(jìn)一步查找左子樹(shù)；

(3)如果key>t，則進(jìn)一步查找右子樹(shù)。顯然，這是一個(gè)遞歸過(guò)程?？捎萌缦逻f歸算法實(shí)現(xiàn)。

算法7-7

二叉排序樹(shù)查找的遞歸算法。在根指針bst所指二叉排序樹(shù)中，遞歸查找某關(guān)鍵字等于key的元素，若查找成功，則返回指向該元素結(jié)點(diǎn)指針，否則返回空指針。

BSTreeSearchBST(BSTreebst,Keytypekey)

{

if(!bst)

returnNULL;

elseif(bst->key==key)

returnbst; //查找成功

elseif(key<bst->key)

returnSearchBST(bst->lchild,key);//在左子樹(shù)繼續(xù)查找

elsereturnSearchBST(bst->rchild,key);//在右子樹(shù)繼續(xù)查找}根據(jù)二叉排序樹(shù)的定義，二叉排序樹(shù)查找的遞歸算法可以用循環(huán)方式直接實(shí)現(xiàn)。二叉排序樹(shù)的非遞歸查找過(guò)程如下：

算法7-8二叉排序樹(shù)非遞歸查找算法。在根指針bst所指二叉排序樹(shù)上，查找關(guān)鍵字等于key的結(jié)點(diǎn)，若查找成功，則返回指向該元素結(jié)點(diǎn)指針，否則返回空指針。BSTreeSearchBST(BSTreebst,KeyTypekey)

{BSTreeq;

q=bst;

while(q)

{if(q->key==key)returnq; //查找成功

if(key<q->key)q=q->lchild; //在左子樹(shù)中查找

elseq=q->rchild; //在右子樹(shù)中查找

}

returnNULL; //查找失敗

}7.3.5二叉排序樹(shù)的查找性能顯然，在二叉排序樹(shù)上進(jìn)行查找，若查找成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到待查結(jié)點(diǎn)的路徑。若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根到某個(gè)葉子結(jié)點(diǎn)的路徑。因此，二叉排序樹(shù)的查找與折半查找過(guò)程類似，在二叉排序樹(shù)中查找一個(gè)記錄時(shí)，其比較次數(shù)不超過(guò)樹(shù)的深度。但是，對(duì)長(zhǎng)度為n的表而言，無(wú)論其排列順序如何，折半查找對(duì)應(yīng)的判定樹(shù)是唯一的，而含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)卻是不唯一的。所以對(duì)于含有同樣關(guān)鍵字序列的一組結(jié)點(diǎn)，結(jié)點(diǎn)插入的先后次序不同，所構(gòu)成的二叉排序樹(shù)的形態(tài)和深度不同。而二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)，二叉排序樹(shù)的各分支越均衡，樹(shù)的深度淺，其平均查找長(zhǎng)度ASL越小。例如，如圖7-9所示的兩棵二叉排序樹(shù)，它們對(duì)應(yīng)同一元素集合，但建立二叉排序樹(shù)的順序不同，分別是(45，24，53，12，37，93)和(12，24，37，45，53，93)。圖7-9二叉查找樹(shù)的不同形態(tài)假設(shè)每個(gè)元素的查找概率相等，則它們的平均查找長(zhǎng)度分別是由此可見(jiàn)，在二叉排序樹(shù)上進(jìn)行查找時(shí)的平均查找長(zhǎng)度和二叉排序樹(shù)的形態(tài)有關(guān)。在最壞情況下，二叉排序樹(shù)是通過(guò)把一個(gè)有序表的n個(gè)結(jié)點(diǎn)插入生成的，由此得到二叉排序樹(shù)退化為一棵深度為n的單支樹(shù)，它的平均查找長(zhǎng)度和單鏈表上的順序查找相同，也是(n+1)/2。在最好情況下，二叉排序樹(shù)在生成過(guò)程中，樹(shù)的形態(tài)比較均勻，最終得到的是一棵形態(tài)與折半查找的判定樹(shù)相似的二叉排序樹(shù)，此時(shí)它的平均查找長(zhǎng)度大約是log2(n+1)-1。就平均性能而言，二叉排序樹(shù)上的查找和折半查找相差不大，并且二叉排序樹(shù)上的插入和刪除結(jié)點(diǎn)十分方便，無(wú)需移動(dòng)大量結(jié)點(diǎn)。因此，對(duì)于需要經(jīng)常做插入、刪除、查找運(yùn)算的表，宜采用二叉排序樹(shù)結(jié)構(gòu)。由此，人們也常常將二叉排序樹(shù)稱為二叉查找樹(shù)。7.3.6平衡二叉樹(shù)二叉排序樹(shù)具有較好的查找性能，但樹(shù)的建立過(guò)程決定了樹(shù)的形態(tài)，在最壞的情況下，二叉排序樹(shù)會(huì)退化成單鏈表。為了克服這個(gè)問(wèn)題，1962年科學(xué)家Adelson-Velskii和Landis提出平衡二叉樹(shù)，也稱為AVL樹(shù)。這是一種附加了一定條件的二叉樹(shù)。我們把二叉樹(shù)中每一結(jié)點(diǎn)的左子樹(shù)高度減去右子樹(shù)高度定義為該結(jié)點(diǎn)的平衡因子。所謂平衡二叉樹(shù)，是指一個(gè)二叉樹(shù)中任一結(jié)點(diǎn)的平衡因子的值只能是?+1、0或?-1，換句話說(shuō)，平衡二叉樹(shù)的每一個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值不超過(guò)1。如圖7-10所示給出了一個(gè)平衡二叉樹(shù)的例子。每個(gè)結(jié)點(diǎn)旁所標(biāo)數(shù)字為該結(jié)點(diǎn)的平衡因子。圖7-10一棵平衡二叉樹(shù)因?yàn)槠胶舛鏄?shù)的每一個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差不超過(guò)?±1，可以證明它的深度和log2n是同數(shù)量級(jí)的，因此它的平均查找時(shí)間復(fù)雜性為O(log2n)。利用平衡二叉樹(shù)進(jìn)行查找，可以較利用普通二叉排序樹(shù)有更快的最壞情況查找速度。當(dāng)然，因?yàn)槠胶舛鏄?shù)附加了任一結(jié)點(diǎn)左右子樹(shù)高度之差不超過(guò)?±1的限制條件，因此在構(gòu)成平衡二叉樹(shù)時(shí)，或向平衡二叉樹(shù)插入結(jié)點(diǎn)時(shí)，可能會(huì)使它失去平衡，這就需要進(jìn)行調(diào)整，以使其總能符合這個(gè)限制條件。在平衡二叉樹(shù)某個(gè)結(jié)點(diǎn)的左子樹(shù)插入一個(gè)新結(jié)點(diǎn)，可能會(huì)使它失去平衡，我們會(huì)遇到下列三種情況：

(1)若原來(lái)其左子樹(shù)高度與右子樹(shù)高度相等，即原來(lái)此結(jié)點(diǎn)的平衡因子為0，則插入新結(jié)點(diǎn)后將使得平衡因子變?yōu)?+1，仍符合平衡樹(shù)條件，不必進(jìn)行調(diào)整。

(2)若原來(lái)其左子樹(shù)高度小于右子樹(shù)高度，即原來(lái)此結(jié)點(diǎn)的平衡因子為?-1，則插入新結(jié)點(diǎn)后將使得平衡因子變?yōu)?，平衡更加改善，也不需要調(diào)整。

(3)若原來(lái)其左子樹(shù)高度大于右子樹(shù)高度，即原來(lái)此結(jié)點(diǎn)的平衡因子為?+1，則插入結(jié)點(diǎn)后將使得平衡因子變?yōu)?+2，不符合平衡樹(shù)條件，需要對(duì)其進(jìn)行調(diào)整。如果給平衡二叉樹(shù)某結(jié)點(diǎn)的右子樹(shù)插入一個(gè)新結(jié)點(diǎn)，且此新結(jié)點(diǎn)使右子樹(shù)的高度增加1，則也會(huì)出現(xiàn)上述三種情況。對(duì)于第(1)種情況，平衡因子將由0變?yōu)?-1，不需要調(diào)整；對(duì)于第(2)種情況，平衡因子由1變?yōu)?，也不需要調(diào)整；對(duì)于第(3)種情況，平衡因子由-1變?yōu)?2，需要進(jìn)行調(diào)整。當(dāng)插入結(jié)點(diǎn)后平衡二叉樹(shù)失去平衡時(shí)，我們基本上是用四種不同的旋轉(zhuǎn)LL、LR、RR和RL進(jìn)行調(diào)整使其重新達(dá)到平衡的。這些調(diào)整都是基于距插入結(jié)點(diǎn)最近而平衡因子為

2的結(jié)點(diǎn)(不妨將該結(jié)點(diǎn)設(shè)為A)進(jìn)行的?？梢宰C明，只要調(diào)整結(jié)點(diǎn)A的子樹(shù)中的有關(guān)結(jié)點(diǎn)的鏈接關(guān)系，使之符合平衡條件，就不需要調(diào)整樹(shù)中其他結(jié)點(diǎn)。上述四種調(diào)整的特征如下。

1)?LL型調(diào)整

LL型調(diào)整指的是新結(jié)點(diǎn)插入A結(jié)點(diǎn)的左子樹(shù)的左子樹(shù)里，如圖7-11所示。圖中矩形表示子樹(shù)，矩形的高度表示子樹(shù)的高度，帶陰影的方形則表示插入新結(jié)點(diǎn)后造成子樹(shù)高度加1，各結(jié)點(diǎn)旁所標(biāo)數(shù)字為該結(jié)點(diǎn)的平衡因子。調(diào)整規(guī)則為，將結(jié)點(diǎn)B向上旋轉(zhuǎn)代替A的位置，而令結(jié)點(diǎn)A向下旋轉(zhuǎn)成為B的右子樹(shù)的根結(jié)點(diǎn)，B的右子樹(shù)成為A的左子樹(shù)。此調(diào)整過(guò)程需要修改三個(gè)指針。圖7-11LL型調(diào)整

2)?LR型調(diào)整

LR型調(diào)整指的是新結(jié)點(diǎn)插入A結(jié)點(diǎn)的左子樹(shù)的右子樹(shù)里。調(diào)整是將結(jié)點(diǎn)B的右兒子C代替原來(lái)A的位置。因?yàn)榻Y(jié)點(diǎn)C的關(guān)鍵字值大于結(jié)點(diǎn)B而小于A的關(guān)鍵字值，故將結(jié)點(diǎn)B和結(jié)點(diǎn)A分別變成C的左兒子和右兒子。原來(lái)結(jié)點(diǎn)C的左子樹(shù)，其所有關(guān)鍵字值均大于結(jié)點(diǎn)B而小于結(jié)點(diǎn)C，將變成結(jié)點(diǎn)B的右子樹(shù)；類似地，結(jié)點(diǎn)C的右子樹(shù)成為結(jié)點(diǎn)A的左子樹(shù)。這種調(diào)整需要修改五個(gè)指針，如圖7-12所示。圖7-12LR型調(diào)整

3)?RR型調(diào)整

RR型調(diào)整指的是新結(jié)點(diǎn)插入到A結(jié)點(diǎn)的右子樹(shù)的右子樹(shù)里，使得結(jié)點(diǎn)A的平衡因子由?-1變?yōu)?-2。調(diào)整規(guī)則為，將結(jié)點(diǎn)B向上旋轉(zhuǎn)代替A的位置，而令結(jié)點(diǎn)A向下旋轉(zhuǎn)成為B的左子樹(shù)的根結(jié)點(diǎn)，B的左子樹(shù)成為A的右子樹(shù)。此調(diào)整過(guò)程與LL型調(diào)整過(guò)程對(duì)稱，需要修改三個(gè)指針，如圖7-13所示。圖7-13RR型調(diào)整

4)?RL型調(diào)整

RL型調(diào)整指的是新結(jié)點(diǎn)插入A結(jié)點(diǎn)的右子樹(shù)的左子樹(shù)里，使得結(jié)點(diǎn)A的平衡因子由-1變?yōu)?-2。調(diào)整是將結(jié)點(diǎn)B的左兒子C代替原來(lái)A的位置。因?yàn)榻Y(jié)點(diǎn)C的關(guān)鍵字值小于結(jié)點(diǎn)B而大于A的關(guān)鍵字值，故將結(jié)點(diǎn)B和結(jié)點(diǎn)A分別變成C的右兒子和左兒子。原來(lái)結(jié)點(diǎn)C的右子樹(shù)，其所有關(guān)鍵字值均小于結(jié)點(diǎn)B而大于結(jié)點(diǎn)C，將變成結(jié)點(diǎn)B的左子樹(shù)；類似地，結(jié)點(diǎn)C的左子樹(shù)成為結(jié)點(diǎn)A的右子樹(shù)。此調(diào)整過(guò)程與LR型調(diào)整過(guò)程對(duì)稱，需要修改五個(gè)指針，如圖7-14所示。圖7-14RL型調(diào)整為進(jìn)行這四種不同的旋轉(zhuǎn)，就必須找到結(jié)點(diǎn)A。前面我們已說(shuō)過(guò)，結(jié)點(diǎn)A就是平衡因子已成為?

2，離新插入結(jié)點(diǎn)最近的那個(gè)祖先結(jié)點(diǎn)。一個(gè)結(jié)點(diǎn)的平衡因子要成為?

2，那么，在插入之前，該結(jié)點(diǎn)的平衡因子必定為?

1。而且，其平衡因子要變?yōu)?

2的最近祖先結(jié)點(diǎn)，在插入前也是平衡因子為?

1的最近祖先。因此，插入前，在A至新插入結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)的平衡因子必定是0。知道了這一點(diǎn)，即可確定結(jié)點(diǎn)A就是在插入前其平衡因子為?

1，離新結(jié)點(diǎn)最近的祖先。另外，還需要知道結(jié)點(diǎn)A的雙親結(jié)點(diǎn)F，知道了結(jié)點(diǎn)A和其雙親結(jié)點(diǎn)F，便可很容易地完成調(diào)整。為了說(shuō)明在插入結(jié)點(diǎn)時(shí)，維持平衡二叉樹(shù)時(shí)所涉及的各種處理，我們以數(shù)值序列(30，46，95，23，6，27，82)為例構(gòu)造平衡二叉樹(shù)，并分析其調(diào)整過(guò)程。插入30和46，結(jié)果產(chǎn)生如圖7-15(a)所示的平衡二叉樹(shù)。當(dāng)我們把95插入樹(shù)中時(shí)，結(jié)點(diǎn)30的平衡因子變?yōu)?-2，出現(xiàn)不平衡，為了使樹(shù)重新平衡，執(zhí)行一次旋轉(zhuǎn)，使30成為46的左子結(jié)點(diǎn)，46成為樹(shù)根，如圖7-15(b)所示。插入23，樹(shù)是平衡的，如圖7-15(c)所示。然而，插入6時(shí)，就再度使樹(shù)失去平衡。為了保持樹(shù)的平衡，再執(zhí)行一次旋轉(zhuǎn)，這次是順時(shí)針旋轉(zhuǎn)。30變成23的右子結(jié)點(diǎn)，而23成了子樹(shù)的根結(jié)點(diǎn)，如圖7-15(d)所示。在插入27時(shí)，樹(shù)又成為不平衡樹(shù)。但是這次調(diào)整要比前面兩次調(diào)整復(fù)雜一些。30成為樹(shù)根，23連同其左子樹(shù)一起成為30的左子樹(shù)，30的左子樹(shù)成為23的右子樹(shù)，46及其右子樹(shù)成為30的右子樹(shù)，如圖7-15(e)所示。插入結(jié)點(diǎn)82時(shí)，樹(shù)又失去平衡，調(diào)整82代替46成為子樹(shù)的根，46變成82的左子樹(shù)，46的右子樹(shù)變成82的右子樹(shù)，如圖7-15(f)所示。圖7-15平衡二叉樹(shù)建立過(guò)程在平衡二叉樹(shù)上進(jìn)行查找的過(guò)程與二叉排序樹(shù)相同，但查找過(guò)程中和給定關(guān)鍵字值進(jìn)行比較的次數(shù)不超過(guò)樹(shù)的高度h，因此其查找所需時(shí)間為O(h)。由于n個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)的高度h至多為O(log2n)，因此，最壞情況下，在平衡二叉樹(shù)上進(jìn)行查找的時(shí)間復(fù)雜性為O(log2n)。7.4哈?希?表?查?找

7.4.1哈希表與哈希查找前面討論的查找方法，由于數(shù)據(jù)元素的存儲(chǔ)位置與關(guān)鍵字之間不存在確定的關(guān)系，因此，查找時(shí)，需要進(jìn)行一系列對(duì)關(guān)鍵字的查找比較，即“查找算法”是建立在比較的基礎(chǔ)上的，查找效率由比較一次縮小的查找范圍決定。理想的情況是依據(jù)關(guān)鍵字直接得到其對(duì)應(yīng)的數(shù)據(jù)元素存儲(chǔ)位置，即要求關(guān)鍵字與數(shù)據(jù)元素的存儲(chǔ)位置間存在一一對(duì)應(yīng)關(guān)系，通過(guò)這個(gè)關(guān)系，能很快地由關(guān)鍵字得到對(duì)應(yīng)的數(shù)據(jù)元素的存儲(chǔ)位置。實(shí)例7-211個(gè)數(shù)據(jù)元素的關(guān)鍵字分別為18，27，1，20，22，6，10，13，41，15，25。我們規(guī)定，數(shù)據(jù)元素的存儲(chǔ)位置和關(guān)鍵字之間滿足如下函數(shù)：Hash(key)=key%11通過(guò)這個(gè)函數(shù)對(duì)11個(gè)元素建立查找表如下：查找時(shí)，對(duì)給定值依然通過(guò)這個(gè)函數(shù)計(jì)算出地址，再將給定值與該地址單元中元素的關(guān)鍵字比較，若相等，則查找成功。現(xiàn)在來(lái)看看哈希查找的定義。所謂哈希查找，就是選取某個(gè)函數(shù)，將關(guān)鍵字帶入該函數(shù)計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值計(jì)算地址，將給定值與地址單元中元素關(guān)鍵字進(jìn)行比較，確定查找是否成功，這就是哈希查找。哈希查找中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)，按這個(gè)思想構(gòu)造的表稱為哈希表。對(duì)于有n個(gè)數(shù)據(jù)元素的集合，總能找到關(guān)鍵字與存放地址一一對(duì)應(yīng)的函數(shù)。若最大關(guān)鍵字為m，則可以分配m個(gè)存儲(chǔ)單元，選取函數(shù)f(key)=key即可，但這樣會(huì)造成存儲(chǔ)空間的很大浪費(fèi)，甚至不可能分配這么大的存儲(chǔ)空間。通常關(guān)鍵字的集合比哈希地址集合大得多，因而經(jīng)過(guò)哈希函數(shù)變換后，可能將不同的關(guān)鍵字映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。映射到同一哈希地址上的關(guān)鍵字稱為同義詞。可以說(shuō)，沖突不可能避免，只能盡可能減少。所以，哈希查找需要解決以下兩個(gè)問(wèn)題：

(1)構(gòu)造好的哈希函數(shù)，所謂好的哈希函數(shù)，是指盡可能滿足如下條件：①哈希函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；②哈希函數(shù)對(duì)關(guān)鍵字計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。

(2)制定解決沖突的方案。7.4.2構(gòu)造哈希函數(shù)的方法

1．直接地址法直接地址法，就是選取關(guān)鍵字的某個(gè)線性函數(shù)值為哈希地址，這類函數(shù)是一一對(duì)應(yīng)函數(shù)，不會(huì)產(chǎn)生沖突，但要求地址集合與關(guān)鍵字集合大小相同，因此，對(duì)于較大的關(guān)鍵字集合不適用。哈希函數(shù)的一般形式為Hash(key)?=?a?×?key?+?b(a、b為常數(shù))例：關(guān)鍵字集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則建立哈希表如下：

2．除留余數(shù)法除留余數(shù)法，就是選取關(guān)鍵字除以整數(shù)p的余數(shù)作為哈希地址。使用除留余數(shù)法，選取合適的p很重要，若哈希表表長(zhǎng)為m，則要求p≤m，且接近m。p一般選取素?cái)?shù)。哈希函數(shù)的一般形式為Hash(key)?=?key%p(p是一個(gè)整數(shù))

3．?dāng)?shù)字分析法數(shù)字分析法是取關(guān)鍵字中某些取值較分散的數(shù)字位作為哈希地址的方法，它適合于所有關(guān)鍵字已知的情況。例如，有一組關(guān)鍵字為(92317602，92326875，92739628，92343634，92706816，92774638，92381262，92394220)，通過(guò)分析可知，每個(gè)關(guān)鍵字從左到右的第1、2、3位和第6位取值較集中，不宜作為哈希地址，剩余的第4、5、7和8位取值較分散，可根據(jù)實(shí)際需要取其中的若干位作為哈希地址，例如，可以取最后兩位作為哈希地址，構(gòu)造哈希表。

4．平方取中法平分取中法是取關(guān)鍵字平方的中間幾位作為哈希地址的方法，具體取多少位視實(shí)際要求而定。一個(gè)數(shù)平方后的中間幾位和數(shù)的每一位都有關(guān)，由此可知，用平方取中法得到的哈希地址同關(guān)鍵字的每一位都有關(guān)，使得哈希地址具有較好的分散性。平方取中法適用于關(guān)鍵字中每一位取值都不夠分散或者較分散的位數(shù)小于哈希地址所需要的位數(shù)的情況。

5．折疊法折疊法是首先將關(guān)鍵字分割成位數(shù)相同的幾段，段的位數(shù)取決于哈希地址的位數(shù)，由實(shí)際需要而定，然后將它們疊加求和作為哈希地址的方法。例如一個(gè)關(guān)鍵字為68242324，哈希地址為3位，則將關(guān)鍵字從左到右每3位為一段，得到三段為682、423、240，疊加求和得345，這個(gè)值就是關(guān)鍵字為68242324的數(shù)據(jù)元素的哈希地址。折疊法適用于關(guān)鍵字的位數(shù)較多，而哈希地址的位數(shù)又比較少，同時(shí)關(guān)鍵字的每一位的取值又較集中的情況。7.4.3處理沖突的方法在哈希存儲(chǔ)中，因?yàn)榇鎯?chǔ)空間的有限性，通常都會(huì)出現(xiàn)沖突。處理沖突的方法可分為開(kāi)放地址法和拉鏈法兩種。1．開(kāi)放地址法開(kāi)放地址法就是從發(fā)生沖突的那個(gè)單元開(kāi)始，按照一定的次序，從哈希表中查找一個(gè)空閑的存儲(chǔ)單元，把發(fā)生沖突的待插入元素存入到該單元中的一種處理沖突的方法。使用開(kāi)放地址法，哈希表中的地址為d的空閑存儲(chǔ)單元，不僅允許哈希地址為d的數(shù)據(jù)元素使用，也允許發(fā)生沖突的其他數(shù)據(jù)元素使用。即空閑存儲(chǔ)單元不僅對(duì)同義詞元素開(kāi)放，也對(duì)非同義詞元素開(kāi)放，這就是開(kāi)放地址法名稱的來(lái)源。在使用開(kāi)放地址法處理沖突的哈希表中，地址為d的單元存儲(chǔ)的是同義詞中的一個(gè)數(shù)據(jù)元素，還是非同義詞中的一個(gè)數(shù)據(jù)元素，由誰(shuí)先占用它決定。一個(gè)哈希表，如果采用開(kāi)放地址法來(lái)解決沖突，那么查找一個(gè)數(shù)據(jù)元素的過(guò)程就是：首先根據(jù)給定的關(guān)鍵字key，代入相應(yīng)的哈希函數(shù)，計(jì)算出哈希地址d。然后比較d單元的數(shù)據(jù)元素的關(guān)鍵字是否為key。如果是，則查找成功；否則，按照和插入時(shí)處理沖突相同的次序依次比較，直到查找成功，或找到一個(gè)空的存儲(chǔ)單元為止。而找到空的存儲(chǔ)單元，意味著查找失敗。開(kāi)放地址法中，發(fā)生沖突時(shí)查找空閑存儲(chǔ)單元常用的方法有線性探查法、平方探查法和雙哈希函數(shù)探查法。

1)線性探查法線性探查法是開(kāi)放法中處理沖突的一種最簡(jiǎn)單的探查方法，它從發(fā)生沖突的d單元開(kāi)始，依次探查下一個(gè)單元，當(dāng)?shù)竭_(dá)表尾時(shí)，再?gòu)牡谝粋€(gè)單元開(kāi)始探查，也就是把哈希表看做首尾相接的循環(huán)表，直到找到一個(gè)空閑的存儲(chǔ)單元為止。這種方法的探查序列為

實(shí)例7-3

關(guān)鍵字集為{47，7，29，11，16，92，22，8，3}，哈希表表長(zhǎng)為11，哈希函數(shù)為Hash(key)=key%11，用線性探查法處理沖突。建表如下：

47、7、11、16、92均是由哈希函數(shù)得到的沒(méi)有沖突的哈希地址而直接存入的。

Hash(29)?=?7，哈希地址沖突，需尋找下一個(gè)空的哈希地址。由d1?=?(Hash(29)?+?1)%11?=?8，哈希地址8為空，將29存入。另外，22、8同樣在哈希地址上有沖突，也是由d1找到空的哈希地址的。而Hash(3)=3，哈希地址沖突，由d1?=(Hash(3)+1)%11=4，仍然沖突；d2?=(Hash(3)+2)%11=5，仍然沖突；d3?=(Hash(3)+3)%11=?6，找到空的哈希地址，存入。線性探查法可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞。因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來(lái)，大大降低了查找效率。為此，可采用平方探查法，或雙哈希函數(shù)探查法，以改善“堆積”問(wèn)題。

2)平方探查法平方探查法的探查序列為d，d+12，d+22，…，使用公式可表示為平方探查法是一種較好的處理沖突的方法，能夠較好地避免堆積現(xiàn)象。它的缺點(diǎn)是不能探查到哈希表上所有的單元，但至少能探查到一半單元。例如當(dāng)key=5，m=17時(shí)，則只能探查到下標(biāo)依次是5、6、9、14、4、13、7、3、1的單元，而不能探查到剩余的單元。不過(guò)在實(shí)際應(yīng)用中，能探查到一半單元就可以了。若探查到一半單元還找不到一個(gè)空閑的單元，則表明此哈希表太滿，應(yīng)該重新建立。仍以上例用平方探查法處理沖突，建表如下：

3)雙哈希函數(shù)探查法這種方法使用兩個(gè)哈希函數(shù)Hash1(key)和Hash2(key)，第一個(gè)哈希函數(shù)的作用和前面哈希函數(shù)的作用相同，而第二個(gè)哈希函數(shù)的值是作為探查序列的地址增量。雙哈希函數(shù)探查法的探查序列可以用公式表示為以上三種方法，區(qū)別主要在于探查序列步長(zhǎng)不同。對(duì)于線性探查法，探查序列的步長(zhǎng)值固定是1；對(duì)于平方探查法，探查序列的步長(zhǎng)值是探查次數(shù)i的兩倍減1；對(duì)于雙哈希函數(shù)探查法，探查序列的步長(zhǎng)是同一關(guān)鍵字的另一哈希函數(shù)的值。

2．拉鏈法設(shè)哈希函數(shù)得到的哈希地址域在區(qū)間[0，m-1]上，以每個(gè)哈希地址作為一個(gè)指針，指向一個(gè)單鏈表鏈，即分配一個(gè)指針數(shù)組：

Elemtype*eptr[m]；建立m個(gè)空鏈表，由哈希函數(shù)對(duì)關(guān)鍵字轉(zhuǎn)換后，映射到同一哈希地址i的同義詞均加入到*eptr[i]指向的鏈表中。

實(shí)例7-4

關(guān)鍵字序列為{47，7，29，11，16，92，22，8，3，50，37，89}，哈希函數(shù)為Hash(key)=key%11用拉鏈法處理沖突。建表如圖7-16所示，向鏈表中插入元素均在表頭進(jìn)行。圖7-16拉鏈法處理沖突時(shí)的哈希表

3．公共溢出區(qū)法設(shè)哈希函數(shù)產(chǎn)生的哈希地址集為[0，m-1]，則分配兩個(gè)表：一個(gè)基本表Elemtypebase_tbl[m]，每個(gè)單元只能存放一個(gè)元素。一個(gè)溢出表Elemtypeover_tbl[k]，只要關(guān)鍵字對(duì)應(yīng)的哈希地址在基本表上產(chǎn)生沖突，則所有這樣的元素一律存入溢出表中。查找時(shí)，對(duì)給定值key通過(guò)哈希函數(shù)計(jì)算出哈希地址i，先與基本表的base_tbl[i]單元比較，若相等，查找成功；否則，再到溢出表中進(jìn)行查找。

7.4.4哈希表的查找分析哈希表的查找過(guò)程基本上和造表過(guò)程相同。一些關(guān)鍵字可通過(guò)哈希函數(shù)轉(zhuǎn)換的地址直接找到，另一些關(guān)鍵字在哈希函數(shù)得到的地址上產(chǎn)生了沖突，需要按處理沖突的方法進(jìn)行查找。在介紹的三種處理沖突的方法中，產(chǎn)生沖突后的查找仍然是給定值與關(guān)鍵字進(jìn)行比較的過(guò)程。所以，對(duì)哈希表查找效率的量度，依然用平均查找長(zhǎng)度來(lái)衡量。查找過(guò)程中，關(guān)鍵字的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，影響產(chǎn)生沖突多少的因素，也就是影響查找效率的因素。影響產(chǎn)生沖突多少有以下三個(gè)因素：

(1)哈希函數(shù)是否均勻；

(2)處理沖突的方法；

(3)哈希表的裝填因子。分析這三個(gè)因素，盡管哈希函數(shù)的“好壞”直接影響沖突產(chǎn)生的頻度，但一般情況下，我們總認(rèn)為所選的哈希函數(shù)是“均勻的”，因此，可不考慮哈希函數(shù)對(duì)平均查找長(zhǎng)度的影響。就線性探查法和平方探查法處理沖突的例子看，相同的關(guān)鍵字集合、同樣的哈希函數(shù)，但在數(shù)據(jù)元素查找等概率情況下，它們的平均查找長(zhǎng)度卻不同。線性探查法的平均查找長(zhǎng)度：ASL?=?(5?×?1?+?3?×?2?+?1?×?4)/9?=?5/3平方探查法的平均查找長(zhǎng)度：ASL?=?(5?×?1?+?3?×?2?+?1?×?2)/9?=?13/9哈希表的裝填因子定義為

α是哈希表裝滿程度的衡量標(biāo)志。由于表長(zhǎng)是定值，α與“填入表中的元素個(gè)數(shù)”成正比，因此α越大，填入表中的元素較多，產(chǎn)生沖突的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生沖突的可能性就越小。實(shí)際上，哈希表的平均查找長(zhǎng)度是裝填因子α的函數(shù)，只是不同處理沖突的方法有不同的函數(shù)。哈希查找存取速度快，也較節(jié)省空間，靜態(tài)查找、動(dòng)態(tài)查找均適用，但由于存取是隨機(jī)的，因此不便于順序查找。小結(jié)

本章首先介紹了查找的基本概念，然后具體介紹了順序查找、折半查找、索引查找等靜態(tài)查找方法和基于二叉排序樹(shù)的動(dòng)態(tài)查找方法，最后介紹了利用關(guān)鍵字和地址對(duì)應(yīng)的哈希查找法。

(1)順序查找既適用于順序表，也適用于鏈表，并且對(duì)表中元素的排列次序沒(méi)有要求。順序查找的時(shí)間復(fù)雜度為O(n)，平均查找長(zhǎng)度為(n+1)/2。折半查找法只能適用于順序存儲(chǔ)的有序表，不適用于鏈表。折半查找法的時(shí)間復(fù)雜度為O(log2n)，它的平均查找長(zhǎng)度等于判定樹(shù)中所有結(jié)點(diǎn)層數(shù)之和的平均值。分塊查找的基本思想是利用索引表縮小查找的范圍。

(2)二叉排序樹(shù)是一種有序樹(shù)，它的查找性能取決于樹(shù)的形態(tài)，其查找性能介于折半查找和順序查找之間。

(3)哈希查找是通過(guò)構(gòu)造哈希函數(shù)來(lái)計(jì)算存儲(chǔ)地址的一種查找方法，時(shí)間復(fù)雜度為O(1)。兩個(gè)關(guān)鍵字不同，其哈希函數(shù)值相同，因而得到同一個(gè)表的相同地址的現(xiàn)象稱為沖突。常用的解決沖突的方法有：開(kāi)放地址法、拉鏈法和公共溢出區(qū)法。習(xí)題

一、填空題

1．順序查找法的平均查找長(zhǎng)度為

；折半查找法的平均查找長(zhǎng)度為

。

2．在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是

。

3．折半查找的存儲(chǔ)結(jié)構(gòu)僅限于

，且是

。

4．假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為

，比較二次查找成功的結(jié)點(diǎn)數(shù)為

，比較三次查找成功的結(jié)點(diǎn)數(shù)為

，比較四次查找成功的結(jié)點(diǎn)數(shù)為

，比較五次查找成功的結(jié)點(diǎn)數(shù)為

，平均查找長(zhǎng)度為

。

5．對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為

；若采用折半法查找，則時(shí)間復(fù)雜度為

。

6．已知有序表為{12，18，24，35，47，50，62，83，90，115，134}，當(dāng)用折半法查找90時(shí)，需進(jìn)行

次查找可確定成功；查找47時(shí)，需進(jìn)行

次查找可確定成功；查找100時(shí)，需進(jìn)行

次查找才能確定不成功。

7．二叉排序樹(shù)的查找長(zhǎng)度不僅與

有關(guān)，也與二叉排序樹(shù)的

有關(guān)。

8．一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵

樹(shù)而變成一棵有序樹(shù)，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。

9．

法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。

10．在哈希函數(shù)H(key)=key%p中，p應(yīng)取

。

11．在哈希存儲(chǔ)中，裝填因子α的值越大，則

；α的值越小，則

。二、選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為()的線性表。A.散列存儲(chǔ) B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ) D.索引存儲(chǔ)2.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須()。A.以順序方式存儲(chǔ) B.以鏈?zhǔn)椒绞酱鎯?chǔ)C.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序D.以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序

3.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為()。

A.

n B.

n/2 C.

(n+1)/2 D.

(n-1)/2

4.采用折半查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為()。

A．O(n2)

B.?O?(nlog2n) C.?O(n) D.?O(log2n)

5.折半查找和二叉排序樹(shù)查找的時(shí)間性能()。

A.相同 B.不相同

6.有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，()次比較后查找成功。

A.?1

B.?2 C.?4 D.?8

7.設(shè)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用平方探查法處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地址是()。

A.?8

B.?3 C.

5 D.

9

8.有一個(gè)長(zhǎng)度為12的有序表，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為()。

A.

35/12 B.

37/12

C.

39/12 D.

43/12

9．對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為()。

A.從第0個(gè)元素往后查找該數(shù)據(jù)元素

B.從第1個(gè)元素往后查找該數(shù)據(jù)元素

C.從第n個(gè)元素開(kāi)始往前查找該數(shù)據(jù)元素

D.與查找順序無(wú)關(guān)

10．解決哈希法中出現(xiàn)的沖突問(wèn)題常采用的方法是()。

A.數(shù)字分析法、除留余數(shù)法、平方取中法

B.數(shù)字分析法、除留余數(shù)法、線性探查法

C數(shù)字分析法、線性探查法、雙哈希函數(shù)探查法

D.線性探查法、雙哈希函數(shù)探查法、拉鏈法

11．采用線性探查法解決沖突問(wèn)題，所產(chǎn)生的一系列后繼散列地址()。

A.必須大于等于原哈希地址

B.必須小于等于原哈希地址

C.可以大于或小于但不能等于原哈希地址

D.地址大小沒(méi)有具體限制

12．對(duì)于查找表的查找過(guò)程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于()。

A.靜態(tài)查找表 B.動(dòng)態(tài)查找表

C.靜態(tài)查找表與動(dòng)態(tài)查找表 D.兩種表都不適合

13.哈希表的平均查找長(zhǎng)度()。

A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無(wú)關(guān)

B.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度有關(guān)

C.與處理沖突方法有關(guān)而與表的長(zhǎng)度有關(guān)

D.與處理沖突方法無(wú)關(guān)而與表的長(zhǎng)度無(wú)關(guān)三、應(yīng)用題

1.畫(huà)出對(duì)長(zhǎng)