如何释放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;
}

如何释放C中的链表

How to free a linked list in C

c

free

valgrind

linked-list

doubly-linked-list