用于反转链表的非迭代等价物 [英] Non iterative equivalent for reversing a linked list

问题描述

我正在阅读RobertSedwick的Algorithms书中的列表遍历。函数定义如下所示。提到可以有遍历和删除功能可以有迭代计数器部分，但traverseR不能。我的问题为什么traverseR不能有迭代计数器部分？是的，如果递归调用不是函数的结束，即，像遍历，那么我们不能有迭代，是我的理解吗？

I am reading about list traversals in Algorithms book by RobertSedwick. Function definitions are shown below. It is mentioned that it is possible to have traverse and remove functions can have iterative counter parts, but traverseR cannot have. My question why traverseR cannot have iterative counter part? Is it that if recursive call is not end of function i.e., like in traverse then we cannot have iterative, Is my understanding right?

感谢您的时间和帮助。 / p>

Thanks for your time and help.

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); 
  }

推荐答案

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

traverseR uses the call stack to store pointers to all the nodes of the list, so that they can be accessed in reverse order as the call stack unwinds.

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

In order to do this without a call stack (i.e. non-recursively), you'll need some other stack-like data structure to store these pointers in.

其他函数只需在当前节点上工作，并继续运行，而不需要在递归函数调用返回后存储任何要使用的内容。这意味着尾递归可以用一个循环来代替（通过修改代码，或者根据编译器，让它确定这是可能的，并使转换本身）。

The other functions simply work on the current node and move on, with no need to store anything for use after the recursive function call returns. This means that the tail recursion can be replaced with a loop (either by modifying the code or, depending on the compiler, letting it determine that that's possible and make the transformation itself).

这篇关于用于反转链表的非迭代等价物的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！