7.2.1 一般线性表的顺序查找

教材导航 · 第7章

原书定位

印刷页P270起,对应PDF第282页。下文为目视整理的知识提要;完整内容见原书对照。

从表的一端依次比较,找到匹配即返回,否则到表尾失败。顺序表与链表均可使用,不要求关键字有序。

等概率成功时 ASL=(n+1)/2ASL=(n+1)/2,最坏 O(n)O(n)。教材用第 0 位作哨兵、从后向前查,失败时还比较哨兵,计为 n+1n+1 次;不使用哨兵且只比较实际记录时为 nn 次。

已知查询概率时,把高频记录放在先检查的位置可降低 ASL;这会改变元素顺序,是否允许需由应用决定。

下级知识点

对应练习

7.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P270,PDF第282页

原书对照,原书P271,PDF第283页