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

第八章查找8.1概述8.3基于樹(shù)的查找8.5算法總結(jié)8.2基于線性表的查找8.4散列8.1概述1、

列表(查找表):是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合,可由任意數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)。2、關(guān)鍵字:數(shù)據(jù)元素中某數(shù)據(jù)項(xiàng)的值,用以標(biāo)識(shí)(識(shí)別)一個(gè)(組)數(shù)據(jù)元素(記錄)。若關(guān)鍵字可以唯一的識(shí)別一個(gè)記錄，則稱之為“主關(guān)鍵字”；若關(guān)鍵字識(shí)別的記錄不唯一，則稱之為“次關(guān)鍵字”。3、查找

根據(jù)某個(gè)給定值,在列表中確定其關(guān)鍵字等于給定值的數(shù)據(jù)元素(記錄)的過(guò)程稱為查找。

若列表中存在待查記錄,則稱“查找成功”。查找結(jié)果給出整個(gè)記錄的信息,或指示該記錄在列表中的位置；

若列表中不存在待查紀(jì)錄,則稱“查找不成功”.查找結(jié)果給出“空記錄”或“空指針”。4、查找表的分類1)靜態(tài)查找表:僅作查詢和檢索操作的列表。2)動(dòng)態(tài)查找表:不僅作查詢和檢索操作，還經(jīng)常進(jìn)行插入和刪除操作的列表。

在查找算法中要用到三類參量，即：①查找對(duì)象K（找什么）②查找范圍L（在哪找）③查找的結(jié)果（K在L中的位置）其中①②為輸入?yún)⒘?，在函?shù)中不可缺少；③為輸出參量，可用函數(shù)返回值表示。5、平均查找長(zhǎng)度為確定數(shù)據(jù)元素在列表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度。對(duì)于長(zhǎng)度為n的列表，查找成功時(shí)的平均查找長(zhǎng)度為：nASL=P1C1+P2C2+…+PnCn

=i=1PiCi其中：Pi為查找列表中第i個(gè)數(shù)據(jù)元素的概率，

Ci為找到列表中第i個(gè)數(shù)據(jù)元素時(shí)，已經(jīng)進(jìn)行過(guò)的關(guān)鍵字比較次數(shù)。6、查找的基本方法：查找方法：比較式查找法計(jì)算式查找法－HASH(哈希)查找法基于線性表的查找法基于樹(shù)的查找法8.2基于線性表的查找有順序查找、折半查找和索引查找法三種一、順序查找法順序查找的特點(diǎn)是：用所給關(guān)鍵字與線性表中各元素的關(guān)鍵字逐個(gè)比較，直到成功或失敗。存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)#defineMAXSIZE1000Typedef

int

KeyTypetypedef

struct{

KeyTypekey;

OtherTypeother_data; }RecordType;typedef

struct{

RecordTyper[MAXSIZE+1];

/*r[0]為工作單元*/

intlength; }SeqRList;1、順序結(jié)構(gòu)數(shù)據(jù)類型定義：順序查找過(guò)程示例：或ii假設(shè)給定值k=64,要求r[i].key=k,問(wèn):i=?結(jié)果:i=7

2137881992

5

6456807513…

901234567891011

niiiiiii2、順序查找算法int

SeqSearch（SeqRListL,KeyTypeK）{i=L.length;while(i>=1&&L.r[i].key!=K)i--;if(i>=1)return（i）elsereturn(0);}循環(huán)條件i>=1判斷查找是否越界。設(shè)置監(jiān)視哨的順序查找算法int

SeqSearch（SeqRListL,KeyTypeK）{L.r[0].key=K;i=L.length;while(L.r[i].key!=K)i--;return（i）;}l.r[0]為監(jiān)視哨，可以防止越界。例：

2137881992

5

6456807513…

901234567891011

niiK=56

2137881992

5

6456807513…

901234567891011

