从 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

您可以使用例如以下 appeoach

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 2

有两处错误：

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

Answer 3

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

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

摆脱头部删除的特殊情况的一种方法是通过指向节点指针的指针通过iterationg引入一层间接。该指针保存 "previous" 指针的地址——列表头或前一个节点的 next 指针。其余部分或多或少类似于您的原始代码，期望当前节点现在位于 *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 的项目；我认为这是理想的行为。（额外的间接寻址也适用于插入。）

从 C 中的列表中删除

Deleting from a List in C

c

pointers

linked-list

singly-linked-list