数据结构JAVA语言描述习题答案(刘小晶等主编)第8章查找(Java版).ppt

1,第八章 查找,教学内容,8.1 查找的基本概念,8.2 静态表查找,8.3 动态表查找,8.4 哈希表查找,教学重点与难点,重点：,掌握查找的基本概念以及各种常见查找方法的实现。,难点：,动态表查找,4/52,，就是在由一组记录组成的集合中寻找主关键字值等于给定值的某个记录，或是寻找属性值符合特定条件的某些记录。,8.1 查找的基本概念,1. 查找,为简单起见，本章所涉及的关键字均指主关键字，且假设关键字的类型为Comparable接口类。,5/52,8.1 查找的基本概念,2. 查找表,是一种以同一类型的记录构成的集合为逻辑结构，以查找为核心运算的数据结构。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,6/52,8.1 查找的基本概念-查找表,根据给定的某个值，在查找表中确 定一个其关键字等于给定值的数据元素 或（记录）的过程。,查找：,若查找表中存在这样一个记录， 则称“查找成功”。查找结果给出整个记 录的信息，或指示该记录在查找表中的 位置；,查找成功:,查找不成功:,若在查找表中不存在这样的 记录，则称“查找不成功”。查找结果 给出“空记录”或“空指针”。,7/52,8.1 查找的基本概念-查找表,对查找表经常进行的操作:,1）建表； 2）查找； 3）读表元； 4）修改（如插入、删除等）。,8/52,8.1 查找的基本概念-查找表,仅作查找和读表元操作的查找表。,静态查找表：,如果在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果在“在查找表中”的数据元素，此类查找表就称为“动态查找表”。,动态查找表：,查找表可分为两类:,需做修改操作的查找表。,9/52,8.1 查找的基本概念,平均查找长度,如何评价查找算法的时间效率？,衡量一个查找算法效率优劣的标准是什么？,10/52,8.1 查找的基本概念,3. 平均查找长度(Average Search Length),为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值 其中: n 为表中记录个数，Pi 为查找表中第i个记录的概率，且 ， Ci为找到该记录时，曾和给定值比较过的关键字的个数。,11/52,8.1 查找的基本概念,如何进行查找？,查找的方法取决于查找表的结构,12,1. 顺序查找,2. 二分查找,3. 分块查找,静态查找表上的几种查找方法,8.2 静态查找表,静态查找表的存储结构,顺序存储和链式存储，本节都以顺序存储为例,13,8.2 静态查找表,待排序的顺序表记录类描述如下:(P242) public class RecordNode private Comparable key; /关键字 private Object element; /数据元素 ,14,8.2 静态查找表,public class SeqList private RecordNode r; /顺序表记录结点数组 private int curlen; /顺序表长度，即记录个数 / 构造方法:构造一个存储空间容量为maxSize的顺序表 public SeqList (int maxSize) this.r = new RecordNodemaxSize; / 为顺序表分配maxSize个存储单元 this.curlen = 0; / 置顺序表的当前长度为0 ,15,从顺序表的一端开始，依次将每一个数据元素的关键字值与给定值key进行比较，若某个数据元素的关键字值等于给定值key，则表明查找成功；若直到所有数据元素都比较完毕，仍找不到关键字值为key的数据元素，则表明查找失败。,在表中按顺序进行的查找叫顺序查找。,思想：,8.2.1 顺序查找,16,回顾顺序表的查找过程：,假设给定值 key=64,要求 ri.getKey() .compareTo(key)=0, 问: i= ?,8.2.1 顺序查找,17,public int seqSearch (Comparable key) int i = 0, n = length(); while (i n ,8.2.1 顺序查找,P275 算法8.1,改进此算法？,18,r,i,r,i,60,key=64,key=60,64,8.2.1 顺序查找-带监视哨,19,public int seqSearchWithGuard (Comparable key) int i = length(); r0.setKey(key); /哨兵 while ( ri.getKey().compareTo(key) != 0) i-; if (i0) return i; else return -1; ,P276 算法8.2,8.2.1 顺序查找-带监视哨,20,在等概率查找的情况下， 顺序表查找的平均查找长度为：,对顺序表而言，Ci = n-i+1 (带哨兵),ASL = P1 +2P2 + +(n-2)Pn-1+nPn（不带哨兵）,分析顺序查找的时间性能,8.2.1 顺序查找,21,上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。,若以有序表表示静态查找表，则查找过程可以基于“折半”（“二分”）进行。,8.2.2 二分查找（折半查找）,22,要求：查找表是按关键字从小到大排序好的有序顺序表。,思想：取出表中的中间元素，若其关键字值为key，则查找成功，算法结束；否则以中间元素为分界点，将查找表分成两个子表，并判断所查的key值所在的子表是前部分，还是后部分，再重复上述步骤直到找到关键字值为key的元素或子表长度为0。,8.2.2 二分查找,23,例如: key=64 的查找过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2,8.2.2 二分查找,24,public int binarySearch (Comparable key) if (length()0) int low=0; high = length()-1; while(low0) high=mid-1; else low=mid-1; return -1 ; ,P277 算法8.3,8.2.2 二分查找-算法,25,8.2.2 二分查找-性能分析,先看一个具体的情况，假设：n=11,判定树,1,2,2,3,3,3,3,4,4,4,4,思考题： 画出对表长为12，关键字序列为（，）的有序表进行折半查找的判定树。并求出其在等概率时查找成功和查找不成功的平均查找长度。,26,8.2.2 二分查找-性能分析,先看一个具体的情况，假设：n=11,判定树,1,2,2,3,3,3,3,4,4,4,4,27,假设 n=2k-1 并且查找概率相等，则 在n50时，可得近似结果,8.2.2 二分查找-性能分析,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,28,23 47 0 5 12,3 6 9 12 4 15 23 14 17 18 31 25 27 47 38,索引表,最大关键字,起始地址,8.2.3 分块查找,29,1）由索引确定记录所在块（区间）；,2）在顺序表的某个块内进行查找。,注意：索引表可以根据查找表的特点来构造。,可见，索引顺序查找的过程也是一个 “缩小区间”的查找过程。（分块查找）,索引顺序表的查找过程：,8.2.3 分块查找,30,索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度,注：索引表是有序表，而块内的记 录无序的。索引查找的性能介 于顺序查找和折半查找之间。,8.2.3 分块查找,31,一、二叉排序树（二叉查找树）,二、平衡二叉树,三、B - 树,四、B+树,五、红黑树,8.3 动态查找表,32,8.3.1 二叉排序树（或称二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,33,（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；,二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉 排序树。,（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；,8.3.1 二叉排序树-定义,34,例如:,是二叉排序树。,66,不,8.3.1 二叉排序树-定义,35,通常，取二叉链表作为二叉排序树的存储结构,二叉树结点类P156： public class BiTreeNode private RecordNode data; private BiTreeNode lchild, rchild; ,8.3.1 二叉排序树,36,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,若二叉排序树为空，则查找不成功；否则：,8.3.1 二叉排序树-查找算法,37,例如:,二叉排序树,查找关键字,= 50 ,35 ,90 ,95,8.3.1 二叉排序树-查找算法,38,从上述查找过程可见，,在查找过程中，生成了一条查找路径：,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,8.3.1 二叉排序树-查找算法,39,Object searchBST(BiTreeNode p, Comparable key) /在二叉排序树中查找关键字值为key的结点，若查找成功，则返回结点值；否则返回null if (p != null) if (pareTo(RecordNode)p.getData().getKey() = 0) /查找成功 return p.getData(); if (pareTo(RecordNode) p.getData().getKey() 0) return searchBST( p.getLchild() , key); /在左子树中查找 else return searchBST( p.getRchild() , key); /在右子树中查找 ,8.3.1 二叉排序树-查找算法,40,设 key = 48,25,8.3.1 二叉排序树-查找算法,41,根据动态查找表的定义，“插入”操作在查找不成功时才进行；,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点。,8.3.1 二叉排序树-插入算法,42,public boolean insertBST(Comparable key,Object theElement) if (key = null | !(key instanceof Comparable)/不能插入空对象或不可比较大小的对象 return false; if (root = null) root = new BiTreeNode(new RecordNode(key,theElement); /建立根结点 return true; return insertBST(root, key,theElement); ,8.3.1 二叉排序树-插入算法（P282算法8.5),43,/将关键字值为key，数据元素为theElement的结点插入到以p为根的二叉排序树中的递归算法 private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) if (pareTo(RecordNode) p.getData().getKey() = 0) return false; if (pareTo(RecordNode) p.getData().getKey() 0) if (p.getLchild() = null) /若p的左子树为空 p.setLchild(new BiTreeNode(new RecordNode(key, theElement); /建立叶子结点作为p的左孩子 return true; else /若p的左子树非空 return insertBST(p.getLchild(), key, theElement); else if (p.getRchild() = null) /若p的右子树为空 p.setRchild(new BiTreeNode(new RecordNode(key, theElement); /建立叶子结点作为p的右孩子 return true; else /若p的右子树非空 return insertBST(p.getRchild(), key, theElement); /插入到p的右子树中 ,8.3.1 二叉排序树-插入算法（P283算法8.5),44,（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。,可分三种情况讨论：,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。,8.3.1 二叉排序树-删除算法,45,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,46,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树 或者只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,47,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,以其中序遍历序列下的前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,48,/二叉排序树中删除一个结点算法。若删除成功，则返回被删除结点值；否则返回null public Object removeBST(Comparable key) if (root = null | key = null | !(key instanceof Comparable) return null; /在以root为根的二叉排序树中删除关键字值为Key的结点 return removeBST(root,key,null); ,8.3.1 二叉排序树-删除算法（P285算法8.6),49,/二叉排序树中删除一个结点算法。若删除成功，则返回被删除结点值；否则返回null public Object removeBST(Comparable key) if (root = null | key = null | !(key instanceof Comparable) return null; /在以root为根的二叉排序树中删除关键字值为Key的结点 return removeBST(root,key,null); ,8.3.1 二叉排序树-删除算法（P285算法8.6),见P285算法8.6,50,8.3.2 平衡二叉树,何谓“平衡二叉树”？,平衡二叉树的查找性能分析,如何构造“平衡二叉树”,51,平衡二叉树（AVL树）：,它或者是一棵空树，或者是具有下列性质的二叉树；它的左子树或右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。,平衡因子：,该结点的左子树的深度减去它右子树的 深度。,平衡二叉树上所有结点的平衡因子只 可能是-1、0、1。,8.3.2 平衡二叉树-定义,52,二叉平衡树是二叉排序树的另一种形式，其特点为：,树中每个结点的左、右子树深度之差的绝对值不大于1,例如:,5,4,8,2,5,4,8,2,1,是平衡树,不是平衡树,8.3.2 平衡二叉树-定义,53,构造二叉平衡（查找）树的方法是： 在插入过程中，采用平衡旋转技术。,1、右旋(LL型)：,8.3.2 平衡二叉树-构造,54,2、先左后右(LR型)：,8.3.2 平衡二叉树-构造,55,插入结点,3、左旋(RR型)：,8.3.2 平衡二叉树-构造,56,4、先右后左(RL型)：,8.3.2 平衡二叉树-构造,57,例如:以关键字5，4，2，8，6，9构造一 棵平衡二叉树。,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转 一次,先向右旋转 再向左旋转,8.3.2 平衡二叉树-构造,58,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字 9,8.3.2 平衡二叉树-构造,59,在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。,8.3.2 平衡二叉树-查找性能分析,在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log2(n) 相当。,60,一、哈希表的定义,二、常用的哈希函数,三、处理冲突的方法,四、哈希表的查找和性能分析,8.4 哈希表查找,61,以上两节讨论的表示查找表的各种结构的共同特点：,查找的过程:,查找的效率:,为给定值按某种顺序和记录集合中各个关键字进行比较的一个过程,记录在表中的位置和它的关键字之间不存在一个确定的关系,取决于和给定值进行比较的关键字个数。,8.4.1 哈希表的定义,62,用这类方法表示的查找表，其平均查找长度都不为零。,不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。,8.4.1 哈希表的定义,63,只有一个办法：预先知道所查关键字在表中的位置，,对于频繁使用的查找表，希望 ASL = 0。,即，要求：记录在表中位置和其关键字之间存在一种确定的关系。,8.4.1 哈希表的定义,64,若以下标为000 999 的有序表表示之。,例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份)。,则查找过程可以简单进行：取给定值（学号）的后三位，直接可确定学生记录在查找表中的位置,不需要经过比较.,8.4.1 哈希表的定义,65,即:记录在表中的位置为关键字的某个 函数值H(key) ，通常称这个函数 H(key) 为哈希函数。,所以如能：,8.4.1 哈希表的定义,66,Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei,例如：对于如下 9 个关键字,设 哈希函数 f(key) = (Ord(第一个字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题: 若添加关键字 Zhou , 怎么办？,字符的次序函数,8.4.1 哈希表的定义,67,1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上；,从这个例子可见：,由于哈希函数是一个压缩映象，因 此，在一般情况下，很容易产生“冲突”现象，即： key1 key2， 而 f(key1) = f(key2)。,8.4.1 哈希表的定义,68,3) 很难找到一个不产生冲突的哈希函数。一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表” 时,除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。,8.4.1 哈希表的定义,69,根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,8.4.1 哈希表的定义,70,所以，要构造哈希表则要解决两个主要问题：,1、如何构造哈希函数 2、如何解决冲突,8.4.1 哈希表的定义,71,对数字的关键字可有下列构造方法：,若是非数字关键字，则需先对其进行数字化处理。,2. 直接定址法,4. 平方取中法,1.除留余数法,5. 折叠法,6. 随机数法,3. 数字分析法,8.4.2 常用的哈希函数,72,1. 除留余数法,设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数 或是 不含20 以下的质因子,73,若取 p=9, 则他们对应的哈希函数值将为： 3, 3, 0, 6, 6, 3,例如：给定一组关键字为：12, 39, 18, 24, 33, 21,为什么要对 p 加限制？,可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。,74,哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b,2. 直接定址法,此法仅适合于： 地址集合的大小 = = 关键字集合的大小,75,3. 数字分析法,假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,76,如：关键字是7位十进制数,8106354 8112321 8103317 8105342 8108378 8101335,取出,H（k) 654 221 317 542 878 135,此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。,77,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。,4. 平方取中法,此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。,78,将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。,5. 折叠法,此方法适合于: 关键字的数字位数特别多。,79,如：Key=81 675 436 假设哈希表的长度为小于1000,436,675,81,1192,H(key)=192,移位叠加,436,576,81,1093,H(key)=093,间界叠加,（按低位对齐）,（按高位与低位对齐）,80,6.随机数法,设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,81,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。,8.4.2 常用的哈希函数,82,“处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址。,1. 开放定址法,2. 链地址法,8.4.3 处理冲突的方法,*3. 公共溢出区法,*4. 再哈希法,83,为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, , Hs 1 sm-1 其中：H0 = H(key) Hi = ( H(key) + di ) % m i=1, 2, , s,8.4.2 处理冲突的方法-开放地址法,84,对增量 di 有三种取法：,1) 线性探测法 di = 1,2,k (k=m-1) 2) 二次探测法 di = 12, -12, 22, -22, , 3) 双哈希函数探测法 Hi=(H(key)+i*RH(key)%m (i=1,2,m-1),8.4.2 处理冲突的方法-开放地址法,85,即：产生的 Hi 均不相同，且所产生的 s(m-1)个 Hi 值能覆盖哈希表中所有 地址。则要求：,注意：增量 di 应具有“完备性”, 双哈希探测时的 m 和 di 没有公因子。, 二次探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, 等）；,8.4.2 处理冲突的方法-开放地址法,86,例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),19,01,23,14,55,68,若采用线性探测再散列处理冲突,11,82,36,1 1 2 1 3 6 2 5 1 查找次数,ASL(成功）=,ASL(不成功）=,（4*1+2*2+3+5+6）/9=22/9,（10+9+1+1）/11=56/11,8.4.2 处理冲突的方法-开放地址法,87,19,01,23,14,68,若采用二次探测再散列处理冲突,55,11,82,36,例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),ASL(成功）=,1 1 2 1 2 1 4 1 3,（1*5+2*1+3+4）/9=14/9,8.4.2 处理冲突的方法-开放地址法,88,因 m=11，则可设 H2(key)=(3 *key) % 10+1,19,01,23,14,55,68,11,82,36,2 1 1 1 2 1 2 1 3,若采用再哈希法处理冲突,例如: 关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 ,设定哈希函数 H(key) = key MOD 11 ( 表长=11 ),8.4.2 处理冲突的方法-开放地址法,89,将所有哈希地址相同的记录 都链接在同一链表中。,ASL成功=(1 6 +22+3)/9=13/9,例如:同前例的关键字，哈希函数设为 H(key)=key MOD 7,ASL不成功=(14 +2 + 3)/7=9/7,8.4.2 处理冲突的方法-链地址法,90,基本思想是：除基本的存储区(称为基本表)之外，另建一个公共溢出区(称为溢出表)，当不发生冲突时，数据元素可存入基本表中；当发生冲突时，不管哈希地址是什么，数据元素都存入溢出表。查找时，对给定值K通过哈希函数计算出哈希地址i，先与基本表对应的存储单元相比较，若相等，则查找成功；否则，再到溢出表中进行查找。,8.4.2 处理冲突的方法-公共溢出法,91,主要思想是：当发生冲突时，再用另一个哈希函数来得到一个新的哈希地址，若再发生冲突，则再使用另一个函数，直至不发生冲突为止。 预先需要设置一个哈希函数的序列： Hi=RHi(key) (i=1,2,k)。,8.4.2 处理冲突的方法-再哈希法,92,8.4.4 哈希表的查找及其分析,哈希表的查找,哈希表查找性能的分析,93,查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为：,对于给定值 K， 计算哈希地址 i = H(K),若 ri = NULL 则查找不成功,若 ri.key = K 则查找成功,否则 “求下一地址 Hi” ，直至 rHi = NULL (查找不成功) 或 rHi.key = K (查找成功) 为止。,哈希表的查找,94,1) 选用的哈希函数； 2) 选用的处理冲突的方法； 3) 哈希表饱和的程度，装载因子 =n/m 值的大小（n记录数，m表的长度）,决定