n56結(jié)果:i=8iiK=6060結(jié)果:i=03、順序查找的時(shí)間復(fù)雜度分析?i=1PiCiASL=n因?yàn)椋簩?duì)順序表而言：Ci=n-i+1在等概率查找的情況下：順序表查找成功的平均查找長(zhǎng)度為：順序表查找不成功的平均查找長(zhǎng)度為：

ASLSS=n+1所以，順序表查找的時(shí)間復(fù)雜度為:O(n)二、折半查找法（二分搜索法）條件：要求待查找的列表必須是按關(guān)鍵字大小有序排列的順序表。查找方法：由于列表是按關(guān)鍵字有序排列，所以可以基于“折半確定區(qū)間”的思想進(jìn)行查找。優(yōu)點(diǎn)：比較次數(shù)少，查找速度快;缺點(diǎn)：要求表為有序表，插入、刪除困難。1、概念例如:nK=64

的查找過(guò)程如下：lowhighmid

mid

midlow

：指示查找區(qū)間的下界high：指示查找區(qū)間的上界mid=(low+high)/2:每次比較、劃分區(qū)間的“點(diǎn)”lowhigh0123456789101105131921375664758088922、折半查找算法int

BinSrch

（SeqRListL,KeyTypeK）

{low=1;high=L.length;/*置區(qū)間初值*/while(low<=high){mid=(low+high)/2;

if(K==L.r[mid].key)return（mid）;

/*找到待查元素*/

elseif(K<L.r[mid].key)high=mid-1;

/*繼續(xù)在前半?yún)^(qū)間查找*/

elselow=mid+1;

/*繼續(xù)在后半?yún)^(qū)間查找*/}return(0);}3、折半查找時(shí)間復(fù)雜度分析先看一個(gè)具體的情況，假設(shè)：n=11折半查找判定樹(shù)1223333444

46391471025811一般情況,表長(zhǎng)為n的折半查找判定樹(shù)的深度和含有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度相同。假設(shè)n=2h-1并且查找概率相等則ASLbs?log2(n+1)-1所以，折半查找的時(shí)間復(fù)雜度為:O(logn)最壞情況查找長(zhǎng)度為二叉樹(shù)的深度：log2n+1查找不成功時(shí)的比較次數(shù)最多也為：log2n+1當(dāng)n>50時(shí)近似為三、索引查找分塊查找要將列表組織成以下索引順序結(jié)構(gòu)：★首先將列表分成若干個(gè)塊(子表),一般情況下塊的長(zhǎng)度均勻,最后一塊可以不滿。每塊中元素任意排列(塊內(nèi)無(wú)序)，但塊與塊之間有序?！飿?gòu)造一個(gè)索引表,其中每個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)塊,

記錄每塊的起始位置及每塊中的最大關(guān)鍵字

(或最小關(guān)鍵字)。索引表按關(guān)鍵字有序排列。

整個(gè)表由兩部分組成：基本塊表與索引表。例：224886

1

6

12索引表各塊最大關(guān)鍵字

各塊起始地址221213

8

9

3342382448287449…12345678910111213…分塊查找過(guò)程1)由索引確定記錄所在的塊(折半或順序查);2)在塊內(nèi)進(jìn)行查找(順序查)。索引可以根據(jù)查找表的特點(diǎn)來(lái)構(gòu)造?？梢?jiàn):

索引順序表查找的過(guò)程也是一個(gè)

“縮小區(qū)間”的查找過(guò)程。

分塊查找時(shí)間復(fù)雜度分析分塊查找的平均查找長(zhǎng)度=

查找“索引”的平均查找長(zhǎng)度

+“塊內(nèi)”查找的平均查找長(zhǎng)度

若n個(gè)記錄分為b塊，每塊含s個(gè)記錄，則等概率情況下,順序查找索引時(shí)：

ASL=(b+1)/2+(s+1)/2=(n/s+s)/2+1

