電子科數(shù)據(jù)結(jié)構(gòu)pascal版課件chapt

第九章查找

靜態(tài)查找表動態(tài)查找表哈希查找表

9.1靜態(tài)查找表查找表(table):由同類型的DE(或記錄)構(gòu)成的集合.查找表上的基本運算:

建立查找表create(ST,n)查找search(ST,k)遍歷查找表traverse(ST)9.1靜態(tài)查找表關(guān)鍵字(key):

是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值,用它可以標(biāo)識(識別)一個數(shù)據(jù)元素(或記錄)。主關(guān)鍵字(primarykey):

可以唯一地標(biāo)識一個數(shù)據(jù)元素(或記錄)的關(guān)鍵字。次關(guān)鍵字(secondarykey):

用以標(biāo)識若干數(shù)據(jù)元素(或記錄)的關(guān)鍵字。9.1靜態(tài)查找表查找:

根據(jù)給定的值，在查找表中確定關(guān)鍵字與給定值相等的DE的過程。查找結(jié)果:

查找成功

(table中存在給定值的記錄)查找不成功

(table中不存在給定值的記錄)查找表分為:

靜態(tài)查找表

(對查找表中的數(shù)據(jù)元素不進(jìn)行插入和刪除操作)

動態(tài)查找表

(對查找表中的數(shù)據(jù)元素可進(jìn)行插入和刪除操作)9.1靜態(tài)查找表查找表的類型描述:

TYPErectype=RECORDkey:keytype;

……END;sqlisttp=ARRAY[0..n]OFrectype;9.1靜態(tài)查找表一.順序表的查找(順序查找)

方法一：

FUNCseqsrch1(r:sqlisttp;k:keytype):integer;i:=1;WHILE（i<=n)CAND(r[i].key<>k)DOi:=i+1;IFi<=nTHENRETURN(i)ELSERETURN(0)ENDF;{seqsrch1}9.1靜態(tài)查找表一.順序表的查找(順序查找)

方法二：

FUNCseqsrch2(r:sqlisttp;k:keytype):integer;FORi:=1TOnDOIFr[i].key=kTHENRETURN(i);RETURN(0)ENDF;{seqsrch2}9.1靜態(tài)查找表一.順序表的查找(順序查找)

方法三：

FUNCseqsrch3(r:sqlisttp;k:keytype):integer;i:=n;WHILE（i>0)CAND(r[i].key<>k)DOi:=i-1;RETURN(i)ENDF;{seqsrch3}9.1靜態(tài)查找表一.順序表的查找(順序查找)FUNCseqsrch(r:sqlisttp;k:keytype):integer;r[0].key:=k;i:=n;WHILEr[i].key<>kDOi:=i-1;RETURN(i)ENDF;{seqsrch}9.1靜態(tài)查找表

FUNCseqsrch(r:sqlisttp;k:keytype):integer;r[0].key:=k;i:=n;WHILEr[i].key<>kDOi:=i-1;RETURN(i)ENDF;{seqsrch}1.r[0]起監(jiān)視哨作用i:=n;WHILEi>=1CANDr[i].key<>kDOi:=i-1;RETURN(i);9.1靜態(tài)查找表

FUNCseqsrch4(r:sqlisttp;k:keytype):integer;r[n+1].key:=k;i:=1;WHILEr[i].key<>kDOi:=i+1;IFi=n+1THENRETURN(0)ELSERETURN(i)ENDF;{seqsrch4}2.查找方向可換FUNCseqsrch(r:sqlisttp;k:keytype):integer;r[0].key:=k;i:=n;WHILEr[i].key<>kDOi:=i-1;RETURN(i)ENDF;{seqsrch}9.1靜態(tài)查找表平均查找長度(ASL):查找過程中,給定值需與關(guān)鍵字比較的次數(shù)的期望值.

nASL=∑PiCi

i=1其中:Pi為查找第i個記錄的概率;Ci為找到第i個記錄時,已比較的次數(shù).順序查找的平均查找長度ASLss=np1+(n-1)p2+……+pnn當(dāng)pi=1/n時,ASLss=∑PiCi=(n+1)/2

i=19.1靜態(tài)查找表有序表的順序查找FUNCseqsrch5(r:sqlisttp;k:keytype):integer;i:=1;WHILEi<=nCANDk>r[i].keyDOi:=i+1;IFi<=nCANDk=r[i].keyTHENRETURN(i)ELSERETURN(0)ENDF;{seqsrch5}9.1靜態(tài)查找表有序表的順序查找(設(shè)置監(jiān)視哨)FUNCseqsrch6(r:sqlisttp;k:keytype):integer;r[0].key:=k;i:=n;WHILEk<r[i].keyDOi:=i-1;IFk=r[i].keyTHENRETURN(i)ELSERETURN(0)ENDF;{seqsrch6}ASL成功=(n+1)/2+1ASL不成功=(n+1+1)/2+1=n/2+1+19.1靜態(tài)查找表二.有序表的查找(折半查找)有序表:

