c ++链表，删除元素会断开列表的其余部分

Question

我正在尝试为我的家庭作业实现这个简单的链表项目。当我尝试实现 removeByKey 函数时，我运行遇到了一个问题，即当它发现要删除的密钥时，它会完全断开列表的其余部分。

这是class：

class LancElem
{
private:
    int key;
    LancElem* next;
public:
    LancElem(){next = nullptr;}
    LancElem(int keyy, LancElem* nextt){key = keyy;next = nextt;}
    LancElem* getNext(){return next;}
    int getKey(){return key;}
    void setNext(LancElem* nextt){next = nextt; }
    void setKey(int keyy){key = keyy;}
};

删除函数：

void removeByKey(LancElem& head, int key){
    LancElem* n = head.getNext();
    while(n->getNext()!=nullptr){
        if(n->getNext()->getKey()==key){
            n->setNext(n->getNext()->getNext());
            delete n->getNext();
            break;
        }
        n=n->getNext();
    }
}

当我尝试删除最大的元素时：

原始链表：4 1 9 8 2 7 3 6 3

预期输出：4 1 8 2 7 3 6 3

实际输出：4 1 0

问题可能出在我将当前元素连接到下一个->下一个元素的位置，但我无法弄清楚为什么我的实现不好。

Answer 1

问问自己：

行 n->setNext(n->getNext()->getNext()); 之后的 n->next 是什么？ delete n->getNext(); 行删除了什么？

您不想delete刚更新的next但您想删除要删除的元素：

        auto to_be_deleted = n->getNext(); 
        n->setNext(to_be_deleted->getNext());
        delete to_be_deleted;

Answer 2

您的列表似乎有一个没有值的虚拟头节点。

由于使用表达式 n->getNext()

，当 head.getNext() returns 为空指针时，函数 removeByKey 可以调用未定义的行为

LancElem* n = head.getNext();
while(n->getNext()!=nullptr){

也在 if 语句中

    if(n->getNext()->getKey()==key){
        n->setNext(n->getNext()->getNext());
        delete n->getNext();
        break;
    }

您正尝试通过使用函数 setNext.

删除由于之前分配数据成员 next 而要删除的节点之后的节点

        n->setNext(n->getNext()->getNext());
        delete n->getNext();

注意你的函数因为你调用了两次getNext()

所以无法删除dummy head节点之后的节点

LancElem* n = head.getNext();  // the first call of getNext
while(n->getNext()!=nullptr){
    if(n->getNext()->getKey()==key){   // the second call of getNext.
    //...

函数可以这样定义

void removeByKey( LancElem &head, int key )
{
    if ( head.getNext() != nullptr )
    {
        if ( head.getNext()->getKey() == key )
        {
            LancElem *current = head.getNext();
            head.setNext( head.getNext()->getNext() );
            delete current;
        }
        else
        {
            LancElem *n = head.getNext();

            while( n->getNext() != nullptr && n->getNext()->getKey() != key )
            {
                n = n->getNext();
            }

            if ( n->getNext() != nullptr )
            {
                LancElem *current = n->getNext();
                n->setNext( n->getNext()->getNext() );
                delete current;
            }                
        }
    }
}

现在尝试使用此函数删除列表中值为 4 的第一个节点和您当前拥有的函数并比较它们的结果。

c ++链表，删除元素会断开列表的其余部分

c++ linked list, removing element disconnects the rest of the list

c++

class

linked-list

singly-linked-list

function-definition