第九章 查找課件

卷

煙

料

福

W出

小

普就

費(fèi)

。

查找的概念

查找表是由同一類型的數(shù)據(jù)元素（或記錄）

構(gòu)成的集合，由于“集合”中的數(shù)據(jù)元素之

間存在著松散的關(guān)系，因此查找表是一種

應(yīng)用靈便的數(shù)據(jù)結(jié)構(gòu)。對(duì)查找表的操作:

■查詢某個(gè)“特定的”數(shù)據(jù)元素是否在查找表中；

■檢索某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；

■在查找表中插入一個(gè)數(shù)據(jù)元素；

■從查找表中刪去某個(gè)數(shù)據(jù)元素

查找表的分類:

靜態(tài)查找表

僅作查詢和檢索操作的查找表。

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

在查找過程中同時(shí)插入查找表中不存在的

數(shù)據(jù)元素，或者從查找表中刪除已存在的某個(gè)

數(shù)據(jù)元素，此類表為動(dòng)態(tài)查找表。

關(guān)鍵字

是數(shù)據(jù)元素（或記錄）中某個(gè)數(shù)據(jù)項(xiàng)

的值，用以標(biāo)識(shí)（識(shí)別）一個(gè)數(shù)據(jù)元素

（或記錄）。若此關(guān)鍵字可以識(shí)別唯一的

一個(gè)記錄，則稱之謂“主關(guān)鍵字”。若此

關(guān)鍵字能識(shí)別若干記錄，則稱之謂“次關(guān)

鍵字”。

查找

根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)

鍵字等于給定值的數(shù)據(jù)元素或（記錄）。

若查找表中存在這樣一個(gè)記錄，則稱“查

找成功”，查找結(jié)果：給出整個(gè)記錄的信

息，或指示該記錄在查找表中的位置；

否則稱“查找不成功”，查找結(jié)果：給

出

“空記錄”或“空指針”。

如何進(jìn)行查找？

查找的方法取決于查找表的結(jié)構(gòu)。

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組

織規(guī)律，因此不便于查找。

為了提高查找的效率，需要在查找表中的

元素之間人為地附加某種確定的關(guān)系，換句

話說，用另外一種結(jié)構(gòu)來表示查找表。

查找方法評(píng)價(jià)

?查找速度

?占用存儲(chǔ)空間多少

?算法本身復(fù)雜程度

?平均查找長(zhǎng)度ASL(AverageSearchLength):

為確定記錄在表中的位置，需和給定值進(jìn)行比

較的關(guān)鍵字的個(gè)數(shù)的期望值叫查找算法的?

n

對(duì)含有〃個(gè)記錄的表，ASL=￡pc.

n

其中：P,為查找表中第，個(gè)元素的概率，Epj=T

Z=1

為找到表中第個(gè)元素所需比較次數(shù)

c.I2

磬態(tài)查找表

抽象數(shù)據(jù)類型靜態(tài)查找表的定義：

ADTStaticSearchTable{

數(shù)據(jù)對(duì)象D:D是具有相同特性的

數(shù)據(jù)元素的集合。每

個(gè)數(shù)據(jù)元素含有類型

相同的關(guān)鍵字，可唯

一標(biāo)識(shí)數(shù)據(jù)元素。

數(shù)據(jù)關(guān)系R:數(shù)據(jù)元素同屬一個(gè)集合。

基本操作P:

Create(&ST,n);//構(gòu)造一個(gè)含n個(gè)數(shù)據(jù)

元素的靜態(tài)查找表ST。

Destroy(&ST);〃銷毀表ST。

Search(ST,key);//查找ST中其關(guān)鍵字等

于kval的數(shù)據(jù)元素。

//按某種次序?qū)?/p>

Traverse(ST5Visit());

ST的每個(gè)元素調(diào)用函數(shù)

Visit。一次且僅一次，

}ADTStaticSearchTable

■順序表的查找

以順序表表示靜態(tài)查找表）則Search函數(shù)可

用順序查找來實(shí)現(xiàn)。其順序存儲(chǔ)結(jié)構(gòu)如下：

typedefstruct{

ElemType*elem;〃數(shù)據(jù)元素存儲(chǔ)空間基址，建表時(shí)

按實(shí)際長(zhǎng)度分配，o號(hào)單元留空

intlength;//表的長(zhǎng)度

}SSTable;

