2

我看过这个问题：

其中使用以下代码添加元素oa列表：C链表在末尾插入节点

int addNodeBottom(int val, node *head){

    //create new node
    node *newNode = (node*)malloc(sizeof(node));

    if(newNode == NULL){
        fprintf(stderr, "Unable to allocate memory for new node\n");
        exit(-1);
    }

    newNode->value = val;
    newNode->next = NULL;  // Change 1

    //check for first insertion
    if(head->next == NULL){
        head->next = newNode;
        printf("added at beginning\n");
    }

    else
    {
        //else loop through the list and find the last
        //node, insert next to it
        node *current = head;
        while (true) { // Change 2
            if(current->next == NULL)
            {
                current->next = newNode;
                printf("added later\n");
                break; // Change 3
            }
            current = current->next;
        };
    }
    return 0;
}

为什么 head 作为节点传递，*head而不是node **head我们要在内部更改它并且我们希望将更改传播到函数外部？我在这里想念什么？

4

3 回答 3

3

head永远不会在此函数中直接修改。只有head->next被分配给另一个值。因此，您不需要使用指向指针的指针。

于 2013-02-13T18:01:27.870 回答
0

从根本上说，没有理由不能。事实上，这是 Linus Torvalds 指出的表现出对指针的精通的事情之一。相关问题：使用指针从单链表中删除项目

于 2013-02-13T18:03:36.077 回答
0

您可能可以使用指向指针的指针使该代码更加优雅，如下所示：

int addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    if(*link == NULL){
        printf("added at beginning\n");
    }
    else
    {
        while (*link)
            link = &(*link)->next;
        printf("added later\n");
    }
    *link = newNode;
    return 0;
}

...
addNodeBottom(some_val, &head->next);

......有这种效果。虽然不是最大的区别，但可能更好一点。如果列表不使用虚拟节点作为头部并且在添加到列表的开头与结尾时不需要打印出来，则会更简单。在这种情况下，我们可以简单地做：

void addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    while (*link)
        link = &(*link)->next;
    *link = newNode;
}
...
addNodeBottom(some_val, &head);

...在没有特殊情况需要处理的情况下，它开始看起来好多了。如果绝对需要使用这种虚拟头并打印出插入是否在列表的前面，也许返回一个指向新节点的指针（例如，失败时为空）会有所帮助，例如所以：

node* addNodeBottom(int val, node **link){
    node *newNode = ...;
    ...
    while (*link)
        link = &(*link)->next;
    *link = newNode;
    return newNode;
}
...
if (addNodeToBottom(some_val, &head->next) == head->next)
     printf("added at beginning\n");
else
     printf("added later\n");

如果我们要在内部更改 head 并且希望将更改传播到函数外部，为什么 head 作为 node *head 而不是 node **head 传递？

正如其他人指出的那样，这是一种不寻常的链表，其中它head是某种虚拟节点或其他东西。它永远不会在该函数中被修改，只有head->next，所以更改head将传播并导致外部副作用。

我从来不理解那些类型的链表实现在 C 和 C++ 等语言中存储虚拟节点的意义，因为它们不会减少特殊情况。他们只是无缘无故地浪费内存。它们对于不允许多于一级间接的语言可能有意义，但在具有指针的语言中根本没有意义。也许实现该链表的人最初更多来自没有指针的语言背景，例如 Java 或 Python 之类的。在这些语言中，这种带有虚拟节点的链接列表可能并不罕见，作为一种解决方法，可以解决语言不允许指向指针（或引用引用）的指针来避免if此处和那里的某些语句这一事实。

于 2018-01-04T14:44:18.840 回答