可以證明：當(dāng)s=√n時(shí),ASL取最小值√n+1折半查找索引時(shí)：ASL=log2(n/s+1)+s/2.線性表的三種查找方法比較順序查找折半查找索引查找表的結(jié)構(gòu)有序、無(wú)序有序表間有序表的存儲(chǔ)順序、鏈?zhǔn)巾樞蝽樞?、鏈?zhǔn)紸SL最大最小次之8.3基于樹(shù)的查找法一、二叉排序樹(shù)二、平衡二叉樹(shù)三、B樹(shù)和B+樹(shù)四、伸展樹(shù)五、紅黑樹(shù)

8.3.1二叉排序樹(shù)（二叉查找樹(shù)）一、定義二、查找三、插入四、刪除五、性能分析一、定義：（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；二叉排序樹(shù)：或者是一棵空樹(shù)，或者是具有如下特性的二叉樹(shù)：（3）左、右子樹(shù)也分別為二叉排序樹(shù)。（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；例如:是二叉排序樹(shù)。不50308020901085403525238866*中序遍歷一個(gè)二叉排序樹(shù),可以得到一個(gè)遞增有序序列。

typedef

structNode{KeyTypekey;/*關(guān)鍵字的值*/

……

structnode*Lchild,*Rchild;/*左右指針*/}BSTNode,*BSTree;通常用二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)二、查找根據(jù)二叉排序樹(shù)的特點(diǎn)，查找過(guò)程如下：（1）k=t：則查找成功，返回根結(jié)點(diǎn)地址；（2）k<t：則進(jìn)一步查左子樹(shù)；（3）k>t：則進(jìn)一步查右子樹(shù)。顯然這是一個(gè)遞歸過(guò)程，可用遞歸算法實(shí)現(xiàn)查找。若二叉排序樹(shù)為空，則查找不成功；否則將待查關(guān)鍵字k與根結(jié)點(diǎn)關(guān)鍵字t進(jìn)行比較，如果：例如:50308020908540358832二叉排序樹(shù)查找關(guān)鍵字==50,505035,503040355090,50809095,從上述查找過(guò)程可見(jiàn)：在查找過(guò)程中，生成了一條查找路徑：

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點(diǎn);或者

從根結(jié)點(diǎn)出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹(shù)為止。

——查找成功

——查找不成功BSTree

SearchBST(BSTree

bst,KeyType

K){if(!bst)returnNULL;else

if(bst->key==K)returnbst;else

if(K<bst->key)returnSearchBST(bst->lchild,key);else

returnSearchBST(bst->rchild,key);}二叉排序樹(shù)查找的遞歸算法BSTree

SearchBST(BSTree

bst,KeyType

K){BSTreeq;q=bst;while(q){if(q->key==K)returnq;

if(K<q->key)q=q->lchild;

elseq=q->rchild;}returnNULL;}二叉排序樹(shù)查找的非遞歸算法三、插入1、若二叉排序樹(shù)為空樹(shù)，則s成為二叉排序樹(shù)的根；2、若二叉樹(shù)排序樹(shù)非空，則將key與二叉樹(shù)排序樹(shù)根結(jié)點(diǎn)的值t進(jìn)行比較，如果:已知關(guān)鍵字值為Key的結(jié)點(diǎn)由s指示，將其插入二叉排序樹(shù)的過(guò)程為：（1）key=t：不進(jìn)行插入；（2）key<t：則將s插入左子樹(shù)；（3）key>t：則將s插入右子樹(shù)。顯然，可以用遞歸算法實(shí)現(xiàn)插入。voidInsertBST(BSTree*bst,KeyType

K){BiTrees;

if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s->key=K;*bst=s;s->lchild=NULL;s->rchild=NULL;}

else

if(K<(*bst)->key)

InsertBST(&((*bst)->lchild),K);else

if(K>(*bst)->key)

