基本概念
查找–在数据集合中寻找满足某种条件的数据元素的过程称为查找
查找表(查找结构)–用于查找的数据集合称为查找表,它由同一类型的数据元素(或记录)组成
关键字–数据元素中唯一标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的
对查找表的常见操作
1、查找符合条件的数据元素
2、插入、删除某个数据元素
只需进行操作1–静态查找表(仅关注查找速度即可)
也要进行操作2–动态查找表(除了查找速度,也要关注插入删除操作是否方便实现)
查找算法的评价指标
查找长度–在查找运算中,需要对比关键字的次数称为查找长度
平均查找长度(ASL,Average Search Length)-- 所有查找过程中进行关键字的比较次数的平均值