删除双向链表中的功能故障

Question

我从双向链表中删除节点的功能是向列表添加（覆盖？）值，这些值在打印列表时出现。

下面列出了 main、remove 和 print 函数的代码。当前代码与其输出之间的预期输出和相关性也如下所示。

主要代码

main中调用add函数，将参数中的整数作为节点添加到链表中。添加功能和打印功能一样有效。

int main()
{
    LinkedList aList;

    aList.add(3);
    aList.add(10);
    aList.add(1);
    aList.add(7);
    aList.add(9);
    aList.add(12);
    aList.printAscending();
    aList.printDescending();
    aList.remove(3);
    aList.remove(1); //The integer to be removed with this line ends up in the output
    aList.remove(7);
    aList.remove(12);
    cout << "remove operations should be complete" <<endl;
    aList.printAscending();
    aList.printDescending();

    return 0;
}

删除函数的代码

bool LinkedList::remove(int val) //parameter contains value to be removed
{
    bool removed = false;
    Node* newNode = new Node;
    newNode->data = val;
    newNode->next = NULL;
    newNode->prev = NULL;

    Node* curr = head;
    while(curr)
    {
        if(curr->data == val)
        {
            if(curr == head)
            {
                head = head->next;
                curr->next = NULL;
                delete curr;
            }

            else if(curr != head && curr != tail)
            {
                Node * previous = curr->prev;
                Node * following = curr->next;
                previous->next = following;
                following->prev = previous;
                curr->next = NULL;
                curr->prev = NULL;
                delete curr;
            }

            else if(curr == tail)
            {
                tail = tail->prev;
                curr->prev = NULL;
                delete curr;
            }
            removed = true;
        }
        curr = curr->next;
    }
    return removed;
}

打印函数代码

//Prints from head to tail of list
void LinkedList::printAscending() const
{
    Node* curr = head;
    cout<<"\nascending: ";
    while(curr)
    {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout <<'\n';
}

//Prints from tail to head of list
void LinkedList::printDescending() const
{
    Node* curr = tail;
    cout << "\ndescending: ";
    while(curr)
    {
        cout << curr->data << " ";
        curr = curr->prev;
    }

    cout << endl;
}

预期输出

ascending: 3 10 1 7 9 12
descending: 12 9 7 1 10 3
remove operations should be complete
ascending: 10 9
descending: 9 10

实际输出

ascending: 3 10 1 7 9 12                  //correct
descending: 12 9 7 1 10 3                 //correct
remove operations should be complete      //correct
ascending: 10 9 0                         //last number, 0, is incorrect
descending: 9 10 1                        //last number, 1, is incorrect

如果 int main 中删除整数 1 aList.remove(1) 的调用被替换为 aList.remove(999)，则整数 999 出现在降序打印的实际输出中而不是 1。但是，整数 0 始终附加到升序打印。

Answer 1

删除 curr 后，您可以取消引用它：

curr = curr->next;

这是未定义的行为。

Answer 2

除了 Beta 指出的未定义行为外，您的头部和尾部的特殊情况都有问题。运行通过调试器进行此操作并在每次删除后检查列表中的值会告诉您出了什么问题。

此代码：

        else if(curr == tail)
        {
            tail = tail->prev;
            curr->prev = NULL;
            delete curr;
        }

不对倒数第二个元素的 next 指针做任何事情。这意味着你的倒数第二个元素（然后成为最后一个元素）有一个指向释放内存的 next 指针。

要修复它，您需要将倒数第二个元素的 next 指针设置为空。像这样：

        else if(curr == tail)
        {
            tail = tail->prev;
            tail->next = NULL;
            curr->prev = NULL;
            delete curr;
        }

但是等等！（几乎*）不能保证前一个元素存在（即在 1 元素列表中），因此您需要检查新尾巴是否不为 NULL。

        else if(curr == tail)
        {
            tail = tail->prev;
            if (tail != NULL)
               tail->next = NULL;
            curr->prev = NULL;
            delete curr;
        }

*实际上如果这是一个单元素列表，你不会到达这段代码，你会已经通过 "head" if 测试代码，它有一个类似的问题，它不会改变第二个节点的 prev 指针。

因此您还需要在 "head" if 测试代码中进行相同类型的测试。

完成后，您可能会发现可以重新安排测试以摆脱重复的代码。

删除双向链表中的功能故障

Remove function malfunctioning in doubly linked list

c++

linked-list

doubly-linked-list

主要代码

删除函数的代码

打印函数代码

预期输出

实际输出