我在 C 中实现双向链表，并在销毁函数中出现分段错误

Question

我把代码分成两个文件，.h 和.c 函数名的定义在.h，函数的实现在.c

在我的主文件中：

struct no
{        
    tipo info;      
    struct no *ant; 
    struct no *nxt;
};
struct list    
{
    no_t *head; 
    no_t *tail; 
    int size;
};

这在我的 .h 文件中：

typedef     struct no       no_t;
typedef     struct list     list_t;
typedef     int             tipo;

...再次进入主要

void list_destroy(list_t **l)
{
    if ((*l) == NULL || l == NULL)
        return;
    if (!(*l)->head)
        return;

    no_t *next = (*l)->head;       //create two variables for iterating through the list
    no_t *aux;                     //set aux to free

    while (next->nxt)             //the pointer for next node, in the last node, is NULL
    {                             //by that I believe I'm able to iterate through all nodes
        aux = next;
        free(aux);
        next = next->nxt;
    }

    free(*l);
    (*l) = NULL;
}

是一个非常简单的代码，但我看不出我遗漏的地方

Answer 1

这有问题

no_t *next = (*l)->head;
no_t *aux;

while (next->nxt)
{
    aux = next;       // aux point to the same object as next
    free(aux);        // free aux, which is the same as next
    next = next->nxt; // deference next, which just got free'd.  OOPS!
}

您在 aux 上调用 free，这也是 next 的别名。然后你试着尊重next->nxt。好吧，next 刚刚在前面的声明中发布了。另外，正如我在评论中指出的那样，您正在泄漏列表中的最后一个元素。

固定：

no_t* aux = (*l)->head;
while (aux)
{
    no_t* next = aux->nxt;
    free(aux);
    aux = next;
}

Answer 2

  next = next->nxt;

对于编译器来说，这当然没有区别。但是对于某些人来说，即使是您，也很难阅读这些 next = next->nxt 内容。或者不是？

一个可能的替代方案（使用您的代码）和一个简短的测试程序

so_list.h

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

typedef int Tipo;

typedef struct st_no
{
    Tipo            info;
    struct st_no*   prev;
    struct st_no*   next;

}   Node;


typedef struct
{
    Node*       head;
    Node*       tail;
    unsigned    size;

}   List;


List*       list_create();
List*       list_destroy(List*);
int         list_insert(const Tipo, List*);

在 header 中，只有 typedef 和函数原型。
只有第一个字母大写的名称在这里保留给定义的名称。一个有用的约定。
而不是使用 List** 通常更清楚 return 指向列表的指针。通过这种方式，例如使指针无效并创建链接列表更容易，如

    List* my_list = list_create();
    my_list = list_destroy(my_list);

并且在使用**时不需要测试两层间接寻址

main.c：极简测试集

#include "so-list.h"

int main(void)
{
    List* my_list = list_create();
    my_list = list_destroy(my_list);

    my_list = list_create();
    for (int i = 1; i <= 5; i += 1)
        printf("insert(%d,list) returned %d\n",
            i, list_insert(i,my_list) 
        );
    my_list = list_destroy(my_list);


    my_list = list_create();
    for (int i = 11; i <= 15; i += 1)
        printf("insert(%d,list) returned %d\n",
            i, list_insert(i, my_list)
        );
    my_list = list_destroy(my_list);
    return 0;
}

创建一个列表，然后销毁
使用相同的指针，创建一个列表，插入值 1 到 5，然后删除列表。
使用相同的指针，创建一个列表，插入值 11 到 15，然后再次删除列表。

输出

List created!
List deleted!

List created!
insert(1,list) returned 1
insert(2,list) returned 2
insert(3,list) returned 3
insert(4,list) returned 4
insert(5,list) returned 5
1 deleted
2 deleted
3 deleted
4 deleted
5 deleted
List deleted!

List created!
insert(11,list) returned 1
insert(12,list) returned 2
insert(13,list) returned 3
insert(14,list) returned 4
insert(15,list) returned 5
11 deleted
12 deleted
13 deleted
14 deleted
15 deleted
List deleted!

