c++ - 我的链表节点删除功能导致程序的其他部分崩溃

Question

我在一些作业中遇到了一个奇怪的错误，它让我用链表创建一个堆栈。我程序中的所有函数都运行良好，即使在开始时我没有节点，或者在删除一些节点之后也是如此。但是当我创建节点并将它们全部删除以便我回到零时，每个函数都会导致崩溃。我已经尝试研究这个问题，但我找到的解决方案看起来与我已经得到的几乎相同，所以显然有一些关键的东西我没有看到。

这是节点删除函数(我怀疑是这一切的罪魁祸首)

void remove(node** root)
{   
    node* temp = *root;
    node* previous = 0;
    if(*root)
    {
        while((*root)->next)
        {
            previous = *root;
            *root = (*root)->next;
        }
        delete *root;
        *root = temp;
        if(previous)
        {
            previous->next = 0;
        }
    }
    else
    {
        std::cout<<"cannot delete items from empty list\n";
    }
}

这里是节点插入函数

void insert(node** root)
{
    node* temp = *root;
    if(*root)
    {
        while((*root)->next)
        {
            (*root) = (*root)->next;
        }
        (*root)->next = new node;
        (*root)->next->data = getnum();
        (*root)->next->next = 0;
        *root = temp;
    }
    else
    {
        (*root) = new node;
        (*root)->data = getnum();
        (*root)->next = 0;
    }

}

我相当确定问题出在我链接的代码中的某处，但以防万一，这是完整作业的 pastebin http://pastebin.com/AWtG4qjD

Answer 1

remove 实现不正确。假设列表只有一个元素。在这种情况下，执行 delete *root; 后 temp 将指向“不存在的内存”但是你正在做的是 *root = temp;这样你就可以让 root 指向无效的节点。这会导致后来的奇怪行为使您的实现正确的可能方法是:

void remove(node** root)
{
    //TODO: your code here
    node* temp = *root;
    node* previous = 0;
    if(*root)
    {
        while((*root)->next)
        {
            previous = *root;
            *root = (*root)->next;
        }
        delete *root;
        if(previous)
        {
            *root = temp;
            previous->next = 0;
        }
        else {
            *root = NULL;
        }
    }
    else
    {
        std::cout<<"cannot delete items from empty list\n";
    }
}

但我不建议你用根指针迭代列表。定义一些迭代器并用它寻找结尾而不是改变 *root