《數(shù)據(jù)結(jié)構(gòu)》課件第8章

第8章查找8.1查找的基本概念8.2基于線性表的查找法8.3基于樹的查找8.4計算式查找法——哈希法本章小結(jié)習(xí)題八實(shí)訓(xùn)8-1分塊查找實(shí)訓(xùn)8-2二叉排序樹的建立

【教學(xué)目標(biāo)】通過本章的學(xué)習(xí)，掌握查找的基本概念；重點(diǎn)掌握順序查找、折半查找的思想與算法及平均查找長度；掌握二叉排序樹的查找、插入和刪除方法；掌握哈希表查找的思想；掌握構(gòu)造哈希函數(shù)的幾種常用方法；掌握用鏈地址法和開放定址法解決哈希沖突。查找不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種基于數(shù)據(jù)結(jié)構(gòu)的對數(shù)據(jù)進(jìn)行處理時經(jīng)常使用的一種操作。查找又稱為檢索，它是計算機(jī)科學(xué)中重要的研究課題之一，查找的目的就是從確定的數(shù)據(jù)集合中找出某個特定的元素。查找的方法很多，而且與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，查找算法的優(yōu)劣對計算機(jī)系統(tǒng)的運(yùn)行效率影響很大。本章主要學(xué)習(xí)查找的基本概念、順序查找算法、折半查找算法、二叉排序樹和哈希查找算法等。8.1查找的基本概念在日常生活中，人們幾乎每天都要進(jìn)行“查找”工作。例如，在奧運(yùn)跨欄運(yùn)動員信息表中查找某人的報名成績，在電話號碼本中查找某人或某單位的電話號碼等等。要進(jìn)行查找操作，必須首先明確要查找的對象，也就是要查找的數(shù)據(jù)元素的特征。在計算機(jī)中，一個數(shù)據(jù)元素通常是一條記錄，具有多個數(shù)據(jù)項(xiàng)，如表8-1所示。表8-1查找表表8-1就是一張查找表，每行是一個數(shù)據(jù)元素，稱為一條記錄(Record)。下面給出相關(guān)的一些概念：

(1)查找表。是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合，可利用任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。

(2)查找表的操作：①查詢某個“特定的”數(shù)據(jù)元素是否在查找表中。②檢索某個“特定的”數(shù)據(jù)元素的各種屬性。③在查找表中插入一個數(shù)據(jù)元素。④從查找表中刪去某個數(shù)據(jù)元素。若對查找表只進(jìn)行前兩種“查找”操作，則稱此類查找表為靜態(tài)查找表(StaticSearchTable)；若在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素，則稱此類查找表為動態(tài)查找表(DynamicSearchTable)。

(3)關(guān)鍵字。數(shù)據(jù)元素的某個數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識列表中的一個或一組數(shù)據(jù)元素。如果一個關(guān)鍵字可以唯一標(biāo)識列表中的一個數(shù)據(jù)元素，則稱其為主關(guān)鍵字，如上表中的“學(xué)號”，否則為次關(guān)鍵字，如上表中的“高等數(shù)學(xué)”。當(dāng)數(shù)據(jù)元素僅有一個數(shù)據(jù)項(xiàng)時，數(shù)據(jù)元素的值就是關(guān)鍵字。

(4)查找。根據(jù)給定的關(guān)鍵字值，在特定的列表中確定一個其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。若找到相應(yīng)的數(shù)據(jù)元素，則稱查找是成功的，否則稱查找是失敗的，此時應(yīng)返回空地址及失敗信息，并可根據(jù)要求插入這個不存在的數(shù)據(jù)元素。關(guān)鍵字(key)可以作為查找的依據(jù)。在本章的各個算法及示例中，只給出各數(shù)據(jù)元素的關(guān)鍵字，而忽略其它數(shù)據(jù)項(xiàng)的內(nèi)容，如無特別說明，均認(rèn)為要查找的數(shù)據(jù)集合中元素的類型如下：typedefstructelem{KeyTypekey； /*關(guān)鍵字*/

… /*其他數(shù)據(jù)項(xiàng)*/}ET；衡量查找算法效率的標(biāo)準(zhǔn)是平均查找長度。為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個數(shù)的期望值，稱為查找算法在查找成功時的平均查找長度。對于長度為n的查找表，查找成功時的平均查找長度為

ASL

=

P1C1?+?P2C2?+?…

