查找的基本概念

查找

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

查找表（查找结构）

用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有4种：

• 查询某个特定的数据元素是否在查找表中。
• 检索满足条件的某个特定的数据元素的各种属性。
• 在查找表中插入一个数据元素；④从查找表中删除某个数据元素。

静态查找表

若一个查找表的操作只涉及上述操作①和②，则无须动态地修改查找表， 此类查找表称为静态查找表。与此对应，需要动态地插入或删除的查找表称为动态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；适合动态查找表的查找方法有二叉排序树的查找、散列查找等。

关键字

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

平均查找长度

总结