递归函数如何在堆栈概念的链接列表中工作？

Question

在这里我给出了一个代码来打印链接列表的反转。

fun1（）以相反的方式打印给定的链接列表。对于链接列表1-> 2-> 3-> 4-> 5，fun1（）打印5-> 4-> 3-> 2-> 1。

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 

    fun1(head->next); 
    printf("%d ", head->data); 
} 

任何人都可以解释如何在每次调用fun1（）时构建栈帧吗？我期待链接列表的最后一个节点将被打印。但我正在以相反的顺序获取链接列表。它没有使链表反向。它只是反向打印。我认为这是由于像Push/Pop这样的堆栈操作。但我不完全清楚。请在图表中逐步操作的帮助下帮助我理解。

Answer 1

我不太确定你想要达到的目标。你的代码完全打印出它应该做的事情。以下是符合您的期望的代码段：

我期望链接列表的最后一个节点将被打印。

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 
    if(head->next == NULL) 
    { 
    printf("%d ", head->data); 
    return; 
    } 
    else 
    fun1(head->next); 
} 

Answer 2

如果提供列表1-> 2到它：

1. 头= 1-> 2，头不为空，复发与2（5续）
2. => head = 2，head不为null，null为null（继续4）
3. => => head = null，head为null，返回
4. => print head-> data“2”并返回
5. 打印头数据 “1”，并返回

如果你移动你的print语句重复发生之前：

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 

    printf("%d ", head->data); 
    fun1(head->next); 
} 

这将是这样的：

1. 头= 1-> 2，头不为空，打印头 - >数据“1”，重复2（5上继续）
2. => head = 2，头不为空，打印头 - >数据“2”重复发生null（继续4）
3. => =>头= NULL，头部为空时，返回
4. =>返回
5. 返回

在这两种情况下的所有非空的节点被打印。只能获得印刷他们中的一个，你的代码必须从其他区分开来，像这样：

void print_last(struct node* n) 
{ 
    if(n == NULL) 
    { 
     printf("empty list!"); 
    }   
    else if(n->next == NULL) 
    { 
     printf("%d", n->data); 
    } 
    else 
    { 
     print_last(n->next); 
    } 
} 

与同一列表1-> 2叫你;

1. N = 1-> 2，N！= null，并且正>下！= NULL，复发与2（3续）
2. => n = 2时，正！= NULL且n = = null。打印N->数据“2”，并返回
3. 回报

请注意，当最后一个元素发现所以唯一的办法，n是空的，如果你尝试打印一个空链表（NULL）不递归。