九章节查找.ppt

《九章节查找.ppt》由会员分享，可在线阅读，更多相关《九章节查找.ppt（64页珍藏版）》请在三一文库上搜索。

1、第九章 查找,静态查找表 动态查找表 哈希查找表,9.1 静态查找表,查找表(table):由同类型的DE(或记录)构成的集合. 查找表上的基本运算: 建立查找表create(ST, n) 查找search(ST, k) 遍历查找表traverse(ST),9.1 静态查找表,查找 : 在查找表中确定与给定值相等的DE的过程. 查找结果: 查找成功 (table 中存在给定值的记录) 查找不成功 (table 中不存在给定值的记录),查找表分为: 静态查找表 (对查找表中的数据元素不进行插入和删除操作) 动态查找表 (对查找表中的数据元素可进行插入和删除操作),9.1 静态查找表,一. 顺序表

2、的查找 FUNC seqsrch(r: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 条件控制式

3、 查找不成功 i = 0 计数控制式 这两种可能形成两种不同类型的循环控制： 条件循环 WHILE 条件 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

4、(i),9.1 静态查找表,FUNC seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; WHILE 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. 查找方向

5、可换,FUNC seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; WHILE ri.key k DO i:=i-1; RETURN(i) ENDF; seqsrch,9.1 静态查找表,平均查找长度(ASL): 查找过程中, 给定值需与关键字比较的次数的期望值. n ASL=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 静态查

6、找表,二. 有序表的查找 有序表 : 查找表中记录按关键字有序排列的表. 即: ri.key=ri+1.key i=1,2,n-1 折半查找 : 要求: 查找表为有序表; 查找过程: 先确定待查记录范围; 然后逐步缩小范围; 直到: 查找成功或不成功.,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

7、; 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(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: f

8、ound:=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, mid=6 2. 2119 low=4 mid= 4 4. 21=21 found=true return(4),折半查找的平均查找长度 ASLbs=(n+1)/nlog2(n+1)-1 log2(n+1)-1,9.1 静态查找表,三. 索引顺序表的

9、查找(分块查找) 索引表 : 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 索引表为:,9.1 静态查找表,查找分为两步: 1. 确定待查记录所在块; (可以用顺序

10、或折半查找) 2. 在块内顺序查找. (只能用顺序查找),9.1 静态查找表,分块查找表的平均查找长度ASL=Lb+Lw 其中: Lb为查索引表确定所在块的平均查找长度; Lw为在块内查找记录的平均查找长度;,9.2 动态查找表,动态查找表的特点是: 表结构本身是在查找过程中动态生成的。 即查找不成功时，将该记录插入在动态查找表中。 一、二叉排序树（Binary Sort Tree)（又称为二叉查找树） 1、BST定义： BST或者是一棵空树；或者是具有如下性质的BT: 若左子树非空，则左子树上所有结点的值均小于根结点的值； 若右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树也

11、为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) THEN RETURN(t) ELSE IF t.keyk THEN RETURN(bstsrc

12、h(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,9.2 动态查找表,FUNC srch

13、_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, found)

14、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:=s ENDP;ins_bstree,9.2 动态查找表,例：设BST为空， 查找关键字序列为45，24，53，45，12，24，90， 则经过一系列查找插入操作后，生成的BST为：,9.2 动态查找表,4. BS

15、T的特点： (1) 中序遍历BST可得到一个关键字的有序序列。 如上例：中序遍历结果为：12 ，24，45，53，90 这是由于BST中左子树的所有结点的值均小于其根结点的值， 右子树的所有结点的值均大于其根结点的值； 而中序遍历又是以L DR顺序访问的。,9.2 动态查找表,(2) 在BST上插入新结点时，不必移动其他结点，仅需改动某结点的指针（因新结点总是BST上的一个新叶结点）。 (3) BST既具有类似折半查找的特性（与BST的平衡度有关）又采用了链表存储结构（折半查找不能为链表存储结构），因此，对于经常要进行查找、插入和删除记录的有序表，采用BST尤其合适。,9.2 动态查找表,5

16、BST的删除 删除的原则： 删除某个结点后仍保持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的左

17、孩子有两种处理办法： (1) S不动，仍作为Q的右孩子，C代替P ，作为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

18、 rchild ； bst：= plchild； s rchild：= prchild； ENDC,9.2 动态查找表,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； ENDC ENDP；del_bstree1,9.2 动态查找表,6BST 的查找分析 BST 上查找过程与折半查找类

19、似，是从根结点到所找到结点的一条路径。与给定值比较次数等于该路径长度+1（即结点所在层次数），最大次数不超过树的深度。 但长度为n的折半查找表对应的判定树是唯一的。而含有n个结点的BST却不唯一。,ASL(a)=1/6（1+2+2+3+3+3）=14/6 ASL(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的过程中

20、可进行 “平衡化”处理。,二. 平衡二叉树 (Balanced Binary Tree), 又称为AVL树 1 、AVL树定义 AVL树或者是一棵空树，或者是具有下列性质的BT: 左、右子树均为AVL， 且任一左、右子树的深度之差的绝对值不超过1. 称某结点左子树的深度右子树的深度为该结点的平衡因子（balance factor),9.2 动态查找表,例如：,结点中的值为该结点的平衡因子,9.2 动态查找表,9.2 动态查找表,2、AVL树的特点 AVL树上任何结点的平衡因子只可能为-1，0或1; AVL树的深度与log n同数量级; AVL树的ASL也与log n同数量级; 完全二叉树一定是

21、AVL , 当AVL树不一定是完全二叉树,9.2 动态查找表,3、BST变为AVL树 例：设表的关键字序列为（13，24，37，90，53）, BST生成过程为：,9.2 动态查找表,在BST上插入结点而失去平衡，失去平衡后需进行调整.,(2) 调整形态 (可归纳为四种) LL型平衡旋转（顺时针） 失去平衡点的平衡因子为2, 其左孩子的平衡因子为1,调整语句为： b：alchild; alchild =brchild ; abf：=0 b rchild：=a; bbf：=0,9.2 动态查找表, LR型平衡旋转 失去平衡点的平衡因子为2, 其左孩子的平衡因子为 -1,b：alchild; c：

22、 brchild； alchild =crchild ; b rchild： = clchild crchild：a; clchild ：b;,9.2 动态查找表, RR型平衡旋转（逆时针，与LL对称) 失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 -1,9.2 动态查找表, RL型平衡旋转 失去平衡点的平衡因子为 -2, 其右孩子的平衡因子为 1,中序遍历：AL A CL C CR B BR AL A CL C CR B BR,9.2 动态查找表,(3) 为了得到平衡树，需作如下处理 找到可能失去平衡的最小子树的根结点 可能失去平衡的最小子树的根结点，是离插入结点最近的且插入前平衡因

