7.1 查找的基本概念

教材导航 · 第7章

原书定位

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

查找可成功或失败。静态查找表主要做查询,动态查找表还要频繁插入和删除;关键字用于标识记录,主关键字可唯一标识记录。

平均查找长度按各种情况的概率加权:

ASL=∑ipiCiASL=\sum_i p_i C_i

成功与失败分别建立样本空间与概率。CiC_i 通常统计与记录关键字的比较次数,边界检查、空指针检查是否计入要按题意处理。

关联知识

原书对照

展开原书对照截图

原书对照,原书P269,PDF第281页

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