C#讲义第6章 查找.ppt

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

2、找表、查找、读取表元，以及对表做修改操作（如插入、删除元素）等等。,2020年9月18日,2. 关键码 关键码是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素。,2020年9月18日,3. 查找 查找：是指在含有n个元素的查找表中，找出关键码等于给定值kx的数据元素（或记录）。,2020年9月18日,4. 静态查找 动态查找 若对查找表的查找过程不包括对表的修改操作，则此类查找称为静态查找，若在查找的同时插入表中不存在的数据元素，或从查找表中删除已存在的指定元素，则此类查找称为动态查找。,2020年9月18日,5平均查找长度-衡量查找效率的指标 由于查找运算的主要操作是关键字的

3、比较，所以，通常把查找过程中对关键字的比较次数的平均值作为衡量一个查找算法效率优劣的标准，称之为平均查找长度（Average Search Length），通常用ASL表示。,2020年9月18日,6.2线性表查找,在本节中，定义线性查找表的顺序存储结构如下： #define MAXNUM datatype dataMAXNUM； /*查找表存储空间*/ int n；/*查找表中元素的个数*/,2020年9月18日,线性查找表链式存储其结点结构类型定义如下： typedef struct node datatype data； /* 元素的数据域 */ struct node *next； /

4、* 下一个元素的指针域 */ LSNode, *LSTable；,2020年9月18日,6.2.1 顺序查找,顺序查找又称线性查找，是最基本的查找方法之一。 其查找方法为：从表的一端开始，向另一端逐个按给定值kx与关键码进行比较，若找到，查找成功，并给出数据元素在表中的位置；若整个表检测完，仍未找到与kx相同的关键码，则查找失败，给出失败信息。,2020年9月18日,1顺序表上的查找 象顺序表一样，查找表中的数据元素依次顺序存储。顺序查找简单，很容易按下列算法7-1(a)方法实现。,2020年9月18日,2020年9月18日,时间性能： 则查找成功时，顺序查找的平均查找长度为：,设每个数据元素

5、的查找概率相等，则等概率情况下有：,2020年9月18日,2单链表上的查找 设查找表组织为带头结点的单链表，在单链表上的顺序查找算法如下。,2020年9月18日,讨论以下4种方法： 1折半查找 *2 插值查找 *3斐波那契查找 4分块查找,6.2.2 在顺序存储的有序表上查找,2020年9月18日,1折半查找 条件：查找表按关键码有序且顺序存储。 【例6-1】顺序存储的有序表关键码排列如下，做折半查找。 7，14，18，21，23，29，31，35，38，42，46，49，52,2020年9月18日,2020年9月18日,【例6-1】顺序存储的有序表关键码排列如下，做折半查找。 7，14，18

6、，21，23，29，31，35，38，42，46，49，52,图7-2 例7-1描述折半查找过程的判定树,折半查找的时间效率为O(log2n) 。,2020年9月18日,2. 插值查找：,使用条件：顺序存储且按关键码有序且均匀分布。 时间性能： O(log2n),插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布。 以下式取中间点：,2020年9月18日,3. 斐波纳契查找,按斐波纳契数列将有序的查找便分割成两个不等的区间： 若表长n=F(k)-1,分割点为：mid=F(k-1)-1,使用条件：顺序存储且关键码有序。 时间性能： O(log2n),2020年9月

7、18日,4分块查找 若查找表中的数据元素的关键字是按块有序的，则可以做分块查找。分块查找又称索引顺序查找，是对顺序查找的一种改进。,2020年9月18日,树表查找是将查找表按照某种规律建构成树型结构。因为建构的树型结构是按某种规律建立的，因此查找过程也遵循这种规律，可以获得较高的查找效率。,6.3 树表的查找,2020年9月18日,1.二叉排序树定义,6.3.1 二叉排序树,特点：中序遍历序列关键码有序。,2020年9月18日,以二叉链表作为二叉排序树的存储结构，二叉链表结点的类型定义如下： typedef struct bistnode datatype data; struct bistn

8、ode *lchild, *rchild; BiSTNode, *BiSTree;,2020年9月18日,2020年9月18日,2020年9月18日,3二叉排序树中插入一个结点 设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因此，新插入结点一定是作为叶子结点添加上去的。,2020年9月18日,2020年9月18日,4构造一棵二叉排序树 按照读入的关键码序列，构造一棵二叉排序树的算法如下：,2020年9月18日,【例6-3】记录的关键码序列为：63,90,70,55,67,42,98,83,1

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

