algorithm - 算法介绍，练习 10.2-4

Question

这是第三版算法简介练习中的一个问题：（我知道这是一个微不足道的问题，但我无法理解这个问题。）

第 10 章，第 240 页：

10.2-4

正如所写，LIST-SEARCH 过程中的每个循环迭代都需要两个测试：一个 forx != L.nil和一个 for 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是带有标记的循环双向链表。（哨兵是开始时固定的静态元素，有助于简化边界条件。例如，假设我们为列表提供了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

Answer 3

做这样的事情：

LIST-SEARCH(L,k)
    nil.key = k;
    currentPtr = nil.next;
         while(currentPtr.key != k) 
    currentPtr = currentPtr.next;
    nil.data = -1; // dummy key
    return currentPtr;