+?Pn?Cn?=?其中，Pi為查找第i個數(shù)據(jù)元素的概率，Ci為找到第i個數(shù)據(jù)元素時已經(jīng)進(jìn)行過的關(guān)鍵字比較次數(shù)。由于查找算法的基本運(yùn)算是關(guān)鍵字之間的比較操作，因此可用平均查找長度來衡量查找算法的性能。查找的基本方法可以分為兩大類，即比較式查找法和計算式查找法。其中比較式查找法又可以分為基于線性表的查找法和基于樹的查找法，而計算式查找法也稱為HASH(哈希)查找法。8.2基于線性表的查找法基于線性表的查找可以分為順序查找法、折半查找法(或稱二分查找法)以及分塊查找法。8.2.1順序查找順序查找(SequentialSearch)又稱為線性查找，是一種最簡單的查找方法。其基本思想是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個比較，直到成功或失敗。存儲結(jié)構(gòu)通常為順序結(jié)構(gòu)，也可為鏈?zhǔn)浇Y(jié)構(gòu)。下面給出用C語言描述的順序結(jié)構(gòu)有關(guān)數(shù)據(jù)類型的定義：#defineLISTSIZE20#defineKeyTypeint /*關(guān)鍵字類型*/#defineOtherTypeint /*其他數(shù)據(jù)項(xiàng)類型*/typedefstruct{KeyTypekey;OtherTypeother-data;}RecordType;typedefstruct{RecordTyper[LISTSIZE+1]; /*r[0]為工作單元*/intlength;}RecordList;基于順序結(jié)構(gòu)的線性查找算法如下：intSeqSearch(RecordListl,KeyTypek)/*在順序表l中順序查找其關(guān)鍵字等于k的元素，查找成功則返回該元素在表中的位置，否則為0*/{inti;l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return(i);}其中l(wèi).r[0]稱為監(jiān)視哨，即l.r[0].key?=w?k，以便控制循環(huán)最多執(zhí)行到數(shù)組中下標(biāo)為0的元素位置，可以起到防止越界的作用。不用監(jiān)視哨的算法如下：intSeqSearch(RecordListl,KeyTypek)/*不用監(jiān)視哨法，在順序表中查找關(guān)鍵字等于k的元素*/{inti;i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>=1)return(i)elsereturn(0);}其中，循環(huán)條件i?>=1判斷查找是否越界。利用監(jiān)視哨可省去這個條件，從而提高查找效率。下面用平均查找長度來分析一下順序查找算法的性能。假設(shè)列表長度為n，那么查找第i個數(shù)據(jù)元素時需進(jìn)行n-i?+?1次比較，即Ci?=?n-i?+?1。又假設(shè)查找每個數(shù)據(jù)元素的概率相等，即Pi=1/n，則順序查找算法的平均查找長度為查找失敗時的平均查找長度為n。假設(shè)被查找記錄在查找表中的概率為P，則不在查找表中的概率為1-P，考慮到查找成功和失敗兩種情況下的平均查找長度為可見，順序查找雖然簡單，但查找效率卻很低。8.2.2折半查找我們先來玩一個“猜數(shù)”游戲：甲先在心中想好一個100以內(nèi)的整數(shù)x，然后讓乙來猜，每次甲可提示乙所猜的數(shù)是比x大還是比x小，乙怎樣才能猜得快呢？學(xué)習(xí)完這一節(jié)，相信你就能得到答案。再來看看查英文字典的方法，我們并不需要從最前或最后開始逐個查找，為什么呢？因?yàn)樽值涫前醋帜傅拇涡蚺帕械?。換句話說，在按某關(guān)鍵字排序的有序表中進(jìn)行查找，效率會比順序查找更高。這就是在有序表中采用的折半查找。折半查找法(BinarySearch)又稱為二分法查找法，這種方法要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。其基本過程是：將表中間位置記錄的關(guān)鍵字與查找關(guān)鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、后兩個子表，如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子表，否則進(jìn)一步查找后一子表。重復(fù)以上過程，直到找到滿足條件的記錄時查找成功，或直到子表不存在為止，此時查找不成功。

例8.1

已知含有11個數(shù)據(jù)元素的有序表，其關(guān)鍵字序列如下：(7，13，18，25，46，55，58，61，67，69，72)現(xiàn)要查找關(guān)鍵字為58，30的數(shù)據(jù)元素。用指針low和high分別指示待查元素所在范圍的下界與上界，指針mid指示區(qū)間的中間位置，則有初始時，取low=0，high=10。下面先看查找關(guān)鍵字為58的數(shù)據(jù)元素的過程：第一次比較：mid=5，58＞55，則low=mid+1=6，high不變。第二次比較：mid=8，58＜67，則low不變，high=mid–1=7。第三次比較：mid=6，58==58查找成功。三次查找比較如圖8.1所示。下面再看查找關(guān)鍵字為30的數(shù)據(jù)元素的過程：第一次比較：mid=5，30＜55，則low不變，high=4。第二次比較：mid=2，30＞18，則low=3，high不變。第三次比較：mid=3，30＞25，則low=4，high不變。第四次比較：mid=4，30＜46，則low不變，high=3。此時，low>high，結(jié)束查找，說明查找不成功。四次查找比較如圖8.2所示。圖8.1折半查找成功圖8.2折半查找失敗折半查找算法用C語言描述如下：intBinSrch(SqListl,KeyTypek)/*在有序表l中折半查找其關(guān)鍵字等于k的元素，查找成功則返回該元素在表中的位置，查找失敗返回0*/{intlow,high,mid；low=0; /*置區(qū)間初值*/high=l.length-1; while(low<=high){mid=(low+high)/2;if(k==l.r［mid］.key) /*找到待查元素*/return(mid+1); /*數(shù)組下標(biāo)從0開始，元素位置從1開始，為mid+1*/elseif(k<l.r［mid］.key)high=mid-1; /*未找到，則繼續(xù)在前半?yún)^(qū)間進(jìn)行查找*/elselow=mid+1; /*未找到，繼續(xù)在后半?yún)^(qū)間進(jìn)行查找*/}return(0);}下面我們來分析折半查找的平均查找長度。折半查找過程可用一個稱為判定樹的二叉樹描述，判定樹中每一結(jié)點(diǎn)對應(yīng)表中一個記錄，但結(jié)點(diǎn)值不是記錄的關(guān)鍵字，而是記錄在表中的位置序號(或用數(shù)組下標(biāo)表示)。根結(jié)點(diǎn)對應(yīng)當(dāng)前區(qū)間的中間記錄，左子樹對應(yīng)前一子表，右子樹對應(yīng)后一子表。顯然，找到有序表中任一記錄的過程，對應(yīng)判定樹中從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑，而所做比較的次數(shù)恰為該結(jié)點(diǎn)在判定樹上的層次數(shù)。因此，折半查找成功時，關(guān)鍵字比較次數(shù)最多不超過判定樹的深度。由二叉樹的性質(zhì)可知，判定樹的深度為?

