Как рекурсивные функции работают в связанном списке с концепцией стека?

Здесь я дал код для печати реверса связанного списка.

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. Но я точно не знаю. Пожалуйста, помогите мне понять с помощью пошаговых операций на диаграммах.


recursion function-call linked-list
person Anuraj Aspire    schedule 29.07.2013    source источник
comment
Этот вопрос не ясен. Ваш код печатает содержимое списка в обратном порядке, он не пытается перестроить список в обратном порядке. Кажется, это вас удивляет. Вы просите код, чтобы фактически перевернуть список? Или объяснение того, как работает текущий код?   -  person djna    schedule 29.07.2013

Ответы (2)


arrow_upward
1
arrow_downward

Я не совсем уверен, чего вы пытаетесь достичь. Ваш код точно печатает то, что он должен делать. Ниже приведен сегмент кода, который соответствует вашим ожиданиям:

Я ожидал, что последний узел связанного списка будет напечатан.

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

arrow_upward
1
arrow_downward

Если вы предоставите ему список 1->2:

  1. head=1->2, head не null, повторяется с 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 не null, печатает head->data "1", повторяется с 2 (продолжение с 5)
  2. => head=2, head не null, печатает head->data "2", повторяется с null (продолжение 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->data "2" и вернуться
  3. вернуть

Обратите внимание, что он не повторяется, когда найден последний элемент, поэтому единственный способ, которым n равен нулю, - это если вы попытались напечатать пустой связанный список (NULL).

person Sylwester    schedule 29.07.2013