《九章节查找.ppt》由会员分享，可在线阅读，更多相关《九章节查找.ppt（64页珍藏版）》请在三一办公上搜索。
1、第九章 查找,静态查找表 动态查找表 哈希查找表,9.1 静态查找表,查找表(table):由同类型的DE(或记录)构成的集合.查找表上的基本运算:建立查找表create(ST,n)查找search(ST,k)遍历查找表traverse(ST),9.1 静态查找表,查找:在查找表中确定与给定值相等的DE的过程.查找结果:查找成功(table 中存在给定值的记录)查找不成功(table 中不存在给定值的记录),查找表分为:静态查找表(对查找表中的数据元素不进行插入和删除操作)动态查找表(对查找表中的数据元素可进行插入和删除操作),9.1 静态查找表,一.顺序表的查找 FUNC seqsrch(r
2、:sqlisttp;k:keytype):integer;r0.key:=k;i:=n;WHILE ri.key k DO i:=i-1;RETURN(i)ENDF;seqsrch,9.1 静态查找表,1.查找过程:从n开始,依次与k进行比较,若相等则查找成功;否则,继续进行,直到与r0.key比较为止.2.算法分析:(1)算法结构应由一个循环构成;(2)循环结束有两种可能：查找成功 ri.key=k 查找不成功 i=0,9.1 静态查找表,(2)循环结束有两种可能：查找成功 ri.key=k 条件控制式 查找不成功 i=0 计数控制式这两种可能形成两种不同类型的循环控制：条件循环 WHILE
3、 条件 DO 循环体 REPEAT 循环体 UNTIL 条件 计数循环 FOR i:=n DOWNTO 0,9.1 静态查找表,常规解决办法:(1)条件循环为主 WHILE ri.key k DO IF i=1 THEN RETURN(0)ELSE i:=i-1;(2)复合条件 WHILE ri.key k AND i=1 DO i:=i-1;(3)计数循环为主 FOR i:=n DOWNTO 1 DO IF ri.key=k THEN RETURN(i),9.1 静态查找表,FUNC seqsrch(r:sqlisttp;k:keytype):integer;r0.key:=k;i:=n;W
4、HILE ri.key k DO i:=i-1;RETURN(i)ENDF;seqsrch,3.r0起监视哨作用,9.1 静态查找表,FUNC seqsrch2(r:sqlisttp;k:keytype):integer;rn+1.key:=k;i:=1;WHILE ri.key k DO i:=i+1;IF i=n+1 THEN RETURN(0)ELSE RETURN(i)ENDF;seqsrch2,4.查找方向可换,FUNC seqsrch(r:sqlisttp;k:keytype):integer;r0.key:=k;i:=n;WHILE ri.key k DO i:=i-1;RETU
5、RN(i)ENDF;seqsrch,9.1 静态查找表,平均查找长度(ASL):查找过程中,给定值需与关键字比较的次数的期望值.nASL=PiCi i=1其中:Pi 为查找第i 个记录的概率;Ci 为找到第i 个记录时,已比较的次数.,顺序查找的平均查找长度ASLss=np1+(n-1)p2+pn n当pi=1/n时,ASLss=PiCi=(n+1)/2 i=1,9.1 静态查找表,二.有序表的查找有序表:查找表中记录按关键字有序排列的表.即:ri.key=ri+1.key i=1,2,n-1折半查找:要求:查找表为有序表;查找过程:先确定待查记录范围;然后逐步缩小范围;直到:查找成功或不成功
6、.,9.1 静态查找表,折半查找算法 FUNC binsrch(r:ordlisttp;k:keytype):integer;low:=1;high:=n;found:=false;WHILE lowhigh AND NOT found DO mid:=(low+high)DIV 2 CASE krmid.key:low:=mid+1;k=rmid.key:found:=true;krmid.key:high:=mid-1;ENDC;IF found THEN RETURN(mid)ELSE RETURN(i)ENDF;binsrch,9.1 静态查找表,折半查找算法 FUNC binsrch
7、(r:ordlisttp;k:keytype):integer;low:=1;high:=n;found:=false;WHILE lowhigh AND NOT found DO mid:=(low+high)DIV 2 CASE krmid.key:low:=mid+1;k=rmid.key:found:=true;krmid.key:high:=mid-1;ENDC;IF found THEN RETURN(mid)ELSE RETURN(i)ENDF;binsrch,例:k=21,有序表为:(5,13,19,21,37,56,64,75,80,88,92)1.Low=1,high=11
8、,mid=62.2119 low=4 mid=44.21=21 found=true return(4),折半查找的平均查找长度ASLbs=(n+1)/nlog2(n+1)-1 log2(n+1)-1,9.1 静态查找表,三.索引顺序表的查找(分块查找)索引表:1)按表中记录的关键字分块,R1,R2,RL要求:第Rk 块中的所有关键字 Rk+1块中的所有关键字 k=1,2,L-1,称为“分块有序”2)对每块建立一个索引项,包含以两项内容:关键字项:为该块中最大关键字值;指针项:为该块第一个记录在表中位置.3)所有索引项组成索引表,9.1 静态查找表,例.查找表为:22,12,13,8,9,20
9、,33,42,44,38,24,48,60,58,74,49,86,53索引表为:,9.1 静态查找表,查找分为两步:1.确定待查记录所在块;(可以用顺序或折半查找)2.在块内顺序查找.(只能用顺序查找),9.1 静态查找表,分块查找表的平均查找长度ASL=Lb+Lw其中:Lb为查索引表确定所在块的平均查找长度;Lw为在块内查找记录的平均查找长度;,9.2 动态查找表,动态查找表的特点是:表结构本身是在查找过程中动态生成的。即查找不成功时，将该记录插入在动态查找表中。一、二叉排序树（Binary Sort Tree)（又称为二叉查找树）1、BST定义：BST或者是一棵空树；或者是具有如下性质的
10、BT:若左子树非空，则左子树上所有结点的值均小于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树也为BST,9.2 动态查找表,9.2 动态查找表,2、查找过程为:(1)当前BST非空时，将给定值k与当前根结点的关键字比较:(2)若相等，查找成功，结束;若k小于当前根结点的关键字，则将左子树作为当前BST;若k大于当前根结点的关键字，则将右子树作为当前BST;(3)重复(1)。,9.2 动态查找表,算法描述为：FUNC bstsrch(t:bitreptr;k:keytype):bitreptr;查找不成功时返回NIL IF(t=NIL)COR(t.key=k)TH
11、EN RETURN(t)ELSE IF t.keyk THEN RETURN(bstsrch(t.rchild,k)ELSE RETURN(bstsrch(t.lchild,k)ENDF bstsrch,9.2 动态查找表,3.BST的插入插入原则：记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。PROC insbst(VAR bst:bitreptr;k:keytype);f:=NIL;found:=false;f:=srch_bstree(f,bst,k,found)IF NOT found THEN ins_bstree(f,bst,k)ENDP;insbst
12、,9.2 动态查找表,FUNC srch_bstree(VAR f:bitreptr;bst:bitreptr;k:keytype;VAR found:Boolean):bitreptr;IF bst=NIL THEN found:=false;RETURN(f)ELSE IF t.key=k THEN found:=true;RETURN(bst)ELSE f:=bst;f记载上次比较的结点的位置 IF t.keyk THEN RETURN(srch_bstree(f,bst.rchild,k,found)ELSE RETURN(srch_bstree(f,bst.lchild,k,foun
13、d)ENDF srch_bstree,9.2 动态查找表,PROC ins_bstree(VAR f,bst:bitreptr;k:keytype);new(s);s.key:=k;s.lchild:=NIL;s.rchild:=NIL;IF bst=NIL THEN bst:=s ELSE IF kf.key THEN f.lchild:=s ELSE f.rchild:=sENDP;ins_bstree,9.2 动态查找表,例：设BST为空，查找关键字序列为45，24，53，45，12，24，90，则经过一系列查找插入操作后，生成的BST为：,9.2 动态查找表,4.BST的特点：(1)中
14、序遍历BST可得到一个关键字的有序序列。如上例：中序遍历结果为：12，24，45，53，90 这是由于BST中左子树的所有结点的值均小于其根结点的值，右子树的所有结点的值均大于其根结点的值；而中序遍历又是以L DR顺序访问的。,9.2 动态查找表,(2)在BST上插入新结点时，不必移动其他结点，仅需改动某结点的指针（因新结点总是BST上的一个新叶结点）。(3)BST既具有类似折半查找的特性（与BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用BST尤其合适。,9.2 动态查找表,5 BST的删除删除的原则：删除某个结点
15、后仍保持BST的特性。设：被删除结点为p(指针p所指结点）其双亲结点为f,且不失一般性，设p 是f 的左孩子。,9.2 动态查找表,分三种情况讨论：若P结点为叶结点（即PL和PR均为空树，仅需将flchild:=NIL 若P结点只有左子树PL或只有右子树PR，只需 令PL或PR为f 的左子树，即f lchild:=P lchild(或 Prchild)若P结点左、右子树均不空，此时，按中序遍历序列为：CL CQL Q SL S P PR F FR删除p后为：CLCQL Q SL S PR F FR结果是将PR作为SR。,对F的左孩子有两种处理办法：(1)S不动，仍作为Q的右孩子，C代替P，作为
16、F的左孩子;,(2)S代替P，而 SL为QR;,9.2 动态查找表,PROC del_bstree1(VAR bst：bitreptr；f，p：bitreptr）；删除p结点；f 是p的双亲 IF f=NIL THEN p为根结点 CASE plchild=NIL AND prchild=NIL：bst：=NIL；plchild=NIL：bst：=prchild；prchild=NIL：bst：=plchild；ELES s：=plchild；WHILE s rchild NIL DO s：=s rchild；bst：=plchild；s rchild：=prchild；ENDC,9.2 动态
17、查找表,ELSE p不是根结点 CASE p rchild=NIL：f lchild：=p lchild：p lchild=NIL：f lchild：=p rchild；ELSE s：=p lchild；WHILE s rchildNIL DO s:=s rchild；s lchild：=p rchild；f lchild：=p lchild；ENDCENDP；del_bstree1,9.2 动态查找表,6BST 的查找分析 BST 上查找过程与折半查找类似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度+1（即结点所在层次数），最大次数不超过树的深度。但长度为n的折半查找表
18、对应的判定树是唯一的。而含有n个结点的BST却不唯一。,ASL(a)=1/6（1+2+2+3+3+3）=14/6ASL(b)=1/6（1+2+3+4+5+6）=21/6,9.2 动态查找表,因此，含有n个结点的BST的ASL和树的形态有关。最差情况是BST退化为单支树，其深度为n，ASL=(n+1)/2(同顺序查找）。最好情况与折半查找相同，ASL=log2n 随机情况下，平均查找长度为1+4log n 为了避免出现单支树，在构成BST的过程中可进行“平衡化”处理。,二.平衡二叉树(Balanced Binary Tree),又称为AVL树 1、AVL树定义AVL树或者是一棵空树，或者是具有下
19、列性质的BT:左、右子树均为AVL，且任一左、右子树的深度之差的绝对值不超过1.称某结点左子树的深度右子树的深度为该结点的平衡因子（balance factor),9.2 动态查找表,例如：,结点中的值为该结点的平衡因子,9.2 动态查找表,9.2 动态查找表,2、AVL树的特点 AVL树上任何结点的平衡因子只可能为-1，0或1;AVL树的深度与log n同数量级;AVL树的ASL也与log n同数量级;完全二叉树一定是AVL,当AVL树不一定是完全二叉树,9.2 动态查找表,3、BST变为AVL树 例：设表的关键字序列为（13，24，37，90，53）,BST生成过程为：,9.2 动态查找表
20、,在BST上插入结点而失去平衡，失去平衡后需进行调整.,(2)调整形态(可归纳为四种)LL型平衡旋转（顺时针）失去平衡点的平衡因子为2,其左孩子的平衡因子为1,调整语句为：b：alchild;alchild=brchild;abf：=0b rchild：=a;bbf：=0,9.2 动态查找表,LR型平衡旋转失去平衡点的平衡因子为2,其左孩子的平衡因子为-1,b：alchild;c：brchild；alchild=crchild;b rchild：=clchild crchild：a;clchild：b;,9.2 动态查找表,RR型平衡旋转（逆时针，与LL对称)失去平衡点的平衡因子为-2,其右孩
21、子的平衡因子为-1,9.2 动态查找表,RL型平衡旋转失去平衡点的平衡因子为-2,其右孩子的平衡因子为 1,中序遍历：AL A CL C CR B BR AL A CL C CR B BR,9.2 动态查找表,(3)为了得到平衡树，需作如下处理 找到可能失去平衡的最小子树的根结点 可能失去平衡的最小子树的根结点，是离插入结点最近的且插入前平衡因子值0:插入前平衡因子的绝对值0 插入后平衡因子的绝对值1 离插入结点最近的失去平衡的祖先结点判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡，（该结点的平衡因子的绝对值1）;判别旋转类型作相应处理。,9.2 动态查找表,4、AVL树上插入结点算
22、法(1)算法描述 查找 s 结点的插入位置过程中，记下离s 最近的，且平衡因子不等于0的结点，令 a 指向该结点；（即可能失去平衡的最小子树的根结点）。修改 a 至 s 路径上所有结点的平衡因子值；判别a 结点的平衡因子绝对值是否大于1，若是，作旋转处理,（2）过程描述 PROC ins_AVLtree(VAR t：AVLinktp；：keytype）；在t为根结点的AVL上插入关键字为K的新结点 new(s)；skey：=K，slchild：=srchild：=NIL；sbf：=0；IF t=NIL THEN t：=s 插入根结点 ELSE(1)查找s 的插入位置q,同时记下：a及a的双亲f
23、 从根到叶结点搜索 f：=NIL；a：=t；p：=t；q：=NIL；WHILE pNIL DO IF p bf 0 THEN a：=p；f：=q；q是p的双亲,p、q是沿路径移动,a、f是跳跃移动 q：=p；IF skeyp key THEN p：=p lchild ELSE p：=p rchild；插入s IF skeyq key THEN q lchild：=s ELSE q rchild：=s;,9.2 动态查找表,（2）修改a至s 路径上的平衡因子从a 到叶 IF skeyakey THEN p：=alchild；b：=p；d：=1 ELSE p：=archild；b：=p；d：=-1
24、；左子树插入，使左子树深度增1，反之右树深度增1 WHILE PS DO IF skeypkey THEN pbf：=1；p：=plchild ELSE pbf：=-1；p：=prchild;原来从ps的所有结点的叶全部为0，所以计算方法并不是用定义左深右深，方向也不是从下到上,9.2 动态查找表,（3）判a为根的子树是否失去平衡 balanced:=true;CAES abf=0：abf：=d 原来为0,插入后为d abf+d=0：abf：=0 原来为1(-1),插入-1/1后为0 ELSE 失去平衡 IF d=+1 THEN CASE bbf=1：LL-rotation bbf=-1：LR
25、-rotation ENDC；ELSE CASE bbf=-1：RR-rotation bbf=1：RL-rotation ENDC；balanced：=false ENDC；,9.2 动态查找表,IF NOT balanced THEN CASE RL，LR旋转处理后，b：=c f=NIL:t：=b;b指向失去平衡调整后子树根 flchild=a:flchild：=b;frchild=a:frchild：=b ENDC；ENDP；ins_AVLtree平衡树查找时间复杂度为O(logn),9.3 哈希查找表,前面介绍的查找算法,有一个共同特点:就是以待查关键字k在表中，通过一系列比较来确定该
26、记录在表中的“地址”。这一节将介绍另一种通过计算来查找的新型方法-哈希法（Hash）或称杂凑法、散列法。设关键字集合为A，地址空间为D，哈希法就是在A和D之间建立一种函数关系H，通过计算函数H（k），就能得到关键字K的地址。,关键字集A m,地址空间D n,哈希函数 H（k）,9.3 哈希查找表,设D是长度为n的表，A是含m个记录的关键字集合，如果存在一个函数H，使得对A中任一关键字Ki，均有，0H（Ki）n-1 i=1，2，m 同时,Ki 所标识的记录R i在表D中的地址是H(Ki)，则称函数H为关键字集合A到地址空间D之间的哈希函数，地址空间D为哈希表。哈希函数并不一定是一对一的，例如，当
27、mn时，对任何哈希函数H，至少存在两个关键字Ki Kj，使得H(Ki)=H(Kj)，这种对不同关键字而得到同一地址的现象，成为冲突。,9.3 哈希查找表,因此，在应用哈希查找方法时，主要要解决两个技术问题：一是构造好哈希函数的方法;二是研究解决冲突的方法。一.哈希函数构造方法 一个好的哈希函数应满足下列两个条件：计算简单容易 冲突极少,9.3 哈希查找表,1直接哈希函数 取关键字本身或关键字的某个线性函数值作为哈希地址，即：H（key）=key 或H（key）=a*key+b（a，b为常数）例如：有一个解放后出生人口调查表，每个记录包含年份、人数等数据项，其中年分为关键字，则哈希函数可取为:H
28、（key）=key+（-1948）这样就可以方便地存储和查找1948年后任一年的记录。,9.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个数在这四位分布不均匀
29、，不取。可在剩下的4，5，6，7位中任取两位，作为哈希地址。,9.3 哈希查找表,3平方取中法 取关键字平方后的中间几位作为哈希地址，即哈希函数为:H（key）=“key2的中间几位”其中，所取的位数由哈希表的大小确定。,9.3 哈希查找表,4折叠法将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。相加时有两种方法：一是移位叠加法，即将每部分得最后一位对齐，然后相加；另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。,9.3 哈希查找表,设关键字key=d3 rd 2 r+1
30、d2 rd r+1d rd2d1允许的存储地址有r位。则 移位叠加法为：d r d2d1 d2 r d r+1+)d r d 2 r+1,Sr S2S1,9.3 哈希查找表,5除留余数法 取关键字被某个不大于哈希表长m的数p除后的余数为哈希地址。即 H（key）=key MOD p，pm p的选择很重要，选得不好会产生很多冲突，通常，选择 p m的某个质数。,6随机数法 选择一个随机函数，取关键字的随机函数值作为它的哈希地址。即 H（key）=random（key）,9.3 哈希查找表,二.处理冲突的方法 冲突是指由关键字得到的Hash地址上已有其他记录,处理冲突就是为该关键字找到另一个“空”
31、的Hash地址。1.开放定址法 Hi=（H（key）+di）mod m i=1，2m-1;其中:Hi 为第i次冲突的地址,H（key）为Hash函数值,m 为Hash表表长,di 为增量序列,9.3 哈希查找表,Hi=（H（key）+di）mod m i=1，2m-1;其中:di为增量序列,有三种取法：di=1，2，3m-1 称为线性探测再散列 di=12,-12,22,-22,32k2|k|m-1 称为二次探测再散列 di=伪随机序列 称为伪随机探测再散列,例：设m=16,表中已有关键字,分别为：19，70，33三个记录，Hash函数取为H（key）=key mod13，现第四个关键字为18的记录要填入表中，由Hash函数得地址5，产生冲突,18,9.3 哈希查找表,2.再哈希法 Hi=RHi（key）i=1，2n;RHi 为不同哈希函数 用n个不同哈希函数排成一个序列,当发生冲突时,由RHi确定第i次冲突的地址Hi,3.链地址法 将关键字发生冲突的记录存储在同一个线性链表中。例：H（key）=key mod 13 对关键字19，14，23，01，68，20，84，27，55，11，10，79 处理的结果为：,9.3 哈希查找表,4.公共溢出区法将同哈希表中关键字发生冲突的所有记录填入一个溢出表中.例如上例的结果为：,
