在C++中删除链表中的节点

Question

我正在尝试删除列表第 n 位的单向链表中的节点，但在运行项目时不断收到分段错误：11。下面是我认为问题所在remove函数，但我似乎无法弄清楚为什么它不起作用，因为逻辑是有意义的。此外，列表中第一项中的headM点是第 0 位。在我调用删除我的列表之前，是订单770 440 330 220 110我打了两个电话来删除

remove(0)
remove(2)

之后的列表应该440 330 110，但现在我正在770 330 110....

void SimpleList::remove(int n)
{
if( n < 0 || n > sizeM ) { 
    return;
}
Node* p = headM;
for( int c = 0; c < n - 1; c++ )
{
    p = p->next;
    //assert( p != nullptr );
}
Node* const p_doomed = p->next;
//assert( p_doomed != nullptr );
p->next = p_doomed->next;
delete p_doomed;
--sizeM;
}

下面是节点的结构。这部分是正确的，因为我的push_front和push_back工作。

class Node {
public:
    ListItem item;
    Node *next;
};
Node *headM;
int sizeM;
void destroy();
// Deallocate all nodes, and sets headM to zero.
void copy(const SimpleList& source);
// List becomes copy of source.

Answer 1

考虑最后一个节点，例如，如果列表有 （i） 节点：{0 .. i - 1}，则节点位于位置 （i - 1）。在循环之后，您应该能够满足自己：

for(int c = 0; c < n; c++) p = p->next; // where: n = i - 1

p->next是NULL（或nullptr），因此：

p->next = p->next->next;取消引用空指针。

Answer 2

删除的方式有点错误。您必须将前一个指针的next节点获取到 p 的后续节点，然后将其删除。

反正你也可以这样写：

void SimpleList::remove(int value)
{
    Node** ptr = &headM, *next;
    while (*ptr && (*ptr)->data != value)
        ptr = &(*ptr)->next;
    if (*ptr)
    {    
        next = (*ptr)->next;
        delete *ptr;
        *ptr = next;
    }
}

就像弗拉德说的，你也应该减小尺寸。

Answer 3

^{这个答案现在被OP问题中的新信息所否定。事实证明，他没有一个虚拟的头节点（正如命名和逻辑所暗示的那样），并且（引用）"nth"中的n不是基于1的索引，而是基于0的索引。我保持答案不变，宁愿不追逐一个不断变化的问题。}

此原始代码

void SimpleList::remove(int n)
{
    Node *p = headM;
    for(int c=0;c<n;c++)
    {
        p = p->next;
    }
    Node *todel = p->next;
    p->next = p->next->next;
    delete todel; 
}

暗示headM指向虚拟标头节点。

考虑到 n = 1 时会发生什么，todel被错误地设置为 p->next ，即您要删除的节点之后的节点。就此而言，p直接指向要删除的节点，否则您无法做太多事情，除非保证至少有一个后续节点并且没有其他指向列表的指针。此外，即使列表包含 n 个节点（正好），p->next->next表达式也可以具有 UB。

而是像这样做：

void SimpleList::remove( int const n )
{
    if( n <= 0 || n > sizeM ) { throw std::runtime_error( "Ouch!" ); }
    Node* p = headM;
    for( int c = 1; c <= n - 1; ++c )
    {
        p = p->next;
        assert( p != nullptr );
    }
    Node* const p_doomed = p->next;
    assert( p_doomed != nullptr );
    p->next = p_doomed->next;
    delete p_doomed;
    --sizeM;
}

Answer 4

您不检查节点是否等于 nullptr 并且 sizeM 不会减小，以防节点被删除

该函数可以按以下方式编写

size_t sizeM;
//...
void SimpleList::remove( size_t n )
{
    Node *current = headM;
    Node *prev    = nullptr;
    while ( current && n-- )
    {
        prev    = current;
        current = current->next;
    }
    if ( current )
    {
        if ( prev ) prev->next = current->next;
        else headM = headM->next;
        delete current;
        --sizeM;
    }
}

我想列表的索引从零开始。

考虑到sizeM应定义为size_t而不是int。将其声明为 int 是没有意义的，在这种情况下，您应始终检查sizeM是否小于零。您还可以为 sizeM 定义更通用的类型。例如

typedef size_t size_type;

如果headM和sizeM是全局变量，那么最好将headM和sizeM封装在一个单独的类中，例如名为 List 。

您也可以在函数中检查索引是否大于或等于 sizeM 。如果它确实大于或等于sizeM那么你可以简单地退出函数或抛出一个 exceprion。

例如

void SimpleList::remove( size_t n )
{
    if ( !( b < sizeM ) ) return;

或

void SimpleList::remove( size_t n )
{
    if ( !( b < sizeM ) ) throw std::out_of_range( "Incorrect value of the index" );