我是一个初学者在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,显示内存泄漏,但我仍然不知道如何解决这个问题
1条答案
按热度按时间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->tail
和t->head
不都应该设置为NULL吗?在
dll_remove()
中,您正在访问curr->next->next
,但cur->next
可能为NULL。例如,假设列表有2个节点。因此,count
将为2。但如果有人使用pos
1调用dll_remove()
,则curr
将指向最后一个元素。访问temp->next
时也会出现同样的问题。