电子科数据结构pascal版课件chapt

第九章查找

静态查找表动态查找表哈希查找表

9.1静态查找表查找表(table):由同类型的DE(或记录)构成的集合.查找表上的基本运算:

建立查找表create(ST,n)查找search(ST,k)遍历查找表traverse(ST)9.1静态查找表关键字(key):

是数据元素(或记录)中某个数据项的值,用它可以标识(识别)一个数据元素(或记录)。主关键字(primarykey):

可以唯一地标识一个数据元素(或记录)的关键字。次关键字(secondarykey):

用以标识若干数据元素(或记录)的关键字。9.1静态查找表查找:

根据给定的值，在查找表中确定关键字与给定值相等的DE的过程。查找结果:

查找成功

(table中存在给定值的记录)查找不成功

(table中不存在给定值的记录)查找表分为:

静态查找表

(对查找表中的数据元素不进行插入和删除操作)

动态查找表

(对查找表中的数据元素可进行插入和删除操作)9.1静态查找表查找表的类型描述:

TYPErectype=RECORDkey:keytype;

……END;sqlisttp=ARRAY[0..n]OFrectype;9.1静态查找表一.顺序表的查找(顺序查找)

方法一：

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静态查找表一.顺序表的查找(顺序查找)

方法二：

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

方法三：

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静态查找表一.顺序表的查找(顺序查找)FUNCseqsrch(r:sqlisttp;k:keytype):integer;r[0].key:=k;i:=n;WHILEr[i].key<>kDOi:=i-1;RETURN(i)ENDF;{seqsrch}9.1静态查找表

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]起监视哨作用i:=n;WHILEi>=1CANDr[i].key<>kDOi:=i-1;RETURN(i);9.1静态查找表

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静态查找表平均查找长度(ASL):查找过程中,给定值需与关键字比较的次数的期望值.

nASL=∑PiCi

i=1其中:Pi为查找第i个记录的概率;Ci为找到第i个记录时,已比较的次数.顺序查找的平均查找长度ASLss=np1+(n-1)p2+……+pnn当pi=1/n时,ASLss=∑PiCi=(n+1)/2

i=19.1静态查找表有序表的顺序查找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静态查找表有序表的顺序查找(设置监视哨)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静态查找表二.有序表的查找(折半查找)有序表:

查找表中记录按关键字有序排列的表.

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

要求:查找表为有序表;查找过程:先确定待查记录范围;

然后逐步缩小范围;

直到:查找成功或不成功.9.1静态查找表折半查找算法

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静态查找表折半查找的过程对应一棵二叉树，称为判定树：

56198005216488133775929.1静态查找表三.索引顺序表的查找(分块查找)索引表:

1)按表中记录的关键字分块,R1,R2,…,RL要求:第Rk块中的所有关键字<Rk+1块中的所有关键字

k=1,2,…,L-1,称为“分块有序”2)对每块建立一个索引项,包含有两项内容:①关键字项:

为该块中最大关键字值;②指针项

:

为该块第一个记录在表中位置.3)所有索引项组成索引表9.1静态查找表例.查找表为:22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53索引表为:关键字项指针项22488617139.1静态查找表查找分为两步:1.确定待查记录所在块;(可以用顺序或折半查找)2.在块内顺序查找.(只能用顺序查找)关键字项指针项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静态查找表一个示意算法:PROCbsb(T,r,n,b,s,k)；{T为升序排列的块最大关键字表（索引表），b为块数，r为查找表，n为r的元素个数，s为每块元素个数，k为关键字｝

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静态查找表分块查找表的平均查找长度ASL=Lb+Lw其中:Lb为查索引表确定所在块的平均查找长度;Lw为在块内查找记录的平均查找长度;三种查找方法比较顺序查找折半查找分块查找ASL大小

中表结构要求无有序表

分段有序（块之间有序）9.2动态查找表动态查找表的特点是:

表结构本身是在查找过程中动态生成的。即查找不成功时，将该记录插入在动态查找表中。一、二叉排序树（BinarySortTree)（又称为二叉查找树）1、BST定义：

