C 列表的实现

Question

我使用以下代码来实现我自己的列表版本，以帮助我理解和掌握指针的概念。但是这段代码有错误，我不知道哪里出了问题？

#include <stdio.h>

typedef struct node
{
    int n;
    struct node* next;
} node;

int main(void)
{
    int i;
    node item;
    item.n = 0;
    item.next = NULL;
    node* list = &item;
    node* new_node = NULL;
    node* old_node = &item;

    while (1 == 1)
    {
        // get int from user
        scanf("%i", &i);

        if (i < 0)
        {
            break;
        }
        else
        {
            // Create new node
            node new_item;
            new_node = &new_item;

            // Set the value of new node
            new_node->n = i;
            new_node->next = NULL;

            // Point old node to new node
            old_node->next = new_node;

            // Swap nodes
            old_node = new_node;
            new_node = NULL;
        }

    }

    // Print the list
    node* pointer = list;
    int count = 1;
    while (pointer->next != NULL)
    {
        printf("Item %i %p: %i\n", count, pointer, pointer->n);
        pointer = pointer->next;
        getchar();
    }
}

我正在使用上面的代码创建我自己的列表实现。问题是当我尝试打印列表时，它进入无限循环。谁能指出我哪里错了？

Answer 1

您似乎正在尝试构建一个前向链表，同时保留插入顺序。代码中最明显的问题是:

• 无限 while 循环条件
• 在列表中使用自动变量来表示动态节点。

这两个问题都是必须解决的。前者可以通过简单地修改 while 循环来解决:(a) 检查 scanf 执行的结果(您应该始终这样做)，以及 (b) 检查i 的范围。因此，

while (scanf("%i", &i) == 1 && i >= 0)
{
     ... use i here
}

关于第二个问题，这就变得更麻烦了。使用内存管理函数 malloc 和 free 进行动态分配可能是正确的。下面介绍了执行此操作的实现，并且使用指针到指针来简化前向链接:

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

typedef struct node
{
    int n;
    struct node* next;
} node;

int main()
{
    // builds the list. uses a pointer-to-pointer that holds
    //  the address of the next pointer to populate wih a
    //  dynamic node allocation. initially it holds the
    //  addres of our list head pointer.

    node *list = NULL;  // list head pointer
    node **pp = &list;
    int i;

    while (scanf("%i", &i) == 1 && i >= 0)
    {
        *pp = malloc(sizeof **pp);
        if (*pp == NULL)
        {
            perror("Failed to allocate node");
            exit(EXIT_FAILURE);
        }

        (*pp)->n = i;
        pp = &(*pp)->next;
    }
    *pp = NULL; // terminates the list with NULL next value

    // print the list
    const node* pointer = list;
    for (i=1; pointer; ++i)
    {
        printf("Item %i %p: %i\n", i, pointer, pointer->n);
        pointer = pointer->next;
    }

    // free the list
    while (list)
    {
        void *victim = list;
        list = list->next;
        free(victim);
    }

    return EXIT_SUCCESS;
}

示例输入

1 3 2 4 3 5 -1

示例输出

Item 1 0x100300000: 1
Item 2 0x100300010: 3
Item 3 0x100300020: 2
Item 4 0x100300030: 4
Item 5 0x100300040: 3
Item 6 0x100300050: 5