第7章查找技术.ppt

《第7章查找技术.ppt》由会员分享，可在线阅读，更多相关《第7章查找技术.ppt（93页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第 7 章 查找技术,本章的主要内容是:,查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术,查找的基本概念,关键码：可以标识一个记录的某个数据项。 键值：关键码的值。主关键码：可以唯一地标识一个记录的关键码。次关键码：不能唯一地标识一个记录的关键码。,7.1 概述,查找的基本概念,查找 ：在具有相同类型的记录构成的集合中找出满足给定条件的记录。,7.1 概述,查找的结果 ：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。,静态查找 ：不涉及插入和删除操作的查找 。动态查找 ：涉及插入和删除操作的查找。,7.1 概述,查找的基本概念,静态查找适用于：查找集合

2、一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作；动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。,7.1 概述,查找的基本概念,查找结构 ：面向查找操作的数据结构 ，即查找基于的数据结构。,集合中元素之间不存在明显的组织规律，不便查找。,本章讨论的查找结构 ：线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。树表：适用于动态查找，主要采用二叉排序树的查找技术。散列表：静态查找和动态查找均适用，主要采用散列技术。,7.1 概述,查找结构 ：面向查

3、找操作的数据结构 ，即查找基于的数据结构。,查找的基本概念,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,算法；问题规模；待查关键码在查找集合中的位置；查找频率。,7.1 概述,查找频率与算法无关，取决于具体应用。通常假设pi是已知的。,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,查找算法的时间复杂度是问题规模n和待查关键码在查找集合中的位置k的函数，记为T(n，k)。,7.1 概述,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：,其中：n：问题规模，查找集合中的记录个数； pi：查找第i个记录的概率； ci：查找第

