一尘不染

前哨节点如何提供优于NULL的好处?

algorithm

Sentinel Node
Wikipedia页面上,
它说到一个哨兵节点优于NULL的好处是:

  • 加快运作速度
  • 减少算法代码大小
  • 增强的数据结构鲁棒性(可以说)。

我真的不了解针对哨兵节点的检查会更快(或如何在链接列表或树中正确实施检查),所以我想这更多是一个两部分的问题:

  1. 是什么导致前哨节点比NULL更好的设计?
  2. 您将如何在(例如)列表中实现哨兵节点?

阅读 262

收藏
2020-07-28

共1个答案

一尘不染

如果仅执行简单的迭代而不查看元素中的数据,则哨兵没有任何优势。

但是,将其用于“查找”类型算法时会获得一些实际收益。例如,假设std::list您想在其中找到特定值的链表列表x

如果没有哨兵,您将要做的是:

for (iterator i=list.begin(); i!=list.end(); ++i) // first branch here
{
  if (*i == x) // second branch here
    return i;
}
return list.end();

但是使用前哨(当然,终点实际上必须是一个真正的节点……):

iterator i=list.begin();
*list.end() = x;

while (*i != x) // just this branch!
  ++i;

return i;

您会看到不需要额外的分支来测试列表的结尾-始终保证该值在那里,因此,end()如果x在“有效”元素中找不到该值,则会自动返回。

有关哨兵的另一个很酷且实际上有用的应用程序,请参阅“介绍排序”,这是大多数std::sort实现中使用的排序算法。它是分区算法的一个很酷的变体,它使用哨兵删除一些分支。

2020-07-28