查找表中記錄按關(guān)鍵字有序排列的表.

即:r[i].key<=r[i+1].keyi=1,2,…,n-1折半查找:

要求:查找表為有序表;查找過程:先確定待查記錄范圍;

然后逐步縮小范圍;

直到:查找成功或不成功.9.1靜態(tài)查找表折半查找算法

FUNCbinsrch(r:ordlisttp;k:keytype):integer;low:=1;high:=n;found:=false;WHILElow≤highANDNOTfoundDO[mid:=(low+high)DIV2;CASEk>r[mid].key:low:=mid+1;k=r[mid].key:found:=true;k<r[mid].key:high:=mid-1;ENDC;]IFfoundTHENRETURN(mid)ELSERETURN(0)ENDF;{binsrch}例:k=21,有序表為:(5,13,19,21,37,56,64,75,80,88,92)1.low=1,high=11,mid=62.∵21<56high=6-1mid=33.∵21>19low=4mid=44.21=21found=truereturn(4)折半查找的平均查找長度ASLbs=(n+1)/nlog2(n+1)-1≈log2(n+1)-19.1靜態(tài)查找表折半查找的過程對應(yīng)一棵二叉樹，稱為判定樹：

56198005216488133775929.1靜態(tài)查找表三.索引順序表的查找(分塊查找)索引表:

1)按表中記錄的關(guān)鍵字分塊,R1,R2,…,RL要求:第Rk塊中的所有關(guān)鍵字<Rk+1塊中的所有關(guān)鍵字

k=1,2,…,L-1,稱為“分塊有序”2)對每塊建立一個索引項,包含有兩項內(nèi)容:①關(guān)鍵字項:

為該塊中最大關(guān)鍵字值;②指針項

:

為該塊第一個記錄在表中位置.3)所有索引項組成索引表9.1靜態(tài)查找表例.查找表為:22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53索引表為:關(guān)鍵字項指針項22488617139.1靜態(tài)查找表查找分為兩步:1.確定待查記錄所在塊;(可以用順序或折半查找)2.在塊內(nèi)順序查找.(只能用順序查找)關(guān)鍵字項指針項224886171322,12,13,8,9,20,33,42,44,38,24,48,

60,58,74,49,86,53例如:k=38第1步:k=38的記錄只可能在塊2中;第2步:從r[7]開始,直到k=r[i].key或i>12為止.9.1靜態(tài)查找表一個示意算法:PROCbsb(T,r,n,b,s,k)；{T為升序排列的塊最大關(guān)鍵字表（索引表），b為塊數(shù)，r為查找表，n為r的元素個數(shù)，s為每塊元素個數(shù)，k為關(guān)鍵字｝

T[b+1]:=k；i:=1；

WHILET[i]＜kDOi:=i+1；

IFi≤bTHEN【j:=(i-1)s+1；i:=is；

WHILEj≤iCANDr[j].key≠kDOj:=j+1；

IFj≤iTHENWRITE(‘SUCC’) ELSEWRITE(‘UNSUCC’)】 ELSEWRITE(‘UNSUCC’) ENDP；｛bsb｝9.1靜態(tài)查找表分塊查找表的平均查找長度ASL=Lb+Lw其中:Lb為查索引表確定所在塊的平均查找長度;Lw為在塊內(nèi)查找記錄的平均查找長度;三種查找方法比較順序查找折半查找分塊查找ASL大小

中表結(jié)構(gòu)要求無有序表

分段有序（塊之間有序）9.2動態(tài)查找表動態(tài)查找表的特點是:

表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的。即查找不成功時，將該記錄插入在動態(tài)查找表中。一、二叉排序樹（BinarySortTree)（又稱為二叉查找樹）1、BST定義：

BST或者是一棵空樹；或者是具有如下性質(zhì)的BT:

若左子樹非空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；若右子樹非空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；左、右子樹也為BST9.2動態(tài)查找表78100619012372484553例如：注意查找不成功的情形9.2動態(tài)查找表2、查找過程為:(1)當(dāng)前BST非空時，將給定值k與當(dāng)前根結(jié)點的關(guān)鍵字比較:(2)若相等，查找成功，結(jié)束;

若k小于當(dāng)前根結(jié)點的關(guān)鍵字，則將左子樹作為當(dāng)前BST;