10、日,删除p结点后，有2种调整方法： 直接令p结点的右孩子pl为f相应的子树，将p的原左子树PL作为以pl为根的子树中序遍历的第一个结点 pr的左子树；如图9-7(a)。,图9-7(a) 按方法进行调整的图示,2020年9月18日,令*p结点的中序直接后继PR(或中序直接前驱)替换*p结点，再按单支结点的(2)的方法删去PR。,图9.8所示 以*p结点的直接后继PR替换*p。,2020年9月18日,2020年9月18日,如何使二叉排序树的查找效率提高？ 如查找表中的关键码顺序为： 63,90,70,55,67,42,98,83,10,45,58 和顺序为： 10,42,45,55,58 63,6

11、7,70,83,90,98的情况，组织的二叉排序树大不相同。,2020年9月18日,*6.3.2 平衡二叉树（AVL）树 1平衡二叉树的定义,a.非平衡二叉树,b. 平衡二叉树,2020年9月18日,对该子树进行平衡化调整归纳起来有以下四种情况：,(1)在某结点左孩子的左子树上插入结点使该结点失衡（LL）； (2)在某结点右孩子的右子树上插入结点使某结点失衡（RR）； (3)在某结点左孩子的右子树上插入结点使某结点失衡（LR）； (4)在某结点右孩子的左子树上插入结点使某结点失衡（RL）。,2020年9月18日,对于平衡二叉树的定义如下： typedef struct avlnode data

12、type data; /*数据元素*/ int bf; /*平衡因子*/ struct avlnode *lchild,*rchild;/*左右孩子指针*/ AVLNode, *AVLTree;,2020年9月18日,(1)LL型：做右单旋转调整,a.插入前,b.插入后，调整前,c.调整后,2020年9月18日,2020年9月18日,(2)RR型：做左单旋转调整,a.插入前,b.插入后，调整前,c.调整后,2020年9月18日,2020年9月18日,(3)LR型：做先左后右双向旋转调整,2020年9月18日,1型： a.插入后，调整前 b.先左旋转 c.再右旋转,2020年9月18日,2型：

13、d.插入后调整前 e.先左旋转 f.再右旋转,调整策略：无论将结点x插入到c的左子树还是右子树，只要使得c的高度增加，调整的方法都是一样的。先对以b为根的子树进行RR型调整，然后再对以a为根的树进行LL型调整。,2020年9月18日,2020年9月18日,(4) RL型：做先右后左双向旋转 这种失衡是因为在失衡结点的右孩子的左子树上插入结点造成的。,调整策略：无论将结点x插入到c的左子树还是右子树，只要使得c的高度增加，调整的方法相同。先对以b为根的子树进行LL型调整，然后再对以a为根的树进行RR型调整。调整后的二叉树如图(c),a.插入后，调整前 b.先右旋转 c.再左旋转,2020年9月1

14、8日,2020年9月18日,【例6-4】已知长度为11的表： 20,12,6,28,16,36,32,10,2,30,8。请按表中元素的顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。,2020年9月18日,因此，含有n个结点得平衡树的最大深度为：,故：在平衡树上进行查找的时间复杂度近似为： (log2n),可证明：当h0时Nh=Fh+2-1,而Fk约等于：,其中：,则Nh约等于：,2020年9月18日,6.3.3 B树和B树 B树是一种平衡的多路查找树，它在文件系统中很有用，是大型数据库文件的一种组织结构。数据库文件是同类型记录的值的集合，是存储在外存储器上的数据结

15、构。因此，在数据库文件中按关键码查找记录，对数据库文件进行记录的插入和删除，就要对外存进行读、写操作。由于外存读、写较慢，因而在对大的数据库文件进行操作时，为了减少外存的读、写次数，应按关键码对其建立索引，即组织成索引文件。,2020年9月18日,1、B树的定义 定义：一棵m阶的B树，或者为空树，或为满足下列特性的m叉树： 树中每个结点至多有m棵子树； 若根结点不是叶子结点，则至少有两棵子树； 除根结点之外的所有非终端结点至少有m/2 棵子树；,2020年9月18日,所有的非终端结点中包含以下信息数据： （n，A0，K1，A1，K2，Kn，An） 其中： m/2 1nm 1 ，n为关键码的个数

16、。 Ki（i=1,2,n）为关键码，且KiKi+1； 所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。,2020年9月18日,下图所示为一棵5阶的B树，其深度为4。,2020年9月18日,2、B树的查找过程,2020年9月18日,2020年9月18日,3、B树的插入 在B树上插入关键码与在二叉排序树上插入结点不同，关键码的插入不是在叶结点上进行的，而是在最底层的某个非终端结点中添加一个关键码。添加分两种情况：,(1)若添加后，结点上关键码个数小于等于m-1，则插入结束； (2)若添加后，该结点上关键码个数为m个

