第七章查找 ★查找—也叫检索,是根据给定的某个值,在表 中确定一个关键字等于给定值的记录或数据元素 ★关键字—是数据元素中某个数据项的值。它可 以标识一个数据元素 ★查找方法评价 对含有n个记录的表,ASL=∑PC 心查找速度 其中:P为查找表中第个元素的概率∑p1= ◆占用存储空间多少 c为找到表中第个元素所需比较次数 ◆算法本身复杂程度 ☆平均查找长度ASL( Average Search Length):为确定 记录在表中的位置,需和给定值进行比较的关键字的 个数的期望值叫查找算法的第七章 查找 查找——也叫检索，是根据给定的某个值，在表 中确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可 以标识一个数据元素 查找方法评价 ❖查找速度 ❖占用存储空间多少 ❖算法本身复杂程度 ❖平均查找长度ASL(Average Search Length)：为确定 记录在表中的位置，需和给定值进行比较的关键字的 个数的期望值叫查找算法的~ 为找到表中第 个元素所需比较次数 其中： 为查找表中第 个元素的概率， 对含有 个记录的表， c i p i p n ASL p c i n i i i n i i i 1 1 1 = =   = =