知识卡片
哨兵键减少循环分支
搜索链表前先把目标键写入哨兵,扫描循环便可只检查键是否相等,不必每轮检查是否走到表尾。
停止后若落在哨兵则表示未找到,落在真实节点才返回。
此法减少常数开销,不改变线性最坏时间,还要求哨兵键可临时写入。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第10章 基本数据结构 · 查看原书依据
The sentinel provides a place to put the key before starting the search.
参考来源
- 位置:《算法导论(第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.