1. 查找表

问题：在哪里找？

答：在一个新的数据结构查找表上面找。

查找表

查找表是由同一类型的数据元素（或记录）构成的集合 由于 “集合” 中的数据元素之间存在着松散的关系（没有严格的前趋和后继关系），因此查找表是一种应用灵便的结构。 在这样一个表格中，不管把哪个同学的成绩信息放在前面，都不会打乱这张表的所要表示的信息，这样的一个没有严格前趋后继关系的表格就称为查找表

2. 关键字

问题：什么查找？

根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 如：给定一个姓名叫张三，在上面的成绩表中找一个叫张三的人的数学这一个关键字的值。 想找出物理考了 92 分的人是谁，当物理的关键字的值为 92 的时候就说明找到了。

关键字

用来标识一个数据元素（或记录）的某个数据项的值。

主关键字：可唯一的表示一个记录的关键字是主关键字。 如：准考证号，如果按照准考证号去找的话，只能找到一个人。 次关键字：反之，用以识别若干记录的关键字是次关键字。 如：姓名，如果用一个叫张三的名字就可能找出好几个同学。

3. 查找

问题：查找成功否？

查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。

若查找表中存在这样一个记录，则称：查找成功。 查找结果给出整个记录的信息，或指示该记录在查找表中的位置。 否则称：查找不成功。 查找记录给出空记录或空指针。

问题：查找目的是什么？

对查找表经常进行的操作：

1. 查询：查询某个特定的数据元素是否在查找表中。 如：看看成绩单中有没有叫张三的人、有没有物理 100 分的人。
2. 检索：检索某个特定的数据元素的各种属性。 如：我知道有张三这个人，现在就想知道张三的各科成绩是多少、总分是多少。 根据张三这个姓名来查找其他的值。
3. 插入：在查找表中插入一个数据元素。 看看成绩表里有没有张三这个人，没有的话就把张三的成绩插入到表中。
4. 删除：删除查找表中的某个数据元素。 张三转学了，要把他的信息从成绩表中删除。

4. 动态查找表和静态查找表

问题：查找表怎么分类？

1. 静态查找表： 仅作查询（检索）操作的查找表。 不改变集合内的数据元素。
2. 动态查找表： 作插入和删除操作的查找表。 即查找又改变集合内的数据元素。 有时在查询之后，还要将 查询 结果为不在查找表中 的数据元素插入到查找表中； 或者，从查找表中删除其 查询 结果为在查找表中的数据元素，此类表尾动态查找表。

5. 平均查找长度

问题：如何评价查找算法？

查找表的评价指标：

关键字的平均比较次数，也称平均查找长度 ASL（Average Search Length）

ASL 值 ↓，时间效率 ↑。 n：查找表中，总共有多少个数据记录。 pi：每一条数据记录可能被查找到的概率（通常认为 pi = 1/n） ci：找到第 i 个数据元素所需要的比较次数。

问题：查找过程中我们要研究什么？

查找的方法取决于查找表的结构，即表中数据元素是依何种关系组织在一起的。 由于对查找表来书，在集合中查询或检索一个特定的数据元素时，若无规律可循，只能对集合中的元素：加以辨认直到找到为止。 而这样的 “查询” 或 “检索” 是任何计算机应用系统中使用频度都很高的操作，因此设法提高查找表的查找效率，是本章讨论问题的出发点。 为了提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为的加上某种确定的约束关系。 研究查找表的各种组织方法以及查找过程的实施。