Указатель на начало связанного списка

Question

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

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

typedef struct node node_t;
struct node {
    int data;
    node_t* next;
};

void append(node_t *head, int data) {
    if (head == NULL) {
        node_t *node = (node_t*)malloc(sizeof(node_t*));
        node->data = data;
        node->next = NULL;
        head = node;
    } else {
        node_t *node = (node_t*)malloc(sizeof(node_t*));
        node->data = data;
        node->next = NULL;

        if (head->next == NULL) {
            head->next = node;
        } else {
            node_t *current = head;
            while (1) {
                if (current->next == NULL) {
                    current->next = node;
                    break;
                }
                current = current->next;
            }
        }
    }
}

int main(void) {
    node_t *head = NULL;

    append(head, 4);
    append(head, 6);
    printList(head);

    return 0;
}

Мой код ломается, когда я делаю head = node; Он не меняет значение head в main. Я думаю, что что-то упустил, но не уверен, что. Заранее спасибо

Answer 1

Вы передаете головку указателя по значению в функции append. Таким образом, функция имеет дело с копией переданного ей указателя. Изменение копии не влияет на исходный указатель. Либо передайте его по ссылке, либо верните обновленную головку из функции.

Первый подход намного лучше.

Функция может выглядеть следующим образом

int append( node_t **head, int data )
{
    node_t *node = malloc( sizeof( node_t ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = node;
    }

    return success;
}

Здесь демонстрационная программа.

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

typedef struct node node_t;
struct node
{
    int data;
    node_t *next;
};

int append( node_t **head, int data )
{
    node_t *node = malloc( sizeof( node_t ) );
    int success = node != NULL;

    if ( success )
    {
        node->data = data;
        node->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = node;
    }

    return success;
}

void printList( node_t *head )
{
    for ( ; head != NULL; head = head->next )
    {
        printf( "%d -> ", head->data );
    }

    puts( "null" );
}

int main(void) 
{
    node_t *head = NULL;

    const int N = 10;

    for ( int i = 0; i < N; i++ )
    {
        append( &head, i );
    }

    printList( head );

    return 0;
}

Ее вывод

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null

Answer 2

Это не меняет значение головы в главном

И не должно! Если значение head в main изменилось при вызове append(), то при вызове printList() будет напечатан только последний узел в списке, и у вас не будет возможности обратиться к другим узлам в списке .

Причина 1011 *, что head не изменилась, хорошо объясняется в других ответах, т. Е. Вы передаете указатель головы по значению. Важно понимать, что head в main() и параметр head в append() - это совершенно разные переменные.

Answer 3

Вы передаете заголовок списка по значению, поэтому функция append не может обновить указатель в пространстве вызывающего абонента, который имеет одно и то же имя head. Аргумент head в append является отдельной переменной от локальной переменной head в main.

Вы должны либо передать указатель на головной узел, чтобы append мог изменить его:

void append(node_t **headp, int data) { ...

Или вернуть вызывающему, возможно, измененный головной узел, который сохранит его обратно в свою собственную переменную:

node_t *append(node_t *head, int data) { ...

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

Вот модифицированная версия с первым подходом:

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

typedef struct node node_t;
struct node {
    int data;
    node_t *next;
};

// append a new node to the list, return 0 for success, -1 for allocation failure
int append(node_t **headp, int data) {
    node_t *node = (node_t *)malloc(sizeof(node_t *));
    if (node == NULL)
        return -1;
    node->data = data;
    node->next = NULL;
    if (*headp == NULL) {
        *headp = node;
    } else {
        node_t *current = *headp;
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = node;
    }
    return 0;
}

int main(void) {
    node_t *head = NULL;

    if (append(&head, 4) || append(&head, 6))
        printf("node allocation error\n");
    printList(head);
    // should free the list
    return 0;
}

Answer 4

Кажется, проблема в том, что вы передаете указатель head на значение , поэтому, когда вы изменяете его внутри append(), вы изменяете только локальную переменную в этой функции - в отличие от переменная head в main().

Это может немного сбивать с толку - если вы передаете указатель, как вы можете передавать по значению? Ну, возможно, вы захотите взглянуть на этот вопрос:

Передача аргумента указателя, передача по значению в C ++?

... и нижняя строка что append() нужно взять node_t** head, и вы позвоните с основного с append(&head, 4);. Посмотрите работает на Coliru .

Также вы выделяете sizeof(node_t*) на узел. Вы должны выделить sizeof(node_t).