17、，因而使该结点的子树超过了m棵，这与B树定义不符，所以要进行调整，即结点的“分裂”。,2020年9月18日,【例6-5】按以下关键码序列, 建立一棵5阶B树。 20,54,69,84,71,30,78,25,93,41,7,76,51,66,68,53,3,79,35,12,15,65 ,(3) 插入71，索引项达到5，则分裂成三部分：20,54，69和71,84，并将69上升到该结点的父结点中，如图6-21 (c)。,(c),(1) 向空树中插入20，得图6-21 (a)。,(2) 插入54,69,84，得图6-21 (b)。,建立过程：,2020年9月18日,(4) 插入30,78,25,

18、93得图6-21 (d)。,(d),(5) 插41又分裂，得图6-21 (e)。,(e),2020年9月18日,(6) 7直接插入。 (7) 76插入，分裂，得图6-21 (f)。,(8) 51,66直接插入，当插入68后，需分裂，得图6-21 (g)。,(g),(f),2020年9月18日,(9) 53,3,79,35直接插入，到12插入时，需分裂，当中间关键码12插入父结点时，又需要分裂，则54上升为新根。 (10)15,65直接插入得图6-21 (h)。,84,(g),2020年9月18日,5. B+树 B+树是应文件系统所需而产生的一种B树的变形树。一棵m阶的B+树和m阶的B树的差异在

19、于： 有n棵子树的结点中含有n个关键码； 所有的叶子结点中包含了全部关键码的信息，及指向含有这些关键码记录的指针，且叶子结点本身依关键码的大小自小而大的顺序链接。 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键码。,2020年9月18日,一棵5阶二叉树,例如下图是一棵五阶的B+树，通常在B+树上有两个头指针，一个指向根结点，另一个指向关键码最小的叶子结点 。因此，可以对B+树进行两种查找运算：一种是从最小关键码起顺序查找，另一种是根结点开始，进行随机查找。,2020年9月18日,6.4 散列表查找,散列是一种存储策略，散列表也叫哈希（hash）表、杂凑表，是基

20、于散列存储策略建立的查找表。,2020年9月18日,6.4.1 散列表 哈希表、哈希方法、哈希函数：,2020年9月18日,【例6-6】11个元素的查找表其关键码分别为： 18,27,1,20,22,6,10,13,41,15,25 选取关键码与元素位置间的函数为：f(key)=key mod 11,(2)查找时，对给定值kx依然通过这个函数计算出地址，再将kx与该地址单元中元素的关键码比较，若相等，查找成功。,(1) 通过这个函数对11个元素建立查找表如下：,2020年9月18日,冲突 对于n个数据元素的集合，总能找到关键码与存放地址一一对应的函数。 如若最大关键码为m，可以分配m个数据元素

21、存放单元，选取函数f(key)=key即可，但这样会造成存储空间的很大浪费，甚至不可能分配这么大的存储空间。 通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突，映射到同一哈希地址上的关键码称为同义词。 可以说，冲突不可能避免，只能尽可能减少。,2020年9月18日,哈希方法需要解决以下两个问题： 1. 构造好的哈希函数 （1）所选函数尽可能简单，以便提高转换速度。 （2）所选函数对关键码计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。 2. 制定解决冲突的方案,2020年9月18日,6.4.2 常用的哈希函数

22、1. 直接定址法(线性函数) Hash(key)=akey+b (a、b为常数) 即取关键码的某个线性函数值为哈希地址，这类函数是一一对应函数，不会产生冲突，但要求地址空间与关键码涉及到的地址空间大小相同，因此，对于较大的关键码分布范围大的不适用。,【例6-7】关键码集合为100，300，500，700，800，900， 选取哈希函数为 Hash(key)=key/100，则存放如下：,2020年9月18日,2. 除留余数法 Hash(key)=key mod p (p是一个整数) 即取关键码除以p的余数作为哈希地址。使用除留余数法，选取合适的p很重要，若哈希表表长为m，则要求pm，且接近m或

23、等于m。 p一般选取=m的最大质数。,2020年9月18日,3、乘余取整法,（A、B均为常数，且0A1，B为整数),一般较为理想取是：,。,2020年9月18日,4、 数字分析法 设关键码集合中，每个关键码均由m位组成，每位上可能有r种不同的符号。,2020年9月18日,例：有一组关键码如下：,2020年9月18日,5、平方取中法 对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。 6、折叠法(Folding) 此方法将关键码自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。这种方法称为折叠法。 有两种叠加方法： (1)

