数据结构与算法基础课件章节7

第7章查找7.1查找的基本概念1．查找在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找是数据结构的一种基本操作，查找的效率决定了计算机某些应用系统的效率。查找算法依赖于数据结构，不同的数据结构需要采用不同的查找算法。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。2．查找表用于查找的数据集合称为查找表，它由同一类型的数据元素或记录组成，可以是一个数组或者链表等数据类型。在查找表中常做的操作有4种：①查询某个特定的数据元素是否在查找表中；②检索满足条件的某个特定的数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删除某个数据元素。查找表可分为静态查找表和动态查找表两种。静态查找表是指对表的操作中不包括对表的修改的表；动态查找表是指对表的操作中包括对表中的记录进行插入或删除操作的表。适合静态查找表的查找方法有顺序查找、二分查找、散列查找等。适合动态查找表的查找方法有排序二叉树的查找、散列查找等。

7.2顺序查找和二分查找7.2.1顺序查找顺序查找是一种最直观的查找方法，其基本思想就是从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表的位置，否则返回查找失败的信息。顺序查找的算法如下：

7.2.2二分查找二分查找算法（binarysearchalgorithm）是一种在有序数组中查找某一特定元素的搜索算法，又称折半查找。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。二分查找的算法如下：例如已知有一有序列{5,8,13,17,20,28,33,44,49,51,53}，在该序列中查找元素8的过程如图所示。

7.3散列表7.3.1散列表的基本概念散列表（Hashtable，也叫哈希表），是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，记为Hash(key)=Addr。散列函数可能会把两个或两个以上的不同的关键字映射到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。所以在设计散列表时，一方面，设计合适的散列函数来尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方式。理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素的个数无关。7.3.2散列表的构造方法散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快定位。在构造散列函数时，需要遵循以下几点原则：①散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。②散列函数计算出来的地址应该能够等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。③散列函数应尽量简单，能够在较短的时间内计算出任一关键字对应的散列地址。下面介绍几种常用的散列函数

3．数字分析法

分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。这种方法适用于已知的关键字集合，但如果更换了关键字，则需要重新构造新的散列函数。4．平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

2．拉链法（Chaining）

为了避免非同义词产生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一表示，结构上类似于邻接表。拉链法适用于经常进行插入和删除的情况。例如有一关键字序列为{43,63,75,23,39,24,12,78,62,84,93,3}，散列函数为H(key)=key%13，使用拉链法来处理冲突，建立的表如图所示。7.3.4散列表的查找效率

散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和填装因子。散列表的填装因子定义为：α=填入表中的元素个数/散列表的长度

α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。对于开放定址法，填装因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中（cachemissing）按照指数曲线上升。因此