第6章 查找技术

《第6章 查找技术》由会员分享，可在线阅读，更多相关《第6章 查找技术（59页珍藏版）》请在金锄头文库上搜索。

1、第6章 查找技术,2019年10月18日,教学内容： 查找的基本概念、线性表查找 、树结构查找、散列表查找 教学目的： 理解查找的基本思想； 掌握查找表的几种组织及查找方法。 教学重点： 查找表的基本概念及查找原理； 查找表的几种组织及查找方法。 教学难点： 查找表的不同组织及查找方法,2019年10月18日,6.1 引言 1. 查找表 (1) 查找表是一种以集合为逻辑结构、以查找为核心的数据结构。 (2) 由于集合中的数据元素之间是没有“关系”的，因此在查找表的实现时就不受“关系”的约束，而是根据实际应用对查找的具体要求去组织查找表，以便实现高效率的查找。 (3) 对查找表中常做的运算有：建

2、立查找表、查找、读取表元，以及对表做修改操作（如插入、删除元素）等等。 2. 关键码 关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素。 能唯一确定一个数据元素的关键码，称为主关键码。 不能唯一确定一个数据元素的关键码，称为次关键码。 3. 查找 查找：是指在含有n个元素的查找表中，找出关键码等于给定值kx的数据元素（或记录）。,2019年10月18日,4. 静态查找 动态查找 简言之，静态查找仅对查找表进行查找操作，而不能改变查找表本身；动态查找除了对查找表进行查找操作外，还可以向表中插入数据元素或删除表中数据元素。 5平均查找长度-衡量查找效率的指标,2019年10月

3、18日,6数据元素类型定义 本章讨论中，涉及到的数据元素类型及关键码类型定义如下： public class DataType KeyType key; / 关键码字段 / 其他信息 ;,2019年10月18日,6.2 线性表查找,线性表查找属于静态查找，是将查找表视为一个线性表，将其顺序或链式存储，再进行查找，因此查找思想较为简单，效率不高。,2019年10月18日,1顺序表上的查找,2019年10月18日,时间性能： 对于n个数据元素的表，给定值kx与表中第i个元素关键码相等，即定位第i个记录时，需进行n-i+1次关键码比较，即Ci=n-i+1 。 则查找成功时，顺序查找的平均查找长度为：

4、,查找不成功时，关键码的比较次数总是 n+1 次。 算法中的基本工作就是关键码的比较，因此，查找长度的量级就是查找算法的时间复杂度，其为O(n)。,设每个数据元素的查找概率相等，则等概率情况下有：,2019年10月18日,1折半查找 条件：查找表按关键码有序且顺序存储。 【例6-1】顺序存储的有序表关键码排列如下，做折半查找。 7，14，18，21，23，29，31，35，38，42，46，49，52,7.2.2 在顺序存储的有序表上查找,2019年10月18日,查找关键码为14的过程,2019年10月18日,查找关键码为22的过程,2019年10月18日,2019年10月18日,描述折半查找

5、过程的判定树,折半查找的时间效率为O(log2n) 。,2019年10月18日,2. 插值查找：,使用条件：顺序存储且按关键码有序且均匀分布。 时间性能： O(log2n),插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布。 以下式取中间点：,2019年10月18日,3. 斐波纳契查找,按斐波纳契数列将有序的查找便分割成两个不等的区间： 若表长n=F(k)-1,分割点为：mid=F(k-1)-1,使用条件：顺序存储且关键码有序。 时间性能： O(log2n),2019年10月18日,1.二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵空

6、树；或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于根结点的值；若右子树不空，则右子树上所有结点的值均大于根结点的值。 左右子树也都是二叉排序树。,6.3.1 二叉排序树,特点：中序遍历序列关键码有序。,6.3 树结构查找,2019年10月18日,2.二叉排序树中的查找,2019年10月18日,2019年10月18日,3二叉排序树中插入一个结点,2019年10月18日,63,(1),(6),(3),(4),(5),(2),(8),(7),(9),4构造一棵二叉排序树 【例6-2】记录的关键码序列为： 63,90,70,55,67,42,98,83,10,45,58，则构

7、造一棵二叉排序树的过程如下：,2019年10月18日,从空树开始建立二叉排序树的过程,(10),(11),(9),2019年10月18日,2019年10月18日,5二叉排序树中删除一个结点 从二叉排序树中删除一个结点之后，使其仍能保持二叉排序树的特性即可。 设待删结点为p（p为指向待删结点的指针），其双亲结点为f，以下分三种情况进行讨论。,(1)p结点为叶结点。,F,2019年10月18日,(2)p结点只有右子树pR 或只有左子树pL。 只需将pR或pL替换f结点的p子树即可。,f,2019年10月18日,(3)p结点既有左子树PL又有右子树PR，可按中序遍历保持有序进行调整。 设删除p结点前

8、，中序遍历序列为： ,PL子树,p,pr ,SR子树,pj ,SJ子树, p2,S2子树,p1,S1子树， 。 则删除p结点后，中序遍历序列应为： ,PL子树,pr ,SR子树,pj ,SJ子树, p2,S2子树,p1,S1子树， 。,2019年10月18日,删除p结点后，有2种调整方法： 直接令p结点的右孩子pl为f相应的子树，将p的原左子树PL作为以pl为根的子树中序遍历的第一个结点 pr的左子树；如图 9-7(a)。,图9-7(a) 按方法进行调整的图示,2019年10月18日, 令*p结点的中序直接后继PR(或中序直接前驱)替换*p结点，再按单支结点的(2)的方法删去PR。,图9.8所