若k大于當(dāng)前根結(jié)點的關(guān)鍵字，則將右子樹作為當(dāng)前BST;(3)重復(fù)(1)。9.2動態(tài)查找表算法描述為：

FUNCbstsrch(t:bitreptr;k:keytype):bitreptr;{查找不成功時返回NIL}IF(t=NIL)COR(t↑.key=k)THENRETURN(t)ELSEIFt↑.key<kTHENRETURN(bstsrch(t↑.rchild,k))ELSERETURN(bstsrch(t↑.lchild,k))ENDF;{bstsrch}

9.2動態(tài)查找表3.BST的插入插入原則：記下查找不成功時比較的最后一個結(jié)點的位置，將插入結(jié)點作為該結(jié)點的左或右孩子。

PROCinsbst(VARbst:bitreptr;k:keytype);f:=NIL;found:=false;f:=srch_bstree(f,bst,k,found)IFNOTfoundTHENins_bstree(f,bst,k)ENDP;{insbst}9.2動態(tài)查找表

FUNCsrch_bstree(VARf:bitreptr;bst:bitreptr;k:keytype;VARfound:boolean):bitreptr;IFbst=NILTHEN[found:=false;RETURN(f)]ELSEIFbst↑.key=kTHEN[found:=true;RETURN(bst)]ELSE[f:=bst;{f記載上次比較的結(jié)點的位置}IFbst↑.key<kTHENRETURN(srch_bstree(f,bst↑.rchild,k,found))ELSERETURN(srch_bstree(f,bst↑.lchild,k,found))]ENDF;{srch_bstree}

9.2動態(tài)查找表一個改進(jìn)的非遞歸算法:

FUNCsrch_bstree1(VARf:bitreptr;bst:bitreptr;k:keytype;VARfound:boolean):bitreptr;IFbst=NILTHEN[found:=false;RETURN(f)]ELSE[p:=f:=bst;{查找不成功時,f記載插入點的雙親}WHILEp<>NILDOIFp↑.key=kTHEN[found:=true;RETURN(p)]ELSEIFp↑.key<kTHEN[f:=p;p:=p↑.rchild]ELSE[f:=p;p:=p↑.lchild];found:=false;RETURN(f)]ENDF;{srch_bstree1}9.2動態(tài)查找表PROCins_bstree(VARf,bst:bitreptr;k:keytype);new(s);s↑.key:=k;s↑.lchild:=NIL;s↑.rchild:=NIL;IFbst=NILTHENbst:=sELSEIFk<f↑.keyTHENf↑.lchild:=sELSEf↑.rchild:=sENDP;{ins_bstree}9.2動態(tài)查找表4514543753902246125例：設(shè)BST為空，查找關(guān)鍵字序列為{45，24，53，45，12，24，90}，則經(jīng)過一系列查找插入操作后，生成的BST為：9.2動態(tài)查找表4.BST的特點：(1)中序遍歷BST可得到一個關(guān)鍵字的有序序列。如上例：中序遍歷結(jié)果為：12，24，45，53，90

這是由于BST中左子樹的所有結(jié)點的值均小于其根結(jié)點的值，右子樹的所有結(jié)點的值均大于其根結(jié)點的值；而中序遍歷又是以LDR順序訪問的。9.2動態(tài)查找表(2)在BST上插入新結(jié)點時，不必移動其他結(jié)點，僅需改動某結(jié)點的指針（因新結(jié)點總是BST上的一個新葉結(jié)點）。

