为什么我打印单链表时会有一个假节点

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

代替这个定义

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 );

请注意，您还必须编写一个函数，该函数将释放为列表分配的所有内存。

Answer 2

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

最简单的解决方案是什么?考虑到你的代码更接近于C而不是c++，最初根本不分配内存，而只是创建一个指针并将其初始化为NULL :

node *head = NULL;

---

在c++中，一个正确的方法是根本不使用malloc，而是使用c++操作符new，并在初始化它的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

在设计中有一个虚拟节点(head本身)。所以print函数需要跳过这个虚拟节点。