log2n

+1，因此，折半查找在查找成功與不成功時和給定值進(jìn)行比較的關(guān)鍵字個數(shù)最多不超過

log2n

?+?1。對于例8.1中長度為11的有序表，它的折半查找的二叉判定樹(用數(shù)組下標(biāo)表示)如圖8.3所示。在進(jìn)行查找時，首先要進(jìn)行比較的記錄是r[5]，因此該二叉判定樹的根結(jié)點(diǎn)表示為⑤。若x==r[5].key，則查找成功；若x＜r[5].key，則沿著根結(jié)點(diǎn)的左子樹繼續(xù)下層結(jié)點(diǎn)的比較；若x＞r[5].key，則沿著根結(jié)點(diǎn)的右子樹繼續(xù)下層結(jié)點(diǎn)的比較；所以一次成功的查找所需的比較次數(shù)最多不超過對應(yīng)的二叉判定樹深度。圖8.3折半查找的二叉判定樹例如查找關(guān)鍵字為58的記錄所走的路徑為⑤→⑧→⑥，比較3次。一次不成功的查找所需的比較次數(shù)也不會超過對應(yīng)的二叉判定樹深度。例如查找關(guān)鍵字為30的記錄所走的路徑為⑤→②→③→④，比較4次。那么折半查找的平均查找長度是多少呢？為便于討論，假定表的長度n?=?2h-1，則相應(yīng)判定樹必是深度為h的滿二叉樹，h?=?log2(n?+?1)。又假設(shè)每個記錄的查找概率相等Pi=1/n，則折半查找成功時的平均查找長度為當(dāng)n較大時，有ASL?=?log2(n?+?1)-1可見，折半查找的效率比順序查找要高，但折半查找只適用于順序存儲的有序表。8.3基于樹的查找基于樹的查找法又稱為樹表查找法，是將待查表組織成特定樹的形式并在樹結(jié)構(gòu)上實(shí)現(xiàn)查找的方法，主要包括二叉排序樹、平衡二叉排序樹和B樹等。本章只介紹二叉排序樹。8.3.1二叉排序樹的定義二叉排序樹或者是空樹，或者是滿足如下性質(zhì)的二叉樹：

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

(2)若其右子樹非空，則右子樹上所有結(jié)點(diǎn)的值均大于等于根結(jié)點(diǎn)的值。

(3)其左右子樹本身又各是一棵二叉排序樹。如圖8.4所示就是兩棵二叉排序樹。圖8.4二叉排序樹(a)二叉排序樹示例；(b)根據(jù)ASCII碼大小排序的二叉排序樹示例由二叉排序樹的定義不難發(fā)現(xiàn)，按中序遍歷一棵二叉排序樹，將得到一個以關(guān)鍵字遞增排列的有序序列。8.3.2二叉排序樹上的操作

1.查找因?yàn)槎媾判驑淇煽醋魇且粋€有序表，所以在二叉排序樹上進(jìn)行查找與折半查找類似，也是一個逐步縮小查找范圍的過程。根據(jù)二叉排序樹的特點(diǎn)，首先將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果：

(1)?k?=?t，則返回根結(jié)點(diǎn)地址。

(2)?k＜t，則進(jìn)一步查左子樹。

(3)?k＞t，則進(jìn)一步查右子樹。顯然這是一個遞歸過程。用C語言描述如下：typedefstructnode{

KeyTypekey;

structnode*lchild;

structnode*rchild;}BSTNode,BSTree;BSTree*SearchBST(BSTree*T,KeyTypex)/*在根指針T所指二叉排序樹中，遞歸查找某關(guān)鍵字等于x的元素，若查找成功，則返回指向該元素結(jié)點(diǎn)指針，否則返回空指針*/{if(!T)returnNULL; /*樹為空，查找失敗，返回*/elseif(T->key==x)returnT;/*查找成功*/

else

if(x<T->key) returnSearchBST(T->lchild,x);

/*在左子樹中繼續(xù)查找*/ else returnSearchBST(T->rchild,x);

/*在右子樹中繼續(xù)查找*/}

例8.2

在圖8.5中查找關(guān)鍵字為55和關(guān)鍵字為40的兩個節(jié)點(diǎn)。

解：55大于根結(jié)點(diǎn)關(guān)鍵字值50，因而向它的右子樹查找；55小于右子樹根結(jié)點(diǎn)的關(guān)鍵字的值60，然后向左子樹找；此時的左子樹根結(jié)點(diǎn)關(guān)鍵字值為55，與所找結(jié)點(diǎn)的值相同，查找成功。圖8.5二叉排序樹再來看一下關(guān)鍵字值為40的結(jié)點(diǎn)，首先40小于根結(jié)點(diǎn)關(guān)鍵字值50，因而向根結(jié)點(diǎn)的左子樹查找；40大于根結(jié)點(diǎn)關(guān)鍵字值10，因而向關(guān)鍵值為10的結(jié)點(diǎn)的右子樹查找；40大于根結(jié)點(diǎn)關(guān)鍵值30，繼續(xù)向鍵值為30結(jié)點(diǎn)的右子樹找，但此時它的右子樹為空，查找失敗，返回空指針NULL。

2.插入與生成已知一個關(guān)鍵字值為x的結(jié)點(diǎn)s，若將其插入到二叉排序樹中，只要保證插入后仍符合二叉排序樹的定義即可。插入可以用下面的方法進(jìn)行：

(1)若二叉排序樹是空樹，則x成為二叉排序樹的根；

