第10章 查找电子课件

第10章查找本章讲解查找。理解查找基本概念；掌握各种静态表查找算法；掌握二叉排序树查找算法；了解平衡二叉树查找算法；理解哈希表查找算法；灵活应用查找。过年啦！照年俗，正月初一起床就去包大汤圆煮，在有些大汤圆里面包上小硬币，谁吃到寓意来年发财发大财！难了，摆在我面前的那么多碗，我到底选哪一碗？那一碗里又是哪一个汤圆包了发财硬币的？查找吧！提纲10.1查找基本概念10.2静态表查找10.3动态表查找10.4哈希表查找10.5查找应用10.6查找学习总结10.1查找基本概念定义查找表：被查找的对象。主关键字可以唯一识别。举例：公司每天产生的邮件很多，小王出差办事忙，已经有3天没有时间看邮件了。回来后，同事告诉他公司整体调薪了，具体数据每个人私邮了的。兴奋之余，小王打开邮箱，密密麻麻信件太难找了！还好，有个搜索查找功能，输入时间范围3天前到现在，输入关键字“薪”/“工资”，回车见到了！这个例子说明，查找在我们生活中几乎天天在、无处不在。10.1查找基本概念2.分类按照操作方式分为静态查找表和动态查找表。按照查找是否在内存完成分为内查找和外查找。按照查找是否按照地址查找分为哈希表和非哈希表。10.1查找基本概念3.性能查找的性能主要是由关键字比较次数决定的。关键字平均比较次数也就是平均查找长度（ASL，AverageSearchLength）是作为查找算法效率优劣的依据。10.1查找基本概念求ASL举例，如表10.1所示的查找表和找到关键字时比较的次数。10.2静态表查找静态表在查找时不做插入、删除操作，所以顺序表适合做静态表查找。顺序表查找类SqListSearch描述10.2.1顺序查找举例：大小英语四级考试的考场里，考生就位之后监考老师从座位号1开始逐一检查考试证件，与手上的名单对照，若正确则到下一个，若不正确就找到了问题考生。在这个例子中，按座位号逐一查找是否有问题考生便是顺序查找。10.2.1顺序查找【算法10.1】设计1个算法，对R[0..n-1]进行顺序查找，若找到返回序号，否则返回-1。思路：（1）从顺序表的一端开始依次遍历，将遍历的元素关键字和给定值k相比较，（2）若两者相等，则查找成功，返回该元素的序号。（3）若遍历结束后，仍未找到关键字等于k的元素，则查找失败，返回-1。代码见算法10.110.2.2二分查找在关键字有序序列（2，4，7，9，10，14，18，26，32，40）中采用二分查找方法查找关键字为7的元素。10.2.2二分查找二分查找的性能可以用判定树描述。显然，二分查找的平均性能与判定树的高度h=log2(n+1)有关10.2.2二分查找

10.2.3分块查找举例：每场期末考试考前要在黑板上画出座位号。学生如果从1数到自己座位号找到自己座位，有点糟糕！何不，先确定自己的座位号落在哪一列（区间），再到那一列去找，效率高多了嘛！10.2.3分块查找设查找表为（8，14，6，9，10，22，34，18，19，31，40，38，54，66，46，71，78，68，80，85，100，94，88，96，87），查找关键字为80的元素。10.2.3分块查找

