使用递归创建链接列表

I want to create a linked list using recursion. After executing the code, I get only the value of the first node and rest are not being printed.

我想使用递归创建一个链表。执行代码后，我只得到第一个节点的值，其余的没有被打印。

#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;
    }   
}

I think the problem is when i call create(x-1);, but I am not sure. Is my logic correct? Can someone pin-point my mistake?

我认为问题是当我调用create（x-1）;,但我不确定。我的逻辑是否正确？有人可以指出我的错误吗？

3 个解决方案

#1

Try changing the logic,

尝试改变逻辑，

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);
}

You are not resetting the head correctly.

您没有正确重置头部。

Also good to check this implemetation out > http://geeksquiz.com/linked-list-set-1-introduction/

也很好检查这个实现> http://geeksquiz.com/linked-list-set-1-introduction/

#2

When you're doing this:

当你这样做时：

ptr=node->next;
ptr=node;

You're loosing your reference to the tail of the list, and therefore not adding node to the list. You should be doing this:

您正在丢失对列表尾部的引用，因此不会将节点添加到列表中。你应该这样做：

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

This points the next pointer of the current tail to the new node, then moves ptr down to the new tail.

这会将当前尾部的下一个指针指向新节点，然后将ptr向下移动到新尾部。

Also, the ptr->next=NULL at the end of the loop is unnecessary, since ptr is now the same as node, and you already did node->next = NULL.

此外，循环结束时的ptr-> next = NULL是不必要的，因为ptr现在与节点相同，并且您已经执行了node-> next = NULL。

#3

The significant error leading to your problem was your assignment of pointers in create(int). You were assigning the first pointer correctly, but then assigning NULL to all remaining pointers. There are several ways to handle this, but a clean and straightforward way is to only advance ptr=ptr->next within the else block as follows:

导致问题的重大错误是你在create（int）中指定了指针。您正确分配了第一个指针，但随后为所有剩余指针分配了NULL。有几种方法可以解决这个问题，但是一种干净而直接的方法是只在else块中推进ptr = ptr-> next，如下所示：

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

You are dynamically allocating memory, so this means you are responsible for tracking its use, preserving a pointer to the starting block of each allocation, and finally freeing the memory when it is no longer in use. Start now. Get in the habit of handling your memory cleanup whenever you allocate, and don't simply rely on the program exit to do it for you. While it may seem trivial now, when you begin handling functions with multiple allocations, etc., if you have not developed good habits in this regard, your code will likely leak memory like a sieve. A simple cleanup function could be nothing more than:

您正在动态分配内存，因此这意味着您负责跟踪其使用，保留指向每个分配的起始块的指针，最后在不再使用时释放内存。现在开始。养成在分配时处理内存清理的习惯，而不是简单地依赖程序退出来为你做。虽然现在看起来似乎微不足道，但是当你开始处理具有多个分配等的功能时，如果你在这方面没有养成良好的习惯，你的代码可能会像筛子那样泄漏内存。一个简单的清理功能只不过是：

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

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

The malloc issue. malloc returns the starting address for the block of memory allocated, there is no need to cast the return in C. When you are allocating memory for data types you have just declared, use the variable with sizeof instead of the datatype. e.g.:

malloc问题。 malloc返回分配的内存块的起始地址，不需要在C中转换返回。当您为刚刚声明的数据类型分配内存时，请使用sizeof而不是数据类型的变量。例如。：

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

instead of

代替

node = malloc (sizeof (NODE));

This will become apparent when dealing with pointers to pointers, etc. It makes far more sense to operate on your variable than it does to remember whether you are allocating for NODE* or NODE**. This is especially true when the allocation is many lines below the declaration in your code or when receiving the pointer in a function argument list.

在处理指针指针等时，这将变得很明显。操作变量比记住是否为NODE *或NODE **分配更有意义。当分配在代码中的声明下面多行或者在函数参数列表中接收指针时，尤其如此。

Additionally, you need to validate the return from malloc each time you allocate memory to insure you haven't exhausted the available memory. e.g.:

此外，每次分配内存时都需要验证malloc的返回值，以确保您没有耗尽可用内存。例如。：

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

Finally, putting it all together, one approach to your problem would be:

最后，总结一下，解决问题的方法之一是：

#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);
    }
}

Example

例

$ ./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

Use a Memory Checker

使用内存检查器

Regardless of your platform, it is good to use a memory checker, like valgrind on Linux to check for memory errors and insure you have freed all the memory you have allocated. A memory checker, not only provides a confirmation that all memory has been freed, it will also report on subtle errors in the way you attempt to access the memory you have allocated which can alert you to issues that can bite you later. It is simple to use, simply:

无论您的平台如何，最好使用内存检查程序，例如Linux上的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)

That should get you started, and if you learn the good habits early, managing memory will be a whole lot easier as you get further into programming in C.

这应该让你开始，如果你早点学习好习惯，随着你进一步用C语言编程，管理内存将会变得更加容易。