如何在C中释放链表

Question

我正在用C创建一个链表，需要一些帮助来释放它。元素的结构和整个列表如下所示：

typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element **first;
    element **last;
    int *e_count;
} list;

这是我释放列表的问题。该代码可以正常工作：

void wipe(list l) {
    element *p = *l.first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

但是当我尝试使用双指针时，我开始从valgrind中收到InvalidRead错误：

void wipe(list l) {
    element **p = l.first;
    element **t = l.first;

    while (*p) { // InvalidRead here after "free(*t);"
        *t = *p;
        p = &(*p)->next;
        free(*t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

这是可以预期的，因为在这种情况下，t和p本质上指向free()正在使用的同一地址。我想知道如何解决此问题，以及它是否比使用单个指针的第一种情况更好。

谢谢您的帮助！

代码示例：

#include <stdlib.h>
#include <stdio.h>


typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element **first;
    element **last;
    int *e_count;
} list;


list new_list();
void delete_list(list l);

element *alloc_element(int n);

int append(list l, int n);
void wipe(list l);


int main() {
    list l = new_list();
    append(l, 5);
    append(l, 7);
    delete_list(l);
}


list new_list() {
    element **first = malloc(sizeof(element*));
    element **last = malloc(sizeof(element*));
    int *n = malloc(sizeof(int));
    *first = NULL;
    *last = NULL;

    list list = {first, last, n};
    return list;
}


void delete_list(list l) {
    wipe(l);
    free(l.first);
    free(l.last);
    free(l.e_count);
}


element *alloc_element(int n) {
    element *e = malloc(sizeof(element));
    if (!e) {
        return NULL;
    }
    e->next = NULL;
    e->prev = NULL;
    e->num = n;
    return e;
}


int append(list l, int n) {
    element **p = l.first;
    element *e = alloc_element(n);
    if (!e) {
        return 1;
    }

    while (*p) {
        if (!(*p)->next) {
            e->prev = *p;
        }
        p = &(*p)->next;
    }

    *p = e;
    *l.last = e;
    ++*l.e_count;
    return 0;
}


void wipe(list l) {
    element *p = *l.first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    *l.first = NULL;
    *l.last = NULL;
    *l.e_count = 0;
}

Answer 1

由于需要功能来修改list，因此需要将指向list的指针传递给功能。另外，您的代码中似乎对避免使用双指针有很多困惑。这是修正了所有混乱的代码的整理版本：

#include <stdlib.h>
#include <stdio.h>


typedef struct node_ {
    int num;
    struct node_ *next;
    struct node_ *prev;
} element;


typedef struct list_ {
    element *first;
    element *last;
    int e_count;
} list;


list *new_list(void);
void delete_list(list *l);

element *alloc_element(int n);

int append(list *l, int n);
void wipe(list *l);


int main(void) {
    list *l = new_list();
    append(l, 5);
    append(l, 7);
    delete_list(l);
}


list *new_list(void) {
    list *l = malloc(sizeof(list));
    if (!l) {
        return NULL;
    }
    l->first = NULL;
    l->last = NULL;
    l->e_count = 0;
    return l;
}


void delete_list(list *l) {
    if (l != NULL) {
        wipe(l);
        free(l);
    }
}


element *alloc_element(int n) {
    element *e = malloc(sizeof(element));
    if (!e) {
        return NULL;
    }
    e->next = NULL;
    e->prev = NULL;
    e->num = n;
    return e;
}


int append(list *l, int n) {
    element *e = alloc_element(n);
    if (!e) {
        return 1;
    }
    if (l->last) {
        l->last->next = e;
    } else {
        l->first = e;
    }
    e->prev = l->last;
    l->last = e;
    ++l->e_count;
    return 0;
}


void wipe(list *l) {
    element *p = l->first;
    element *t;

    while (p) {
        t = p;
        p = p->next;
        free(t);
    }

    l->first = NULL;
    l->last = NULL;
    l->e_count = 0;
}