递归函数如何在具有堆栈概念的链表中工作

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. head=1->2，head不为空，用2重复（在5上继续）
2. =>head=2，head不是null，用null重复（4上的继续）
3. =>head=null，head为null，返回
4. =>打印头->数据"2"并返回
5. 打印头数据"1"并返回

如果您要在打印语句再次出现之前移动它：

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

它会是这样的：

1. head=1->2，head不为空，打印head->data"1"，用2重复（第5页继续）
2. =>头=2，头不为空，打印头->数据"2"，用空重复（4上的继续）
3. =>head=null，head为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和n->next！=null，用2重复（在3上继续）
2. =>n=2，n！=null和n==null。打印n->数据"2"并返回
3. 返回

请注意，当找到最后一个元素时，它不会重复出现，所以n为null的唯一方法是尝试打印一个空链表（null）。