(2)若二叉排序樹非空，則將x與二叉排序樹的根進(jìn)行比較。如果x的值等于根結(jié)點(diǎn)的值，則停止插入；如果x的值小于根結(jié)點(diǎn)的值，則將x插入左子樹；如果x的值大于根結(jié)點(diǎn)的值，則將x插入右子樹。相應(yīng)的遞歸算法如下：voidInsertBST(BSTree*T,KeyTypex)/*若在二叉排序樹中不存在關(guān)鍵字等于x的元素，插入該元素*/{BSTree*s;if(T==NULL) /*遞歸結(jié)束條件*/{ s=(BSTree*)malloc(sizeof(BSTNode)); /*申請新的結(jié)點(diǎn)s*/ s->key=x;s->lchild=NULL; s->rchild=NULL; T=s; } elseif(x<T->key) InsertBST(T->lchild,x); /*將s插入左子樹*/ elseif(key>T->key) InsertBST(T->rchild,x); /*將s插入右子樹*/}假若給定一個元素序列，可以利用上述算法創(chuàng)建一棵二叉排序樹。首先，將二叉排序樹初始化為一棵空樹，然后逐個讀入元素，每讀入一個元素，就建立一個新的結(jié)點(diǎn)并插入到當(dāng)前已生成的二叉排序樹中，即調(diào)用上述二叉排序樹的插入算法將新結(jié)點(diǎn)插入。生成二叉排序樹的算法如下：voidCreateBST(BSTree*T)/*從鍵盤輸入元素的值，創(chuàng)建相應(yīng)的二叉排序樹*/{KeyTypekey; T=NULL; scanf(″%d″,&key); while(key!=ENDKEY)

/*ENDKEY為自定義常數(shù)*/{InsertBST(T,key);scanf(″%d″,&key);}}

例8.3

對于關(guān)鍵字值序列(45，24，53，12，28，90)，求出建立二叉排序樹的過程。

解：建立二叉排序樹的過程如圖8.6所示。值得注意的是，對于同一個關(guān)鍵字值集合，如果插入的順序不同，生成的二叉排序樹也可能不同。上例中如果關(guān)鍵字序列為(24，12，53，28，45，90)，則得到的二叉排序樹如圖8.7所示：圖8.6二叉排序樹的建立過程空樹；(b)插入45；(c)插入24；(d)插入53；(e)插入12；(f)插入28；(g)插入90圖8.7輸入順序不同所建立的不同二叉排序樹

3.刪除從二叉排序樹中刪除一個結(jié)點(diǎn)，不能把以該結(jié)點(diǎn)為根的子樹都刪去，只能刪掉該結(jié)點(diǎn)，并且還應(yīng)保證刪除后所得的二叉樹仍然滿足二叉排序樹的性質(zhì)不變。也就是說，在二叉排序樹中刪去一個結(jié)點(diǎn)相當(dāng)于刪去有序序列中的一個結(jié)點(diǎn)。刪除操作首先要查找，以確定被刪結(jié)點(diǎn)是否在二叉排序樹中。若不在，則不做任何操作；否則，假設(shè)要刪除的結(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)；如圖8.8所示，這叫“無后而終”。圖8.8刪除二叉排序樹中葉子結(jié)點(diǎn)(a)原樹；(b)刪除2后

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

f->lchild?=?p->lchild(或f->lchild?=?p->rchild)；

free(p)；如圖8.9所示，這叫“子承父業(yè)”。圖8.9刪除二叉排序樹中只有一棵子樹的結(jié)點(diǎn)(a)原樹；(b)刪除30和65后

(3)若p既有左子樹，又有右子樹，如圖8.10(a)所示。這時要首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，然后可采用兩種不同的處理方法。s是p的左子樹上“最右邊”的結(jié)點(diǎn)，它的右子樹一定為空，否則s的直接后繼就會在它的右子樹上，而不會是p了。方法1：首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，然后將p的左子樹改為f的左子樹，而將p的右子樹改為s的右子樹：

f->lchild?=?p->lchild；

s->rchild?=p->rchild；

free(p)；結(jié)果如圖8.10(b)所示，這叫“左子繼位，右子接前驅(qū)”。方法2：首先找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)s結(jié)點(diǎn)，然后用s結(jié)點(diǎn)的值替代p結(jié)點(diǎn)的值，原s結(jié)點(diǎn)的左子樹改為s的雙親結(jié)點(diǎn)sf的右子樹，再將s結(jié)點(diǎn)刪除：

p->data?=?s->data；

sf->rchild=s->lchild；

