2

我的递归技巧很生疏。我一直在思考这个问题，在论坛上搜索了很长时间，但仍然无法理解。现在我正在查看来自斯坦福 CS ed 库的递归反转链表代码。

#include <stdio.h> 

struct Node {
  int x;
  struct Node *next;
};

void Reverse(struct Node ** headRef){
    struct Node* first;
    struct Node* rest;

    if(*headRef==NULL)
       return;

    first= *headRef;
    rest= first->next;  

    if(rest==NULL)
        return; 

    Reverse(&rest);
    printf("Rest%d\n", (rest)->x); // I added this line to print rest
    first->next->next=first;
    first->next=NULL;
    *headRef=rest;
}

void printList(struct Node* head){

    if(!head)
       return;
    else{
       printf("%d ", head->x);
       printList(head->next);   
    }
}

void main(){
    struct Node *head;
    struct Node * node1= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node2= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node3= (struct Node*) malloc(sizeof(struct Node));
    struct Node * node4= (struct Node*) malloc(sizeof(struct Node));
    head= node1;
    node1->next=node2;
    node1->x=1;
    node2->x=2;
    node3->x=3;
    node4->x=4;
    node2->next=node3;
    node3->next=node4;
    node4->next=NULL;
    Reverse(&head);
}

现在假设我有一个链表 1->2->3->4。我无法理解的是最后一行，它最终会将 headRef 设置为 4，我认为它应该将 headRef 设置为 2。我尝试执行该函数并打印出：

4
4
4

为变量休息。

但是，如果我将 Reverse 函数中的最后一行注释掉，它仍然会反转列表但会打印

4
3
2。

第二个结果我可以理解，但第一个结果似乎很混乱。语句“*headRef=rest”对变量 rest 有什么作用吗？它一直指向4是什么？

另外，如果我通过 *headRef 而不是 **headRef （最后一行没有注释掉），它会打印结果

4
3
2

也。

谁能给我解释一下记忆中发生了什么？太感谢了。

4

2 回答 2

2

在递归调用之前，Reverse我们有：

first---|  
        |  
        v  
        1->2->3->4->NULL
           ^
           |
           |
  rest------

在递归调用之后，Reverse我们有：

first---|
        |
        v
        1->2<-3<-4
           |     ^
           v     |
         NULL    |
  rest------------

现在我们需要修复2->NULL到2->1by first->next->next=first。

first---|
        |
        v
        1<-2<-3<-4
        |  ^     ^
        |--|     |
                 |
  rest------------

现在我们需要修复1->2到1->NULLby first->next=NULL。

first---|
        |
        v
  NULL<-1<-2<-3<-4
                 ^
                 |
                 |
  rest------------

最后 *headRef=rest，这*headRef将指向4而不是指向1。

于 2012-09-01T20:05:17.243 回答
0

这里发生的情况是因为递归调用将rest 的地址传递给局部变量 headRef，当每个递归调用返回时，语句 *headRef=rest 已经更改了执行流程中下一个语句的 rest 指针的地址。

对于链表 1->2->3->4 ：

假设 1 存储在地址 100 中，2 存储在地址 200 中，3 存储在地址 300 中，4 存储在地址 400 中。

第 1 部分： 调用 Reverse(&rest) [rest 指向地址 400]

第一个 = 400 休息 = NULL

由于 rest 为 NULL，因此执行返回到 Reverse(400) 调用后的点

第 2 部分： 执行 first->next->next=first 和 first->next=NULL 后，这里 first = 300 和 rest = 400

我们有 *headRef=rest [rest 指向 400]

但是这个headRef被传递了一个rest = 300的地址。所以现在已经为下一步执行，休息点为 400。

第 3 部分： 现在执行返回到 Reverse(300) 调用后的点

但是在前向呼叫期间 [first 是 200，其余是 300] 和返回期间 [rest = 400]。这是诀窍！

在执行 first->next->next=first 和 first->next=NULL 之后

我们有 *headRef=rest [rest 指向 400]

但是这个headRef被传递了一个rest = 200的地址。所以现在已经为下一步执行，休息点为 400。

第 4 部分： 现在执行返回到 Reverse(200) 调用后的点

但是在前向呼叫期间 [first 是 100，其余是 200] 和返回期间 [rest = 400]。

在执行 first->next->next=first 和 first->next=NULL 之后

我们有 *headRef=rest [rest 指向 400]

因为这是初始调用，所以函数返回 *headRef 具有 400 值。

任务完成！

于 2014-09-22T20:51:17.610 回答