双向链表测试报错信息：free(): double free detected in tcache 2

Question

我是 c 的初学者，我尝试实现双向链表，包括弹出、插入、删除功能。我收到了测试错误消息，上面写着“接近：测试列表中的弹出元素，两端测试失败：free()：在 tcache 2 中检测到双重释放”。

我的代码实现如下所示

#ifndef MYDLL_H
#define MYDLL_H

#include <stdlib.h>


typedef struct node
{
    int data;
    struct node *next;
    struct node *previous;
} node_t;

typedef struct DLL
{
    int count;    
    node_t *head; 
    node_t *tail; 
} dll_t;

// Creates a DLL
dll_t *create_dll()
{
    dll_t* myDLL = (dll_t*)malloc(sizeof(dll_t));
    if (myDLL == NULL) {
        return NULL;
    }
    //initial pointer point to self
    // myDLL->next=myDLL->previous=myDLL;
    // return myDLL;

    // set fileds to default values
    myDLL->count = 0;
    myDLL->head = NULL; 
    myDLL->tail = NULL; 

    return myDLL;
}

// DLL Empty
// Check if the DLL is empty
// Returns -1 if the dll is NULL.
// Returns 1 if true (The DLL is completely empty)
// Returns 0 if false (the DLL has at least one element enqueued)
int dll_empty(dll_t *l)
{
    if (l == NULL) {
        return -1;
    }
    if (l->count == 0) {
        return 1;
    }
    return 0;
}

// push a new item to the front of the DLL ( before the first node in the list).
// Returns -1 if DLL is NULL.
// Returns 1 on success
// Returns 0 on failure 
int dll_push_front(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }

    node_t* newNode = (node_t*)malloc(sizeof(node_t)); 
    if (newNode == NULL) {
        return 0;
    }
    
    newNode->data = item; 
    newNode->previous = NULL; 
    if (l->head == NULL) {
        l->head = newNode;
        l->tail = newNode; 
        newNode->next = NULL;
    }
    else {
        newNode->next = l->head; 
        l->head = newNode; 
        l->head->previous = newNode;
    
    l->count++;
    return 1;
}

// push a new item to the end of the DLL (after the last node in the list).
// Returns -1 if DLL is NULL.
// Returns 1 on success
// Returns 0 on failure ( i.e. we couldn't allocate memory for the new node)
// (i.e. the memory allocation for a new node failed).
int dll_push_back(dll_t *l, int item)
{
    if (l == NULL) {
        return -1;
    }
    node_t* newNode = (node_t*)malloc(sizeof(node_t));
    if (newNode == NULL) {
        return 0;
    }

    newNode->data = item; 
    newNode->next = newNode->previous = NULL; 
    if (l->tail == NULL) {
        l->head = newNode;
        l->tail = newNode; 
        newNode->previous = NULL;
    }
    else {
        newNode->previous = l->tail; 
        l->tail->next = newNode; 
        l->tail = newNode; 
    }
    l->count++;
    return 1;
}

// Returns the first item in the DLL and also removes it from the list.
// Returns -1 if the DLL is NULL.
// Returns 0 on failure, i.e. there is noting to pop from the list.
// Assume no negative numbers in the list or the number zero.
int dll_pop_front(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = (node_t*)malloc(sizeof(node_t));
        temp = t->head; 
        int data = temp->data; 
        t->head = t->head->next;
        free(temp); 
        t->count--;

        if (t->count == 0) { 
            t->tail = NULL; 
        }

        return data;
    }

}

// Returns the last item in the DLL, and also removes it from the list.
// Returns a -1 if the DLL is NULL.
// Returns 0 on failure, i.e. there is noting to pop from the list.
// Assume no negative numbers in the list or the number zero.
int dll_pop_back(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    else if (t->count == 0) {
        return 0;
    }
    else {
        node_t* temp = (node_t*)malloc(sizeof(node_t));
        temp = t->tail; 
        int data = temp->data;
        t->tail = t->tail->previous; 
        free(temp);
        t->count--;

        if (t->count == 0) { 
            t->head = NULL; 
        }

        return data;
    }

}

