考研数据结构cha.ppt

第九章 查找 静态查找表静态查找表 动态查找表动态查找表 哈希查找表哈希查找表 9.1 9.1 静态查找表静态查找表 查找表查找表( (table):table):由同类型的由同类型的DE(DE(或记录或记录) )构成的集合构成的集合. . 查找表上的基本运算: 建立查找表create(ST, n) 查找search(ST, k) 遍历查找表traverse(ST) 9.1 9.1 静态查找表静态查找表 查找查找 : : 在查找表中确定与给定值相等的在查找表中确定与给定值相等的DEDE的过程的过程. . 查找结果: 查找成功查找成功 ( (table table 中存在给定值的记录中存在给定值的记录) ) 查找不成功查找不成功 ( (table table 中不存在给定值的记录中不存在给定值的记录) ) 查找表分为查找表分为: : 静态查找表 ( (对查找表中的数据元素对查找表中的数据元素不不进行插入和删进行插入和删 除操作除操作) ) 动态查找表 ( (对查找表中的数据元素对查找表中的数据元素可可进行插入和删进行插入和删 除操作除操作) ) 9.1 9.1 静态查找表静态查找表 一. 顺序表的查找 FUNC seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; WHILE ri.key k DO WHILE ri.key k AND i=1 DO i: = i - 1 ;WHILE ri.key =1 DO i: = i - 1 ; (3) (3) 计数循环为主计数循环为主 FOR i:=n DOWNTO 1 DO FOR i:=n DOWNTO 1 DO IF ri.key=k THEN RETURN(i) IF ri.key=k THEN RETURN(i) 9.1 9.1 静态查找表静态查找表 FUNC seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; WHILE ri.key k DO i:=i+1; IF i=n+1 THEN RETURN(0) ELSE RETURN(i) ENDF; seqsrch2 4. 4. 查找方向可换查找方向可换 FUNC seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; WHILE ri.key 19 19 low=4 mid= low=4 mid= 4 4 4. 21=21 found=true return(4)4. 21=21 found=true return(4) 折半查找的平均查找长度折半查找的平均查找长度 ASLbs=(n+1)/nlogASLbs=(n+1)/nlog 2 2 (n+1)-1 (n+1)-1 loglog 2 2 (n+1)-1(n+1)-1 9.1 9.1 静态查找表静态查找表 三. 索引顺序表的查找(分块查找) 索引表 : 1) 按表中记录的关键字分块, R1,R2,RL 要求: 第Rk 块中的所有关键字12i12为止为止. . 9.1 静态查找表 分块查找表的平均查找长度ASL=Lb+Lw 其中: Lb为查索引表确定所在块的平均查找长度; Lw为在块内查找记录的平均查找长度; 三种查找方法比较 顺序查找折半查找 分块查找 ASL大小 中 表结构要求 无有序表 分段有序 （块之间有序） 9.2 9.2 动态查找表动态查找表 动态查找表的特点是动态查找表的特点是: : 表结构本身是在查找过程中动态生成的。表结构本身是在查找过程中动态生成的。 即查找不成功时，将该记录插入在动态查找表中。即查找不成功时，将该记录插入在动态查找表中。 一、二叉排序树（一、二叉排序树（Binary Sort Tree)Binary Sort Tree)（又称为二叉查找树）又称为二叉查找树） 1 1、BSTBST定义：定义： BSTBST或者是一棵空树；或者是具有如下性质的或者是一棵空树；或者是具有如下性质的BT:BT: 若左子树非空，则左子树上所有结点的值均小于根结点的值；若左子树非空，则左子树上所有结点的值均小于根结点的值； 若右子树非空，则右子树上所有结点的值均大于根结点的值；若右子树非空，则右子树上所有结点的值均大于根结点的值； 左、右子树也为左、右子树也为BSTBST 9.2 9.2 动态查找表动态查找表 78 100 61 90 12 37 24 8 45 53 例如：例如： 9.2 9.2 动态查找表动态查找表 2 2、查找过程为、查找过程为: : (1) (1) 当前当前BSTBST非空时，将给定值非空时，将给定值k k与当前根结点的关键字比较与当前根结点的关键字比较: : (2) (2) 若相等，查找成功，结束若相等，查找成功，结束; ; 若若k k小于当前根结点的关键字，则将左子树作为当前小于当前根结点的关键字，则将左子树作为当前BST;BST; 若若k k大于当前根结点的关键字，则将右子树作为当前大于当前根结点的关键字，则将右子树作为当前BST;BST; (3) (3) 重复重复(1)(1)。 9.2 9.2 动态查找表动态查找表 算法描述为： FUNC bstsrch (t:bitreptr ; k:keytype):bitreptr; 查找不成功时返回NIL IF (t=NIL) COR (t.key=k) THEN RETURN(t) ELSE IF t.key00 插入后平衡因子的绝对值插入后平衡因子的绝对值11 离插入结点最近的失去平衡的祖先结点离插入结点最近的失去平衡的祖先结点 判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡， 判别插入结点后可能失去平衡的最小子树的根结点是否失去平衡， （该结点的平衡因子的绝对值（该结点的平衡因子的绝对值11）; ; 判别旋转类型作相应处理。 判别旋转类型作相应处理。 9.2 9.2 动态查找表动态查找表 1. 1. 4 4、AVLAVL树上插入结点算法树上插入结点算法 2. 2. (1) (1) 算法描述算法描述 查找查找 s s 结点的插入位置过程中，记下离结点的插入位置过程中，记下离s s 最近的，且平衡因子最近的，且平衡因子 不等于不等于0 0的结点，令的结点，令 a a 指向该结点；（即可能失去平衡的最小指向该结点；（即可能失去平衡的最小 子树的根结点）。子树的根结点）。 修改修改 a a 至至 s s 路径上所有结点的平衡因子值；路径上所有结点的平衡因子值； 判别判别a a 结点的平衡因子绝对值是否大于结点的平衡因子绝对值是否大于1 1，若是，作旋转处理，若是，作旋转处理 （2 2） 过程描述过程描述 PROC ins_AVLtree (VAR tPROC ins_AVLtree (VAR t：AVLinktpAVLinktp；：keytypekeytype）；）； 在t为根结点的AVL上插入关键字为K的新结点 new(s)new(s)；sskeykey：=K=K， s slchildlchild：= s= srchildrchild：=NIL=NIL； s sbfbf：=0=0； IF t=NIL THEN t IF t=NIL THEN t：=s =s 插入根结点 ELSE ELSE (1) (1) 查找查找s s 的插入位置的插入位置q,q,同时记下：同时记下：a a及及a a的双亲的双亲f f 从根到叶结点搜索从根到叶结点搜索 f f：=NIL=NIL； a a：=t=t；p p：=t=t；q q：=NIL=NIL； WHILE pNIL DO WHILE pNIL DO IF p IF p bf 0 THEN abf 0 THEN a：=p=p；f f：=q=q； qq是是p p的双亲的双亲, , p p、q q是沿路径移动是沿路径移动, ,a a、f f是跳跃移动是跳跃移动 q q：=p=p； IF s IF skeyp key THEN pkeyp key THEN p：= p = p lchildlchild ELSE p ELSE p：= p = p rchild rchild ； 插入插入ss IF s IF skeyq key THEN q keyq key THEN q lchild lchild ：= s = s ELSE q ELSE q rchildrchild：= s;= s; 9.2 9.2 动态查找表动态查找表 （2 2） 修改修改aa至至s s 路径上的平衡因子路径上的平衡因子 从从a a 到叶到叶 IF sIF skeyakeyakey key THEN pTHEN p：=a=alchild lchild ；b b：=p=p；d d：=1=1 ELSE p ELSE p：=a=archild rchild ；b b：=p=p；d d：=-1=-1； 左子树插入，使左子树深度增左子树插入，使左子树深度增1 1，反之右树深度增，反之右树深度增1 1 WHILE PS DOWHILE PS DO IF s IF skeypkeypkey key THEN p THEN pbfbf：=1=1；p p：= p= plchildlchild ELSE p ELSE pbfbf：=-1=-1； p p：= p= prchild;rchild; 原来从原来从psps的所有结点的叶全部为的所有结点的叶全部为0 0，所以计算方法并不是用定义左深，所以计算方法并不是用定义左深右右 深，方向也不是从下到上深，方向也不是从下到上 9.2 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 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 9.3 哈希查找表哈希查找表 前面介绍的查找算法前面介绍的查找算法, ,有一个共同特点有一个共同特点: :就是以待查关键字就是以待查关键字k k 在表中，通过一系列在表中，通过一系列比较比较来确定该记录在表中来确定该记录在表中的的“ “地址地址” ”。 这一节将介绍另一种通过这一节将介绍另一种通过计算计算来查找的新型方法来查找的新型方法-哈希法哈希法 （HashHash）或称杂凑法、散列法。或称杂凑法、散列法。 设关键字集合为设关键字集合为A A，地址空间为地址空间为D D，哈希法就是在哈希法就是在A A和和D D之之 间建立一种函数关系间建立一种函数关系HH，通过计算函数通过计算函数HH（k k），），就能得到关键就能得到关键 字字KK的地址。的地址。 关键字集关键字集A A m m 地址空间地址空间D D n n 哈希函数哈希函数 HH（k k） 9.3 9.3 哈希查找表哈希查找表 设设D D是长度为是长度为n n的表，的表， A A是含是含mm个记录的关键字集合，个记录的关键字集合， 如果存在一个如果存在一个函数函数HH，使得对使得对A A中任一关键字中任一关键字KK i i ，均有，均有， 0 0HH（ K K i i ） n-1 i=1 n-1 i=1，2 2，mm 同时同时, , KK i i 所标识的记录所标识的记录R R i i 在表在表D D中的地址是中的地址是H(KH(K i i ) )， 则称函数则称函数HH为关键字集合为关键字集合A A到地址空间到地址空间D D之间的哈希函数，之间的哈希函数， 地址空间地址空间D D为哈希表。为哈希表。 哈希函数并不一定是一对一的，例如，当哈希函数并不一定是一对一的，例如，当mmn n时，对任何时，对任何 哈希函数哈希函数HH，至少存在两个关键字至少存在两个关键字KK i i K K j j ，使得使得H(KH(K i i ) = H(K) = H(K j j) ) ，这种对不同关键字而得到同一地址的现象，成为这种对不同关键字而得到同一地址的现象，成为冲突冲突。 9.3 9.3 哈希查找表哈希查找表 因此，在应用哈希查找方法时，主要要解决两个因此，在应用哈希查找方法时，主要要解决两个 技术问题：技术问题： 一是构造好哈希函数的方法一是构造好哈希函数的方法; ; 二是研究解决冲突的方法。二是研究解决冲突的方法。 一一. . 哈希函数构造方法哈希函数构造方法 一个好的哈希函数应满足下列两个条件：一个好的哈希函数应满足下列两个条件： 计算简单容易计算简单容易 冲突极少冲突极少 9.3 9.3 哈希查找表哈希查找表 1 1直接哈希函数直接哈希函数 取关键字本身或关键字的某个线性函数值作为哈希地址，取关键字本身或关键字的某个线性函数值作为哈希地址， 即：即： HH（keykey）=key =key 或或HH（keykey）=a* key+b =a* key+b （a a，b b为常数为常数 ） 例如：有一个解放后出生人口调查表，每个记录包含年份、人例如：有一个解放后出生人口调查表，每个记录包含年份、人 数等数据项，其中年分为关键字，则哈希函数可取为数等数据项，其中年分为关键字，则哈希函数可取为: : HH（keykey）=key +=key +（-1948-1948） 这样就可以方便地存储和查找这样就可以方便地存储和查找19481948年后任一年的记录。年后任一年的记录。 地址地址 年份年份 人数人数 01 1949 22 1970 9.3 9.3 哈希查找表哈希查找表 2 2数字分析法数字分析法 设个位数的关键字，由个不同的符号组成，此个设个位数的关键字，由个不同的符号组成，此个 符号在关键字的各位出现的频率不一定相同，可能在某些位上符号在关键字的各位出现的频率不一定相同，可能在某些位上 均匀分布，即每个符号出现的次数都接近于次，而在另均匀分布，即每个符号出现的次数都接近于次，而在另 一些位上分布不均匀。一些位上分布不均匀。 则选择其中分布均匀的则选择其中分布均匀的s s位作位作为哈希地为哈希地 址，即址，即 HH（keykey）= =“key“key中数字均匀分布的中数字均匀分布的s s位位” ”，这便是数字分这便是数字分 析哈希函数。析哈希函数。 例：由例：由8080个记录，关键字为个记录，关键字为8 8位十进制数，（位十进制数，（n=80n=80，r=10r=10，d=8d=8 ）对关键字的各位进行分析，发现：第对关键字的各位进行分析，发现：第1 1，2 2位都是位都是“8“8，1”1”，第，第3 3 位只取位只取1 1，2 2，3 3或或4 4，第，第8 8位只取位只取2 2，5 5或或7 7，即，即1010个数在这四位分个数在这四位分 布不均匀，不取。可在剩下的布不均匀，不取。可在剩下的4 4，5 5，6 6，7 7位中任取两位，作为位中任取两位，作为 哈希地址。哈希地址。 9.3 9.3 哈希查找表哈希查找表 3 3平方取中法平方取中法 取关键字平方后的中间几位作为哈希地址，即哈希函数为取关键字平方后的中间几位作为哈希地址，即哈希函数为: : HH（keykey）= =“key“key 2 2 的中间几位的中间几位” ” 其中，所取的位数由哈希表的大小确定。其中，所取的位数由哈希表的大小确定。 9.3 9.3 哈希查找表哈希查找表 4 4折叠法折叠法 将关键字分割成位数相等的几部分（最后一部分位数可以 将关键字分割成位数相等的几部分（最后一部分位数可以 不同），取这几部分的叠加和（舍去高位的进位）作为哈希地不同），取这几部分的叠加和（舍去高位的进位）作为哈希地 址。位数由存储地址的位数确定。址。位数由存储地址的位数确定。 相加时有两种方法：相加时有两种方法： 一是移位叠加法，即将每部分得最后一位对齐，然后相加；一是移位叠加法，即将每部分得最后一位对齐，然后相加； 另一种是间界叠加法，即将关键字看作一纸条，从一端向另一另一种是间界叠加法，即将关键字看作一纸条，从一端向另一 端沿间界逐次折叠，然后对齐相加。端沿间界逐次折叠，然后对齐相加。 9.3 9.3 哈希查找表哈希查找表 设关键字设关键字key=dkey=d3 r 3 r d d 2 r+1 2 r+1 d d 2 r2 r d d r+1 r+1d d r r d d 2 2d d1 1 允许的存储地址有允许的存储地址有r r位。位。 则则 移位叠加法为： 移位叠加法为： d d r r d d2 2d d1 1 d d 2 r 2 r d d r+1 r+1 +) +) d d r r d d 2 r+1 2 r+1 S S r r S S2 2S S1 1 9.3 9.3 哈希查找表哈希查找表 5 5除留余数法除留余数法 取关键字被某个不大于哈希表长取关键字被某个不大于哈希表长mm的数的数p p除后的余数为哈希除后的余数为哈希 地址。地址。 即即 HH（keykey）= =keykey MOD p MOD p，pmpm p p的选择很重要，选得不好会产生很多冲突，的选择很重要，选得不好会产生很多冲突， 通常，选择通常，选择 p mp m的某个质数的某个质数。 6 6随机数法随机数法 选择一个随机函数，取关键字的随机函数值作为它的哈希地址。选择一个随机函数，取关键字的随机函数值作为它的哈希地址。 即即 HH（keykey）=random=random（ key key） 9.3 9.3 哈希查找表哈希查找表 二二. . 处理冲突的方法处理冲突的方法 冲突冲突是指由关键字得到的是指由关键字得到的HashHash地址上已有其他记录地址上已有其他记录, , 处理冲突处理冲突就是为该关键字找到另一个就是为该关键字找到另一个“ “空空” ”的的HashHash地址。地址。 1. 1. 开放定址法开放定址法 HH i i = =（HH（keykey）+d+d i i ）mod m i=1mod m i=1，2 2m-1;m-1; 其中其中: : HH i i 为第为第i i次冲突的地址次冲突的地址, , HH（keykey）为为HashHash函数值函数值, , mm 为为HashHash表表长表表长, , d d i i 为增量序列为增量序列 9.3 9.3 哈希查找表哈希查找表 HH i i = =（HH（keykey）+d+d i i ）mod m i=1mod m i=1，2 2m-1;m-1; 其中其中: : d d i i 为增量序列为增量序列, ,有三种取法：有三种取法： d d i i =1=1，2 2，3 3m-1 m-1 称为线性探测再散列称为线性探测再散列 d d i i =1=1 2 2 , -1, -1 2 2 , 2, 2 2 2 , -2, -2 2 2 , 3, 3 2 2 kk 2 2 |k|m-1 |k|m-1 称为二次探测再散列称为二次探测再散列 d d i i = =伪随机序列伪随机序列 称为伪随机探测再散列称为伪随机探测再散列 例：设例：设m=16,m=16,表中已有关键字表中已有关键字, , 分别为：分别为：1919，7070，3333三个记录，三个记录， HashHash函数取为函数取为HH（keykey）= key mod13= key mod13，现第四个关键字为现第四个关键字为1818的记的记 录要填入表中，由录要填入表中，由HashHas