数据结构（C语言版） 高佳琴 第9章 查找.pptVIP

第九章 查找 高佳琴 2014年 2月 7日 本章要点 查找的基本概念与术语 静态查找表的实现和查找算法 二叉排序树的生成和查找方法 哈希表的构造方法和查找过程 各种查找算法在等概率情况下查找成功时平均查找长度的计算 9.1 “电话簿查找”案例导入 随着人们社交面的不断扩大，手机内存储的联系人在不断增加，我们经常需要在上百个甚至于上千个联系人中（如表9-1）找到所需的友人信息，我们可以很快通过汉语简拼等方式定位到需要的联系人。 表9-1 电话簿 9.2 基本概念与术语 查找又称为检索，是指根据给定的某个值，在给定的同一数据类型构成的查找表中确定一个关键字等于给定值的记录或数据元素。 若存在满足条件的记录，则查找成功，否则查找失败。 在查找成功的情况下，查找的结果为整个记录的信息，或指示该记录在查找表中的位置；在查找不成功情况下，此时查找的结果可给出一个“空”记录或“空”指针。 9.2 基本概念与术语 在查找的过程中，我们经常对查找表进行如下的一些操作： (1)查询某个“特定的”数据元素是否在查找表中； (2)检索某个“特定的”数据元素的各种属性； (3)在查找表中插入一个数据元素； (4)从查找表中删去某个数据元素。 查找算法分析：平均查找长度（ASL——Average Search Length）：为确定记录在表中的位置所进行的和关键字比较的次数的期望值，是衡量一个查找算法好坏的依据。 9.3 静态查找 静态查找表是一种最简单的查找表，它可以是基于顺序存储也可以链表存储，本节主要介绍基于顺序表的查找。 9.3.1 顺序查找 【算法思路】 从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败。 【操作步骤】 将查找表数据元素存放在自下标1开始的连续位置，在下标为0的位置存放被查找关键字，比较顺序从后向前，一旦遇到与被查找关键字相等的元素，结束比较过程，返回其所在位置，当返回值为0时，表明查找不成功。 查找值为37的元素过程见表9-2。 表9-2 顺序查找执行过程 9.3.1 顺序查找 【性能分析】 等概率情况下： 顺序查找算法基本工作就是关键字的比较，因此，顺序查找算法的时间复杂度为O(n)。 【小结】 顺序查找的优点是算法简单，对查找表结构无任何要求，无论是用顺序存储还是用链式存储，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当 n 较大时，不宜采用顺序查找，而必须寻求更好的查找方法。 9.3.2 二分查找 【算法思路】 首先将待查找序列分成两半，确定查找数可能在哪一半，在确定的一半序列中再次折半，直到找到该元素，显示查找成功，返回元素位置；若判断元素不存在，则查找失败，给出相应提示。 【操作步骤】 ①设定3个辅助标志：low，high，mid，分别指向待查找区域的下界、上界及中间点。显然有：mid= (low+high)/2 ②运算步骤： (1) low =1,high =11 ,故mid =6 ，待查范围是 [1,11]； (2) a[mid] x，说明x在[ mid+1,high]之间，则令：low =mid+1;重算 mid＝ (low+high)/2?；. (3) 若a[mid] x，说明x在?[low ,mid-1]之间，则令：high =mid–1;重算 mid ； (4)若a[ mid ] =x，说明查找成功，元素序号=mid; ③结束条件： （1）查找成功：a[mid] = x （2）查找不成功： highlow （即区间长度小于0） 9.3.2 二分查找 【性能分析】 二叉树第K层结点的查找次数为k次(根结点为第1层)，而第k层结点数最多为2k-1个。所以折半查找的时间复杂度为O(log2n)。 【小结】 折半查找算法的效率比顺序查找算法高，但折半查找只适用于顺序存储的有序表，对线性链表无法进行折半查找。 9.3.3 分块查找 【算法思路】 先用给定值k在索引表中检测索引项，以确定所要进行的查找在查找表中的查找分块 (由于索引项按关键码字段有序，可用顺序查找或折半查找)，然后，再对该分块进行顺序查找。 【性能分析】 由于分块查找实际上是两次查找过程，故整个查找过程的平均查找长度是两次查找的平均查找长度之和。 9.4 动态查找 动态查找表经常要用表中的记录进行插入、删除等操作，动态查找表的生