9.1　查找基本概念

查找，又称查询、检索，是在大量的数据中获得我们需要的、满足特定条件的信息或数据。在本书中，查找是指在一组数据集合中找关键字等于给定值的某个元素或记录。

1.查找表

查找表（search table）是由同一类型的数据元素（或记录）构成的集合。因此，它是一种以集合为逻辑结构、以查找为核心的数据结构。

由于集合中的数据元素之间是没有“关系”的，因此查找表的实现就不受“关系”的约束，而是根据实际应用对查找的具体要求去组织查找表，以便实现高效率的查找。

对查找表经常进行的操作有：①查询某个“特定的”数据元素是否在查找表中；②检索某个“特定的”数据元素的各种属性；③在查找表中插入一个数据元素；④从查找表中删去某个数据元素。

若对查找只进行前两种统称为“查找”的操作，则称此类查找表为静态查找表（static search table）。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类表为动态查找表（dynamic search table）。

2.关键字

关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。能唯一确定一个数据元素（或记录）的关键字称为主关键字（primary key）；而不能唯一确定一个数据元素（或记录）的关键字，称为次关键字（secondary key）。

例如，在学生信息查找表中，“学号”可看成学生的主关键字，“姓名”则应视为次关键字。

3.查找

查找是指在含有n个元素的查找表中，找出关键字等于给定值k的数据元素（或记录）。

当要查找的关键字是主关键字时，查找结果是唯一的，一旦找到，称为查找成功，否则称为查找失败。当要查找的关键字是次关键字时，查找结果不唯一，此时需要查遍整个表，或在可以肯定查找失败时，才能结束查找过程。

4.平均查找长度

查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字的比较次数的平均值作为衡量一个查找算法效率优劣的标准，称为平均查找长度（Average Search Length），通常用ASL表示。

对一个含有n个数据元素的查找表，查找成功时：

其中，n是结点的个数；ci是查找第i个数据元素所需要的比较次数；pi是查找第i个数据元素的概率，且，在以后的章节中，若不特别声明，均认为对每个数据元素的查找概率是相等的，即pi＝1／n。

5.数据元素的类型定义

在本章讨论中所涉及的数据元素类型及关键码类型定义如下：