InsertBST(&((*bst)->rchild),K);}二叉排序樹(shù)插入算法二叉排序樹(shù)的生成算法給定一個(gè)元素序列，可以利用插入算法逐步創(chuàng)建一棵二叉排序樹(shù)。將二叉排序樹(shù)初始化為一棵空樹(shù)，然后逐個(gè)讀入元素，每讀入一個(gè)元素，就調(diào)用上述插入算法將新元素插入當(dāng)前已生成的二叉排序樹(shù)中，直至元素序列插入完畢。voidCreateBST(BSTree*bst){KeyTypekey;*bst=NULL;

scanf("%d",&key);while(key!=ENDKEY){InsertBST(bst,key);scanf("%d",&key);}}例如：元素輸入序列為：45,24,53,12,28,90,按上述算法生成的二叉排序樹(shù)的過(guò)程：空樹(shù)45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90對(duì)同樣一組元素值，如果輸入的順序不同，所建的二叉排序樹(shù)形態(tài)也不同。241228539045如將上述關(guān)鍵字順序變?yōu)?24,53,90,12,28,45,則生成的二叉排序樹(shù)為：四、刪除可分三種情況討論：（1）被刪除的結(jié)點(diǎn)是葉子；（2）被刪除的結(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)；（3）被刪除的結(jié)點(diǎn)左、右子樹(shù)都有。和插入相反，刪除在查找成功之后進(jìn)行,并且要求在刪除二叉排序樹(shù)上某個(gè)結(jié)點(diǎn)之后,仍然保持二叉排序樹(shù)的特性。（1）被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)50802090403588328530例如:被刪關(guān)鍵字=2088其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為“空”（2）被刪除結(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指向被刪除結(jié)點(diǎn)的左子樹(shù)或右子樹(shù)”。被刪關(guān)鍵字=408080405020908588323035（3）被刪除的結(jié)點(diǎn)既有左子樹(shù)也有右子樹(shù)方法一：找被刪結(jié)點(diǎn)p在中序序列中的直接前驅(qū)結(jié)點(diǎn)s(如圖a所示),將p的左子樹(shù)改為f(p的雙親)的左子樹(shù)，將p的右子樹(shù)改為s的右子樹(shù),結(jié)果如圖(b)所示。

f->lchild=p->lchild；s->rchild=p->rchild；free(p)；FPCPRfpcSQQLSLqsCL(a)S為P的直接前驅(qū)CLFCSSLPRfc(b)將P的左子樹(shù)改為f的左子，將P的右子樹(shù)改為S的右子樹(shù)。方法二：找到p結(jié)點(diǎn)在中序序列中的直接前驅(qū)結(jié)點(diǎn)s(如圖a所示),用s結(jié)點(diǎn)的值替代p結(jié)點(diǎn)的值,再將s結(jié)點(diǎn)刪除,原s結(jié)點(diǎn)的左子樹(shù)改為s的雙親結(jié)點(diǎn)q的右子樹(shù),如圖(b)所示。

p->data=s->data；q->rchild=s->lchild；free(s)；FPCPRfpcSQQLSLqsCL(a)S為P的直接前驅(qū)(b)將原P結(jié)點(diǎn)的值改為S結(jié)點(diǎn)的值，刪除原S結(jié)點(diǎn)并將原S的左子樹(shù)改為Q的右子樹(shù)FSCPRfpcQQLSLqCL例：方法二被刪關(guān)鍵字=5040508090858820323035以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點(diǎn)4040被刪結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)二叉排序樹(shù)刪除算法BSTNode*DelBST(BSTree

bst,KeyTypeK){BSTNode*p,*f,*s,*q;p=bst;f=NULL;

while(p){if(p->key==K)break;f=p;if（p->key>K）

p=p->lchild;elsep=p->rchild;}

if(p==NULL)returnbst;if(p->lchild==NULL)/*p沒(méi)有左子樹(shù)*/{if(f==NULL)bst=p->rchild;

elseif(f->lchild==p)f->lchild=p->rchild

；

elsef->rchild=p->rchild;free(p);}else/*p有左子樹(shù)*/{q=p;s=p->lchild;

while(s->rchild){q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;

elseq->rchild=s->lchild;p->key=s->key;free(s);}returnbst;}

時(shí)間復(fù)雜度為：O(LOG2N)五、二叉排序樹(shù)的查找性能對(duì)于一組相同的關(guān)鍵字序列，關(guān)鍵字插入的先后次序不同，所構(gòu)成的二叉排序樹(shù)的形態(tài)及深度即不同。二叉排序樹(shù)的平均查找長(zhǎng)度ASL與二叉排序樹(shù)的形態(tài)有關(guān)：二叉排序樹(shù)的各分支越均衡,樹(shù)的深度越淺，其平均查找長(zhǎng)度ASL越小。例如：452412375393(a)輸入關(guān)鍵字序列為{45,24,53,12,37,93}時(shí)的二叉排序樹(shù)12122437455393(b)輸入關(guān)鍵字序列為{12,24,37,45,53,93}時(shí)的二叉排序樹(shù)假設(shè)每個(gè)元素的查找概率相等，則它們的平均查找長(zhǎng)度分別是：ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6由此可見(jiàn)，在二叉排序樹(shù)上進(jìn)行查找時(shí)的平均查找長(zhǎng)度和二叉排序樹(shù)的形態(tài)有關(guān)。若考慮把n個(gè)結(jié)點(diǎn)，按各種可能的次序插入到二叉排序樹(shù)中，則有n！棵二叉排序樹(shù)（其中有的形態(tài)相同）,可以證明，這些二叉排序樹(shù)的平均查找長(zhǎng)度仍然是O(log2n)。8.3.2平衡二叉樹(shù)

對(duì)于二叉排序樹(shù),高度越低查找速度就越快。為此可在構(gòu)造二叉排序樹(shù)的過(guò)程中進(jìn)行樹(shù)形的優(yōu)化，即平衡化處理,使其成為平衡二叉排序樹(shù)。樹(shù)中每個(gè)結(jié)點(diǎn)的左、右子樹(shù)深度之差的絕對(duì)值不大于1，。1、定義：平衡二叉樹(shù)(AVL樹(shù))或是一顆空樹(shù)，或者是具有如下特性的二叉樹(shù)：例如：5472是平衡樹(shù)不是平衡樹(shù)547218結(jié)點(diǎn)的平衡因子：結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度。

平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是-1、0、1，否則不是平衡二叉樹(shù)。例如:平衡二叉樹(shù)不平衡的二叉樹(shù)10010100-12因此，若構(gòu)造的二叉樹(shù)排序樹(shù)是平衡二叉樹(shù)，則可大大降低其查找長(zhǎng)度?？梢宰C明：平衡二叉樹(shù)的深度與logn是同數(shù)量級(jí)2、平衡二叉排序樹(shù)的構(gòu)造

二叉排序樹(shù)的構(gòu)造過(guò)程，是不斷插入新結(jié)點(diǎn)(葉子)的過(guò)程。插入新結(jié)點(diǎn)后,如果失去平衡則應(yīng)立即進(jìn)行平衡化調(diào)整，一般以失去平衡的最小子樹(shù)為調(diào)整對(duì)象,隨時(shí)的調(diào)整可確保二叉排序樹(shù)的平衡。在一般二叉排序樹(shù)的結(jié)點(diǎn)中增加一個(gè)存放平衡因子的域bf。例:輸入(13,24,37,90,53),構(gòu)造過(guò)程如下：13132413243713243790132437539013243790531324373790132453例：402560203010000AB(a)平衡二叉排序樹(shù)402560203020101AB150(b)插入15后失去平衡25204015300010BA6000?調(diào)整后的二叉排序樹(shù)(a)平衡二叉排序樹(shù)2520403060-10000AB2520403060-2-10-10AB700(b)插入70后失去平衡40256030700-1000AB200?調(diào)整后的二叉排序樹(shù)例：18010904020306050708595A0000C000000B(a)一棵平衡二叉排序樹(shù)8010904020306050708595A0001C01000-1B4502(b)插入45后失去平衡060108040203050457090C-100100000BA859500?調(diào)整后的二叉排序樹(shù)(a)一棵平衡二叉排序樹(shù)-140A0508060709085950C00000B2010300000-240A1508060709085950C00-11B2010300040A508060709085950C00B201030005500(b)插入55后失去平衡0040C20608090859500B402007050551030-100000A?調(diào)整后的二叉排序樹(shù)(1)LL型旋轉(zhuǎn):

左子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)而失去平衡，應(yīng)進(jìn)行順時(shí)針旋轉(zhuǎn)。