free(s)；結(jié)果如圖8.10(c)所示，這叫“前驅(qū)替代，依次升級”。圖8.10刪除二叉排序樹中有左右子樹的結(jié)點(diǎn)(a)原樹；(b)刪除10后(方法1)；(c)刪除10后(方法2)8.3.3性能分析在二叉排序樹上進(jìn)行查找時，若查找成功，則顯然是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到待查結(jié)點(diǎn)的路徑。若查找不成功，則是從根結(jié)點(diǎn)出發(fā)走了一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑。因此二叉排序樹的查找與折半查找類似，其查找比較次數(shù)不超過樹的高度。但是，折半查找二叉判定樹的結(jié)點(diǎn)是記錄在表中的位置序號，樹的形態(tài)與數(shù)據(jù)值無關(guān)，其平均查找長度是一定的。而從例8.3可以看出，對于同一個關(guān)鍵字值集合，如果結(jié)點(diǎn)插入的先后次序不同，所形成的二叉排序樹形態(tài)就可能不同，則平均查找長度也就不同。給定二叉排序樹的形態(tài)，等概率查找成功時的ASL=∑Ci/n(Ci為第i個結(jié)點(diǎn)所在的層)。最壞的情況下，二叉排序樹是通過把一個有序表的n個結(jié)點(diǎn)依次插入生成的，由此得到的二叉排序樹退化在一棵高度為n的單支樹，對它的查找相當(dāng)于對線性表的查找，平均查找長度為(n+1)/2。最好的情況下，二叉排序樹在生成過程中，樹的形態(tài)比較均勻，所得二叉排序樹類似折半查找的判定樹，此時平均查找長度約為log2n。如果插入的數(shù)據(jù)是隨機(jī)的，則平均查找長度為O(log2n)。8.4計算式查找法——哈希法在前面介紹的幾種查找方法中，無論是線性查找表還是樹表，記錄在存儲結(jié)構(gòu)中的位置是隨機(jī)的，即存儲位置與記錄關(guān)鍵字之間沒有確定的關(guān)系，其查找操作是通過給定值與記錄關(guān)鍵字之間的比較進(jìn)行的，查找的效率與比較的次數(shù)密切相關(guān)。哈希(Hash)法又稱散列法、雜湊法或關(guān)鍵字地址計算法等，相應(yīng)的表稱為哈希表。哈希技術(shù)既是一種存儲方法，又是一種查找方法。它是通過某種方法的計算，在記錄關(guān)鍵字與其存儲位置之間建立確定的對應(yīng)關(guān)系，這種關(guān)系一旦確定，每條記錄都存儲在固定的存儲單元中，查找時只需根據(jù)這種對應(yīng)關(guān)系，找到給定值對應(yīng)的存儲位置，從而達(dá)到按關(guān)鍵字直接存取記錄的目的。8.4.1哈希法哈希法的基本思想是：首先在元素的關(guān)鍵字k和元素的存儲位置p之間建立一個對應(yīng)關(guān)系H，使得p?=?H(k)，H稱為哈希函數(shù)。創(chuàng)建哈希表時，把關(guān)鍵字為k的元素直接存入地址為H(k)的單元；以后當(dāng)查找關(guān)鍵字為k的元素時，再利用哈希函數(shù)計算出該元素的存儲位置p?=?H(k)，從而達(dá)到按關(guān)鍵字直接存取元素的目的。例如某個會議按與會者的姓名筆畫總數(shù)排定座位號，則關(guān)鍵字為“姓名”，哈希函數(shù)為“求筆畫總數(shù)”，計算的結(jié)果是存取地址“座位號”。則“丁三”的位置是5號，“王五”的位置是8號，他們按此號就座，查找時也可按此號直接找到。當(dāng)關(guān)鍵字集合很大時，關(guān)鍵字值不同的元素可能會映像到哈希表的同一地址上，即k1≠k2，但H(k1)=H(k2)，這種現(xiàn)象稱為沖突，此時稱k1和k2為同義詞。例如按上面的座位號計算函數(shù)，“劉二”的位置也是8號，與“王五”位置相同，這就發(fā)生了沖突。實(shí)際中，沖突是不可避免的，只能通過改進(jìn)哈希函數(shù)的性能來減少沖突。綜上所述，哈希法主要包括以下兩方面的內(nèi)容：

(1)如何構(gòu)造哈希函數(shù)。

(2)如何處理沖突。8.4.2哈希函數(shù)的構(gòu)造方法

Hash表查找技術(shù)的主要目標(biāo)是提高查找效率，縮短查表時間。而在查找關(guān)鍵字為k的元素時，計算哈希函數(shù)H(k)的工作量也是影響查找效率的一個因素。如果哈希函數(shù)的計算比較復(fù)雜，即使沖突的機(jī)會很少，也會降低查找效率。因此，在實(shí)際設(shè)計哈希函數(shù)時，要考慮以下兩方面的因素:

(1)使各關(guān)鍵字盡可能均勻地分布在哈希表中，即哈希函數(shù)值的均勻性要好。

(2)哈希函數(shù)值的計算要盡量簡單。以上兩個方面在實(shí)際應(yīng)用中往往是矛盾的。為了保證哈希函數(shù)值的均勻性比較好，其哈希函數(shù)值的計算就必然要復(fù)雜；反之，如果哈希函數(shù)值的計算比較簡單，則其均勻性就比較差。因此，在實(shí)際設(shè)計哈希函數(shù)值時，要根據(jù)具體情況，選擇一個比較合理的方案。構(gòu)造哈希函數(shù)的方法多種多樣，下面只介紹一些比較常用的、計算比較簡單的方法。

1.數(shù)字分析法如果事先知道關(guān)鍵字集合，并且每個關(guān)鍵字的位數(shù)比哈希表的地址碼位數(shù)多時，可以從關(guān)鍵字中選出分布較均勻的若干位，構(gòu)成哈希地址。例如，以學(xué)號作為關(guān)鍵字，關(guān)鍵字為9位十進(jìn)制整數(shù)d1d2d3…d7d8d9，d1～d2表示入學(xué)年份，d3～d4表示院系，d5～d6表示專業(yè)，d7表示班級，d8～d9表示學(xué)生序號，07級計算機(jī)系軟件專業(yè)一班15號同學(xué)的學(xué)號為07

04

01

1

15。該班共有學(xué)生50人，如哈希表長取100，則哈希表的地址空間為：00～99。經(jīng)過分析，各關(guān)鍵字中d8和d9的取值分布較均勻，則哈希函數(shù)為：H(key)?=?H(d1d2d3…d7d8d9)=d8d9。例如，H(070401143)?=?43，H(070401106)?=?06。相反，經(jīng)過分析，各關(guān)鍵字中其他位的取值分布都極不均勻，d1都等于0，d7都等于1，此時，如果哈希函數(shù)為：H(key)=H(d1d2d3…d7d8)?=?d1d7，則所有關(guān)鍵字的地址碼都是01，顯然不可取。

