知识卡片

普通读书笔记卡 · 3622.b.1

哨兵键减少循环分支

理解等级:高级

搜索链表前先把目标键写入哨兵,扫描循环便可只检查键是否相等,不必每轮检查是否走到表尾。

停止后若落在哨兵则表示未找到,落在真实节点才返回。

此法减少常数开销,不改变线性最坏时间,还要求哨兵键可临时写入。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《算法导论(第4版)》第 10 章 10.2 节(`OEBPS/chapter010.xhtml`,文本字符 [20000, 23000))。 - 结论依据:原文 LIST-SEARCH′ 先设 L.nil.key=k,循环仅比较键,最后再判是否到哨兵。 - 原始内容:The sentinel provides a place to put the key before starting the search.