23、子值0: 插入前平衡因子的绝对值0 插入后平衡因子的绝对值1 离插入结点最近的失去平衡的祖先结点 判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡， （该结点的平衡因子的绝对值1）; 判别旋转类型作相应处理。,9.2 动态查找表,4、AVL树上插入结点算法 (1) 算法描述 查找 s 结点的插入位置过程中，记下离s 最近的，且平衡因子不等于0的结点，令 a 指向该结点；（即可能失去平衡的最小子树的根结点）。 修改 a 至 s 路径上所有结点的平衡因子值； 判别a 结点的平衡因子绝对值是否大于1，若是，作旋转处理,（2） 过程描述 PROC ins_AVLtree (VAR t：AVLi

24、nktp；：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 从根到叶结点搜索 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 rchil

25、d ； 插入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； 左子树插入，使左子树深度增1，反之右树深度增1 WHILE PS DO IF skeypkey THEN pbf：=1；p：= plchild ELSE pbf：=-1； p：= prchild; 原来从ps的所有结点的叶全部为0，所以计算方法并不是用定义左深右深，方向也不是

26、从下到上,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-rotation ENDC； ELSE CASE bbf=-1：RR-rotation bbf= 1：RL-rotation ENDC； balanced：=false ENDC；,9.2 动态查找表,IF NOT balanced THEN CASE RL，

27、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在表中，通过一系列比较来确定该记录在表中的“地址”。 这一节将介绍另一种通过计算来查找的新型方法-哈希法（Hash）或称杂凑法、散列法。 设关键字集合为A，地址空间为D，哈希法就是在A和D之间建立一种函数关系H，通过计算函数H（k），就能得到关键字K的地址。,关键字集A

28、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为哈希表。 哈希函数并不一定是一对一的，例如，当mn时，对任何哈希函数H，至少存在两个关键字Ki Kj ，使得H(Ki) = H(Kj)，这种对不同关键字而得到同一地址的现象，成为冲突。,9.3 哈希查找表,因此，在应用哈希查找方法时，主要要解决两个技术问题： 一是构

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

30、频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于次，而在另一些位上分布不均匀。 则选择其中分布均匀的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 哈希查找表,3平方取中法 取关键字平方后的中间几位作为哈希地址，即哈希函数为: H（key）=“key2的中间几位

31、” 其中，所取的位数由哈希表的大小确定。,9.3 哈希查找表,4折叠法 将关键字分割成位数相等的几部分（最后一部分位数可以不同），取这几部分的叠加和（舍去高位的进位）作为哈希地址。位数由存储地址的位数确定。 相加时有两种方法： 一是移位叠加法，即将每部分得最后一位对齐，然后相加； 另一种是间界叠加法，即将关键字看作一纸条，从一端向另一端沿间界逐次折叠，然后对齐相加。,9.3 哈希查找表,设关键字key=d3 rd 2 r+1d2 rd r+1d rd2d1 允许的存储地址有r位。 则 移位叠加法为： d r d2d1 d2 r d r+1 +) d r d 2 r+1,Sr S2S1,9.3

32、哈希查找表,5除留余数法 取关键字被某个不大于哈希表长m的数p除后的余数为哈希地址。 即 H（key）=key MOD p，pm p的选择很重要，选得不好会产生很多冲突， 通常，选择 p m的某个质数。,6随机数法 选择一个随机函数，取关键字的随机函数值作为它的哈希地址。 即 H（key）=random（ key）,9.3 哈希查找表,二. 处理冲突的方法 冲突是指由关键字得到的Hash地址上已有其他记录, 处理冲突就是为该关键字找到另一个“空”的Hash地址。 1. 开放定址法 Hi =（H（key）+di）mod m i=1，2m-1; 其中: Hi 为第i次冲突的地址, H（key）为H

33、ash函数值, 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. 公共溢出区法 将同哈希表中关键字发生冲突的 所有记录填入一个溢出表中. 例如上例的结果为：,