各種情況下，平衡化調(diào)整的規(guī)則可歸納為如下四種旋轉(zhuǎn)：BAARBRBL新21ABARBRBL新00LL型失衡的特點(diǎn)是：A->bf=2，B->bf=1。操作：B=A->Lchild；A->Lchild=B->rchild；

B->rchild=A；A->bf=0；

B->bf=0；

(2)RR型旋轉(zhuǎn):右子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)而失去平衡，應(yīng)進(jìn)行逆時(shí)針旋轉(zhuǎn)。BAALBLBR新-2-1ABBLALBR新00RR型失衡的特點(diǎn)是：A->bf=-2，B->bf=-1。操作：B=A->rchild；A->rchild=B->lchild；

B->lchild=A；A->bf=0；

B->bf=0；

(3)LR型旋轉(zhuǎn):左子樹(shù)的右子樹(shù)上插入結(jié)點(diǎn)而失去平衡,應(yīng)進(jìn)行先逆時(shí)針后順時(shí)針旋轉(zhuǎn)。CBAARCRCL新BL2-11CBAARCRCL新BL00-1LR型失衡的特點(diǎn)是：A->bf=2，B->bf=-1。操作：B=A->lchild；C=B->Rchild；B->rchild=C->lchild；

A->lchild=C->rchild；C->lchild=B；C->rchild=A；(4)RL型旋轉(zhuǎn):右子樹(shù)的左子樹(shù)上插入結(jié)點(diǎn)而失去平衡,應(yīng)進(jìn)行先順時(shí)針后逆時(shí)針旋轉(zhuǎn)。CBAALCRCL新BR-211CABBRCRCL新AL00-1RL型失衡的特點(diǎn)是：A->bf=-2，B->bf=1。操作:B=A->rchild；C=B->lchild；B->lchild=C->rchild；