(3)BST既具有類似折半查找的特性（與BST的平衡度有關(guān)）又采用了鏈表存儲結(jié)構(gòu)（折半查找不能為鏈表存儲結(jié)構(gòu)），因此，對于經(jīng)常要進(jìn)行查找、插入和刪除記錄的有序表，采用BST尤其合適。9.2動態(tài)查找表5．BST的刪除刪除的原則：刪除某個結(jié)點后仍保持BST的特性。設(shè)：被刪除結(jié)點為p↑(指針p所指結(jié)點）其雙親結(jié)點為f↑,且不失一般性，設(shè)p是f的左孩子。9.2動態(tài)查找表cqCSLsCLFFRfPRpPQQLS分三種情況討論：

若P↑結(jié)點為葉結(jié)點（即PL和PR均為空樹，僅需將f↑．lchild:=NIL

若P↑結(jié)點只有左子樹PL或只有右子樹PR，只需令PL或PR為f↑的左子樹，即f↑．lchild:=P↑．lchild

(或P↑．rchild)

若P↑結(jié)點左、右子樹均不空，此時，按中序遍歷序列為：…CLC…QLQSLSPPRFFR…刪除p后為：…CLC…QLQSLSPR

FFR…結(jié)果是將PR作為SR

。CSLCLPRQQLSFSSLCLFPRQQLC對F的左孩子有兩種處理辦法：(1)S不動，仍作為Q的右孩子，C代替P，作為F的左孩子;(2)S代替P，而

SL為QR;9.2動態(tài)查找表PROCdel_bstree1(VARbst：bitreptr；f，p：bitreptr）；

{刪除p↑結(jié)點；f↑是p↑的雙親}IFf=NILTHEN{p↑為根結(jié)點

}CASEp↑．lchild=NILANDp↑．rchild=NIL：bst：=NIL；

p↑．lchild=NIL：bst：=p↑．rchild；

p↑．rchild=NIL：bst：=p↑．lchild；

ELES[s：=p↑．lchild；

WHILEs↑．rchild≠NILDOs：=s↑．rchild；

bst：=p↑．lchild；s↑．rchild：=p↑．rchild；]ENDC

CSLCLPRQQLSCSLCLPRPQSQL9.2動態(tài)查找表ELSE{p↑不是根結(jié)點}CASE

p↑．rchild=NIL：f↑．lchild：=p↑．lchild：

p↑．lchild=NIL：f↑．lchild：=p↑．rchild；

ELSE[s：=p↑．lchild；

WHILEs↑．rchild≠NILDOs:=s↑．rchild；

s↑．rchild：=p↑．rchild；

f↑．lchild：=p↑．lchild；]ENDC;dispose(p)ENDP；{del_bstree1}9.2動態(tài)查找表6．BST的查找分析

BST上查找過程與折半查找類似，是從根結(jié)點到所找到結(jié)點的一條路徑。與給定值比較次數(shù)等于該路徑長度+1（即結(jié)點所在層次數(shù)），最大層次數(shù)不超過樹的深度。但長度為n的折半查找表對應(yīng)的判定樹是唯一的。而含有n個結(jié)點的BST卻不唯一。459353371224

(a)(45,24,53,12,37,93)122437455393

(b)(12,24,37,45,53,93)ASL(a)=1/6（1+2+2+3+3+3）=14/6ASL(b)=1/6（1+2+3+4+5+6）=21/69.2動態(tài)查找表因此，含有n個結(jié)點的BST的ASL和樹的形態(tài)有關(guān)。最差情況是BST退化為單支樹，其深度為n，ASL=(n+1)/2(同順序查找）。最好情況與折半查找相同，ASL=log2n

隨機(jī)情況下，平均查找長度為1+4logn為了避免出現(xiàn)單支樹，在構(gòu)成BST的過程中可進(jìn)行“平衡化”處理。9.3哈希查找表

前面介紹的查找算法,有一個共同特點:就是以待查關(guān)鍵字k,在表中，通過一系列比較來確定該記錄在表中的“地址”。這一節(jié)將介紹另一種通過計算來查找的新型方法-----哈希法（Hash）或稱雜湊法、散列法。設(shè)關(guān)鍵字集合為A，地址空間為D，哈希法就是在A和D之間建立一種函數(shù)關(guān)系H，通過計算函數(shù)H（k），就能得到關(guān)鍵字K的地址。關(guān)鍵字集Am地址空間Dn哈希函數(shù)

H（k）9.3哈希查找表

設(shè)D是長度為n的表，

A是含m個記錄的關(guān)鍵字集合，如果存在一個函數(shù)H，使得對A中任一關(guān)鍵字Ki，均有，

0≤H（Ki

）≤n-1i=1，2．．．，m

同時,Ki

所標(biāo)識的記錄Ri在表D中的地址是H(Ki)，則稱函數(shù)H為關(guān)鍵字集合A到地址空間D之間的哈希函數(shù)，地址空間D為哈希表。哈希函數(shù)并不一定是一對一的，例如，當(dāng)m＞n時，對任何哈希函數(shù)H，至少存在兩個關(guān)鍵字Ki≠Kj

，使得H(Ki)=H(Kj)，這種對不同關(guān)鍵字而得到同一地址的現(xiàn)象，稱為沖突。9.3哈希查找表

因此，在應(yīng)用哈希查找方法時，主要要解決兩個技術(shù)問題：一是構(gòu)造好哈希函數(shù)的方法;

二是研究解決沖突的方法。一.哈希函數(shù)構(gòu)造方法一個好的哈希函數(shù)應(yīng)滿足下列兩個條件：計算簡單容易沖突極少9.3哈希查找表1．直接哈希函數(shù)取關(guān)鍵字本身或關(guān)鍵字的某個線性函數(shù)值作為哈希地址，即：H（key）=key或H（key）=a*key+b（a，b為常數(shù)）例如：有一個解放后出生人口調(diào)查表，每個記錄包含年份、人數(shù)等數(shù)據(jù)項，其中年分為關(guān)鍵字，則哈希函數(shù)可取為:H（key）=key+（-1948）這樣就可以方便地存儲和查找1948年后任一年的記錄。

地址年份人數(shù)011949．．．．．．．．．．．．．．．．．．

2219709.3哈希查找表2．?dāng)?shù)字分析法設(shè)ｎ個ｄ位數(shù)的關(guān)鍵字，由ｒ個不同的符號組成，此ｒ個符號在關(guān)鍵字的各位出現(xiàn)的頻率不一定相同，可能在某些位上均勻分布，即每個符號出現(xiàn)的次數(shù)都接近于ｎ／ｒ次，而在另一些位上分布不均勻。則選擇其中分布均勻的s位作為哈希地址，即H（key）=“key中數(shù)字均勻分布的s位”，這便是數(shù)字分析哈希函數(shù)。例：由80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，（n=80，r=10，d=8）對關(guān)鍵字的各位進(jìn)行分析，發(fā)現(xiàn)：第1，2位都是“8，1”，第3位只取1，2，3或4，第8位只取2，5或7，即10個數(shù)在這四位分布不均勻，不取?？稍谑Ｏ碌?，5，6，7位中任取兩位，作為哈希地址。9.3哈希查找表813465328137224281387422813013678132281781338967813541578136853781419355......9.3哈希查找表3．平方取中法取關(guān)鍵字平方后的中間幾位作為哈希地址，即哈希函數(shù)為:H（key）=“key2的中間幾位”其中，所取的位數(shù)由哈希表的大小確定。9.3哈希查找表4．折疊法將關(guān)鍵字分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以不同），取這幾部分的疊加和（舍去高位的進(jìn)位）作為哈希地址。位數(shù)由存儲地址的位數(shù)確定。相加時有兩種方法：一是移位疊加法，即將每部分的最后一位對齊，然后相加；另一種是間界疊加法，即將關(guān)鍵字看作一紙條，從一端向另一端沿間界逐次折疊，然后對齊相加。9.3哈希查找表設(shè)關(guān)鍵字key=d3r．．．d2r+1d2r．．．dr+1dr．．．d2d1允許的存儲地址有r位。則移位疊加法為：dr．．．d2d1

d2r．．．dr+1

+)

