查找的基本概念
(1)查找的概念：在数据集合中寻找满足某种条件的数据元素的过程称为查找.
- 查找成功：找到满足条件的数据元素
- 查找失败：未找到满足条件的数据元素
(2)查找表：由同一类型的数据元素构成的集合.
- 静态查找表：只查找不修改,包括以下两个操作
- ① 查询某个特定的数据元素是否在查找表中
- ② 检索某个特定的数据元素的各种属性
- 动态查找表：既查找也修改,还包括以下两个修改操作
- ③ 在查找表中插入一个数据元素
- ④ 从查找表中删去某个数据元素
(3)关键字：
数据元素中某个(或几个)数据项的值，它可以标识一个数据元素。若关键字能唯一标识一个数据元素，则关键字称为主关键字(主键)；将能标识若干个数据元素的关键字称为次关键字.
(4)查找：
根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素. 若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志.
(5)平均查找长度：
为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。(平均查找长度 ASL：Average Search Length)作为衡量一个查找算法效率高低的标准。
- n：查找表中记录的个数
：查找第 i 个记录的概率
：找到第 i 个记录所需要进行比较的次数
若有收获，就点个赞吧
0 人点赞
