Блог

Я написал три алгоритма для удаления элемента / элементов из односвязного списка. Номер 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 = amp;(*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;
}
  

Для начала три функции имеют разное поведение.

В первой функции, если первый узел списка имеет значение, равное указанному значению, удаляется только этот первый узел. В противном случае все узлы с указанным значением удаляются.

Но в любом случае даже после обновления функции она может вызывать неопределенное поведение, например, когда вызывается для пустого списка или когда один узел списка был удален.

Во второй функции удаляются все узлы (независимо от того, имеет ли первый узел значение, равное указанному значению) со значением, равным указанному значению.

Третья функция совершенно неверна, потому что она изменяет локальную переменную curr вместо, например, переменной top или любого элемента данных рядом с узлом. То есть в любом случае функция возвращает предыдущее значение вершины указателя независимо от того, был ли указанный узел удален.

Чтобы поведение первой функции было аналогично поведению второй функции, оно должно быть определено следующим образом.

 struct nodo * delete1(struct nodo * top, int data) 
{
    while ( top amp;amp; 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;
}