我正在学习C语言中的“链表”考试。我发现自己是有这段代码片段的“审阅者”。对于我的一生,我无法理解其余的事情是如何逆转的。这是...它来自尼克·帕兰特先生(链接来自斯坦福的CIS图书馆)的链接列表问题。
我将发表尼克先生的评论。

RecursiveReverse()解决方案

也许最难的部分是接受
RecursiveReverse(&rest)实际上会反转其余部分。然后有一个窍门
一直到列表的最后一个前节点。绘制图纸,看看如何
技巧起作用。

void RecursiveReverse(struct node** headRef) {
struct node* first;
struct node* rest;
if (*headRef == NULL) return; // empty list base case
first = *headRef; // suppose first = {1, 2, 3}
rest = first->next; // rest = {2, 3}
if (rest == NULL) return; // empty rest base case
RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                         // after: rest = {3, 2}
first->next->next = first; // put the first elem on the end of the list
first->next = NULL; // (tricky step -- make a drawing)
*headRef = rest; // fix the head pointer

}

我已经绘制了无数图来尝试跟踪正在发生的事情,而我只是不明白RecursiveRest(&rest)如何实际上反转了其余部分。请帮忙。我感到非常沮丧。我最终得到的是较小的“其余部分”。
提前非常感谢您。

最佳答案

通常很难理解递归,因为很难看到它如何分解成基本步骤。

通常更容易将递归部分视为已经完成,而仅是考虑组合步骤的原因(这在设计算法时最有用)。

当您尝试可视化递归算法的工作原理时,必须记住,有两个过程在起作用:

  • 在较小的问题中分解原始问题,直到找到终止情况
  • 终止情况的解决方案
  • 组合结果。

  • 就像一条两条街道。首先,在解决问题时,您要走到最后一种情况。然后,您解决最终情况。之后,您在合并部分结果的同时开始返回。

    对于您的情况,它可能会像这样。注意[A-B]表示一个列表。
    [A-B-C-D-E] // RecursiveReverse([A, B, C, D, E])
    (A [B-C-D-E]) // this means we are calling RecursiveReverse([B, C, D, E])
    (A (B [C-D-E])) // this means we are calling RecursiveReverse([C, D, E])
    (A (B (C [D-E]))) // this means we are calling RecursiveReverse([D, E])
    (A (B (C (D [E])))) // this means we are calling RecursiveReverse([E])
                        // hit the end case and solve it trivially
    (A (B (C (D [E])))) // solved
    (A (B (C [E-D]))) // and go back while applying the combination case
    (A (B [E-D-C])) // combine
    (A [E-D-C-B]) // combine
    [E-D-C-B-A] // combine
    

    希望这可以帮助。

    09-17 15:06
    查看更多