BST或者是一棵空树；或者是具有如下性质的BT:

若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树也为BST9.2动态查找表78100619012372484553例如：注意查找不成功的情形9.2动态查找表2、查找过程为:(1)当前BST非空时，将给定值k与当前根结点的关键字比较:(2)若相等，查找成功，结束;

若k小于当前根结点的关键字，则将左子树作为当前BST;

若k大于当前根结点的关键字，则将右子树作为当前BST;(3)重复(1)。9.2动态查找表算法描述为：

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动态查找表3.BST的插入插入原则：记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。

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动态查找表

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记载上次比较的结点的位置}IFbst↑.key<kTHENRETURN(srch_bstree(f,bst↑.rchild,k,found))ELSERETURN(srch_bstree(f,bst↑.lchild,k,found))]ENDF;{srch_bstree}

9.2动态查找表一个改进的非递归算法:

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动态查找表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动态查找表4514543753902246125例：设BST为空，查找关键字序列为{45，24，53，45，12，24，90}，则经过一系列查找插入操作后，生成的BST为：9.2动态查找表4.BST的特点：(1)中序遍历BST可得到一个关键字的有序序列。如上例：中序遍历结果为：12，24，45，53，90

这是由于BST中左子树的所有结点的值均小于其根结点的值，右子树的所有结点的值均大于其根结点的值；而中序遍历又是以LDR顺序访问的。9.2动态查找表(2)在BST上插入新结点时，不必移动其他结点，仅需改动某结点的指针（因新结点总是BST上的一个新叶结点）。

