从C中的列表中删除

Question

基本上我必须从链表中删除某个项目。此代码有效：

void delete_(Item client){
    link s=head,r;
    if(head->item==client){
        r=head;
        head=head->next;
        free(r);
    }
    else{
        while(s->next!=NULL){
            if(s->next->item==client){
                r=s->next;
                s->next=s->next->next;
                free(r);
            }
            else
                s=s->next;
        }
    }
}

现在，我尝试使用带有2个指针的for来减少和压缩代码，但我不知道如何使其工作。这是代码：

void delete_(Item client){
    link x,r,p;
    for(x=head;x!=NULL;p=x,x=x->next){
        if(x->item==client){
            r=x;
            p->next=x->next;
            free(r);
        }
    }
}

Answer 1

有两点错误：

• 如果第一个元素是需要删除的项，则该项的前一个不存在，并且代码p->next=。。。不是正确的操作。你应该更改列表的标题，这是正确的操作
• 当您删除当前项目（free（r））时，所以如果您调用x=x->next，您的程序可能会崩溃。在删除之前，您必须备份x->next。你的for循环需要改变

Answer 2

例如，您可以使用以下名称

void delete( Item client )
{
    link current = head, previous = NULL;
    while ( current && current->item != client )
    {
        previous = current;
        current = current->next;
    }
    if ( current )
    {
        if ( !previous ) head = head->next;
        else previous->next = current->next;
        free( current );
    }
}

如果要删除成员item等于client的所有节点，那么实际上可以使用for循环。

例如

void delete( Item client )
{
    for( link current = head, previous = NULL; current != NULL; )
    {
        if ( current->item == client )
        {
            link tmp = current;
            if ( previous != NULL ) 
            {
               previous->next = current->next;
               current = current->next;
            }
            else
            {
                head = current->next;
                current = head;
            }
            free( tmp );
        }
        else
        {
            previous = current;
            current = current->next;
        }
    }
}

Answer 3

删除项目时，必须知道要更新哪个指针。这意味着您必须了解列表中的上一个节点。Vlad的答案是通过保留一个额外的previous变量来实现这一点，您的第一个代码是通过查看当前节点指向的指针来实现的。两者都必须将头部删除视为特殊情况。

您的第二个代码试图简化代码，但在头部丢失了删除的特殊情况，并且在删除后更新迭代器链接，这是不应该的。（您的原始代码正确地将更新放在else子句中。）

消除头部删除的特殊情况的一种方法是通过指针到节点的指针进行迭代，引入一级间接性。该指针保存"上一个"指针的地址–列表头或前一节点的CCD_ 5指针。其余部分或多或少与您的原始代码相似，期望当前节点现在位于*l而不是l->next:

void delete(Item client)
{
    link *l = &head;
    while (*l) {
        if ((*l)->client == client) {
            link r = *l;
            *l = (*l)->next;
            free(r);
        } else {
            l = &(*l)->next;
        }
    }
}

此代码删除所有与client匹配的项；我认为这是我们想要的行为。（附加的间接寻址也适用于插入。）