在链表实现中获取运行时错误

Question

我正在尝试实现单链表的插入功能。我的实现函数应该在头部位置而不是尾部插入新节点。当我尝试编译此 C++ 代码时出现运行时错误。

这是我的代码：

#include <iostream>

using namespace std ;

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

struct node *head = NULL;

// inserting newnode at head position rather than tail
void insert (struct node* root , int idata) {
    if (root == NULL){
        root->next = NULL;
        root->data = idata;
    }
    
    else {
        struct node * newnode = (struct node *) malloc (sizeof (struct node) ) ;
        newnode->data = idata ;
        newnode->next = root ;
        root = newnode ;

    }

}


int main () {
    insert (head, 20) ;

    return 0;
}

但我无法理解为什么会出现编译错误。请帮忙!!

Answer 1

在 insert 函数

的 if 块中更改以下内容

if (root == NULL){
        root = new node;  //this must be added to allocate memory for root node.
        root->next = NULL;
        root->data = idata;
    }

Answer 2

我找不到任何编译器错误。但是有几个逻辑错误

void insert (struct node* root , // the root node is passed by reference
                                 // the pointer is not. So when you change where
                                 // root points, the caller won't know
             int idata) {
    if (root == NULL){
        root->next = NULL; // root points at NULL, a special parking location that, 
                           // on every target I've coded for, sits in a reserved memory
                           // area that will kill a program that reads from or writes 
                           // to it. Technically this would be  undefined behaviour, 
                           // but the results are extremely reliable to help you find 
                           // bugs.
        root->data = idata;
    }
    
    else {
        struct node * newnode = (struct node *) malloc (sizeof (struct node) ) ;
                       // malloc is almost always the wrong choice in C++
                       // use new. malloc requires you to be certain you 
                       // got the size right and does not call constructors. 
                       // It gives you memory, not objects.
        newnode->data = idata ;
        newnode->next = root ;
        root = newnode ;

    }

}

现在，如果您总是想在 root 处插入，则无需 if。节点去的地方只有一个

void insert (struct node*& root , //reference to pointer
             int idata) {
    root = new node {idata, root}; // this is aggregate initialization
}

或

node * insert (struct node* root , 
             int idata) {
    return new node {idata, root};
}

首先，调用者作为 root 提供的 node 指针被更新为新的 node，后者又指向旧的 root node。在第二个中，一个新的 node 被分配并指向 root 并且返回给调用者。来电者使用此版本类似

head = insert(head, 20);

Documentation for aggregate initialization

Documentation for Undefined Behaviour

Answer 3

下一行引起的错误；

struct node *head = NULL;

首先在 C++ 中，您不需要 struct 声明对象。

其次，您可以在 main 局部范围内声明 head 以避免全局污染。

第三，你的主要原因error，你必须分配内存才能访问任何对象。

因此，将 main 和 insert 函数更改为以下内容。

int main () 
{
    node* head = NULL;
    insert(&head, 20) ;
    insert(&head, 30 );

    delete head;
    return 0;
}

并且在insert函数中，使用双指针传递head的address，所以你在函数内部所做的改变会影响实际的head.

void insert (node** root , int idata) {
        if ( (*root) == NULL )
        {
            (*root) = new node;
            (*root)->data = idata;
            (*root)->next = NULL;
        }
        else
        {        
            struct node * newnode = (struct node *) malloc (sizeof (struct node) ) ;
            newnode->data = idata ;
            newnode->next = *root ;
            *root = newnode;
        }

}

在链表实现中获取运行时错误

Getting runtime error in linked list implementation

c++

linked-list

singly-linked-list