一、查找的概念

 1.查找（Searching）：在由一组记录组成的集合中寻找关键字值等于给定值的某个记 录，或是寻找属性值符合特定条件的某些记录。若表中存在这样一个记录，则称查找是成功的， 此时查找的结果给出整个记录的信息，或指示该记录在查找表中的位置。若表中不存在关键字 等于给定值的记录，则称查找不成功，此时查找的结果可以给出一个“空”记录或者“空”指 针

 2.查找表（Search Table）：是一种以同一类型的记录构成的集合为逻辑结构，以查找为核 心运算的数据结构。

 3.关键字（Key):是数据元素中某个数据项的值，又称为键值，用它可以标识一个数据元 素，也可以标识一个记录的某个数据项（字段）。

 4.主关键字（Primary key):可以惟一地标识一个记录的关键字。对于那些可以标识多个 数据元素（或记录）的关键字，称为次关键字（Secondary Key）

 5.查找表的分类： 

  （1）静态查找表（Static Search Table）：只作查找操作的查找表。主要操作（查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素和各种属性。）

  （2）动态查找表（Dynamic Search Table）：动态表的特点是表结构本身是在查找过程中动态生 成的。同时在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在 的某个数据元素。主要操作（查找时插入数据元素；查找时删除数据元素）

 5.静态表和动态表的代表：

  （1）静态表：顺序查找、二分查找、插值查找、斐波那契查找、线性索引查找

  （2）动态表：二叉排序树、平衡二叉树、B树、散列表

 6.平均查找长度：在查找的过程中，一次查找的长度是指需要比较的关键字的次数，而平均查找 长度则是所有查找过程中进行关键字的比较的次数的平均值。

n 表示的是查找表的长度。Pi 表示的是查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即Ci 表示的是找到第 i 个数据元素所...