6

我正在关注关于链接列表的斯坦福 CS Ed 图书馆教程。我正在尝试在链接列表的前面添加一个新列表，但根据我从下面定义的 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("%d\n",len);
    return 0;
}

我得到3，当我期望得到5。请您帮我找出代码中阻止我获得期望值的错误吗？尽管进行了很多修补，但我无法弄清楚为什么。谢谢！

4

3 回答 3

4

问题在于，当您执行类似于指向Push(&beast, 6);什么的操作时，函数 Push 不会改变。beast尽管 Push 将更多元素添加到链表中，但当您稍后在 beast 上调用 Length 时，它会在与 beast 最初在开始时拥有的同一节点上调用它 - 所以它完全不知道额外添加的节点。

在 Push() 结束时，你需要这样做：

*headRef = newNode;

这样这beast将正确地指向列表的新开始。

于 2013-04-09T04:06:29.123 回答
3

您不会headRef在Push函数中进行修改，因此您的列表头部实际上永远不会改变。 beast始终指向它被创建指向的原始节点。添加这一行：

*headRef = newNode;

在Push()中，您将被设置。

于 2013-04-09T04:06:21.513 回答
1

在push()方法结束时，您必须添加：

*headRef = newNode

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

于 2013-04-09T04:23:05.097 回答