在C语言中向链表的前面添加元素

Question

我正在遵循斯坦福大学CS教育图书馆的链表教程。我正试图将一个新列表添加到我的链表的前面，它不工作基于我从下面定义的Length函数得到的打印输出。

#include <stdio.h>
#include <stdlib.h>
//build new struct for node
//node has value and points to next node
struct node{
    int value;
    struct node *next;
};
//declare a new struct node that contains 3 nodes (head, middle, tail)
struct node *Build123(){
    struct node *head, *middle, *tail = NULL;
    head = malloc(sizeof(struct node));
    middle = malloc(sizeof(struct node));
    tail = malloc(sizeof(struct node));
    head->value = 3;
    head->next = middle;
    middle->value = 5;
    middle->next = tail;
    tail->value = 9;
    tail->next = NULL;
    return head;
};
//declare a function Length and variable counter to calculate size of list
int Length(struct node *head) {
    int count = 0;
    struct node *iterator = head;
    while (iterator != NULL) {
        count++;
        iterator = iterator->next;
    }
    return count;
}
//declare function Push to add new lists that would be added to the front
void Push (struct node **headRef, int value){
    struct node *newNode;
    newNode = malloc(sizeof(struct node));
    newNode->value = value;
    newNode->next = *headRef;
}
int main(){
    //instantiate the 3 element linked list named beast
    struct node *beast = Build123();
    //add 2 elements to the front of the linked list via pass by reference
    Push(&beast, 6);
    Push(&beast, 12);
    //calculate length of linked list after elements have been added
    int len = Length(beast);
    //print length of linked list to screen 
    printf("%dn",len);
    return 0;
}

当我期望得到5时，我得到了3。你能帮我找到代码中的错误，使我无法获得我期望的值吗?尽管做了很多修补，我还是不明白为什么。谢谢你！

Answer 1

问题是，当您做Push(&beast, 6);之类的事情时，beast指向的是Push函数不变的。尽管Push向链表中添加了更多的元素，但当你稍后在beast上调用Length时，它会在beast最初拥有的同一节点上调用它——所以它完全不知道额外添加的节点。

在Push()的末尾，您需要这样做:

*headRef = newNode;

使beast正确指向列表的新起点

Answer 2

您不会在Push函数中修改headRef，因此您的列表头部实际上从未更改。beast始终指向它创建时要指向的原始节点。添加这一行:

*headRef = newNode;

在Push()中，您将设置

Answer 3

在push()方法的末尾，您必须添加:

*headRef = newNode

这是因为headRef应该总是指向链表中的第一个节点。