查找過程：從表的一端開始逐個(gè)進(jìn)行記

錄的關(guān)鍵字和給定值的比較。

例如:

Ottt

???

O111

比較次數(shù)：比較次數(shù)=5

查找第n個(gè)元素：1

查找第ml個(gè)元素：2

查找第1個(gè)元素：n

查找第i個(gè)元素：n+1-i

查找失?。簄+1

算法描述：

intSearch_Seq(SSTableST,

KeyTypekval){

//在順序表ST中順序查找其關(guān)鍵字等于

〃key的數(shù)據(jù)元素。若找到，則函數(shù)值為

〃該元素在表中的位置，否則為0。

ST.elem[0].key=kval;〃設(shè)置“哨兵”

for(i=ST.length;ST.elem[i].key!=kval;-i)；

//從后往前找

returni;〃找不到時(shí)，i為o

}//SearchSeq

順序查找性能分析

查找算法的平均查找長(zhǎng)度(AverageSearchLength):

為確定記錄在查找表中的位置，需和給定值

進(jìn)行比較的關(guān)鍵字個(gè)數(shù)的期望值。

n

ASL=VPC

其中：n為表長(zhǎng)士’’

匕為查找表中第i個(gè)記錄的概率z戶,=i

Z=1

Ci為找到該記錄時(shí)，曾和給定值比較過的

關(guān)鍵字的個(gè)數(shù)

對(duì)順序表而言)Cj=n-i+1

ASL=nPi+(n-l)P2++2Pn/+Pn

1

在等概率查找的情況下，p=-

i

n

順序表查找的平均查找長(zhǎng)度為：

1〃n+1

ASLS,=-z僅一，+i)=—

ni=\2

在不等概率查找的情況下，ASL§s在

pn>pnl>…>P2>P1

時(shí)取極小值。表中記錄按查找概率由小到

達(dá)重新排列，以提高查找效率。

若查找概率無法事先測(cè)定，則查找過

程采取的改進(jìn)辦法是，在每次查找之后，

將剛剛查找到的記錄直接移至表尾的位置

上。

■有序表的查找

順序表的查找算法簡(jiǎn)單，但平均查找長(zhǎng)

度較大，不適用于表長(zhǎng)較大的查找表。

若以有序表表示靜態(tài)查找表，則查找過

程可以基于“折半”進(jìn)行。

折半查找

查找過程：每次將待查記錄所在區(qū)間縮小一半。

適用條件：采用順序存儲(chǔ)結(jié)構(gòu)的有序表。

折半查找算法實(shí)現(xiàn)

1.設(shè)表長(zhǎng)為n,low、high和mid分別指向待查

元素所在區(qū)間的上界、下界和中點(diǎn),k為給定

值。

2.初始時(shí)，令

low=l,high=n5mid=L（low+high）/2j

讓k與mid指向的記展比較

若k==r[mid].key）查找成功

若k〈r[mid].key）則high=mid-l

若k>r[mid].key）則low=mid+l

3.重復(fù)上述操作）直至low>high時(shí)）查找失

敗。

high指示查找區(qū)間的上界;

mid=(low+high)/2o

IOMmidhigh

1234567891011

513192137566475808892

mid

當(dāng)下界low大于上界high時(shí)，則說明表中

沒有關(guān)鍵字等于Key的元素，查找不成功。

折半查找算法

intSearchBin(SSTableST,KeyTypekval){

low=1;high=ST.length;〃置區(qū)間初履

while(low<=high){

mid=(low+high)/2;

if(kval==ST.elem[mid].key)

returnmid;//找至j待查元素

elseif(kval<ST.elem[mid].key))

high=mid-1;//繼續(xù)虛前*區(qū)間進(jìn)行查找

elselow=mid+1;〃繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

)

return0;//順序表中不存在待查元素

}//SearchBin

折半查找的性能分析

?判定樹：描述查找過程的二叉樹。

?有n個(gè)結(jié)點(diǎn)的判定樹的深度為I_log2n」+1

?折半查找法伊查找噸程中進(jìn)行的為較洋數(shù)界多

不超過Ltogdj±d_______I______________

先看一個(gè)有11個(gè)元素的表的例子：0=11

*

11234567891011

Ci34234134234

假設(shè)有序表的長(zhǎng)度11=2咄1（反之h=log2（n+l））,

