Удаление из списка в 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 с указателем, но я не могу понять, как сделать это работает. Вот код:

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

Когда вы удаляете элемент, вы должны знать, какой указатель обновить. Это означает, что вы должны знать о предыдущем узле в списке. Ответ Влада делает это, сохраняя дополнительную переменную previous, ваш первый код делает это, глядя на указатель, на который указывает текущий узел. Оба должны рассматривать удаление из головы как особый случай.

Ваш второй код пытается упростить код, но вы теряете специальный случай удаления во главе, а также обновляете ссылку итератора после удаления, чего не следует. (Ваш исходный код правильно помещает обновление в пункт else.)

Метод избавления от специального случая удаления во главе заключается в том, чтобы ввести один уровень косвенности iterationg с помощью указателя на указатель узла. Этот указатель содержит адрес «предыдущего» указателя – заголовка списка или указателя 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; Я считаю, что это желаемое поведение. (Дополнительная нагрузка также работает для вставки.)

Answer 2

Вы можете использовать, например, следующий 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 тогда действительно можно использовать для цикла.

Например

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

Есть два неправильных точек:

• если первый элемент элемент должен быть удален, предыдущий этого пункта не существует, а код р -> next = ... неверное действие. Вы должны изменить заголовок списка, это правильное действие.
• , когда вы удаляете текущий элемент (бесплатно (r)), поэтому, если вы вызываете x = x-> рядом с вашей программой, возможно, сбой. Перед удалением необходимо выполнить резервное копирование x->. И для петли вам необходимо изменить