3

我正在阅读 RobertSedwick 的算法书中的列表遍历。函数定义如下所示。提到可以有 traverse 和 remove 函数可以有迭代的对应部分，但 traverseR 不能有。我的问题为什么 traverseR 不能有迭代对应部分？是不是如果递归调用不是函数的结尾，即像遍历那样我们不能进行迭代，我的理解对吗？

感谢您的时间和帮助。

void traverse(link h, void visit(link))
  { 
    if (h == 0) return;
    visit(h); 
    traverse(h->next, visit);
  }
void traverseR(link h, void visit(link))
  { 
    if (h == 0) return;
    traverseR(h->next, visit);
    visit(h); 
  }
void remove(link& x, Item v)
  { 
    while (x != 0 && x->item == v) 
      { link t = x; x = x->next; delete t; }
    if (x != 0) remove(x->next, v); 
  }
4

6 回答 6

5

traverseR使用调用堆栈来存储指向列表中所有节点的指针，以便在调用堆栈展开时可以以相反的顺序访问它们。

为了在没有调用堆栈（即非递归）的情况下执行此操作，您需要一些其他类似堆栈的数据结构来存储这些指针。

其他函数只是在当前节点上工作并继续前进，无需在递归函数调用返回后存储任何内容以供使用。这意味着可以用循环替换尾递归（通过修改代码或取决于编译器，让它确定这是可能的并自行进行转换）。

于 2012-09-04T13:08:21.643 回答
4

假设列表是单链接的，则不可能以向后的顺序迭代地访问它，因为没有从一个节点指向前一个节点的指针。

递归实现traverseR本质上所做的是它隐式地反转列表并以正向顺序访问它。

于 2012-09-04T13:06:23.037 回答
1

您可以编写traverseR使用堆栈的迭代版本：在循环中从一个节点迭代到另一个节点，将节点推入堆栈。当您到达列表末尾时，在另一个循环中，弹出并访问您访问过的节点。

但他基本上是递归版本所做的。

于 2012-09-04T13:09:30.910 回答
1

可以仅使用 O(1) 额外空间以相反的顺序遍历单链表——即，没有以前访问过的节点的堆栈。然而，它有点棘手，而且根本不是线程安全的。

这样做的诀窍是从头到尾遍历列表，在执行此操作时将其反转到位，然后将其遍历回到开头，在返回时再次反转它。

由于它是一个链表，因此将其反转相当简单：当您到达一个节点时，保存其next指针的当前值，并用链表中前一个节点的地址覆盖它（有关更多详细信息，请参见代码):

void traverseR(node *list, void (*visit)(node *)) { 
    node *prev = nullptr;
    node *curr = list;
    node *next;

    if (!curr)
        return;

    // Traverse forwards, reversing list in-place as we go.
    do {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    } while (curr->next);

    // fix up so we have a fully reversed list
    curr->next = prev;
    prev = nullptr;

    // Traverse the reversed list, visiting each node and reversing again
    do { 
        visit(curr);
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    } while (curr->next);
}

就像几乎所有处理链表的事情一样，我觉得有必要补充一点（至少在 IMO），它们几乎总是应该被视为纯粹的智力练习。在实际代码中使用它们通常是净损失。您通常会得到缓慢、脆弱且难以理解的代码，并且通常会浪费相当多的内存（除非您存储在每个节点中的数据非常大，否则指针通常可以使用与数据一样多的空间本身）。

于 2012-09-04T15:00:50.660 回答
0

我的问题为什么 traverseR 不能有迭代对应部分？是不是如果递归调用不是函数的结尾，即像遍历那样我们不能进行迭代，我的理解对吗？

正确的。函数traverse并remove以对自身的调用结束。它们是尾递归函数。对自身的调用traverseR不在函数的末尾；traverseR不是尾递归。

递归通常会产生创建和随后销毁堆栈帧的费用。通过将递归更改为迭代，尾递归函数可以完全避免这种开销。大多数编译器识别尾递归函数并将递归转换为迭代。

于 2012-09-04T13:23:56.297 回答
0

traverseR可以根据迭代的含义编写迭代版本。如果你受限于单次遍历列表，那是不可能的。但是，如果您可以牺牲大量处理时间，则可以完成。在经典的速度与内存权衡中，它确实使用了更少的内存。

void traverseRI(link h, void visit(link))
{
    if (h == 0) return;

    link last = 0;

    while (last != h)
    {
        link test = h;
        while (test->next != last)
        {
            test = test->next;
        }

        visit(test);
        last = test;
    }
}
于 2012-09-04T13:59:11.597 回答