查找

基本概念

• 查找表：由同一类型的数据元素构成的集合。由于集合中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵活的数据结构，可以利用其它数据结构来实现，例如，线性表、树表以及散列表等。
• 关键字：数据元素某个数据项的值，这个值可以被用于标识一个数据元素（或记录）。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）。反之，称用以识别若干记录的关键字为次关键字。
• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录。若表中存在这样的一个记录，则称查找成功，此时查找的结果可给出整个记录的信息，或记录在表中的位置；若表中不存在这样的记录，则称查找不成功，此时查找的结果可给出一个“空”记录或“空”指针。
• 动态查找表和静态查找表：在查找的同时对表做修改操作（如插入和删除），则相应的表称为动态查找表，否则称之为静态查找表。动态查找表的表结构本身是在查找过程中动态生成的，即在创建表时，对于给定值，若表中存在其关键字等于给定值的记录，则查找成功返回；否则插入关键字等于给定值的记录。
• 平均查找长度：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度（Average Search Length，ASL）。

对于含有 $n$ 个记录的表，查找成功时的平均查找长度为

$$ASL=\sum _{i=1}^n{P}_i{C}_i$$

其中，$P_i$ 为查找表中第 $i$ 个记录的概率，且 $\sum _{i=1}^n{P}_i=1$；$C_i$ 为找到表中其关键字与给定值相等的第 $i$ 个记录时，和给定值已进行过比较的关键字个数。

由于查找算法的基本运算是关键字之间的比较操作，所以可以使用平均查找长度来衡量查找算法的性能。