这些删除列表项算法之间的区别

Question

我写了三个从单链表中删除 item/items 的算法。 1 号工作正常。 2 号也可以正常工作。 3 号行不通，我知道。但是为什么数字3不正确，数字2和双指针有什么区别？

1 号：

struct nodo * delete1(struct nodo * top, int data) {

struct nodo *current, *temp;

if(top->valore == data ) {
     current = top->next;
     free(top);
     top = current;
 }
 
 
     current = top;
     while (current->next)
     {
         if (current->next->valore == data)
         {
             temp = current->next->next;
             free(current->next);
             current->next = temp;
         }
         else
             current = current->next;
     }
 

return top;
}

2号：

void delete2(struct nodo **p, int k) {

while(*p) {
    if ((*p)->valore == k)
    {
        struct nodo * tmp = (*p)->next;
        free(*p);
        (*p) = tmp;
    }
    else
    {
        p = &(*p)->next;
    }
    
}

}

3 号：

struct nodo * delete3(struct nodo * top, int k) {
struct nodo * curr = top;
while(curr) {
    if(curr->d == k) {
        struct nodo * tmp = curr->next;
        free(curr);
        curr = tmp;
    }
    else curr = curr->next;
}
return top;
}

Answer 1

对于初学者来说，这三个函数具有不同的行为。

在第一个函数中，如果列表的第一个节点的值等于指定值，则仅删除第一个节点。否则删除所有具有指定值的节点。

但在任何情况下，即使您更新了函数，它也可能会调用未定义的行为，例如当为空列表调用时或当列表的单个节点被删除时。

在第二个函数中，删除所有值等于指定值的节点（与第一个节点的值是否等于指定值无关）。

第三个函数完全错误，因为它更改了局部变量 curr 而不是例如变量 top 或节点的任何数据成员 next 。也就是说，在任何情况下，函数 returns 指针 top 的先前值与指向的节点是否被删除无关。

要使第一个函数的行为类似于第二个函数的行为，应按以下方式定义。

struct nodo * delete1(struct nodo * top, int data) 
{
    while ( top && top->valore == data ) 
    {
        struct nodo *temp = top->next;
        free( top );
        top = temp;
    }

    if ( top )
    {
        struct nodo *current = top;
        while (current->next)
        {
            if ( current->next->valore == data )
            {
                struct nodo *temp = current->next->next;
                free( current->next );
                current->next = temp;
            }
            else
            {
                current = current->next;
            }
        }
    }

    return top;
}

这些删除列表项算法之间的区别

Difference between these delete-list-item algorithms

c

linked-list

singly-linked-list

function-definition