算法简介,练习10.2-4

Question

这是练习" 算法导论"第3版的问题:(我知道这是一个微不足道的问题,但我无法理解这一点.)

第10章,第240页:

10.2-4

如上所述,LIST-SEARCH过程中的每个循环迭代都需要两个测试:一个用于x != L.nil,一个用于x.key != k.演示如何x != L.nil在每次迭代中消除测试.

LIST-SEARCH(L, k)
  x = L.nil.next
  while x != L.nil and x.key != k
    x = x.next
  return x

L是带有哨兵的圆形双链表.(sentinel是起始中的固定静态元素,有助于简化边界条件.例如,假设我们为list提供了L一个对象L.nil,该对象表示NIL但具有列表中其他对象的所有属性.)

除非k您搜索始终存在,否则简单删除x != L.nil将导致无限次迭代.

您可以将此表达式转换x != L.nil为其他表达式(例如列表中元素的数量),但我认为这不是解决方案.

我在解决这个问题时缺乏什么？

Answer 1

诀窍是k在进入循环之前将您的标记键设置为值.这样,您可以取消nil检查并仍然确保循环终止.当k被发现,发现该节点是定点,或者你想找到的价值.

Answer 2

前置哨兵.使用哨兵,x.key == k无论如何都会满足条件.确保哨兵删除.

LIST-SEARCH(L, k)
    LIST-INSERT(L, k)
    x = L.head.next
    while x.key != k
        x = x.next
    if x == L.head
        ret = NIL
    else
        ret = x
    LIST-DELETE(L, L.head)
    return ret