2.平方取中法當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因?yàn)椋浩椒街抵虚g幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈希地址。例如：把英文字母在字母表中的位置序號作為該英文字母的內(nèi)部編碼。K，E，Y，A，B的內(nèi)部編碼分別為11，05，25，01,02。由此組成關(guān)鍵字“KEYA”的內(nèi)部代碼為11052501，同理我們可以得到關(guān)鍵字“KYAB”、“AKEY”、“BKEY”的內(nèi)部編碼。之后對關(guān)鍵字進(jìn)行平方運(yùn)算后，取出第7到第9位作為該關(guān)鍵字哈希地址，如表8-2所示。表8-2平方取中法求得的哈希地址

3.除留余數(shù)法這是一種最常用的方法，是用關(guān)鍵字k除以一個不大于哈希表長的最大素數(shù)，將所得的余數(shù)作為Hash函數(shù)值。假設(shè)哈希表長為m，p為小于等于m的最大素數(shù)，則哈希函數(shù)為

H(k)=k%p,(p≤m),其中%為模p取余運(yùn)算。例如，已知待散列元素為(18，75，60，43，54，90，46)，表長m?=?10，p?=?7，則有H(18)=18%7=4H(75)=75%7=5H(60)=60%7=4H(43)=43%7=1H(54)=54%7=5H(90)=90%7=6H(46)=46%7=4此時沖突較多。為減少沖突，可取較大的m值和p值，如m=p=13，結(jié)果如下：H(18)=18%13=5H(75)=75%13=10H(60)=60%13=8H(43)=43%13=4H(54)=54%13=2H(90)=90%13=12H(46)=46%13=7

4.分段疊加法按散列表地址位數(shù)將關(guān)鍵字分成位數(shù)相等的幾部分(最后一部分可以較短)，然后將這幾部分相加，舍棄最高進(jìn)位后的結(jié)果，即是該關(guān)鍵字的散列地址。具體方法有折疊法和移位法。移位法是將分割后的每部分低位對齊相加；折疊法是從一端向另一端沿分割界來回折疊(奇數(shù)段為正序，偶數(shù)段為倒序)，然后將各段相加。例key?=?12360324711202065，散列表長度為1000，則應(yīng)把關(guān)鍵字分成3位一段，在此舍去最低的兩位65，分別進(jìn)行移位疊加和折疊疊加，求得Hash地址為105和907，如圖8.11所示。圖8.11由疊加法計算Hash地址(a)移位疊加；(b)折疊疊加

5.偽隨機(jī)數(shù)法選擇一個偽隨機(jī)函數(shù)，取關(guān)鍵字的偽隨機(jī)函數(shù)值為它的哈希地址。即H(key)?=?random(key)其中，random為偽隨機(jī)函數(shù)。在實(shí)際應(yīng)用中，應(yīng)根據(jù)具體情況，靈活采用不同的方法，并用實(shí)際數(shù)據(jù)測試它的性能，以便做出正確判定。通常應(yīng)考慮以下五個因素：(1)計算哈希函數(shù)所需的時間(簡單)。(2)關(guān)鍵字的長度。(3)哈希表的大小。(4)關(guān)鍵字的分布情況。(5)記錄查找的頻率。8.4.3處理沖突的方法通過構(gòu)造性能良好的哈希函數(shù)，可以減少沖突，但一般情況下不可能完全避免沖突，因此解決沖突是哈希技術(shù)的另一個關(guān)鍵問題。下面介紹兩種常用的解決哈希沖突的方法。

1.開放定址法這種方法也稱再散列法，其基本思想是：當(dāng)關(guān)鍵字key的哈希地址p=H(key)出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi，將相應(yīng)元素存入其中。這種方法有一個通用的再散列函數(shù)形式：Hi?=?(H(key)?+?di)%m(i=1,2,…,m)其中，H(key)為哈希函數(shù)，m為表長，di稱為增量序列。使用這種方法時,首先計算出它的直接哈希地址H(key)，若該單元已被其它記錄占用，繼續(xù)查看地址為H(key)?+?d1的單元，若該單元也已被占用，繼續(xù)查看地址為H(key)?+?d2的單元，如此下去，當(dāng)發(fā)現(xiàn)某個單元為空時，將關(guān)鍵字為key的記錄存放到該單元中。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。主要有以下三種：

1)線性探測再散列

di?=?1，2，3，…，m-1這種方法的特點(diǎn)是：沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

2)二次探測再散列

di?=?12，-12，22，-22，…，k2，-k2(k≤m/2)這種方法的特點(diǎn)是：沖突發(fā)生時，在表的左右進(jìn)行跳躍式探測，比較靈活。

3)偽隨機(jī)探測再散列

di?=?偽隨機(jī)數(shù)序列。具體實(shí)現(xiàn)時，應(yīng)建立一個偽隨機(jī)數(shù)發(fā)生器，(如i=(i+p)%m)，并給定一個隨機(jī)數(shù)做起點(diǎn)。

例8.4

有一記錄關(guān)鍵字序列(24，3，13，15，20，0，54，43),要將它們存入表長為11的哈希表A中，散列函數(shù)為：H(key)?=?key%11。分別采用線性探測再散列和二次探測再散列解決沖突，試為其構(gòu)造相應(yīng)的哈希表。

解：(1)采用線性探測再散列：