24、 移位法 将各部分的最后一位对齐相加。 (2) 间界叠加法 从一端向另一端沿各部分分界来回折叠后，最后一位对齐相加。,2020年9月18日,【例】关键码为 key=05326248725，设哈希表长为三位数，则可对关键码每三位一部分来分割。 关键码分割为如下四组： 253 463 587 05 用上述方法计算哈希地址:,Hash(key)=254间界叠加法,对于位数很多的关键码，且每一位上符号分布较均匀时，可采用此方法求得哈希地址 。,2020年9月18日,1. 开放定址法 开放定址法解决冲突的思想是：由关键码得到的散列地址一旦产生了冲突，也就是说该地址已经存放了数据元素，就按照一个探测序列去

25、寻找下一个空的散列地址空间，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。 用开放定址法解决冲突建立的散列表也叫闭散列表。 闭散列表的存储结构一般采用具有m个数据元素空间的向量。,6.4.3 处理冲突的方法及散列表的构造,2020年9月18日,形成探测序列的方法有很多种，下面介绍3种： (1) 线性探测法 发生冲突后的探测序列为： Hi=(Hash(key)+di) mod m ( 1i m ) 其中： Hash(key)为哈希函数 m为哈希表长度 di 为增量序列 1,2,m-1，且di=I Hash(key)+1、Hash(key)+2、,2020年9月18日,【例6-8】关键

26、码集为：47,7,29,11,16,92,22,8,3， 设哈希表表长为11，哈希函数用Hash(key)=key mod 11，用线性探测法处理冲突，构建哈希表。 首先求得各个哈希地址：,2020年9月18日,求其平均查找长度： 对关键码为47、7、11、16、92的查找只需1次比较，对关键码为29、8、22的查找需2次比较，对关键码3的查找需4次比较，故平均查找长度为： WPL=(15+23+41)/8=15/9,2020年9月18日,堆积问题的产生： 线性探测法可能使第i个哈希地址的同义词存入第i+1个哈希地址。 这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，因此

27、，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。 为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。,2020年9月18日,(2) 二次探测法 发生冲突后的探测序列为： Hi=(Hash(key)di) mod m di 为增量序列 12,-12,22,-22, q2,-q2,【例6-9】用二次探测法处理冲突构建【例7-9】关键码集的哈希表。,2020年9月18日,对关键码寻找空的哈希地址只有3这个关键码与上例不同， Hash(3)=3，哈希地址上冲突，由于： H1=(Hash(3)+12) mod 11=4 仍然冲突； H2=(Hash(3)-12) mo

28、d 11=2 找到空的哈希地址，存入。,其平均查找长度： 对关键码为47、7、11、16、92的查找只需1次比较，对关键码为29、8、22的查找需2次比较，对关键码3的查找需3次比较，故平均查找长度为： ASL=(15+23+31)/9=14/9,2020年9月18日,(3) 双哈希函数探测法 Hi=(Hash(key)+i*ReHash(key)mod m (i=1,2,m-1) 其中：Hash(key)，ReHash(key)是两个哈希函数， m为哈希表长度,双哈希函数探测法：先用第一个函数Hash(key)对关键码计算哈希地址，一旦产生地址冲突，再用第二个函数ReHash(key)确定移

29、动的步长因子，最后，通过步长因子序列由探测函数寻找空的哈希地址。 比如，Hash(key)=a时产生地址冲突，就计算ReHash(key)=b，则探测的地址序列为： H1=(a+b) mod m，H2=(a+2b) mod m， Hm-1=(a+(m-1)b) mod m,开放地址法介绍的三种方法只是形成探测序列的规则不同而已。,2020年9月18日,2020年9月18日,2. 拉链法 (1) 拉链法解决冲突的思想 将同义词结点拉成一个链表，将各链表的头指针按散列地址顺序存储在一个向量中。 用拉链法解决冲突建立的散列表也叫开散列表。,2020年9月18日,【例6-10】关键码序列为47,7,29,11,16,92,22,8,3,50,37,89, 94,21，哈希函数为 Hash(key)=key mod 11，建散列表。,拉链法处理冲突时的哈希表 （向链表中插入元素均在表头进行）,2020年9月18日,思考： 查找成功的情况： ASL=? 不成功的情况： ASL=？,2020年9月18日,(2)存储结构： typedef struct hnode datatype data; /*关键字*/ /*其它信息*/ struct hnode *next; /*指向下一个同义词的指针*/ HNode; 定义散列