7.1 查找

查找表是由同一类型的数据元素（或记录）构成的集合。由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构
什么是查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或记录
关键字：用来标识一个数据元素（或记录）的某个数据项的值
主关键字：可唯一的标识一个记录的关键字是主关键字
次关键字：用以识别若干记录的关键字是次关键字
查找的目的：
①查询某个“特定的”数据元素是否在查找表中
②检索某个“特定的”数据元素的各种属性
③在查找表中插入一个数据元素
④删除查找表中的某个数据元素
查找表的分类：
①静态查找表：仅作“查询”（检索）操作的查找表
②动态查找表：作“插入”和“删除”操作的查找表
查找算法的评价指标：关键字的平均比较次数，也称平均查找长度 ASL(Average Search Length)

n：记录的个数
pi：查找第i个记录的概率（通常认为pi=1/n）
cii：找到第i个记录所需的比较次数