c++ - 双链表查找删除

Question

我想在双链表中搜索一些东西并删除它。

我的问题是我丢失了前一个节点和我想删除的节点的节点。

这是我的代码:

    int delnode(string moviename)
        {
            node *temp,*del;
            //check empty
            if(!head)
                {
                    cout<<"empty";
                }
            else
                {
                    temp=head;
                while (temp->next!=NULL)
                    {

                        if (temp->title==moviename)
                            {
                                del=temp;
                                temp=temp->previous;
                                temp->next=del->next;
                                delete del;
                            }
                        temp=temp->next;
                    }
                }
        }

例如，如果我有 5 部电影，movie1,movie2,movie3,movie4,movie5 并且想要删除 movie3，我的列表将是 movie1,movie4,movie5 :S

Answer 1

你正在让这件事对你自己造成难以置信的伤害。您的代码有很多问题，包括:

• 未能正确连接先前的指针
• 未能说明最后一个节点的删除。
• 如果它是前景节点，则无法推进头指针。

考虑到这一点，我认为这符合您的要求，我强烈建议您仔细检查它，甚至在调试器中单步执行它以查看它是如何工作的。

void delnode(const std::string& moviename)
{
    // pp holds the address of the pointer that will
    //  eventually point to our node being deleted.
    node **pp = &head;

    // skip nodes until we find a match
    while (*pp && (*pp)->title.compare(moviename))
        pp = &(*pp)->next;

    if (*pp)
    {
        node *tmp = *pp;
        if ((*pp = tmp->next)) // assignment-eval intentional
            (*pp)->previous = tmp->previous;
        delete tmp;
    }
}

这解决了很多问题，包括

• 如果头指针是与您的字符串匹配的节点，则正确更新头指针。
• 将 next 和 previous 正确连接到所有正确的指针
• 正确删除列表中的最后一个 节点(如果它是您的可疑节点)。
• 如果头指针为空则什么都不做。