7.2.1.1 有序线性表的顺序查找
原书定位
印刷页P271起,对应PDF第283页。下文为目视整理的知识提要;完整内容见原书对照。
递增表从前向后查时,一旦当前关键字大于目标即可提前判失败。成功比较次数仍由位置决定,等概率成功 ASL 与无序顺序查找相同。
失败分布对应 个间隙。在各间隙等概率、且最后一个失败区间需比较 个记录的口径下:
有序链表也能顺序查,但不具备数组的随机定位能力。

有序表顺序查找判定树,原书P271。
对应练习
关联知识
原书对照
展开原书对照截图


原书定位
印刷页P271起,对应PDF第283页。下文为目视整理的知识提要;完整内容见原书对照。
递增表从前向后查时,一旦当前关键字大于目标即可提前判失败。成功比较次数仍由位置决定,等概率成功 ASL 与无序顺序查找相同。
失败分布对应 个间隙。在各间隙等概率、且最后一个失败区间需比较 个记录的口径下:
有序链表也能顺序查,但不具备数组的随机定位能力。

有序表顺序查找判定树,原书P271。