則描述折半查找的判定樹是深度為h的滿二叉樹。

樹中層次為1的結(jié)點(diǎn)有1個(gè)，層次為2的結(jié)點(diǎn)有2

個(gè)，層次為h的結(jié)點(diǎn)有2個(gè)。假設(shè)表中每個(gè)記

錄的查找概率相等

則查找成功時(shí)折半查找的平均查找長(zhǎng)度

1〃1n+I

ASLD=S/一_/VIC.——=-------10g2（〃+1）T

n

在n>50時(shí)，可得近似結(jié)果

ASLbs穴bg2（〃+1）-1

可見，

?折半查找的效率比順序查找高。

?折半查找只能適用于有序表，并且以順序存

儲(chǔ)結(jié)構(gòu)存儲(chǔ)。

順序表和有序表的比較

順序表有序表

表的特性無序有序

存儲(chǔ)結(jié)構(gòu)順序或鏈?zhǔn)巾樞?/p>

插刪操作易于進(jìn)行需移動(dòng)元素

ASL的值大小

■索引順序表

在建立順序表的同時(shí)，建立一個(gè)索引項(xiàng)，包括兩

項(xiàng)：關(guān)鍵字項(xiàng)和指針項(xiàng)。索引表按關(guān)鍵字有序，

表則為分塊有序

順序表

索弓I順序表=索引+順序表

索引順序查找

又稱分塊查找

查找過程：將表分成幾塊，塊內(nèi)無序，塊間有序;

一先確定待查記錄所在塊，再在塊內(nèi)查找

適用條件：分塊有序表

算法實(shí)現(xiàn)：

用數(shù)組存放待查記錄,每個(gè)數(shù)據(jù)元素至少含有

關(guān)鍵字域

建立索引表，每個(gè)索引表結(jié)點(diǎn)含有最大關(guān)鍵

字底和指向本塊第一個(gè)結(jié)點(diǎn)的指針

例如

索引表

224886

1713

1234567189101112131415161718

22I12I13I819I20I33I42I44I38I24I48I60I58I74I57I86I53

分塊查找方法評(píng)價(jià)

ASLb,sb=L+wL

其中：Lf----查找索引表確定所在塊的平均查找長(zhǎng)度

-----在塊中查找元素的平均查找長(zhǎng)度

LW

若將表長(zhǎng)為〃的表平均分成6塊，每塊含s個(gè)記錄，并設(shè)

表中每個(gè)記錄的查找概率相等，則：

h

1]s

(1)用順序查找確定所在塊：ASL6=―2j+i

bj=is(=1

b+1s+11n

=-----+------=—(一+5)+1

222s

Yls

(2)用折半查找確定所在塊：ASLhs?log2(-+1)+-

s2

查找方法比較

順序查找折半查找分塊查找

ASL最大最小兩者之間

表結(jié)構(gòu)有序表、無序表有序表分塊有序表

存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)

線性鏈表線性鏈表

幾種查找表的特性

查找插入刪除

無序順序表O(n)0(1)0(n)

無序線性鏈表O(n)0(1)。⑴

有序順序表O(logn)0(n)0(n)

有序線性鏈表0(n)0(1)0(1)

靜態(tài)查找樹表O(logn)O(nlogn)O(nlogn)

結(jié)論:

?從查找性能看，最好情況能達(dá)O(logn),

此時(shí)要求表有序；

?從插入和刪除的性能看，最好情況能達(dá)

0(1),此時(shí)要求存儲(chǔ)結(jié)構(gòu)是鏈表。

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

動(dòng)態(tài)查找表的特點(diǎn):表結(jié)構(gòu)本身是在查找過程中動(dòng)

態(tài)生成。若表中存在其關(guān)鍵字等于給定值key的記

錄，表明查找成功；否則插入關(guān)鍵字等于key的記錄。

抽象數(shù)據(jù)類型動(dòng)態(tài)查找表的定義：

