6.1 查找

6.1.1 查找的基本概念

查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。 查找表（查找结构）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成。 关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

uTools_1638241191170

uTools_1638241230449

6.1.2 对查找表的常见操作

查找和插入、删除

静态查找表只关注查找速度，动态查找表既关注查找速度又关注插入删除是否方便。

6.1.3 查找算法的评价指标

查找长度：对比关键字的次数

平均查找长度(ASL)：对比关键字次数的平均值。

$ASL=\sum_{i=1}^{n}{P_iC_i}$——查找概率×查找长度的总和

ASL反映了查找算法的时间复杂度。

查找成功和查找失败的平均查找长度：

1638242765366

1638242765362