《c++数据结构(第2版)课件第7章 查找技术》由会员分享，可在线阅读，更多相关《c++数据结构(第2版)课件第7章 查找技术（90页珍藏版）》请在金锄头文库上搜索。
1、第 7 章 查找技术,本章的主要内容是:,查找的基本概念 线性表的查找技术 树表的查找技术 散列表的查找技术,查找的基本概念,关键码：可以标识一个记录的某个数据项。 键值：关键码的值。 主关键码：可以唯一地标识一个记录的关键码。 次关键码：不能唯一地标识一个记录的关键码。,7.1 概述,查找的基本概念,查找 ：在具有相同类型的记录构成的集合中找出满足给定条件的记录。 给定的查找条件可能是多种多样的，为便于讨论，把查找条件限制为“匹配”，即查找关键码等于给定值的记录。,7.1 概述,查找的结果 ：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。,静态查找 ：不涉及插入和
2、删除操作的查找 。 动态查找 ：涉及插入和删除操作的查找。,7.1 概述,查找的基本概念,静态查找适用于：查找集合一经生成，便只对其进行查找，而不进行插入和删除操作，或经过一段时间的查找之后，集中地进行插入和删除等修改操作； 动态查找适用于：查找与插入和删除操作在同一个阶段进行，例如当查找成功时，要删除查找到的记录，当查找不成功时，要插入被查找的记录。,7.1 概述,查找的基本概念,查找结构 ：面向查找操作的数据结构 ，即查找基于的数据结构。,集合中元素之间不存在明显的组织规律，不便查找。,本章讨论的查找结构 ： 线性表：适用于静态查找，主要采用顺序查找技术和折半查找技术。 树表：适用于动态查
3、找，主要采用二叉排序树的查找技术。 散列表：静态查找和动态查找均适用，主要采用散列技术。,7.1 概述,查找结构 ：面向查找操作的数据结构 ，即查找基于的数据结构。,查找的基本概念,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,7.1 概述,关键码的比较次数与哪些因素有关呢？,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度，即：,其中：n：问题规模，查找集合中的记录个数； pi：查找第i个记录的概率； ci：查找第i个记录所需的关键码的比较次数。,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,7.1 概述,关键码的比较次数与哪些因素
4、有关呢？,平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度，即：,ci取决于算法；pi与算法无关，取决于具体应用。如果pi是已知的，则平均查找长度只是问题规模的函数。,顺序查找 （线性查找）,基本思想：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。,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 SeqSe
5、arch1(int r , int n, int k) /数组r1 rn存放查找集合 i = n; while (i 0 ,基本思想：设置“哨兵”。哨兵就是待查值，将它放在查找方向的尽头处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。,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 线性表的查找技术,改进
6、的顺序查找,10 15 24 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 3
8、8 42 46 49 52,3114,1814,714,14=14,7.2 线性表的查找技术,例：查找值为22的记录的过程：,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,3122,1822,2322,2122,7.2 线性表的查找技术,lowhigh,int BinSearch1(int r , int n, int k) /数组r1 rn存放查找集合 low = 1; high = n; while (low rmid) low = mid + 1; else return mid; return
9、 0; ,7.2 线性表的查找技术,折半查找非递归算法,int BinSearch2(int r , int low, int high, int k) /数组r1 rn存放查找集合 if (low high) return 0; else mid = (low + high) / 2; if (k rmid) return BinSearch2(r, mid+1, high, k); else return mid; ,7.2 线性表的查找技术,折半查找递归算法,折半查找判定树,判定树：折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常
10、称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。,7.2 线性表的查找技术, 当n=0时，折半查找判定树为空； 当n0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树，根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,7.2 线性表的查找技术,判定树的构造方法,7.2 线性表的查找技术,判定树的构造方法,具有n个结点的折半查找判定树的深度为,查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。,查找不成功：
11、查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数。,7.2 线性表的查找技术,折半查找性能分析,二叉排序树,二叉排序树（也称二叉查找树）：或者是一棵空的二叉树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于根结点的值； 它的左右子树也都是二叉排序树。,7.3 树表的查找技术,二叉排序树的定义采用的是递归方法。,二叉排序树 非二叉排序树,二叉排序树,7.3 树表的查找技术,中序遍历二叉排序树可以得到一个按关键码有序的序列,二叉排序树的存储结构,以二
12、叉链表形式存储，类声明如下：,class BiSortTree public: BiSortTree(int a , int n); BiSortTree( ); void InsertBST(BiNode *root , BiNode *s); void DeleteBST(BiNode *p, BiNode *f ); BiNode *SearchBST(BiNode *root, int k); private: BiNode *root; ;,7.3 树表的查找技术,二叉排序树的插入,分析：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位
13、置由查找过程得到。,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 *s) if (root = NULL) root = s; else if (s-data data) InsertBST(root-lchild, s); else InsertBST(root-rchild, s); ,7.3 树表的
14、查找技术,二叉排序树的插入算法,二叉排序树的构造,从空的二叉排序树开始，依次插入一个个结点 。,例：关键码集合为 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; InsertBST(root, s); ,7.3 树表的查找技术,二叉排序树的构造算法,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列; 每次插入的新结点都是二叉排序树上新的叶子结点; 找到插入位置后
15、，不必移动其它结点，仅需修改某个结点的指针； 在左子树/右子树的查找过程与在整棵树上查找过程相同； 新插入的结点没有破坏原有结点之间的关系。,小 结：,7.3 树表的查找技术,二叉排序树的删除,在二叉排序树上删除某个结点之后，仍然保持二叉排序树的特性。,分三种情况讨论： 被删除的结点是叶子； 被删除的结点只有左子树或者只有右子树； 被删除的结点既有左子树，也有右子树。,7.3 树表的查找技术,情况1被删除的结点是叶子结点,7.3 树表的查找技术,操作：将双亲结点中相应指针域的值改为空。,情况2被删除的结点只有左子树或者只有右子树,操作：将双亲结点的相应指针域的值指向被删除结点的左子树（或右子树）。,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,