ADTDynamicSearchTable{

數(shù)據(jù)對(duì)象D:D是具有相同特性的數(shù)據(jù)元素的

集合。

每個(gè)數(shù)據(jù)元素含有類型相同的

關(guān)鍵字，可唯一標(biāo)識(shí)數(shù)據(jù)元素。

數(shù)據(jù)關(guān)季R,數(shù)據(jù)元素同屬一'個(gè)集合o

基本操作：

InitDSTable(&DT)〃構(gòu)造一個(gè)空的動(dòng)態(tài)查找表DT。

DestroyDSTable(&DT)//銷毀動(dòng)態(tài)查找表DT。

SearchDSTable(DT,key);〃查找DT中與關(guān)鍵字

key等值的元素。

InsertDSTable(&DT,e);//若DT中不存在其關(guān)鍵

字等于的數(shù)據(jù)元素，貝插入到

e.keyUeDTO

DeleteDSTable(&T,key);//刪除DT中關(guān)鍵字等于

key的數(shù)據(jù)元素。

TraverseDSTable(DT,Visit。);//按某種次序?qū)?/p>

DT的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit。一次且至多一次。

}ADTDynamicSearchTable

next

二叉排序樹（二叉查找樹）

定義

二叉排序樹或者是一棵空樹；或者

是具有如下特性的二叉樹：

若它的左子樹不空，則左子樹上所

有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值；

若它的右子樹不空，則右子樹上所

有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值；

它的左、右子樹也都分別是二叉排

序樹。，

不是二叉排序樹。

二叉排序樹的存儲(chǔ)結(jié)構(gòu)

以二叉鏈表形式存儲(chǔ)

typedefstructBiTNode{〃結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

structBiTNode*lchild,^rchild;//左

右指針

}BiTNode,*BiTree;

二叉排序樹的查找算法

若二叉排序樹為空，則查找不成功；

否則

1）若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找

成功；

2）若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)

在左子樹上進(jìn)行查找；

3）若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)

在右子樹上進(jìn)行查找。

等于50,35,90,95

StatusSearchBST(BiTreeT,KeyTypekval,BiTreef,

BiTree&p){

if(!T)

{p=f;returnFALSE;}//查找不成功

elseif(EQ(kval,T->data.key))

{p=T;returnTRUE;}〃查找成功

elseif(LT(kval,T->data.key))

returnSearchBST(T->lchild,kval,T,p);〃在

左子樹中繼續(xù)查找

else

returnSearchBST(T->rchild,kval,T,p);

〃在右子樹中繼續(xù)查找

}//SearchBST

二叉排序樹的插入算法

?根據(jù)動(dòng)態(tài)查找表的定義，“插入”操作在

查找不成功時(shí)才進(jìn)行；

?若二叉排序樹為空樹，則新插入的結(jié)點(diǎn)為

新的根結(jié)點(diǎn)；否則，新插入的結(jié)點(diǎn)必為一

個(gè)新的葉子結(jié)點(diǎn)，其插入位置由查找過程

得到。

StatusInsertBST(BiTree&T,ElemTypee){

if(!SearchBST(T,e.key,NULL,p))

{s=newBiTNode;〃為新結(jié)點(diǎn)分配空間

s->data=e;

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

if(!p)T=s;//插入s為新的根結(jié)點(diǎn)

elseif(LT(e.key,p->data.key))

p->lchild=s;//插入*s為*p的左孩子

elsep->rchild=s;//插入*s為*p的右孩子

returnTRUE;//插入成功

)

elsereturnFALSE;

}//InsertBST

結(jié)論

?一個(gè)無序序列可以通過構(gòu)造一棵二叉排序樹

二而變最一個(gè)有序序列

?每次插入的新結(jié)點(diǎn)都是二叉排序樹上新的葉

子結(jié)點(diǎn)

?插入時(shí)不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)

點(diǎn)的指針

二叉排序樹的刪除算法

和插入相反，刪除在查找成功之后進(jìn)行，并

且要求在刪除二叉排序樹上某個(gè)結(jié)點(diǎn)之后，仍

然保持二叉排序樹的特性。

可分三種情況討論：

■被刪除的結(jié)點(diǎn)是葉子；

■被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹；

■被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹。

被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，如Key=88

結(jié)果,其雙親結(jié)點(diǎn)中相應(yīng)指針域的值改為空

被刪除的結(jié)點(diǎn)只有左子樹或者只有右子樹如

key=80

結(jié)果,其雙親結(jié)點(diǎn)的相應(yīng)指針域的值改為“指

向被刪除結(jié)點(diǎn)的左子樹或右子樹”。

被刪除的結(jié)點(diǎn)既有左子樹，也有右子樹

如被刪關(guān)鍵字key=50

結(jié)果，以其前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)

點(diǎn)