d３r．．．d2r+1

Sr．．．S2S19.3哈希查找表5．除留余數(shù)法取關(guān)鍵字被某個不大于哈希表長m的數(shù)p除后的余數(shù)為哈希地址。即H（key）=keyMODp，p≤mp的選擇很重要，選得不好會產(chǎn)生很多沖突，通常，選擇p≤m的某個質(zhì)數(shù)。6．隨機(jī)數(shù)法選擇一個隨機(jī)函數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值作為它的哈希地址。即H（key）=random（key）9.3哈希查找表二.處理沖突的方法

沖突是指由關(guān)鍵字得到的Hash地址上已有其他記錄,

處理沖突就是為該關(guān)鍵字找到另一個“空”的Hash地址。1.開放定址法

Hi=（H（key）+di）modmi=1，2．．．m-1;

其中:Hi為第i次沖突的地址,

H（key）為Hash函數(shù)值,

m為Hash表表長,

di為增量序列9.3哈希查找表Hi=（H（key）+di）modmi=1，2．．．m-1;

其中:di為增量序列,有三種取法：

di=1，2，3．．．m-1稱為線性探測再散列

di=12,-12,22,-22,32．．．±k2k≤m/2

稱為二次探測再散列

di=偽隨機(jī)序列稱為偽隨機(jī)探測再散列例：設(shè)m=16,表中已有關(guān)鍵字,分別為：19，70，33三個記錄，

Hash函數(shù)取為H（key）=keymod13，現(xiàn)第四個關(guān)鍵字為18的記錄要填入表中，由Hash函數(shù)得地址5，產(chǎn)生沖突

012345678910111213141570193370193318

H1H2H3

18701933H2H1701933線性二次偽隨機(jī)偽隨機(jī)數(shù)序列9．．．．H1＝１4mod16=14

18例：H（key）=keymod13,采用線性探測再散列法處理沖突,m=16

對關(guān)鍵字19，14，23，01，68，20，84，27，55，11，10，7919，14，23，01，68，20，84，27，55，11，10，796

1

1013

761311101

2724112

835

123

44...