A->rchild=C->lchild；C->lchild=A；C->rchild=B；8.4散列

一、哈希表的定義二、hash函數(shù)的構(gòu)造方法三、處理沖突的方法四、hash表的查找五、hash法性能分析8.4.1哈希表的定義以上討論的各種查找表的共同特點(diǎn)為：

記錄在表中的位置和它的關(guān)鍵字之間不存在一個(gè)確定的關(guān)系，查找的過(guò)程是“基于”比較。查找的效率取決于和給定值進(jìn)行比較的次數(shù),這類方法的平均查找長(zhǎng)度為O(logn)---O(n)。對(duì)頻繁使用的查找表,希望ASL---〉0。能否做到？能！若以下標(biāo)為000~999的順序表表示之。如：為招收的1000名新生建立一張查找表,

其關(guān)鍵字為學(xué)號(hào),其值的范圍為xx000~xx999(前兩位為年份)。則查找過(guò)程可以簡(jiǎn)單進(jìn)行：取給定學(xué)號(hào)的后三位，不需要經(jīng)過(guò)比較便可直接從順序表中找到待查關(guān)鍵字。

另例：1、各年齡人口信息統(tǒng)計(jì)表；

2、解放后各年國(guó)民經(jīng)濟(jì)信息統(tǒng)計(jì)表。上述幾例的特點(diǎn)為：記錄在表中的位置與其關(guān)鍵字之間存在一種確定的對(duì)應(yīng)關(guān)系,按此對(duì)應(yīng)關(guān)系可根據(jù)關(guān)鍵字的值尋址，從而獲得待查紀(jì)錄。這種查找表稱為哈希表，關(guān)鍵字與記錄地址間的對(duì)應(yīng)關(guān)系稱為哈希函數(shù)f(key)