// Inserts a new node before the node at the specified position.
// Returns -1 if the list is NULL
// Returns 1 on success
// Retruns 0 on failure:
//  * we couldn't allocate memory for the new node
//  * we tried to insert at a negative location.
//  * we tried to insert past the size of the list
//   (inserting at the size should be equivalent as calling push_back).
int dll_insert(dll_t *l, int pos, int item)
{
    if (l == NULL) {
        return -1;
    }

    if (pos == l->count) {
        return dll_push_back(l, item);
    }

    if (pos == 0) {
        return dll_push_front(l, item);
    }

    if (pos < 0 || pos > l->count) {
        return 0;
    }

    node_t* temp = (node_t*)malloc(sizeof(node_t));
    if(temp == NULL) {
        return 0;
    }

    temp->data = item;
    node_t* curr = l->head;
    for (int i = 0; i < pos - 1; i++) {
        curr = curr->next;
    }
    
    temp->previous = curr;
    temp->next = curr->next;
    temp->next->previous = temp;
    curr->next = temp;
    l->count++;

    return 1;
}

// Returns the item at position pos starting at 0 ( 0 being the first item )
// Returns -1 if the list is NULL
//  (does not remove the item)
// Returns 0 on failure:
//  * we tried to get at a negative location.
//  * we tried to get past the size of the list
// Assume no negative numbers in the list or the number zero.
int dll_get(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }
    if (pos < 0 || pos > l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }
    return curr->data;
}

// Removes the item at position pos starting at 0 ( 0 being the first item )
// Returns -1 if the list is NULL
// Returns 0 on failure:
//  * we tried to remove at a negative location.
//  * we tried to remove get past the size of the list
// Assume no negative numbers in the list or the number zero.
// Otherwise returns the value of the node removed.
int dll_remove(dll_t *l, int pos)
{
    if (l == NULL) {
        return -1;
    }

    if (pos == l->count) {
        return dll_pop_back(l);
    }

    if (pos == 0) {
        return dll_pop_front(l);
    }

    if (pos < 0 || pos >= l->count) {
        return 0;
    }

    node_t* curr = l->head;
    for (int i = 0; i < pos; i++) {
        curr = curr->next;
    }

    node_t* temp = curr->next;
    curr->next = curr->next->next;
    int data = temp->data;
    free(temp);
    l->count--;
    return data;
}

// DLL Size
// Returns -1 if the DLL is NULL.
// Queries the current size of a DLL
int dll_size(dll_t *t)
{
    if (t == NULL) {
        return -1;
    }
    return t->count;
}

// Free DLL
void free_dll(dll_t *t)
{
    if (t == NULL) {
        return;
    }
    node_t* curr = t->head;
    node_t* next;
   
    while (curr != NULL) {
        next = curr->next;
        free(curr);
        curr = next;

    }
    free(t);
}

#endif

我尝试使用显示内存泄漏的 valgrind，但我仍然不知道如何解决这个问题

Answer 1

看起来你的代码中有多个问题。

在

dll_push_front()

中，

l->head->previous = newNode;

线应该放在

l->head

到

newNode

之前。否则，新创建的节点将指向自身作为前一个节点。你也错过了 else 块的结尾

}

。

在

dll_pop_front()

中，您正在执行

malloc()

并在下一行中覆盖该指针 (

temp

)，这会导致内存泄漏。你不需要这里的 malloc。第二个元素（被删除的元素旁边）也应该更新以将其

previous

链接设置为 NULL。

dll_pop_back()

中存在相同类型的问题。此外，如果

t->count

变为 0，不应该同时将

t->tail

和

t->head

设置为 NULL？

在

dll_remove()

中，您正在访问

curr->next->next

，但

cur->next

可能为NULL。例如，假设列表有 2 个节点。因此，

count

将是 2。但是如果有人用

dll_remove()

1 调用

pos

，则

curr

将指向最后一个元素。访问

temp->next

.

同样的问题