7.2.1.1 有序线性表的顺序查找

教材导航 · 第7章

原书定位

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

递增表从前向后查时,一旦当前关键字大于目标即可提前判失败。成功比较次数仍由位置决定,等概率成功 ASL 与无序顺序查找相同。

失败分布对应 n+1n+1 个间隙。在各间隙等概率、且最后一个失败区间需比较 nn 个记录的口径下:

ASL失败=1+2+⋯+n+nn+1=n2+nn+1ASL_{\text{失败}}=\frac{1+2+\cdots+n+n}{n+1}=\frac n2+\frac n{n+1}

有序链表也能顺序查,但不具备数组的随机定位能力。

有序表顺序查找判定树

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

对应练习

7.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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

原书对照,原书P272,PDF第284页