H(24)?=?2，不沖突，直接存入A[2]。

H(3)?=?3，不沖突，直接存入A[3]。

H(13)?=?2，沖突，計算下一個哈希地址，H1(13)=(2+1)%11=3，沖突，繼續(xù)計算H2(13)?=?(2+2)%11?=?4，不沖突，存入A[4]。

H(15)?=?4，沖突，計算下一個哈希地址，H1(15)?=?(4?+?1)%11?=?5，不沖突，存入A[5]。

H(20)?=?9，不沖突，直接存入A[9]。

H(0)?=?0，不沖突，直接存入A[0]。

H(54)?=?10，不沖突，直接存入A[10]。

H(43)?=?10，沖突，計算下一個哈希地址，H1(43)?=?(10?+?1)%11?=?0，沖突，繼續(xù)計算H2(43)?=?(10+2)%11?=?1，不沖突，存入A[1]。用線性探測再散列法構(gòu)造的哈希表如圖8.12所示。圖8.12線性探測再散列采用二次探測再散列：

H(24)?=?2，不沖突，直接存入A[2]。

H(3)?=?3，不沖突，直接存入A[3]。

H(13)?=?2，沖突，計算下一個哈希地址，H1(13)?=?(2?+?1)%11?=?3，沖突，繼續(xù)計算H2(13)?=?(2-1)%11?=?1，不沖突，存入A[1]。H(15)?=?4，不沖突，直接存入A[4]。

H(20)?=?9，不沖突，直接存入A[9]。

H(0)?=?0，不沖突，直接存入A[0]。

H(54)?=?10，不沖突，直接存入A[10]。

H(43)?=?10，沖突，計算下一個哈希地址，H1(43)=(10+1)%11=0，沖突，繼續(xù)計算H2(43)?=?(10-1)%11=9，沖突，計算H3(43)?=?(10?+?4)%11?=?3，沖突，計算H4(43)?=?(10-4)%11?=?6，不沖突，存入A[6]。用二次探測再散列法構(gòu)造的哈希表如圖8.13所示。圖8.13二次探測再散列在哈希表中怎樣查找記錄呢？哈希表的查找過程與哈希表的創(chuàng)建過程是一致的。當(dāng)查找關(guān)鍵字為k的元素時，首先計算p0?=?H(key)。如果單元p0為空，則所查元素不存在；如果單元p0中元素的關(guān)鍵字為k，則找到所查元素；否則重復(fù)下述解決沖突的過程：按解決沖突的方法，找出下一個哈希地址pi，如果單元pi為空，則所查元素不存在；如果單元pi中元素的關(guān)鍵字為k，則找到所查元素。線性探測再散列方法的優(yōu)點(diǎn)是簡單，且只要散列表不滿，就一定能找到一個不沖突的散列地址，而二次探測再散列和偽隨機(jī)探測再散列則不一定。但線性探測再散列有以下三個主要的缺點(diǎn)：

(1)在線性哈希表的填入過程中，當(dāng)沖突發(fā)生時，首先考慮的是下一項(xiàng)，因此，當(dāng)沖突次數(shù)較多時，在線性哈希表中會存在“群聚”的現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會降低查找效率。

(2)若在線性哈希表中刪除一條記錄，有可能造成某些記錄查找不成功，而事實(shí)上該記錄存在于哈希表中；例如在例8.4中，若已刪除24，查找13時，H(13)?=?2，但A[2]已為空，便認(rèn)為查找失敗，而事實(shí)上13放在了A[4]中。

(3)在線性哈希表的填入過程中，處理沖突時會帶來新的沖突，線性哈希表的填入方法是不顧后效的。

2.鏈地址法這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進(jìn)行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況，也適用于沖突現(xiàn)象比較嚴(yán)重的情況。

例8.5

已知一組關(guān)鍵字(32，40，36，53，16，46，71，27，42，24，49，64)，哈希表長度為13，哈希函數(shù)為：H(key)=key%13，求采用鏈地址法處理沖突時的平均查找長度。

解：采用鏈地址法處理沖突時的哈希表如圖8.14所示。平均查找長度ASL=(1×7+2×4+3×1)/12=1.5圖8.14鏈地址法處理沖突時的哈希表8.4.4哈希法性能分析由于沖突的存在，哈希法仍需進(jìn)行關(guān)鍵字比較，因此仍需用平均查找長度來評價哈希法的查找性能。哈希法中影響關(guān)鍵字比較次數(shù)的因素有三個：哈希函數(shù)、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子α的定義如下：

α可描述哈希表的裝滿程度。顯然，α越小，發(fā)生沖突的可能性越小，而α越大，發(fā)生沖突的可能性越大。假定哈希函數(shù)是均勻的，即該哈希函數(shù)對同一組中的各個關(guān)鍵字產(chǎn)生沖突的可能性是相同的，則影響平均查找長度的因素只剩下兩個：處理沖突的方法以及α。哈希表的平均查找長度是裝填因子α的函數(shù)，而與待散列元素數(shù)目n無關(guān)。因此，無論元素數(shù)目n有多大，都能通過調(diào)整α，使哈希表的平均查找長度較小。在用開放定址法構(gòu)造哈希表時，會產(chǎn)生非哈希函數(shù)引起的沖突，且記錄的個數(shù)不能大于哈希表表長。采用鏈地址法則不會出現(xiàn)這些情況，但需要一些額外的空間。本章小結(jié)本章學(xué)習(xí)了與查找有關(guān)的一些基本概念，學(xué)習(xí)了線性表、樹表及哈希表查找法。線性表查找法介紹順序查找和折半查找，折半查找只適用于順序存儲的有序表，其關(guān)鍵字比較次數(shù)最多不超過判定樹的深度。樹表查找法介紹了二叉排序樹的查找、插入、刪除，二叉排序樹上進(jìn)行查找時的平均查找長度和二叉排序樹上的形態(tài)有關(guān)。哈希查找法是一種計算式查找方法，本章介紹了哈希查找的概念和基本思想。實(shí)現(xiàn)哈希查找必須要構(gòu)造合適的哈希函數(shù)，構(gòu)造哈希函數(shù)的方法有多種多樣，常用的有數(shù)字分析法、平方取中法、除留余數(shù)法、分段疊加法和偽隨機(jī)數(shù)法。哈希函數(shù)是一種“壓縮映射”，它把記錄關(guān)鍵字取值很大的數(shù)據(jù)集合映射到一個范圍確定的表中，因此，沖突是不可避免的，本章介紹了兩種解決沖突的主要方法，即開放定址法和鏈地址法。習(xí)題八