，[3法

VJStatusDeleteBST(BiTree&T,KeyTypekval){

if(!T)returnFALSE;

//不存在關(guān)鍵字等于kval的數(shù)據(jù)元素

else{if(EQ(kval,T->data.key))

{Delete(T);returnTRUE;}

//找到關(guān)鍵字等于key的數(shù)據(jù)元素

elseif(LT(kval,T->data.key))

returnDeleteBST(T->lchild,kval);

//繼續(xù)在左子樹中進(jìn)行查找

else

returnDeleteBST(T->rchild,kval);

//繼續(xù)在右子樹中進(jìn)行查找

}

1//DeleteBST

其中刪除操作過程如下：

voidDelete(BiTree&p){

〃從二叉排序樹中刪除結(jié)點(diǎn)p,

〃并重接它的左子樹或右子樹

if(!p->rchild){}

elseif(!p->lchild){

else(}

}//Delete

右子樹為空樹則只需重接它的左子樹

p；p=p->lchild;delete(q)；

左子樹為空樹只需重接它的右子樹

q=p;p=p->rchild;delete(q);

?

左右子樹均不空

q=p;s=p->lchild;

while(s->rchild)

{q=s;s=s->rchild;}

〃s指向被刪結(jié)點(diǎn)的前驅(qū)

p->data=s->data;

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

elseq->lchild=s->lchild;

〃重接*q的左子樹

delete(s);

C

s

二叉排序樹查找性能的分析

對(duì)于每一棵特定的二叉排序樹，均可按照

平均查找長(zhǎng)度的定義來求它的ASL值，顯然，

由值相同的n個(gè)關(guān)鍵字，構(gòu)造所得的不同形態(tài)

的各棵二叉排序樹的平均查找長(zhǎng)度的值不同，

甚至可能差別很大。

例如：

由關(guān)鍵字序列L2，3，4,5構(gòu)

造而得的二叉排序樹，

ASL=(1+2+3+4+5)/5

=3

由關(guān)鍵字序列3，L2，5，4構(gòu)造

而得的二叉排序樹

ASL=(1+2+3+2+3)/5②

=2.2

下面討論平均情況：

不失一般性，假設(shè)長(zhǎng)度為n的序列中有k個(gè)

關(guān)鍵字小于第一個(gè)關(guān)鍵字，則必有n-k-1個(gè)關(guān)鍵

字大于第一個(gè)關(guān)鍵字，由它構(gòu)造的二叉排序樹

的平均查找長(zhǎng)度是n和k的函數(shù)

P(n,k)(0<k<n-1)

假設(shè)n個(gè)關(guān)鍵字可能出現(xiàn)的n!種排列的可

能性相同，則含n個(gè)關(guān)鍵字的二叉排序樹的

平均查找長(zhǎng)度

]n—1

4sL=尸（H）=一￡P(guān)gk）

nk=a

在等概率查找的情況下，

n]n

尸5,外=￡pG=—￡Ci

Z=1〃Z=1

——

蟲

蟲

——

——

((I——7X(I7￡)+()&X)+Iu

u

蟲

蟲

((I+(I50)(1—7—+(I+()&)+1)——u

「s

H7JRL"

CH+CH+IU—HGH—n—〕d

$i

由此

]n—\(1、

P(H)=一￡1+—oXPg+5_k—1)xP{n—k—l))

n左=oIH)

2"-i

=l+'W(kxP(k))

nk=i

可類似于解差分方程，此遞歸方程有解:

72+1

P(n)=2-------logH+C

n

平衡二叉樹

二叉平衡樹是二叉查找樹的另一種形式，其

特點(diǎn)為：樹中每個(gè)結(jié)點(diǎn)的左、右子樹深度之差

?上構(gòu)造二叉平衡（查找）樹的方法:

在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。

例如:依次插入的關(guān)鍵字為5,4,2,8,6,9

繼續(xù)插入關(guān)鍵字9

哈希表

哈希表的相關(guān)定義

哈希函數(shù)的構(gòu)造方法

處理沖突的方法

哈希表的查找

哈希表的插入

哈希查找分析

哈希表的相關(guān)定義

哈希查找

又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程。

基本思想：在記錄的存儲(chǔ)地址和它的關(guān)鍵字之間建

立一個(gè)確定的對(duì)應(yīng)美系；這樣，不經(jīng)過比較，一

次存取就能得到所查元素的查找方法。

哈希函數(shù)

在記錄的關(guān)鍵字與記錄的存儲(chǔ)地址之間建立的一

種對(duì)應(yīng)關(guān)系。哈希函數(shù)是一種映象,是從關(guān)鍵字

空間到存儲(chǔ)地址空間的一種映象。

可寫成，addr(ai)=H(ki)

其中：ai是表中的一個(gè)元素

addr(ai)是ai的存儲(chǔ)地址

ki是ai的關(guān)鍵字

哈希表

根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中

的處理沖突的方法，將一組關(guān)鍵字映象到

一個(gè)有限的、地址連續(xù)的地址集(區(qū)間)上,

并以關(guān)鍵字在地址集中的“象”作為相應(yīng)

記錄在表中的存儲(chǔ)位置，如此構(gòu)造所得的

查找表稱之為“哈希表”。

例30個(gè)地區(qū)的各民族人口統(tǒng)計(jì)表

從例子可見：

哈希函數(shù)只是一種映象，所以哈希函數(shù)

的設(shè)定很靈活，只要使任何關(guān)鍵字的哈

希函數(shù)值都落在表長(zhǎng)允許的范圍之內(nèi)即

可。

沖突：keyl^key2,但

H(keyl)=H(key2)的現(xiàn)象

哈希函數(shù)構(gòu)造的方法

■直接定址法

■數(shù)字分析法

■平方取中法

■折疊法

■除留余數(shù)法

■隨機(jī)數(shù)法

直接定址法

哈希函數(shù)為關(guān)鍵字的線性函數(shù)

H(key)=key或者H(key)=axkey+b

此法僅適合于：

地址集合的大小==關(guān)鍵字集合的大小

其中a和b為常數(shù)

數(shù)字分析法

假設(shè)關(guān)鍵字集合中的每個(gè)關(guān)鍵字都是由S位數(shù)字組成（Up

112,…,11J,分析關(guān)鍵字集中的全體，并從中提取分布均

勻的若干位或它們的組合作為地址。此法適于能預(yù)先估

計(jì)出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。

例有80個(gè)記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù)

