Удалить элементы из отдельного списка

Question

Я хотел бы удалить некоторые элементы из списка, указанного значением в функции. Моя функция не работает, если функция «val» равна моему первому элементу в списке. В противном случае он работает хорошо. Есть идеи?

struct elem { 
    int val; 
    struct elem *next; 
}; 

void del(struct elem *list, int val) { 
    struct elem* tmp = list; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(list); 
       list = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

Answer 1

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

Одно решение передать список, как struct elem **list:

void del(struct elem **list, int val) { 
    struct elem* tmp = *list; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(*list); 
       *list = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

Edit: Есть и другие решения. Вы можете вернуть новый указатель на список:

struct elem *del(struct elem *list, int val) { ... } 

И вы называете это так:

list = del(list, 12); 

Это решение имеет тот недостаток, что list является несколько излишним в вызове, и что он является законным опускаем возвращаемое значение, таким образом, фактически не обновляя список.

Решение, которое мне нравится, это определить структуру управления для вашего списка. На данный момент, это только содержит указатель головы:

struct list { 
    struct elem *head; 
}; 

Ваши функции, которые работают в этом списке, то принимают указатель на эту структуру в качестве аргумента:

void del(struct list *list, int val) { 
    struct elem* tmp = list->head; 
    struct elem* prev = NULL; 

    while (tmp != NULL) { 
     if (tmp->val == val) { 
      if (prev == NULL) { 
       tmp = tmp->next; 
       free(list->head); 
       list->head = tmp; 
      } else { 
       prev->next = tmp->next; 
       free(tmp); 
       tmp = prev->next; 
      } 
     } else { 
      prev = tmp; 
      tmp = tmp->next; 
     } 
    } 
} 

struct list может иметь дополнительные поля, для Например, указатель хвоста для быстрого добавления в конец. Вы также можете отслеживать длину списка.