`destroy_list()`

代码

List* list_destroy(List* l)
{
    if (l == NULL) return NULL;
    // delete the ´size´ nodes, 1 by 1
    Node* p = NULL;
    for (unsigned i = 0; i < l->size; i += 1)
    {
        p = l->head->next; // save pointer
        printf("%d deleted\n", l->head->info); // just for the demo
        free(l->head); // free head
        l->head = p; // advance head
    }
    free(l); // free list
    printf("List deleted!\n\n"); // just for the demo
    return NULL;
}

此函数始终 return NULL 作为一种使调用方指针在与 pList = destroy_list(pList);

相同的表达式中无效的方法

这与您编写的代码有些不同。我们只是一个一个地删除元素，因为我们知道列表有 size 个元素。循环中使用局部指针来保存下一个元素的地址。看起来更容易阅读。

so-list.c

的完整代码

#include  "so-list.h"

List* list_create()
{
    List* one = (List*)malloc(sizeof(List));
    one->head = NULL;
    one->tail = NULL;
    one->size = 0;
    printf("List created!\n");
    return one;
}


List* list_destroy(List* l)
{
    if (l == NULL) return NULL;
    // delete the ´size´ nodes, 1 by 1
    Node* p = NULL;
    for (unsigned i = 0; i < l->size; i += 1)
    {
        p = l->head->next; // save pointer
        printf("%d deleted\n", l->head->info);
        free(l->head); // free head
        l->head = p; // advance head
    }
    free(l); // free list
    printf("List deleted!\n\n");
    return NULL;
}


// just for test, insert ´info´ at the end, returns size
int         list_insert(const Tipo info, List* l)
{
    // insert node at the end, just for test
    Node* one = (Node*)malloc(sizeof(Node));
    one->info = info;
    one->next = NULL;
    one->prev = l->tail;
    if (l->size == 0)
        l->head = one; // 1st node
    else
        l->tail->next = one;
    l->tail = one;
    l->size += 1;
    return l->size;
};

关于您的 list_destroy()

版本

逻辑有点不对，但是在另一个答案中描述的很清楚。我建议在这种情况下不要使用 **。但是肯定是可以做到的。

so-list.c

这只是进行运行测试的最低要求

#include  "so-list.h"

List* list_create()
{
    List* one = (List*)malloc(sizeof(List));
    one->head = NULL;
    one->tail = NULL;
    one->size = 0;
    printf("List created!\n");
    return one;
}


List* list_destroy(List* l)
{
    if (l == NULL) return NULL;
    // delete the ´size´ nodes, 1 by 1
    Node* p = NULL;
    for (unsigned i = 0; i < l->size; i += 1)
    {
        p = l->head->next; // save pointer
        printf("%d deleted\n", l->head->info);
        free(l->head); // free head
        l->head = p; // advance head
    }
    free(l); // free list
    printf("List deleted!\n\n");
    return NULL;
}


// just for test, insert ´info´ at the end, returns size
int         list_insert(const Tipo info, List* l)
{
    // insert node at the end, just for test
    Node* one = (Node*)malloc(sizeof(Node));
    one->info = info;
    one->next = NULL;
    one->prev = l->tail;
    if (l->size == 0)
        l->head = one; // 1st node
    else
        l->tail->next = one;
    l->tail = one;
    l->size += 1;
    return l->size;
};

Answer 3

你应该看看你的“免费”和你的“next->nxt”声明。希望能帮到你解决。

我在 C 中实现双向链表，并在销毁函数中出现分段错误

I am implementing a doubly linked list in C, and having segmentation fault in a destroy function

c

command-line

gcc

compilation

segmentation-fault

一个可能的替代方案（使用您的代码）和一个简短的测试程序

so_list.h

main.c：极简测试集

输出

`destroy_list()`

so-list.c

关于您的 list_destroy()

so-list.c