7.2.1 一般线性表的顺序查找
原书定位
印刷页P270起,对应PDF第282页。下文为目视整理的知识提要;完整内容见原书对照。
从表的一端依次比较,找到匹配即返回,否则到表尾失败。顺序表与链表均可使用,不要求关键字有序。
等概率成功时 ,最坏 。教材用第 0 位作哨兵、从后向前查,失败时还比较哨兵,计为 次;不使用哨兵且只比较实际记录时为 次。
已知查询概率时,把高频记录放在先检查的位置可降低 ASL;这会改变元素顺序,是否允许需由应用决定。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图

