为什么打印单向链表时有一个虚拟节点？

Question

为什么我的代码打印了一个额外的节点（垃圾值）？我的代码有什么问题吗？让我如何解决它。

void push(node **head_ref,int value)  //function to insert a new node on front of the list
{
    node *new_node=(node*)malloc(sizeof(node));
    new_node->data=value;
    new_node->next=*head_ref;
    *head_ref=new_node;
}

void printll(node *head)    //function to print the list
{
    node *temp = head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
}

实际输出：
45 88 24 34 77 0

预期输出：
45 88 24 34 77

完整代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cassert>

using namespace std;

struct node
{
    int data;
    node *next;
};

void push(node **head_ref,int value)
{
    node *new_node=(node*)malloc(sizeof(node));
    new_node->data=value;
    new_node->next=*head_ref;
    *head_ref=new_node;
}

void printll(node *head)
{
    node *temp = head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }

}

int main()
{
    node *head= (node*)malloc(sizeof(node));
    push(&head,77);
    push(&head,34);
    push(&head,24);
    push(&head,88);
    push(&head,45);
    printll(head);
    printf("\n");
    return 0;
}

Answer 1

您的设计中有一个虚拟节点（head 本身）。所以打印函数需要跳过那个虚拟节点。

Answer 2

当您使用 malloc 分配内存时，内存不会以任何方式初始化，它的内容是 不确定。这意味着当您分配第一个节点（这是一个不需要的虚拟额外节点）时，它的 next 指针不为空，并且取消引用这个不确定的指针会导致 未定义的行为 .

最简单的解决方案？考虑到你的代码比 C++ 更接近 C，一开始不要分配内存，而是创建一个指针 并将其初始化为 NULL:

node *head = NULL;

One 在 C++ 中正确的做法是根本不使用 malloc，而是使用 C++ 运算符 new 并添加一个 constructor 到初始化它的 node 结构：

struct node
{
    node() : data(0), next(nullptr) {}
    node(int d, node* n) : data(d), next(n) {}

    int data;
    node* next;
};

void push(node** head_ref, int value)
{
    *head_ref = new node(value, *head_ref);
}

...

int main()
{
    node* head = nullptr;
    ...
}

现在您可以创建一个新节点，它将具有 0 的初始 value，并且其 next 指针将为空指针。您还可以如上所示，使用特定的 value 和 next.

创建并初始化一个新节点

_{[如果您的编译器不支持 C++11 nullptr 值，请将 nullptr 替换为 0]}

Answer 3

而不是这个定义

node *head= (node*)malloc(sizeof(node));

你应该写得简单

node *head = NULL;

或

node *head = nullptr; // C++

否则你的程序有未定义的行为，因为分配给头部的节点没有初始化。

此外，如果它是 C++ 程序，您应该使用运算符 new 而不是 C 函数 malloc。例如函数 push 看起来像

void push( node * &head_ref, int value )
{
    head_ref = new node { value, head_ref };
}

并称赞

push( head, 77 );

考虑到您还必须编写一个函数来释放列表的所有分配内存。

为什么打印单向链表时有一个虚拟节点？

Why there is a dummy node when I am printing a singly linked list?

c++

pointers

linked-list