双向链接列表测试错误消息:free():在tcache 2中检测到双重释放

1sbrub3j  于 2023-03-07  发布在  其他
关注(0)|答案(1)|浏览(126)

我是一个初学者在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,显示内存泄漏,但我仍然不知道如何解决这个问题

eqqqjvef

eqqqjvef1#

您的代码中似乎存在多个问题。
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->tailt->head不都应该设置为NULL吗?
dll_remove()中,您正在访问curr->next->next,但cur->next可能为NULL。例如,假设列表有2个节点。因此,count将为2。但如果有人使用pos 1调用dll_remove(),则curr将指向最后一个元素。访问temp->next时也会出现同样的问题。

相关问题