(3)BST既具有类似折半查找的特性（与BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用BST尤其合适。9.2动态查找表5．BST的删除删除的原则：删除某个结点后仍保持BST的特性。设：被删除结点为p↑(指针p所指结点）其双亲结点为f↑,且不失一般性，设p是f的左孩子。9.2动态查找表cqCSLsCLFFRfPRpPQQLS分三种情况讨论：

若P↑结点为叶结点（即PL和PR均为空树，仅需将f↑．lchild:=NIL

若P↑结点只有左子树PL或只有右子树PR，只需令PL或PR为f↑的左子树，即f↑．lchild:=P↑．lchild

(或P↑．rchild)

若P↑结点左、右子树均不空，此时，按中序遍历序列为：…CLC…QLQSLSPPRFFR…删除p后为：…CLC…QLQSLSPR

FFR…结果是将PR作为SR

。CSLCLPRQQLSFSSLCLFPRQQLC对F的左孩子有两种处理办法：(1)S不动，仍作为Q的右孩子，C代替P，作为F的左孩子;(2)S代替P，而

SL为QR;9.2动态查找表PROCdel_bstree1(VARbst：bitreptr；f，p：bitreptr）；

{删除p↑结点；f↑是p↑的双亲}IFf=NILTHEN{p↑为根结点

}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动态查找表ELSE{p↑不是根结点}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动态查找表6．BST的查找分析

BST上查找过程与折半查找类似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度+1（即结点所在层次数），最大层次数不超过树的深度。但长度为n的折半查找表对应的判定树是唯一的。而含有n个结点的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动态查找表因此，含有n个结点的BST的ASL和树的形态有关。最差情况是BST退化为单支树，其深度为n，ASL=(n+1)/2(同顺序查找）。最好情况与折半查找相同，ASL=log2n

随机情况下，平均查找长度为1+4logn为了避免出现单支树，在构成BST的过程中可进行“平衡化”处理。9.3哈希查找表

前面介绍的查找算法,有一个共同特点:就是以待查关键字k,在表中，通过一系列比较来确定该记录在表中的“地址”。这一节将介绍另一种通过计算来查找的新型方法-----哈希法（Hash）或称杂凑法、散列法。设关键字集合为A，地址空间为D，哈希法就是在A和D之间建立一种函数关系H，通过计算函数H（k），就能得到关键字K的地址。关键字集Am地址空间Dn哈希函数

H（k）9.3哈希查找表

设D是长度为n的表，

A是含m个记录的关键字集合，如果存在一个函数H，使得对A中任一关键字Ki，均有，

0≤H（Ki

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

同时,Ki

所标识的记录Ri在表D中的地址是H(Ki)，则称函数H为关键字集合A到地址空间D之间的哈希函数，地址空间D为哈希表。哈希函数并不一定是一对一的，例如，当m＞n时，对任何哈希函数H，至少存在两个关键字Ki≠Kj

，使得H(Ki)=H(Kj)，这种对不同关键字而得到同一地址的现象，称为冲突。9.3哈希查找表

因此，在应用哈希查找方法时，主要要解决两个技术问题：一是构造好哈希函数的方法;

二是研究解决冲突的方法。一.哈希函数构造方法一个好的哈希函数应满足下列两个条件：计算简单容易冲突极少9.3哈希查找表1．直接哈希函数取关键字本身或关键字的某个线性函数值作为哈希地址，即：H（key）=key或H（key）=a*key+b（a，b为常数）例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为:H（key）=key+（-1948）这样就可以方便地存储和查找1948年后任一年的记录。

地址年份人数011949．．．．．．．．．．．．．．．．．．

2219709.3哈希查找表2．数字分析法设ｎ个ｄ位数的关键字，由ｒ个不同的符号组成，此ｒ个符号在关键字的各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于ｎ／ｒ次，而在另一些位上分布不均匀。则选择其中分布均匀的s位作为哈希地址，即H（key）=“key中数字均匀分布的s位”，这便是数字分析哈希函数。例：由80个记录，关键字为8位十进制数，（n=80，r=10，d=8）对关键字的各位进行分析，发现：第1，2位都是“8，1”，第3位只取1，2，3或4，第8位只取2，5或7，即10个数在这四位分布不均匀，不取。可在剩下的4，5，6，7位中任取两位，作为哈希地址。9.3哈希查找表813465328137224281387422813013678132281781338967813541578136853781419355......9.3哈希查找表3．平方取中法取关键字平方后的中间几位作为哈希地址，即哈希函数为:H（key）=“key2的中间几位”其中，所取的位数由哈希表的大小确定。9.3哈希查找表4．折叠法将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。相加时有两种方法：一是移位叠加法，即将每部分的最后一位对齐，然后相加；另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。9.3哈希查找表设关键字key=d3r．．．d2r+1d2r．．．dr+1dr．．．d2d1允许的存储地址有r位。则移位叠加法为：dr．．．d2d1

d2r．．．dr+1

+)

d３r．．．d2r+1

Sr．．．S2S19.3哈希查找表5．除留余数法取关键字被某个不大于哈希表长m的数p除后的余数为哈希地址。即H（key）=keyMODp，p≤mp的选择很重要，选得不好会产生很多冲突，通常，选择p≤m的某个质数。6．随机数法选择一个随机函数，取关键字的随机函数值作为它的哈希地址。即H（key）=random（key）9.3哈希查找表二.处理冲突的方法

冲突是指由关键字得到的Hash地址上已有其他记录,

处理冲突就是为该关键字找到另一个“空”的Hash地址。1.开放定址法

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

其中:Hi为第i次冲突的地址,

H（key）为Hash函数值,

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=伪随机序列称为伪随机探测再散列例：设m=16,表中已有关键字,分别为：19，70，33三个记录，

Hash函数取为H（key）=keymod13，现第四个关键字为18的记录要填入表中，由Hash函数得地址5，产生冲突

012345678910111213141570193370193318

H1H2H3

18701933H2H1701933线性二次伪随机伪随机数序列9．．．．H1＝１4mod16=14

18例：H（key）=keymod13,采用线性探测再散列法处理冲突,m=16

对关键字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...