Создание связанного списка с использованием рекурсии

Question

Я хочу создать связанный список, используя рекурсию. После выполнения кода я получаю только значение первого узла и остальное не печатаются.

#include<stdio.h> 
#include<malloc.h> 

typedef struct node NODE; 

struct node 
{ 
    int data; 
    struct node *next; 
} *start=NULL,*ptr; 

void display(); 
int create(int); 

int main() 
{ 
    int n; 
    printf("\nEnter the no of node?\t"); 
    scanf("%d",&n); 
    create(n); 
    display(); 
} 
int create(int x) 
{ 
    if(x==0) 
     return; 

    else{ 
     NODE *node; 
     node=((NODE *)malloc(sizeof(NODE))); 

     printf("Enter the data:\n"); 
     scanf("%d",&node->data); 

     node->next=NULL; 
     if(start==NULL) 
     { 
      ptr=start=node; 
     } 
     else 
     { 
      ptr=node->next; 
      ptr=node; 
     } 
     ptr->next=NULL; 
    } 
    create(x-1); 
} 

void display() 
{ 
    NODE *ds; 
    ds=start; 
    while(ds!=NULL) 
    { 
     printf("%d->",ds->data); 
     ds=ds->next; 
    } 
} 

Я думаю, что проблема, когда я называю create(x-1);, но я не уверен. Правильно ли моя логика? Может ли кто-нибудь указать мою ошибку?

Answer 1

Попробуйте изменить логику,

int create(int x) { 
    if (x == 0) 
     return 0; 
    else { 
     NODE *node; 
     node = ((NODE *) malloc(sizeof (NODE))); 
     printf("Enter the data:\n"); 
     scanf("%d", &node->data); 
     node->next = NULL; 
     if (start == NULL) { 
      ptr = start = node; 
     } else { 
      //ptr = node->next; 
      ptr->next = node; 
      ptr = node; 
     } 
     ptr->next = NULL; 
    } 
    create(x - 1); 
} 

Вы не переустановить головку правильно.

Также хорошо, чтобы проверить это реализация из>http://geeksquiz.com/linked-list-set-1-introduction/

Answer 2

Когда вы делаете это:

ptr=node->next; 
ptr=node; 

Вы проигрышные вашу ссылку на хвост списка, и, следовательно, не добавляя к node список. Вы должны делать это:

ptr->next = node; 
ptr = ptr->next; 

Это указывает next указатель текущего хвоста к новому узлу, затем перемещается вниз ptr на новый хвост.

Кроме того, ptr->next=NULL в конце цикла не является необходимым, так как ptr теперь так же, как node, и вы уже сделали node->next = NULL.

Answer 3

Важной ошибкой, возникшей из-за вашей проблемы, было ваше назначение указателей в create(int). Вы правильно назначили первый указатель, но затем назначили NULL всем остальным указателям. Есть несколько способов справиться с этим, но чистый и простой способ это только заранее ptr=ptr->next в else блока следующим образом:

if (start == NULL) 
{ 
    ptr = start = node; 
} 
else 
{ 
    ptr->next = node; 
    ptr = ptr->next; 
} 

Вы динамически выделяющий память, так что это означает, что вы несете ответственность за отслеживание его использования, сохраняя указатель на начальный блок каждого распределения и, наконец, освобождая память, когда она больше не используется. Начать сейчас. Получайте привычку обрабатывать очистку своей памяти всякий раз, когда вы ее выделяете, и не просто полагайтесь на выход программы, чтобы сделать это за вас. Хотя теперь может показаться тривиальным, когда вы начнете обрабатывать функции с несколькими распределениями и т. Д., Если у вас не сложились хорошие привычки в этом отношении, ваш код, скорее всего, утешит память, как сито. Простая функция очистки не может быть ничего более:

void destroy() 
{ 
    if (!start) return; 

    NODE *ds = start; 
    while (ds != NULL) 
    { 
     NODE *victim = ds; 
     ds = ds->next; 
     free (victim); 
    } 
} 