10.2.3分块查找【算法10.4】设计1个算法，在顺序表R[0..n-1]和索引表I[0..b-1]中进行分块查找，若找到返回序号，否则返回-1。思路：（1）根据查找表长度进行分块，由每1块的最大值/最小值构造索引表。（2）对索引表进行顺序/二分查找，找到对应查找表中的分块。（3）对查找表对应的分块中进行顺序查找。代码见算法10.410.3动态表查找动态表在查找时要做插入或删除操作，所以链表树表适合做动态表查找。10.3.1二叉排序树查找左孩子小于根，右孩子大于根显然，对二叉排序树进行中序遍历，序列为有序序列。10.3.1二叉排序树查找二叉排序树节点类BSTNode描述二叉排序树类BST描述10.3.1二叉排序树查找已知1组关键字为（25,18,46,2,53,39,32,4,74,67,60,11），按表中的元素顺序依次插入到1棵初始为空的二叉排序树中，画出该二叉排序树，并求等概率情况下的ASL成功和ASL不成功。10.3.2平衡二叉树查找它首先是棵二叉排序树，然后保持树的高度较小（左右平衡故得名）。有时又叫做AVL树。10.3.2平衡二叉树查找更新AVL树时会打破“平衡”，需要调整为AVL树，有4种调整方式：（1)LL型调整（右旋）（2)RR型调整（左旋）（3)LR型调整（先左旋后右旋）（4)RL型调整（先右旋后左旋）10.3.2平衡二叉树查找（1)LL型调整（右旋）10.3.2平衡二叉树查找（2)RR型调整（左旋）10.3.2平衡二叉树查找（3)LR型调整（先左旋后右旋）10.3.2平衡二叉树查找（4)RL型调整（先右旋后左旋）*10.3.3B-树*10.3.4B+树10.4哈希表查找问题的提出：比较的方式查找，往往与问题规模和元素位置相关，效率低。解决方案：通过元素关键字值进行存储和查找，从而查找效率可以提高。哈希函数可以实现。10.4.1哈希函数哈希函数存储是把关键字映射为内存地址。10.4.1哈希函数举例：上体育课排队，女生前2排男生后2排，从左到右依次由矮到高排。在身高没有变化的情况下，每个同学每次上体育课排队时都能迅速找到自己的位置列队。在这个例子中，身高是关键字值，通过这个值计算出列队位置，也可以查找到该位置的同学。类似的例子还有看电影时通过电影票对号入座。10.4.1哈希函数查找学号为2018007的学生分数：先计算h(2018007)=2018007-2018001=6。再取ha[6]元素的分数76即可。显然利用哈希函数的查找时间复杂度为O(1)。10.4.1哈希函数

10.4.1哈希函数

10.4.1哈希函数（3）数字分析法提取关键字中有差异的那些位作为哈希地址的方法。10.4.2解决冲突方法对于2个不同的关键字ki和kj（i≠j）出现h(ki)=h(kj)，称为哈希冲突（同义词冲突）。发生哈希冲突的概率与装填因子（α=n/m）有关。开放定址法（1）线性探测法迭代公式为：d0=h(k)，di=(di-1+1)modm(1≤i≤m-1)举例：校车上的座位基本坐满，1个老师上车后从车头向车尾方向走，直到找到空位置坐下。在这个例子中，老师找空位置类似线性探测。10.4.2解决冲突方法

10.4.2解决冲突方法

10.4.2解决冲突方法

10.4.2解决冲突方法2.拉链法拉链法是把所有的同义词用单链表链接起来的方法。10.4.2解决冲突的方法

10.4.3哈希表查找性能分析开放定址法性能分析10.4.3哈希表查找性能分析2.拉链法性能分析如图10.28所示，拉链法的ASL成功和ASL不成功计算如下：10.5查找应用【例10.1】设计1个算法，统计1个整数序列中每个整数出现的次数。思路：（1）将整数序列存入1个数组，设置1个TreeMap集合；（2）遍历数组，每次将当前元素添加到集合中，键存储元素值，值存储其出现的次数；（3）若当前元素已经在集合的键中，则将其值加1，否则将其值置1；（4）遍历完成后，输出集合所有“键-值”对元素。代码见应用10.110.5查找应用【例10.2】设计1个算法，按学号递增顺序输出学生的学号和姓名信息。思路：（1）创建1个含学号和姓名属性的学生类Student；（2）Student去实现Comparable接口，重写compareTo()方法，按学号升序排序；（3）构造若干个学生实例对象，将他们添加到1个TreeSet集合中；（4）遍历输出该集合。代码见应用10.210.6查找学习总结顺序查找算法简单，对查找表的存储结构无关，但不适合n很大情形。二分查找之前，需对关键字排序。分块查找中，对索