c++ - 如何删除 C++ 链表中的节点？

Question

到目前为止，我已将我的工作粘贴在这里: http://codepad.org/WhJuujRm

链表的概念让我感到困惑，所以我想我应该练习一下。我知道如何添加节点和编辑节点，但我不知道如何在我的特定场景中删除节点。

我的伪代码:

previous == now - 1;
if(stdid == now->getID());
previous->setNext(now->getNext);
delete now;
return;

我该如何实现？

Answer 1

从链表中删除一个元素的思路是更新首先将您带到该元素的指针。在您的列表案例中，它可能是 top(和/或可能是 bottom)，它可能是某个节点的 next。当您使用 cur 指针遍历列表搜索时，请保留一个 prev 指针，您在枚举时将其向前移动一步。假设你找到了受害者节点(如果你没有找到，就没什么可做的，哇!)，prev 将处于以下两种状态之一:

• 它将为 NULL，在这种情况下 top 是指向您的受害者节点的指针，并且必须更新 top，或者...
• 它将是一些指向节点的指针，在这种情况下，该节点的 next 成员需要更新以反射(reflect)受害节点的 next 成员值。

在两种情况下，bottom 可能也需要更新。在第一种情况下，如果列表只有一个节点而您要删除它，则 bottom 将需要更改。即完成后你将有一个空列表。很容易分辨，因为在分离 cur 并将 top 设置为 cur->next 之后 top 将为 NULL >。对您来说更容易，因为您在列表容器中保留了一个 size 成员；如果它是 1，则您知道 head 和 bottom

在第二种情况下，最后节点可能是受害者节点。在这种情况下，必须更新 bottom 以反射(reflect)列表的新结尾(恰好在 prev 中，并且可能是 NULL，如果，再一次，列表只有一个元素。你如何判断受害者是否是列表中的最后一个节点？如果 next 成员为 NULL，则它必须是最后一个节点，并且 bottom 必须更新。

类似这样，一个基于ID搜索的删除功能

void deleteStudent(int id)
{
    student *cur = top, *prev = nullptr;
    while (cur && cur->getID() != id)
    {
        prev = cur;
        cur = cur->getNext();
    }

    // found a node?
    if (cur)
    {
        student *pNext = cur->getNext();

        // set new next pointer for prev, or new top
        if (prev)
            prev->setNext(pNext);
        else
            top = pNext;

        // update bottom if needed
        if (!pNext)
            bottom = prev;

        delete cur;
        --scnt;
    }
}

我留给您的其他删除选项和标准。

祝你好运。