The malloc вопрос. malloc возвращает начальный адрес для выделенного блока памяти, нет необходимости отбрасывать возврат в C. Когда вы выделяете память для типов данных, которые вы только что объявили, используйте переменную с sizeof вместо типа данных. например .:

NODE *node; 
node = malloc (sizeof *node); 

вместо

node = malloc (sizeof (NODE)); 

Это станет очевидным при работе с указателями на указатели и т.д.Это имеет гораздо больший смысл для работы с вашей переменной, чем для того, чтобы помнить, выделяете ли вы для NODE* или NODE**. Это особенно актуально, когда распределение представляет собой много строк под декларацией в вашем коде или при приеме указателя в списке аргументов функции.

Кроме того, каждый раз, когда вы выделяете память, вам необходимо подтвердить возврат с malloc, чтобы вы не исчерпали доступную память. например:

NODE *node; 
if (!(node = malloc (sizeof *node))) { 
    fprintf (stderr, "error: virtual memory exhausted\n"); 
    exit (EXIT_FAILURE); 
} 

Наконец, положить все это вместе, один подход к вашей проблеме будет:

#include <stdio.h> 
#include <stdlib.h> /* for exit & EXIT_FAILURE */ 

typedef struct node NODE; 

struct node { 
    int data; 
    struct node *next; 
} *start=NULL,*ptr; 

void display(); 
void create (int); 
void destroy(); 

int main (void) 
{ 
    int n; 
    printf ("\nEnter the no of node: "); 
    scanf ("%d",&n); 
    create (n); 
    display(); 
    destroy(); 
    return 0; 
} 

void create (int x) 
{ 
    if (x == 0) return; 

    NODE *node; 
    if (!(node = malloc (sizeof *node))) { 
     fprintf (stderr, "error: virtual memory exhausted\n"); 
     exit (EXIT_FAILURE); 
    } 

    printf ("Enter the data: "); 
    scanf ("%d",&node->data); 

    node->next = NULL; 
    if (start == NULL) 
    { 
     ptr = start = node; 
    } 
    else 
    { 
     ptr->next = node; 
     ptr = ptr->next; 
    } 

    create (x-1); 
} 

void display() 
{ 
    if (!start) return; 

    NODE *ds = start; 
    while (ds != NULL) 
    { 
     if (ds == start) 
      printf ("%d", ds->data); 
     else 
      printf("->%d", ds->data); 
     ds = ds->next; 
    } 
    printf ("\n"); 
} 

void destroy() 
{ 
    if (!start) return; 

    NODE *ds = start; 
    while (ds != NULL) 
    { 
     NODE *victim = ds; 
     ds = ds->next; 
     free (victim); 
    } 
} 

Пример

$ ./bin/llrecurse 

Enter the no of node: 4 
Enter the data: 2 
Enter the data: 4 
Enter the data: 6 
Enter the data: 8 
2->4->6->8 

Использование Checker памяти

Независимо от вашей платформе, полезно использовать средство проверки памяти, например valgrind, для проверки ошибок памяти и обеспечения освобождения всей выделенной вами памяти. Контроллер памяти не только подтверждает, что вся память освобождена, но также сообщается о тонких ошибках в том, как вы пытаетесь получить доступ к выделенной памяти, которая может предупредить вас о проблемах, которые могут вас укусить позже. Он прост в использовании, просто:

$ valgrind ./bin/llrecurse 
==17434== Memcheck, a memory error detector 
==17434== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al. 
==17434== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info 
==17434== Command: ./bin/llrecurse 
==17434== 

Enter the no of node: 4 
Enter the data: 2 
Enter the data: 4 
Enter the data: 6 
Enter the data: 8 
2->4->6->8 
==17434== 
==17434== HEAP SUMMARY: 
==17434==  in use at exit: 0 bytes in 0 blocks 
==17434== total heap usage: 4 allocs, 4 frees, 64 bytes allocated 
==17434== 
==17434== All heap blocks were freed -- no leaks are possible 
==17434== 
==17434== For counts of detected and suppressed errors, rerun with: -v 
==17434== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2) 

Это должно помочь вам начать работу, и если вы узнаете хорошие привычки рано, управление памятью будет намного проще, так как вы получаете дальше в программирование на C.