从单链表中删除元素

Question

我想删除函数中value指定的列表中的一些元素.如果函数的'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;
        }
    }
}

编辑:还有其他解决方案.您可以返回新的列表指针:

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可具有附加字段,例如用于快速追加到末尾的尾指针.您还可以跟踪列表长度.