①②③④⑤⑥⑦⑧

81346532—

分析：①只取8

81372242

②只取

813874221

③只取、

8130136734

⑧只取2、7、5

81322817-----

④⑤⑥⑦數(shù)字分布近乎隨機(jī)

81338967

所以：?、堍茛蔻呷我鈨晌换騼晌?/p>

8.11.3n68537

與另兩位的疊加作哈希地址

81419355

平方取中法

以關(guān)鍵字的平方值的中間幾位作為存儲(chǔ)地

址。求“關(guān)鍵字的平方值”的目的是“擴(kuò)大

差別”，同時(shí)平方值的中間各位又能受到整

個(gè)關(guān)鍵字中各位的影響。

此方法適合于：

關(guān)鍵字中的每一位都有某些數(shù)字重復(fù)出現(xiàn)頻

度很高的現(xiàn)象。

折疊法

將關(guān)鍵字分割成若干部分，然后取它們的疊加和為哈

希地址。兩種疊加處理的方法：

移位疊加:將分割后的幾部分低位對(duì)齊相加

間界疊加:從一端沿分割界來回折送，然后對(duì)齊相加

此法適于關(guān)鍵字的數(shù)字位數(shù)特別多。

例關(guān)鍵字為：0442205864,哈希地址位數(shù)為4

58645864

42200224

0404

100886092

H(key)=0088H(key)=6092

除留余數(shù)法

設(shè)定哈希函數(shù)為：

H(key)=keyMODp(p<m)

其中，m為表長(zhǎng)

p為不大于m的素?cái)?shù)

或是

不含20以下的質(zhì)因子

為什么要對(duì)P加限制？

例如：

給定一組關(guān)鍵字為:12,39,18,24,33,21,

若取p=9,則他們對(duì)應(yīng)的哈希函數(shù)值將為：

3,3,0,6,6,3

可見，若p中含質(zhì)因子3,則所有含質(zhì)因子3的

關(guān)鍵字均映射到“3的倍數(shù)”的地址上，從而增

加了“沖突”的可能

隨機(jī)數(shù)法

設(shè)定哈希函數(shù)為：

H(key)=Random(key)

其中，Random為偽隨機(jī)函數(shù)