一、單選題

1.對線性表進(jìn)行二分查找時,要求線性表必須

。

A.以順序方式存儲 B.以鏈接方式存儲

C.以順序方式存儲且結(jié)點(diǎn)按關(guān)鍵字有序排列

D.以鏈接方式存儲且結(jié)點(diǎn)按關(guān)鍵字有序排列

2.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為

。

A.?nB.?n/2 C.?(n?+?1)/2D.?(n-1)/2

3．采用二分查找長度為n的線性時，每個元素的平均查找長度為

。

A.?O(n2) B.O?(nlog2n)

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

4.有一個有序表為(5，7，8，22，32，40，45，62，70，77，82，97，100)，當(dāng)二分查找值為82的結(jié)點(diǎn)時，

次比較后查找成功。

A.

1

B.

3

C.

4 D.

8

5.從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，查找成功的情況下，需平均比較

個結(jié)點(diǎn)。

A.

n

B.

n/2C.

(n–1)/2

D.

(n

+

1)/2

二、填空題

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

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

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

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

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

，平均查找長度為

。

2.在散列存儲中，裝填因子α的值越大，存取數(shù)據(jù)元素時發(fā)生沖突的可能性

；α的值越小，則發(fā)生沖突的可能性

。

三、簡答題設(shè)有一組關(guān)鍵字(19，01，23，14，55，20，84，27，68，11，10，77)，采用哈希函數(shù)H(key)=key%13采用開放地址法的線性探測再散列方法解決沖突，試在[0…12]的散列地址空間中對該關(guān)鍵字序列構(gòu)造哈希表。2.對上題中的關(guān)鍵字序列，采用鏈地址法，畫出相應(yīng)的哈希表。

3.對有序表(5，8，27，36，45，48，57，72，89，95)，采用二分查找，畫出二分查找過程的二叉判定樹，并計算其平均查找長度。

四、算法設(shè)計題

1.將折半查找算法改寫為遞歸的形式。

2.以線性探測再散列為例，給出散列表的查找算法。實(shí)訓(xùn)8-1分塊查找【實(shí)訓(xùn)目的】掌握順序查找與折半查找的特點(diǎn)?！緦?shí)訓(xùn)要求】用分塊查找【相關(guān)知識】分塊查找又稱索引順序查找。它是一種順序查找的改進(jìn)方法，用于在分塊有序表中進(jìn)行查找。分塊有序表指將長度為n的線性表分成m個子表，各子表的長度可以相等，也可不等，但要求后一個子表中的每一個元素均大于前一個子表中的所有元素。分塊有序表的結(jié)構(gòu)可以分為兩個部分：

(1)采用順序存儲的線性表。

(2)索引表。在索引表中，對線性表的每一個子表建立一個索引結(jié)點(diǎn)，每個結(jié)點(diǎn)包括兩個域：一是數(shù)據(jù)域，用于存放對應(yīng)子表的最大元素值；二是指針域，用于指示對應(yīng)子表的第一個元素在整個線性表中的序號。索引表關(guān)于數(shù)據(jù)域是有序的。圖8.15是將一個長度n=18的線性表分成m=3個子表的分塊有序表示意圖。圖8.15分塊有序表示意圖(a)采用順序存儲的線性表；(b)索引表【算法分析】根據(jù)分塊有序表的結(jié)構(gòu)，其查找過程可以分為以下兩步：

(1)查找索引表，以確定被查元素所在的子表。由于索引表數(shù)據(jù)域的數(shù)據(jù)是有序的，因此可以采用折半查找。

(2)在相應(yīng)的子表中采用順序查找?！境绦蚯鍐巍縯ypedefstructindnode{intkey; /*數(shù)據(jù)域，存放子表中的最大值*/intk; /*指針域，指示子表中第一個元素在線性表中的序號*/}Inode;

/*折半查找索引表，順序查找子表*/intinserch(intv[],intn,Inodes[],intm,intx)

/*函數(shù)返回被查找元素x在線性表中的序號，如果不存在元素x，則返回-1*/

/*v:待查找表，n:最后元素下標(biāo)，s:索引表，m:塊數(shù)，

x:待查值*/{inti,j,t;i=1; /*起始塊號*/j=m; /*終止塊號*/

/*折半查找索引表*/while(j-i>1) /*塊號相差>1，則循環(huán)，結(jié)束時要確定x在i,i+1兩塊之中*/{t=(i+j)/2;if(x<=s[t].key)j=t;/*可能在第t塊或t塊以下*/elsei=t; /*在第t塊以上*/}if((i!=j)&&(x>s[i].key))i=j; /*j==i+1,且x不在第i塊中，則必在第j塊，調(diào)整i，使其