如何删除双向链表中与某个值匹配的所有项？

Question

我有一个作业，我必须编写一个函数来删除双向链表的任何部分，其中有一个值具有预定的输入。我为此工作了很长一段时间，我找不到我编写的代码有任何其他问题。作业内容如下：

Write a C++ function to delete nodes in a linked list. The function takes two arguments - the head of the linked list and the value to be deleted. It should delete all nodes which contain the value to be deleted. It should return the head of the linked list.

The linked list structure:
struct node
{
    int value;
    node *next;
    node *prev;
};

node *DeleteNode(node *head, int value){
node *tmp=head;
while(tmp!=NULL){
    if(tmp->value==value){
        if(tmp==head){
            head=head->next;
            head->prev=NULL;
            delete tmp;
            tmp=head;
        }
        else if(tmp->next==NULL){
            node *temp=tmp;
            temp->prev->next=NULL;
            delete tmp;
            tmp=temp;
        }
        else{
            node *node1=tmp;
            node1->prev->next=node1->next;
            node1->next->prev=node1->prev;
            delete tmp;
            tmp=node1;
        }
    }
    tmp=tmp->next;
}
return head;}

所以，当它运行

的测试时

1 <-> 2 <-> 3 <-> 4

需要删除所有的3，结果是

1 <-> 2 <-> 4

这是正确的。它适用于其他需要删除头部项目的示例，以及需要删除尾部的示例。它适用于所有需要的功能....除此之外...

2 <-> 2 <-> 2 <-> 2 <-> 65 <-> 83

需要删除2的地方。它只得到

的结果

2<-> 65 <-> 83

所以出于某种原因，额外留下了 2 个。有什么猜测吗？我已经提供了我为这个问题提供的一切。我认为问题可能出在我删除双向链表中的中间项的部分，但我完全迷路了。非常感谢！

Answer 1

这看起来很可疑（添加了一些空格）：

node* node1 = tmp;
node1->prev->next = node1->next;
node1->next->prev = node1->prev;
delete tmp;
tmp = node1;

node1 只是 tmp 的别名。它实际上没有任何其他目的。然后你 delete tmp 并将其分配给 node1 - 这正是你刚刚删除的内容！

你可能想做的事：

tmp->prev->next = tmp->next;
tmp->next->prev = tmp->prev;
node* prev = tmp->prev;
delete tmp;
tmp = prev;

Answer 2

当您的初始头节点与该值匹配时出现问题。

在这里你设置下一个节点为新的头并去掉旧的然后设置tmp为新的头，

if(tmp==head){
        head=head->next;
        head->prev=NULL;
        delete tmp;
        tmp=head;
 }

然后当您退出您设置的 if 语句时

tmp = tmp-> next

所以在你的 if 块中，你将当前节点设置为下一个节点，然后删除曾经是你当前节点的节点，然后当你退出 if 语句时，你再次向下移动到下一个节点，有效地跳过了完全新的头节点。

Answer 3

我除了巴里的回答：

node *temp=tmp;
temp->prev->next=NULL;
delete tmp;
tmp=temp;

这将为您当前的节点tmp设置别名temp，然后将您之前节点的next指针设置为NULL，删除当前节点并设置您的tmp-指向 temp 的指针，但这只是您刚刚删除的节点的别名。您可能希望 node *temp=tmp->prev; 将 tmp 设置为新的最后一个元素。

可能导致你的错误的是，不管你比较值，你调用

tmp=tmp->next;

最后，转到你的下一个节点。您应该将其包装在 else 块中，以便仅在您的值不匹配时执行。

Answer 4

当定义双链表时，通常会定义一个包含两个指针的单独结构：一个指向链表头部的指针，另一个指向链表尾部的指针。例如

struct list
{
    node *head = nullptr;
    node *tail = nullptr;
    //...
};

还在结构中声明了处理列表的成员函数。

然而，如果使用您的方法，那么删除所有值等于给定值的节点的函数看起来就像这个演示程序中显示的那样

#include <iostream>

struct node
{
    int value;
    node *next;
    node *prev;
};

void display( node *head )
{
    for ( ; head; head = head->next )
    {
        std::cout << head->value << ' ';
    }
    std::cout << std::endl;
}

node * AppendNode( node *head, int value )
{
    node *tmp = new node { value, nullptr, nullptr };

    if ( !head )
    {
        head = tmp;
    }
    else
    {
        node *prev = head;
        while ( prev->next ) prev = prev->next;
        tmp->prev = prev;
        prev->next = tmp;
    }

    return head;
}

node * DeleteNode( node *head, int value )
{
    for ( node *current = head; current; )
    {
        if ( current->value == value )
        {
            node *tmp = current;

            if ( current->next )
            {
                current->next->prev = current->prev;
            }

            if ( current->prev )
            {
                current->prev->next = current->next;
                current = current->next;
            }
            else
            {
                head = current->next;
                current = head;
            }

            delete tmp;
        }
        else
        {
            current = current->next;
        }            
    }

    return head;
}    

int main()
{
    node *head = nullptr;

    for ( int x : { 2, 2, 2, 2, 65, 83 } ) head = AppendNode( head, x );

    display( head );

    head = DeleteNode( head, 2 );

    display( head );

    head = DeleteNode( head, 83 );

    display( head );

    head = DeleteNode( head, 65 );

    display( head );
}

它的输出是

2 2 2 2 65 83 
65 83 
65

如何删除双向链表中与某个值匹配的所有项？

How to delete all items in a doubly linked list that match a certain value?

c++

linked-list

nodes

doubly-linked-list