此法用于對(duì)長(zhǎng)度不等的關(guān)鍵字構(gòu)造哈希函數(shù)。

選取哈希函數(shù)考慮的因素：

計(jì)算哈希函數(shù)所需時(shí)間

關(guān)鍵字長(zhǎng)度

哈希表長(zhǎng)度(哈希地址范圍)

關(guān)鍵字分布情況

記錄的查找頻率

處理沖突的方法

“處理沖突”的實(shí)際含義是：

為產(chǎn)生沖突的地址尋找下一個(gè)哈希地址。

■開放定址法

■再哈希法

■鏈地址法

開放定址法

為產(chǎn)生沖突的地址H(key)求得一個(gè)地址

序列：Ho,H1?H2,Hsl<s<m-l

居=(H(key)+djMODm

其中：i=l,2,…,s

H(key)為哈希函數(shù);m為哈希表長(zhǎng)；

4為增量序列，有下列三種取法：

對(duì)增量di的三種取法：

1）線性探測(cè)再散列

dj=exi最簡(jiǎn)單的情況c=l

2）二次探測(cè)再散列

4=12,42,22,一22,...,

3）隨機(jī)探測(cè)再散列

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

4=ixH2（key）（又稱雙散列函數(shù)探測(cè)）

注意：增量4應(yīng)具有“完備性”

即：產(chǎn)生的Hi均不相同，且所產(chǎn)生的

s(m-l)個(gè)居值能覆蓋哈希表中所有

地址。則要求：

長(zhǎng)平方探測(cè)時(shí)的表長(zhǎng)m必為形如4j+3

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

X隨機(jī)探測(cè)時(shí)的m和4沒有公因子。

例表長(zhǎng)為11的哈希表中已填有關(guān)鍵字為17,60,29

的記錄，H(key)=keyMOD11,現(xiàn)有第4個(gè)記錄，其關(guān)

鍵字為38,按三種處理沖突的方法，將它填入表中

012345678910

383860172938

(1)H(38)=38MOD11=5沖突

Hl=(5+1)MOD11=6沖突

H2=(5+2)MOD11=7沖突

H3=(5+3)MOD11=8不沖突

(2)H(38)=38MOD11=5沖突

Hl=(5+12)MOD11=6沖突

H2=(5-l2)MOD11=4不沖突

(3)H(38)=38MOD11=5沖突

設(shè)偽隨機(jī)數(shù)序列為9,貝I：

Hl=(5+9)MOD11=3不沖突

例如：給定關(guān)鍵字集合構(gòu)造哈希表

{19,01,23,14,55,68,11,82,36)

設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)

若采用線性探測(cè)再散列處理沖突

012345678910

550123146811823619

112136251

若采用二次探測(cè)再散列處理沖突

012345678910

550123143682681911

鏈地址法

將所有哈希地址相同的記錄都鏈接在同一鏈表中。

例:給定關(guān)鍵字｛1%01,23,14,55,68,11,82,36)

哈希函數(shù)為H(key)=keyMOD7

014K

136A

21231A|

3A

11A

4

1982A

5

55A4

例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11JO,79)

哈希函數(shù)為：H(key)=keyMOD13,

用鏈地址法處理沖突

再哈希法

方法：構(gòu)造若干個(gè)哈希函數(shù)，當(dāng)發(fā)

生沖突時(shí)，計(jì)算下一個(gè)哈希地址，

直到?jīng)_突不再發(fā)生。

即：Hi=Rhj(key)i=l,2,.......k

其中：R%——不同的哈希函數(shù)

特點(diǎn)：計(jì)算時(shí)間增加

哈希表的查找

哈希查找過程

對(duì)于給定值K,

計(jì)算哈希地址i=H（K）

若r[i]=NULL則查找不成功

若r[i].key=K則查找成功

否則“求下一地址Hi”，

直至r[Hi]=NULL（查找不成功）

或r[Hi].key=K（查找成功）為止。

開放定址哈希表的存儲(chǔ)結(jié)構(gòu)

inthashsize[]={997,...};

typedefstruct{

ElemType*elem;

intcount;〃當(dāng)前數(shù)據(jù)元素個(gè)數(shù)

intsizeindex;

//hashsize[sizeindex]當(dāng)前容量

}HashTable;

#defineSUCCESS1

#defineUNSUCCESS0

#defineDUPLICATE-1

查找算法

StatusSea