查找的基本概念

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

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

  • 操作：

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

  • 静态查找表：查找后不会改表

  • 动态查找表：查找后改表

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

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

  • 数学表达式：

    $$ASL=\sum _{i=1}^n{P}_i{C}_i$$

  • 参数含义：

    • n：查找表的长度
    • P_i：查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 P=1/n
    • C_i：找到第 i 个数据元素所需进行的比较次数

平均查找长度是衡量查找算法效率的最主要指标