C语言 插入链表的末尾

Question

我写了一个函数，用于在链表的末尾插入一个节点。当我运行程序以及调用此函数时，程序会停止工作。

这是函数：

void insert(node **head, int x) {
    node *new = malloc(sizeof(node));
    new->data = x;
    new->next = NULL;
    node *temp = *head;
    while (temp != NULL) {
        temp = temp->next;
    }
    temp->next = new;
}

谁能说出哪里出了问题？

Answer 1

1. 当while循环终止时temp NULL。所以temp -> next会产生Segmentation Fault.

   而不是while(temp!=NULL)您应该使用 while(temp->next!=NULL) .

2. 如果head NULL怎么办？(空链表(
   为此，请检查head是否NULL。

3. 另外，如果malloc失败了怎么办？

所以解决方案将是：

node *insert(node **head, int x)
{
    node *new = (node *) malloc(sizeof(node));        
    if (new == NULL) {
        printf("Memory allocation failed!n");
        exit(1);
    }
    new->data = x;
    new->next = NULL;
    node *temp = *head;
    if (temp == NULL) {
        *head = new;
    }
    else {
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = new;
    }
    return new;
}

Answer 2

你的代码有两个问题：

• temp指针被推到列表的末尾，直到它变得NULL，到那时存储指向其next成员的新指针为时已晚，并尝试调用未定义的行为(Segmentation fault在您的系统上(。
• 如果列表为空，则即使temp->next == NULL时停止了循环，也无法以这种方式存储新项目。

还希望避免使用 C++ 关键字来命名 C 代码中的变量，因为如果需要这样做，会使将代码迁移到 C++ 变得更加困难。

此外，测试malloc是否失败并在失败时返回指向新节点或NULL的指针会更正确。

这是更正后的版本：

node *insert(node **head, int x) {
    node *new_node = malloc(sizeof(node));
    if (new_node != NULL) {
        new_node->data = x;
        new_node->next = NULL;
        node *temp = *head;
        if (temp == NULL) {
            *head = new_node;
        } else {
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = new_node;
        }
    }
    return new_node;
}

您还可以使用指针到指针来迭代列表：它稍微复杂一些，但更短，因为您只有一个测试来查找存储new指针的位置：

node *insert(node **head, int x) {
    node *new_node = malloc(sizeof(node));
    if (new_node != NULL) {
        new_node->data = x;
        new_node->next = NULL;
        node **np = head;
        while (*np) {
            np = &(*np)->next;
        }
        *np = new_node;
    }
    return new_node;
}

Answer 3

使用 node** 进行迭代。所以列表是否为空并不重要。迭代，直到找到next NULL的节点。您可以直接在目标上分配内存。

void insert( node **head, int x){
    node **ptr_new = head;
    while( *ptr_new != NULL ){
        ptr_new = &((*ptr_new)->next);
    }
    // now temp refers either to head or to next of the last node.
    *ptr_new = malloc( sizeof(node) );
    if ( *ptr_new != NULL )
    {
        (*ptr_new)->next = NULL;
        (*ptr_new)->data = x;
    }
}

与原始代码相反，您有一个指向指针的指针，其中存储了新节点的地址。在您的原始版本中，您在未NULL temp时进行了迭代。

while (temp != NULL) {
    temp = temp->next;
}

在此之后while循环temp==NULL，因为这是循环的终止条件。因此，您的程序在这里停止工作temp->next = new;