Прогулка по двусвязному списку работает вечно (несмотря на очевидный терминатор NULL)

Question

Моя реализация двусвязного списка C не работает правильно.Боюсь, это может быть связано с моим беглым знанием указателей в C (происходящих из блаженного незнания интерпретируемых языков).Когда я запускаю этот код, кажется, что print_list() работает вечно, даже если он должен завершаться полем next, равным NULL.

#include<stdio.h>

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

void print_list(Node* head) {
    Node* cursor = head;
    while(cursor != NULL) {
        printf("data: %d\n", cursor->data);
        cursor = cursor->next;
    }
}

void push_node(Node* head, int data) {  
    Node node = {data, NULL, NULL};
    Node* cursor = head;
    while(cursor->next != NULL) {       
        cursor = cursor->next;
    }
    cursor->next = &node;
    node.prev = cursor;
}

int main() {
    Node root = {0, NULL, NULL};
    push_node(&root, 1);
    push_node(&root, 2);
    print_list(&root);
    return 0;
}

Что я делаюнеправильно??Любая помощь будет высоко ценится.

Answer 1

Программа работает вечно, потому что ваш вызов push-узла помещает объявленный узел в стеке в список дважды.Вы используете два имени для одной и той же вещи:

cursor->next = &node;

указывает на узел стека и создает условия для бесконечного цикла.Что происходит после второго вызова этого цикла (в push_node).

while(cursor->next != NULL) {
    printf("ptr: %p -> %p\n",cursor,cursor->next); //add this
    cursor = cursor->next;
}

Добавьте к отладке значение указателя и вы увидите, что происходит,

while(cursor != NULL) {
    printf("ptr: %p, data: %d\n",cursor,cursor->data); //change this
    cursor = cursor->next;
}

.

Answer 2

В push_node вы создаете новый узел в стеке, после того как push_node возвращает, что память больше не читается без вызова неопределенного поведения (включая бесконечные циклы).Вы можете использовать malloc внутри push_node, но, вероятно, не стоит, если вы не создадите огромный список.Вам также нужно будет отслеживать память и free правильно позже.Если вы не создаете массивный список, вы можете просто создать вместо него узлы в main, с минимальными изменениями в вашем коде:

#include<stdio.h>

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

void print_list(Node* head) {
    Node* cursor = head;
    while(cursor != NULL) {
        printf("data: %d\n", cursor->data);
        cursor = cursor->next;
    }   
}

void push_node(Node* head, Node* new) {
    Node* cursor = head;
    while(cursor->next != NULL) {    
        cursor = cursor->next;
    }   
    cursor->next = new;                                                                                                                               
    new->prev = cursor;
}

int main() {
    Node root = {0,NULL,NULL};
    push_node(&root, &(Node){ 1, NULL, NULL }); 
    push_node(&root, &(Node){ 2, NULL, NULL }); 
    print_list(&root);
    return 0;
}

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

Answer 3

вместо создания локальных переменных в функции push вы должны использовать динамически распределенную память, использовать malloc для выделения & free для ее освобождения перед выходом из main, или, что еще лучше, вы можете использовать calloc, работает так же, как mallocно заполняет выделенную память нулями, так что вам не нужно заботиться о заполнении нулями, подтверждение концепции:

void push_node(Node* head, int data){
    Node* node = calloc(sizeof(Node), 1);
    node->data = data;
    Node* cursor = head;
    while(cursor->next != NULL) {       
        cursor = cursor->next;
    }
    cursor->next = node;
    node->prev = cursor;
}

и в вашем main перед возвратом вы должны освободить выделенную память, функция должна быть похожа на вашу printфункция, но вместо того, чтобы печатать данные, вам нужно освободить данный элемент, пока вы не дойдете до конца, подтверждение концепции:

void free_list(Node* head){
   if(head){
       free_list(head->next);
       free(head);
   }
}

вызовите free_list в вашем списке перед выходом

Answer 4

Ваш код не работает, потому что Node node = { data, NULL, NULL }; создает локальную переменную node, ограниченную функцией push_node.Как только эта функция возвращается, вы используете локальный адрес, который не определен.Вместо этого используйте malloc или calloc для выделения пространства для узла.

Кроме того, ваша функция push_node неправильно обрабатывает случай, когда указатель head равен NULL.Есть несколько исправлений для этого.Один из способов - проверить NULL и, если это так, вернуть новый указатель как новый head.

Кроме того, вы должны написать функцию для удаления вашего списка, когда закончите.

Node *push_node(Node* head, int data) 
{  
    Node *node = malloc(sizeof(*node));
    node->data = data;
    node->prev = node->next = NULL;
    Node* cursor = head;
    if (cursor == NULL)
    {
        head = node;
    }
    else
    {
        while(cursor->next != NULL) {       
            cursor = cursor->next;
        }
        cursor->next = node;
        node->prev = cursor;
    }
    return head; 
}   

void free_list(Node *head) {
    if(head != NULL)
    {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main()  {
    Node *root = NULL;
    root = push_node(root, 1);
    root = push_node(root, 2);
    print_list(root);
    free_list(root);
    return 0; 
}

Answer 5

Вы не можете создать узел таким способом

Node node = { data, NULL, NULL };

Он создаст узел, используя стековую память, которая будет освобождена после возврата из функции.Вы должны использовать malloc() для выделения памяти кучи.

void push_node(Node* head, int data) {
    Node *node = malloc(sizeof(*node));
    if (node == NULL) {
        printf("memory error\n");
        return;
    }
    node->data = data;
    node->next = node->prev = NULL;

    Node* cursor = head;
    while (cursor->next != NULL) {
        cursor = cursor->next;
    }
    cursor->next = node;     // note the changes here
    node->prev = cursor;     //
}