9、示 以*p结点的直接后继PR替换*p。,2019年10月18日,2019年10月18日,6.3.2 平衡二叉树（AVL）树 1平衡二叉树的定义 结点的平衡因子：其左子树高度-右子树高度。,a.非平衡二叉树,b. 平衡二叉树,2019年10月18日,(1)LL型：做右单旋转调整,a.插入前,b.插入后，调整前,c.调整后,调整策略：对失衡的子树做右旋转，即将结点c做为新的根结点，结点a作为结点c的右孩子，a的右子树B不变，将c的右子树D做为a的左子树，c的左子树E不变。调整后的二叉树如上图 c所示。各平衡且仍是排序树。,2019年10月18日,2019年10月18日,(2)RR型：做左单旋转调整

10、,a.插入前,b.插入后，调整前,c.调整后,【调整策略】 调整策略：对失衡的子树做左旋转，即将结点c做为新的根结点，结点a作为结点c的左孩子，a的左子树B不变，将c的左子树D做为a的右子树，c的右子树E不变。调整后的二叉树如上图c所示。各平衡且仍是排序树。,2019年10月18日,2019年10月18日,(3)LR型：做先左后右双向旋转调整,右图为插入前的子树，根结点a的左子树比右子树高度高1，待插入结点x将插入到结点b的右子树上，并使结点b的右子树高度增1，从而使结点a的平衡因子的绝对值大于1，导致结点a为根的子树平衡被破坏。,2019年10月18日,1型： a.插入后，调整前 b.先左旋

11、转 c.再右旋转,2019年10月18日,2型： d.插入后调整前 e.先左旋转 f.再右旋转,调整策略：无论将结点x插入到c的左子树还是右子树，只要使得c的高度增加，调整的方法都是一样的。先对以b为根的子树进行RR型调整，然后再对以a为根的树进行LL型调整。,2019年10月18日,2019年10月18日,(4) RL型：做先右后左双向旋转 这种失衡是因为在失衡结点的右孩子的左子树上插入结点造成的。,a.插入后，调整前 b.先右旋转 c.再左旋转,2019年10月18日,2019年10月18日,6.4 散列表查找,散列是一种存储策略，散列表也叫哈希（hash）表、杂凑表，是基于散列存储策略建

12、立的查找表。基本思想是确定一个函数，求得每个关键码相应的函数值并以此作为存储地址，直接将该数据元素存入到相应的地址空间去，因此它的查找效率很高。,2019年10月18日,6.4.1 散列表 哈希表、哈希方法、哈希函数： 按照一定规则确定关键码的某个函数f(key)，依该函数求得每个数据元素关键码的函数值，依此函数值作为该元素的存储位置，并按此存放在查找表中，按这个思想构造的查找表称为散列表(哈希表)。 查找时，由同一个函数对给定值kx计算地址，将kx与计算出的地址单元中数据元素的关键码进行比较，确定查找是否成功，这就是哈希方法(散列法)。 散列方法中使用的转换函数称为散列函数(哈希函数)。,6

13、.4 散列表查找,2019年10月18日,【例6-4】11个元素的查找表其关键码分别为： 18,27,1,20,22,6,10,13,41,15,25 选取关键码与元素位置间的函数为：f(key)=key mod 11,(2)查找时，对给定值kx依然通过这个函数计算出地址，再将kx与该地址单元中元素的关键码比较，若相等，查找成功。,(1) 通过这个函数对11个元素建立查找表如下：,2019年10月18日,哈希方法需要解决以下两个问题： 1. 构造好的哈希函数 （1）所选函数尽可能简单，以便提高转换速度。 （2）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 2.

14、制定解决冲突的方案,2019年10月18日,6.4.2 常用的哈希函数 1. 直接定址法(线性函数) Hash(key)=akey+b (a、b为常数) 即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址空间与关键码涉及到的地址空间大小相同，因此，对于较大的关键码分布范围大的不适用。,2019年10月18日,2. 除留余数法 Hash(key)=key mod p (p是一个整数) 即取关键码除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求pm，且接近m或等于m。 p一般选取=m的最大质数。,2019年10月18日,3、

15、乘余取整法,（A、B均为常数，且0A1，B为整数),以关键码key乘以A，取其小数部分(A*key mod 1就是取A*key的小数部分)，之后再用整数B乘以这个值，取结果的整数部分作为哈希地址。 该方法B取什么值并不关键，但A的选择却很重要，最佳的选择依赖于关键码集合的特征。有实验表明，一般较为理想取是：,。,2019年10月18日,4、 数字分析法 设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。 5、平方取中法 对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。 6、折叠法(Folding) 此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，

16、然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。 有两种叠加方法： (1) 移位法 将各部分的最后一位对齐相加。 (2) 间界叠加法 从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。,2019年10月18日,1. 开放定址法 开放定址法解决冲突的思想是：由关键码得到的散列地址一旦产生了冲突，也就是说该地址已经存放了数据元素，就按照一个探测序列去寻找下一个空的散列地址空间，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。,6.4.3 处理冲突的方法及散列表的构造,形成探测序列的方法有很多种，下面介绍3种： (1) 线性探测法 发生冲突后的探测序列为： Hi=(Hash(key)+di) mod m ( 1i m ) 其中： Hash(key)为哈希函