。{Zi,Qi,Su,Li,Wu,Ci,He,Ye,Du}

又例：對(duì)于如下9個(gè)關(guān)鍵字設(shè)

哈希函數(shù)f(key)=

(Ord(第一個(gè)字母)-Ord('A')+1)/2CiZiQiSuLiWuHeYeDu問(wèn)題:

若需添加關(guān)鍵字Zh,怎么辦？此類問(wèn)題稱為“沖突”，如何解決？

0123

4567

8

9

10

11

12

13從上述例子可見(jiàn)：哈希表的構(gòu)造、使用中有兩個(gè)問(wèn)題有待研究：1、如何根據(jù)關(guān)鍵字集合的特點(diǎn)，選擇合適的哈希函數(shù)，使關(guān)鍵字均勻的散列到表中？2、當(dāng)不同的關(guān)鍵字所得的哈希函數(shù)值相同時(shí)，即f(k1)=f(k2),如何有效的處理這類“沖突”現(xiàn)象（碰撞），使建表、查找均能有效地進(jìn)行？根據(jù)選定的函數(shù)H(key)

和處理沖突的方法,將一組關(guān)鍵字映象到一個(gè)有限的、連續(xù)的地址集(區(qū)間)上，并以每個(gè)關(guān)鍵字在地址集中的“映象”作為相應(yīng)記錄在表中的存儲(chǔ)位置，由此構(gòu)造所得的查找表稱為“哈希表”

(散列表、雜湊表),所選擇的函數(shù)H(key)稱為哈希函數(shù)。哈希表的定義：若是非數(shù)字關(guān)鍵字，則需先對(duì)其進(jìn)行數(shù)字化處理。5.

基數(shù)轉(zhuǎn)換法3.平方取中法1.除留余數(shù)法4.分段疊加法2.數(shù)字分析法

“好的”哈希函數(shù)應(yīng)該是“均勻”的，對(duì)數(shù)字型關(guān)鍵字，一般有下列哈希函數(shù)的構(gòu)造方法：二、構(gòu)造哈希函數(shù)的方法設(shè)定哈希函數(shù)為:H(key)=keyMODp其中：p≤m(表長(zhǎng))

也可對(duì)2,3,4種方法的結(jié)果取模。

這是一種簡(jiǎn)單且適用范圍很廣的哈希函數(shù)，但要求：1、P不能取關(guān)鍵字基數(shù)的冪；

2、P應(yīng)盡可能的取質(zhì)數(shù)，或不包含小于20的質(zhì)因數(shù)的合數(shù)；

3、P應(yīng)盡可能的接近m。1.除留余數(shù)法此方法僅適合于：能預(yù)先估計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由s位數(shù)字組成(u1,u2,…,us)，分析關(guān)鍵字集中的全體,去掉數(shù)字重復(fù)出現(xiàn)頻度很高的位,提取數(shù)字均勻分布的若干位或它們的組合作為地址。2.

數(shù)字分析法

以關(guān)鍵字平方值的中間幾位作為存儲(chǔ)地址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大差別”,平方值的中間幾位與整個(gè)關(guān)鍵字中的每一位數(shù)字都相關(guān)。

此方法適合于:

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻度很高的現(xiàn)象。3.平方取中法

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈希地址。有兩種疊加處理的方法：移位疊加和間界疊加。

此方法適合于:

