C 中链表的实现失败

Question

我不明白为什么这个程序不工作，元素没有按预期插入到列表中。

每次我在调试的时候，我看到在'insert'方法之后转到main方法时，Linked List还是空的，我不明白为什么，因为我认为它应该很好，因为我正在使用指针（这似乎是 'Dangling Pointer' 的情况，但如果是，我不明白为什么）。

也许我应该使用双星 (**)？如果是，为什么在数组中无关紧要？

这里是源代码：

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

struct A{
    int val;
    struct A* next;
} A;

void insert(struct A* L, int newVal) {

    if (L == NULL) {

        L = (struct A*) malloc(sizeof(struct A));
        L->val = newVal;
        L->next = NULL;
    }

    else {

        struct A* p = L;

        while (p->next != NULL) {

            p = p->next;
        }

        p->next = (struct A*) malloc(sizeof(struct A));
        p->next->val = newVal;
        p->next->next = NULL;
    }
}


void printA(struct A* printed) {

    struct A* p = printed;

    while (p != NULL) {
        printf("%d\n", p->val);
        p = p->next;
    }
}


int main() {

    struct A* L = NULL;

    insert(L, 1);
    printf("1 success\n");

    insert(L, 2);
    printf("2 success\n");

    insert(L, 3);
    printf("3 success\n");

    insert(L, 4);
    printf("4 success\n");

    insert(L, 5);
    printf("5 success\n");

    printf("\n\n\n");

    printA(L);

    return 0;
}

谢谢。

Answer 1

insert 函数的第一个参数是指向结构的指针。当您传递结构时，insert 收到地址，并创建指向同一位置的本地指针。为了更改实际结构（来自 main）指向的内容，您必须传递一个双指针。

下面写的是需要修改的部分：

void insert(struct A** L, int newVal) {

    if (*L == NULL) {

        *L = (struct A*) malloc(sizeof(struct A));
        (*L)->val = newVal;
        (*L)->next = NULL;
    }

    else {

        struct A* p = *L;

        ...
        ...
        ...
    }
}    

int main() {

    struct A* L = NULL;

    insert(&L, 1);
    printf("1 success\n");

    ...
    ...
    ...

    printA(L);

    return 0;
}

另一种方法是保留单个指针，但将 insert 的 return 值更改为 struct A*。您只需将 return 值分配给您的 main 结构，如下所示：

struct A *insert(struct A* L, int newVal) {

    if (L == NULL) {

        L = (struct A*) malloc(sizeof(struct A));
        L->val = newVal;
        L->next = NULL;

        return L;
    }

    else {
        ...
    }

    return L;
}

int main() {

    struct A* L = NULL;

    L = insert(L, 1);
    ...
    return 0;
}

此外，您的打印功能没有移动到任何地方。添加行 p = p->next;

void printA(struct A* printed) {

    struct A* p = printed;

    while (p != NULL) {
        printf("%d\n", p->val);
        p = p->next;
    }
}

C 中链表的实现失败

Failed implementation of a Linked List in C

c

linked-list

dangling-pointer