Как сделать односвязный список на основе входных данных

Question

Я только изучаю связанные списки и хочу создать один с вводом с консоли, но почему-то это не работает.

#include <stdio.h>
#include <stdlib.h>

typedef struct datatype Node;
struct datatype {
    int data;
    Node *next;
};

int main() {

    int i,n;
    Node *node[50];

    printf("Number of intergers: ");
    scanf("%d",&n);
    for(i=0; i<n; i++) {
        printf("Enter interger one by one: ");
        scanf("%d",&node[i]->data);
        node[i]->next=node[i+1];
    }
    
    for(i=0;i<n;i++)
    printf("%d->",node[i]->data);
}

Answer 1

Вы должны выделить память для отдельных узлов связанного списка. Вместо этого вы выделяете память для 50 указателей на отдельные узлы, но не для самих узлов.

Я предлагаю вам создать стандартный связанный список и использовать функцию malloc для отдельных узлов, например:

typedef struct Node {
    int data;
    struct Node *next;
} Node;

int main( void )
{
    //this pointer always points to the first element, or NULL if there is no first element
    Node *pRoot = NULL;

    //this pointer always points to the NULL pointer at the end of the list, which is, when the list is empty, the root pointer
    Node **ppNext = &pRoot;

    Node *pCurrent;
    int retval, n;

    //ask user for total number of data elements
    printf( "Number of integers: " );
    retval = scanf( "%d", &n );
    if ( retval != 1)
    {
        fprintf( stderr, "scanf failed!\n" );
        goto cleanup;
    }

    //build the list from user input
    for ( int i = 0; i < n; i++ )
    {
        //allocate memory for new node
        pCurrent = malloc( sizeof( Node ) );
        if ( pCurrent == NULL )
        {
            fprintf( stderr, "malloc failed!\n" );
            goto cleanup;
        }

        //ask user for individual data elements
        printf( "Enter integer one by one: " );
        retval = scanf( "%d", &pCurrent->data );
        if ( retval != 1 )
        {
            fprintf( stderr, "scanf failed!\n" );
            free( pCurrent );
            goto cleanup;
        }
        pCurrent->next = NULL;

        //link new node to linked list and update ppNext
        *ppNext = pCurrent;
        ppNext = &pCurrent->next;
    }

    //print the list
    for ( pCurrent = pRoot; pCurrent != NULL; pCurrent = pCurrent->next )
    {
        printf( "%d\n", pCurrent->data );
    }

cleanup:

    //free the linked list
    for ( pCurrent = pRoot; pCurrent != NULL; )
    {
        Node *tmp = pCurrent;
        pCurrent = pCurrent->next;
        free( tmp );
    }

    return 0;
}

Обратите внимание, что в моем коде перед использованием значения, записанного в scanf, я проверяю возвращаемое значение scanf. Это необходимо, потому что функция может дать сбой и не записать никакого значения, например, когда пользователь вводит буквы вместо цифр. См. Эту страницу для получения дополнительной информации:

Руководство для новичков от scanf()

Answer 2

Основываясь на комментарии Андреаса, вот комментированная и безопасная для памяти реализация. Вам не обязательно использовать mallo c и бесплатно; вместо этого вы могли бы иметь фиксированный пул памяти:

#define MAX_NODE_SIZE 256

...

Node node[MAX_NODE_SIZE]; 

с последующей проверкой, чтобы убедиться, что пользователь никогда не ставит n больше MAX_NODE_SIZE. Однако, если вы попытаетесь реализовать вставку и удаление списков, все будет сложно. Кроме того, использование индекса «i» для итерации по связному списку лишает смысла наличие связанного списка.

Вот версия malloc / free:

#include <stdio.h>
#include <stdlib.h>

typedef struct datatype Node;
struct datatype {
    int data;
    Node *next;
};

int main() {
    //Allocate the root node
    Node *rootnode=malloc(sizeof(Node));
    rootnode->data=0; rootnode->next=NULL; 
    Node *currentnode=rootnode;

    //Populate n and check for validity
    printf("Number of integers: ");
    int n;
    scanf("%d",&n);
    if(n<=0){
        printf("List must have a nonzero/nonnegative number of elements.\n");
        return 1;
    }

    //Populate the list
    for(int i=0; i<n; i++) {
        printf("Enter integer one by one: ");
        scanf("%d",&currentnode->data);
        //If there is more data...
        if(i!=n-1){
            //Allocate room for the data
            currentnode->next=malloc(sizeof(Node));
            //Initialize things correctly
            currentnode->next->data=0;
            currentnode->next->next=NULL;
            //Step to the next node.
            currentnode=currentnode->next;
        }
    }

    //Print the list
    currentnode=rootnode;
    do {
        printf("%d",currentnode->data);
        if(currentnode->next!=NULL)
            printf(" -> ");
        else
            printf("\n");
    } while((currentnode=currentnode->next)!=NULL);

    //Deallocate the list
    currentnode=rootnode;
    while(currentnode!=NULL){
        Node *next=currentnode->next;
        free(currentnode);
        currentnode=next;
    }

    return 0;
}

Пример вывода :

user@desktop:~$ ./a.out
Number of integers: 3
Enter integer one by one: 1
Enter integer one by one: 2
Enter integer one by one: 3
1 -> 2 -> 3