遍历双向链表永远运行（尽管明显的 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

您不能以这种方式创建节点

Node node = { data, NULL, NULL };

它将使用堆栈内存创建节点，一旦函数 returns 将被释放。您需要使用 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;     //
}

Answer 2

而不是在 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;
}

并且在 return 之前的 main 中你应该释放分配的内存，函数应该类似于你的 print 函数但是你需要释放给定元素而不是打印数据直到你结束，概念验证：

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

退出前在您的名单上致电 free_list

Answer 3

您的代码不起作用，因为 Node node = { data, NULL, NULL }; 创建了一个作用域为函数 push_node 的局部变量 node。一旦该函数 returns，您将使用局部范围外的地址，这是未定义的行为。相反，使用 malloc 或 calloc 为节点分配 space。

此外，您的 push_node 函数无法正确处理 head 指针为 NULL 的情况。有几个修复方法。一种方法是检查 NULL，如果是，return 新指针作为新的 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 4

在 push_node 中，您正在堆栈上创建新节点，在 push_node returns 之后，如果不调用未定义的行为（包括无限循环），内存将不再可读。您可以在 push_node 中使用 malloc，但您可能不应该这样做，除非您要创建一个巨大的列表。您还需要跟踪内存并在以后正确 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 5

程序将永远运行，因为您对 push node 的调用将在堆栈上声明的 Node 两次放入列表中。您对同一事物使用了两个名称，

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

.

遍历双向链表永远运行（尽管明显的 NULL 终止符）

Walking through doubly linked list runs forever (despite apparent NULL terminator)

c

doubly-linked-list