(54)王道数据结构-查找的基本概念

基本概念

查找。在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合找到了满足条件的数据元素；二是查找失败。

关键字。数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。例如，在由一个学生元素构成的数据集合中，学生元素中”学号”这一数据项的值唯一地标识一名学生。

查找: 在数据集合中寻找满足某种条件的数据元素的过程称为查找

查找表(查找结构) 用于查找的数据元素的集合称为查找表，它由同一类型的数据元素(或记录)组成，可以是一个数组或链表等数据类型

关键字: 数据元素中唯一标识该元素的某个数据项，使用基于关键字的查找，查找结果应该是唯一的。

查找表

①查询某个特定的数据元素是否在查找表中；

②检索满足条件的某个特定的数据元素的各种属性；

③在查找表中插入一个数据元素；

④从查找表中删除某个数据元素。

分类

①静态查找表。若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表，此类查找表称为静态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等

②需要动态地插入或删除的查找表称为动态查找表。适合动态查找表的查找方法有二叉排序树的查找、散列查找等。

性能分析

查找长度: 在查找运算中，需要对比关键字的次数称为查找长度

平均查找长度: 简称ASL，所有查找过程中进行关键字的比较次数多平均值

$$
ASL = \sum_{i=1}^nP_iC_i
$$
n是查找表的长度。Pi是查找第i个数据元素的概率，一般认为每个数据元素的查找概率相等，即Pi= 1/n；C是找到第i个数据元素所需进行的比较次数

ASL举例在(38)王道数据结构-二叉排序树中有所提及