關(guān)鍵字的數(shù)字位數(shù)特別多，且每一位的數(shù)字分布大致均勻。4.分段疊加法首先將關(guān)鍵字看成是另一種進(jìn)制的數(shù)，然后再轉(zhuǎn)換成原來(lái)進(jìn)制的數(shù)，再選擇其中幾位作為散列地址。例如：對(duì)于十進(jìn)制關(guān)鍵字先把它看成是十三進(jìn)制數(shù)，再轉(zhuǎn)換為十進(jìn)制數(shù)。5.

基數(shù)轉(zhuǎn)換法

實(shí)際造表時(shí),采用何種方法來(lái)構(gòu)造哈希函數(shù),考慮的因素有：建表的關(guān)鍵字集合的情況(包括關(guān)鍵字的范圍和形態(tài)),哈希表的大小,哈希函數(shù)計(jì)算時(shí)間和查找頻率。總的原則是:減少集聚現(xiàn)象,在關(guān)鍵字取值范圍內(nèi),使哈希函數(shù)值盡量均勻散列在函數(shù)值范圍內(nèi),從而使產(chǎn)生沖突的可能性盡量減小。為產(chǎn)生沖突的關(guān)鍵字尋找下一個(gè)哈希地址。1.開(kāi)放定址法2.鏈地址法除了需要選擇一個(gè)“好”(盡可能少產(chǎn)生沖突)的哈希函數(shù)之外；還需要找到一種“處理沖突”

的方法。其含義是：三、處理沖突的方法

為產(chǎn)生沖突的關(guān)鍵字H(key)求得一個(gè)探測(cè)地址序列(在其中逐個(gè)探測(cè)空哈希地址)：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+

di

)MODm

di

為探測(cè)增量有三種，i=1,2,…,m-1

1.開(kāi)放定址法(1)線性探測(cè)再散列

di=ci

最簡(jiǎn)單的情況

c=1(2)平方探測(cè)再散列

di=12,-12,22,-22,…,(3)隨機(jī)探測(cè)再散列

di

是一組偽隨機(jī)數(shù)列或者

di=i×H2(key)(又稱雙散列函數(shù)探測(cè))探測(cè)增量序列

di

的三種取法：即：產(chǎn)生的Hi

均不相同,且m-1個(gè)Hi值能覆蓋

哈希表中所有地址。則要求：

注意：增量di

應(yīng)具有“完備性”※

隨機(jī)探測(cè)時(shí)的m

和di

應(yīng)沒(méi)有公因子；※

平方探測(cè)時(shí)的表長(zhǎng)

m

應(yīng)為形如4j+3

的素?cái)?shù)（如:7,11,19,23,…等）；※

避免二次聚集。012345678910例如哈希表長(zhǎng)m=11，現(xiàn)有關(guān)鍵字集合：

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11

190123145568(1)采用線性探測(cè)再散列處理沖突1182361121362510123456789101901231468(2)采用二次探測(cè)再散列處理沖突55118236112121412ASL=22/9ASL=15/9設(shè)：H2(key)=(3key)MOD10+1

di=i×H2(key)190123145568118236211121214ASL=15/9012345678910(3)采用雙散列函數(shù)探測(cè)線性探測(cè)處理沖突時(shí)：ASL=雙散列探測(cè)處理沖突時(shí)：ASL=22/915/9二次探測(cè)處理沖突時(shí)：ASL=15/9本例不同的處理沖突方法的ASL為：將所有哈希地址相同的記錄都鏈接在同一鏈表中。

012345614

0136198223116855ASL=(6×1+2×2+3)/9=13/9設(shè)哈希函數(shù)為：H(key)=keyMOD7顯然不會(huì)發(fā)生二次聚集2.鏈地址法：

哈希表的查找過(guò)程和造表過(guò)程一致。

對(duì)于給定值K，計(jì)算哈希地址i=H(K)若r[i]=NULL則查找不成功若r[i].key=K則查找成功否則“求下一地址Hi”

，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)為止。采用開(kāi)放定址處理沖突，則查找過(guò)程為：四、哈希表的查找數(shù)據(jù)類型描述為#defineHASHSIZE11

typedef

struct{intkey;

otherdat