4、i个记录所需的关键码的比较次数。,结论：ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。,7.1 概述,查找算法的性能,顺序查找 （线性查找）,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,7.2 线性表的查找技术,例：查找k35,顺序查找 （线性查找）,7.2 线性表的查找技术,int SeqSearch1(int r

5、, int n, int k)/数组r1 rn存放查找集合 i=n; while (i0 ,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找k35,哨兵,35,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6

6、 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例：查找k25,25,int SeqSearch2(int r , int n, int k) /数组r1 rn存放查找集合 r0=k; i=n; while (ri!=k) i -; return i;,7.2 线性表的查找技术,改进的顺序查找,平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。,7.2 线性表的查找技术,顺序查找的缺点：,算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接存储均可；对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。,顺序查找的优点：,折半查找,使用

7、条件：线性表中的记录必须按关键码有序；必须采用顺序存储。,基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。,7.2 线性表的查找技术,折半查找的基本思想,7.2 线性表的查找技术,例：查找值为14的记录的过程：,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3114,1814,7

8、22,1822,21high,int BinSearch1(int r , int n, int k)/数组r1 rn存放查找集合 low=1; high=n; while (lowrmid) low=mid+1; else return mid; return 0;,7.2 线性表的查找技术,折半查找非递归算法,int BinSearch2(int r , int low, int high, int k)/数组r1 rn存放查找集合 if (lowhigh) return 0; else mid=(low+high)/2; if (krmid) return BinSearch2(r, m

9、id+1, high, k); else return mid; ,7.2 线性表的查找技术,折半查找递归算法,折半查找判定树,判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。,7.2 线性表的查找技术, 当n=0时，折半查找判定树为空； 当n0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树，根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,7.2 线性表的查找技术,判

10、定树的构造方法,7.2 线性表的查找技术,判定树的构造方法,具有n个结点的折半查找判定树的深度为,查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。,查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。,7.2 线性表的查找技术,折半查找性能分析,二叉排序树,二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于根

11、结点的值； 它的左右子树也都是二叉排序树。,7.3 树表的查找技术,二叉排序树的定义采用的是递归方法。,二叉排序树 非二叉排序树,二叉排序树,7.3 树表的查找技术,中序遍历二叉排序树可以得到一个按关键码有序的序列,二叉排序树的存储结构,以二叉链表形式存储，类声明如下：,class BiSortTree public: BiSortTree(int a , int n); BiSortTree( ); void InsertBST(BiNode *root , BiNode *s); void DeleteBST(BiNode *p, BiNode *f ); BiNode *SearchBS

12、T(BiNode *root, int k); private: BiNode *root; ;,7.3 树表的查找技术,二叉排序树的插入,分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,7.3 树表的查找技术,void InsertBST(BiNode *root , BiNode *s);,例：插入值为98的结点,7.3 树表的查找技术,63,55,90,58,70,55,63,root,90,58,70,98,s,root,void BiSortTree:InsertBST(BiNode *root, BiNode

13、 *s) if (root=NULL) root=s; else if (s-datadata) InsertBST(root-lchild, s); else InsertBST(root-rchild, s);,7.3 树表的查找技术,二叉排序树的插入算法,二叉排序树的构造,从空的二叉排序树开始，依次插入一个个结点 。,例：关键码集合为63，90，70，55，58，二叉排序树的构造过程为：,7.3 树表的查找技术,63,BiSortTree:BiSortTree(int r , int n) for (i=0; i; s-data=ri; s-lchild=s-rchild=NULL; I

14、nsertBST(root, s); ,7.3 树表的查找技术,二叉排序树的构造算法,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;每次插入的新结点都是二叉排序树上新的叶子结点;找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；在左子树/右子树的查找过程与在整棵树上查找过程相同；新插入的结点没有破坏原有结点之间的关系。,小 结：,7.3 树表的查找技术,二叉排序树的删除,在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。,分三种情况讨论：被删除的结点是叶子；被删除的结点只有左子树或者只有右子树；被删除的结点既有左子树，也有右子树。,7.3 树表的查找技术,情况1被删

15、除的结点是叶子结点,7.3 树表的查找技术,操作：将双亲结点中相应指针域的值改为空。,情况2被删除的结点只有左子树或者只有右子树,操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,50,30,20,90,85,88,40,35,32,情况3被删除的结点既有左子树也有右子树,操作：以其前驱（左子树中的最大值）替代之，然后再删除该前驱结点。,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,40,30,20,80,90,85,88,35,32,1. 若结点p是叶

16、子，则直接删除结点p；2. 若结点p只有左子树，则只需重接p的左子树； 若结点p只有右子树，则只需重接p的右子树； 3. 若结点p的左右子树均不空，则 3.1 查找结点p的右子树上的最左下结点s及其双亲结点par； 3.2 将结点s数据域替换到被删结点p的数据域； 3.3 若结点p的右孩子无左子树， 则将s的右子树接到par的右子树上； 否则，将s的右子树接到结点par的左子树上； 3.4 删除结点s；,7.3 树表的查找技术,二叉排序树的删除算法伪代码,二叉排序树的查找,在二叉排序树中查找给定值k的过程是：, 若root是空树，则查找失败； 若kroot-data，则查找成功；否则 若kro

17、ot-data，则在root的左子树上查找；否则 在root的右子树上查找。 上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。二叉排序树的查找效率在于只需查找二个子树之一。,7.3 树表的查找技术,例：在二叉排序树中查找关键字值为35，95的过程：,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,二叉排序树的查找,50,30,20,80,90,85,88,40,35,32,BiNode *BiSortTree:SearchBST(BiNode *root, int k) if (root=NULL) return NULL；

18、 else if (root-data=k) return root; else if (kdata) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k);,7.3 树表的查找技术,二叉排序树的查找,二叉排序树的查找性能分析,由序列3, 1, 2, 5, 4得到二叉排序树：,由序列1, 2, 3, 4, 5得到二叉排序树：,ASL =（1+2+3+4+5）/ 5= 3,ASL =（1+2+3+2+3）/ 5 = 2.2,二叉排序树的查找性能取决于二叉排序树的形状，在O(log2n)和O(n)之间。,7.

19、3 树表的查找技术,平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树： 根结点的左子树和右子树的深度最多相差1; 根结点的左子树和右子树也都是平衡二叉树。,平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。,平衡二叉树,7.3 树表的查找技术,7.3 散列表的查找技术,平衡二叉树,在平衡树中，结点的平衡因子可以是1，0，-1。,结点的平衡因子HL-HR,最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。,7.3 树表的查找技术,4,平衡二叉树,基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检

20、查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。,7.3 树表的查找技术,平衡二叉树,例：设序列20，35，40，15，30，25 ，构造平衡树。,20,7.3 树表的查找技术,例：设序列20，35，40，15，30，25 ，构造平衡树。,7.3 树表的查找技术,30,设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况： 1. LL型 2. RR型 3. LR型 4. RL型,7.3 树表的查找技术,平衡二叉树,插入前 插入后，调整前 调整后,7.

21、3 树表的查找技术,平衡二叉树LL型,旋转：扁担原理；冲突：旋转优先,12,例:LL型,7.3 树表的查找技术,平衡二叉树RR型,7.3 树表的查找技术,插入前 插入后，调整前 调整后,插入后，调整前 先顺时针旋转 再逆时针旋转,7.3 树表的查找技术,平衡二叉树LR型,插入后，调整前 先顺时针旋转 再逆时针旋转,7.3 树表的查找技术,平衡二叉树RL型,课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树,7.3 树表的查找技术,课堂练习：设有关键码序列5, 4, 2, 8, 6, 9，构造平衡树,7.3 树表的查找技术,7.3 树表的查找技术,课堂练习：设有关键码序列5,

22、4, 2, 8, 6, 9，构造平衡树,7.3 散列表的查找技术,顺序查找、折半查找、二叉排序树查找等。这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。,在存储位置和关键码之间建立一个确定的对应关系,概 述,散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。,7.3 散列表的查找技术,关键码集合,ki,ri,H(ki),H,散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。,概 述,7.3 散列表的查找技术,关键码集合,ki,r

23、i,H(ki),H,散列函数：将关键码映射为散列表中适当存储位置的函数。,概 述,7.3 散列表的查找技术,关键码集合,ki,ri,H(ki),H,散列函数,散列地址：由散列函数所得的存储位置址 。,概 述,7.3 散列表的查找技术,关键码集合,ki,ri,H(ki),H,散列函数,散列地址,概 述,7.3 散列表的查找技术,散列既是一种查找技术，也是一种存储技术。,散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。,散列技术一般不适用于允许多个记录有同样关键码的情况。散列方法也不适用于范围查找，换言之，在散列表中，我们不可能找到最大或最

24、小关键码的记录，也不可能找到在某一范围内的记录。散列技术最适合回答的问题是：如果有的话，哪个记录的关键码等于待查值。,概 述,7.3 散列表的查找技术,散列技术的关键问题： 散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。 冲突的处理。如何采取合适的处理冲突方法来解决冲突。,7.3 散列表的查找技术,概 述,冲突：对于两个不同关键码kikj，有H(ki)H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。,7.3 散列表的查找技术,概 述,关键码集合,ki,ri,H(ki),kj,H(kj),散列函数,7.3 散列表的查找技术,设计散列函数一般应

25、遵循以下原则： 计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。 函数值即散列地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。,散列函数直接定址法,散列函数是关键码的线性函数，即：,H(key) = a key + b （a，b为常数）,例：关键码集合为10, 30, 50, 70, 80, 90，选取的散列函数为H(key)=key/10，则散列表为：,10,30,50,70,80,90,适用情况？,事先知道关键码，关键码集合不是很大且连续性较好。,7.3 散列表的查找技术,散列函数为：,H(key)=key mod p,7.3 散列表的查

26、找技术,散列函数除留余数法,如何选取合适的 p，产生较少同义词？,例： p 2137,7.3 散列表的查找技术,散列函数除留余数法,一般情况下，选p为小于或等于表长（最好接近表长）的最小素数或不包含小于20质因子的合数。,除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。,适用情况？,根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。,例：关键码为8位十进制数，散列地址为2位十进制数,8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8

27、 1 3 3 8 9 6 7, ,7.3 散列表的查找技术,散列函数数字分析法,适用情况:,能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。,7.3 散列表的查找技术,散列函数数字分析法,对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。,7.3 散列表的查找技术,散列函数平方取中法,事先不知道关键码的分布且关键码的位数不是很大。,适用情况:,例：散列地址为2位，则关键码123的散列地址为：,(1234)21522756,将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。,7.3 散列表的查找技术,散列函数

28、折叠法,例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。,2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位叠加,2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间界叠加,适用情况:,关键码位数很多，事先不知道关键码的分布。,处理冲突的方法开放定址法,由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。,如何寻找下一个空的散列地址?,7.3 散列表的查找技术,（1）线性探测法（2）二次探测法（3）随机探测法,线性探测法,当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。,对于键值key，设H(k

29、ey)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为： Hi=(H(key)di) % m （di=1，2，m-1）,7.3 散列表的查找技术,用开放定址法处理冲突得到的散列表叫闭散列表。,例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散列表表长为11，散列函数为H(key)=key mod 11，用线性探测法处理冲突，则散列表为：,47,7,29,11,16,92,29,22,22,8,8,3,3,3,3,堆积：在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。,7.3 散列表的查找技术,线性探测法,在线性探测法构造的散列

30、表中查找算法伪代码,1. 计算散列地址j;2. 若htj=k，则查找成功，返回记录在散列表中的下标； 否则3. 若htj为空或将散列表探测一遍，则查找失败，转4； 否则，j指向下一单元，转2；4. 若整个散列表探测一遍，则表满，抛出溢出异常； 否则，将待查值插入；,7.3 散列表的查找技术,int HashSearch1(int ht , int m, int k) j=H(k); if (htj=k) return j; /没有发生冲突，比较一次查找成功 i=(j+1) % m; while (hti!=Empty /查找不成功时插入,7.3 散列表的查找技术,在线性探测法构造的散列表中查找

31、算法C+描述,二次探测法,当发生冲突时，寻找下一个散列地址的公式为： Hi=(H(key)di)% m（di=12，12，22，22，q2，q2且qm/2）,7.3 散列表的查找技术,47,7,29,11,16,92,29,22,22,8,8,3,3,3,例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散列表表长为11，散列函数为H(key)=key mod 11，用二次探测法处理冲突，则散列表为：,二次探测法,7.3 散列表的查找技术,随机探测法,当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为： Hi=(H(key)+di)

32、% m （di是一个随机数列，i=1，2，m-1）,7.3 散列表的查找技术,基本思想：将所有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指针。,用拉链法处理冲突构造的散列表叫做开散列表。,设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为n / m。,7.3 散列表的查找技术,处理冲突的方法拉链法（链地址法）,例：关键码集合 47, 7, 29, 11, 16, 92, 22, 8, 3，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造的开散列表为：,7.3 散列表的查找技术,在拉链法构造的散列

33、表查找算法伪代码,1. 计算散列地址j； 2. 在第j个同义词子表中顺序查找； 3. 若查找成功，则返回结点的地址； 否则，将待查记录插在第j个同义词子表的表头。,7.3 散列表的查找技术,Node *HashSearch2(Node *ht , int m, int k) j=H(k); p=htj; while (p ,7.3 散列表的查找技术,在拉链法构造的散列表查找算法C+描述,基本思想：散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比较，若相等，则查找成功；否则，再到溢

34、出表中进行顺序查找。,7.3 散列表的查找技术,处理冲突的方法公共溢出区,例：关键码集合 47, 7, 29, 11, 16, 92, 22, 8, 3，散列函数为H(key)=key mod 11，用公共溢出区法处理冲突，构造的散列表为：,7.3 散列表的查找技术,0 1 2 3 4 5 6 7 8 910,基本表 溢出表,0 1 2 3 4 5 6 7 8 910,散列查找的性能分析,由于冲突的存在，产生冲突后的查找仍然是给定值与关键码进行比较的过程。在查找过程中，关键码的比较次数取决于产生冲突的概率。而影响冲突产生的因素有：（1）散列函数是否均匀（2）处理冲突的方法（3）散列表的装载因子 =表中填入的记录数/表的长度,7.3 散列表的查找技术,查找成功时,查找不成功时,ASL,处理冲突方法,几种不同处理冲突方法的平均查找长度,7.3 散列表的查找技术,开散列表与闭散列表的比较,7.3 散列表的查找技术,本课程选用 主教材王红梅.数据结构（C版）.清华大学出版社本课程辅导及实验教材王红梅.数据结构学习辅导与实验指导.清华大学出版社本课程课件在课程教材所自带课件基础上，根据大纲需要进行修改。,关于教材及课件,