提问人:Cindy_ l 提问时间:10/24/2023 最后编辑:Cindy_ l 更新时间:10/24/2023 访问量:95
如何在 C 语言中释放 linkedlist 中动态分配的内存
How to free dynamically allocated memory in a linkedlist in C
问:
我尝试在 C 中实现链表,但由于没有释放一些 malloc 的变量,我有一些内存泄漏。我不确定何时以及如何释放它们,因为我无法在使用它们之前释放它们。
这是我的 insertStart 代码
void main()
{
LinkedList* undo = createLinkedList();
Position* place = (Position*)malloc(sizeof(Position));
place->row = 1;
place->col = 2;
insertStart(undo, (void*)place);
}
void insertStart(LinkedList* list, void* entry)
{
void* newEntry = malloc(sizeof(Position));
ListNode* newNd = (ListNode*)malloc(sizeof(ListNode));
memcpy(newEntry, entry, sizeof(Position));
newNd->data = newEntry;
newNd->next = list->head;
list->head = newNd;
list->size++;
}
我从管路上得到泄漏void* newEntry = malloc(sizeof(Position));
我尝试使用 valgrind,这就是它输出的内容,
==1385==
==1385== HEAP SUMMARY:
==1385== in use at exit: 900 bytes in 19 blocks
==1385== total heap usage: 78 allocs, 59 frees, 14,808 bytes allocated
==1385==
==1385== 20 bytes in 1 blocks are definitely lost in loss record 1 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x109668: controls (game.c:78)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 48 bytes in 2 blocks are indirectly lost in loss record 2 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x10AA5B: insertStart (linkedList.c:24)
==1385== by 0x109829: controls (game.c:114)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 48 bytes in 2 blocks are indirectly lost in loss record 3 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x10AA5B: insertStart (linkedList.c:24)
==1385== by 0x1099F2: controls (game.c:144)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 120 bytes in 5 blocks are indirectly lost in loss record 4 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x10AA5B: insertStart (linkedList.c:24)
==1385== by 0x109910: controls (game.c:129)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 168 bytes in 7 blocks are indirectly lost in loss record 5 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x10AA5B: insertStart (linkedList.c:24)
==1385== by 0x109AD9: controls (game.c:159)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 408 (24 direct, 384 indirect) bytes in 1 blocks are definitely lost in loss record 6 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x10AA5B: insertStart (linkedList.c:24)
==1385== by 0x109AD9: controls (game.c:159)
==1385== by 0x109596: game (game.c:44)
==1385== by 0x109455: main (main.c:49)
==1385==
==1385== 472 bytes in 1 blocks are still reachable in loss record 7 of 7
==1385== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==1385== by 0x48DF64D: __fopen_internal (iofopen.c:65)
==1385== by 0x48DF64D: fopen@@GLIBC_2.2.5 (iofopen.c:86)
==1385== by 0x109347: main (main.c:26)
==1385==
==1385== LEAK SUMMARY:
==1385== definitely lost: 44 bytes in 2 blocks
==1385== indirectly lost: 384 bytes in 16 blocks
==1385== possibly lost: 0 bytes in 0 blocks
==1385== still reachable: 472 bytes in 1 blocks
==1385== suppressed: 0 bytes in 0 blocks
==1385==
==1385== For lists of detected and suppressed errors, rerun with: -s
==1385== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
我也搜索了它并尝试实现这个deleteAll方法,但它似乎仍然不起作用。
我已经更新了我的 deleteAll 函数,现在它是 Valgrind 输出。
==3055==
==3055== HEAP SUMMARY:
==3055== in use at exit: 20 bytes in 1 blocks
==3055== total heap usage: 72 allocs, 71 frees, 14,676 bytes allocated
==3055==
==3055== 20 bytes in 1 blocks are definitely lost in loss record 1 of 1
==3055== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==3055== by 0x10AA80: insertStart (linkedList.c:22)
==3055== by 0x109A1E: controls (game.c:144)
==3055== by 0x1095C2: game (game.c:44)
==3055== by 0x109475: main (main.c:49)
==3055==
==3055== LEAK SUMMARY:
==3055== definitely lost: 20 bytes in 1 blocks
==3055== indirectly lost: 0 bytes in 0 blocks
==3055== possibly lost: 0 bytes in 0 blocks
==3055== still reachable: 0 bytes in 0 blocks
==3055== suppressed: 0 bytes in 0 blocks
==3055==
==3055== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
现在它说泄漏来自:void* newEntry = malloc(sizeof(Position));
答:
deleteAll
仅释放 分配的块之一。另外,我不知道你是否希望它也释放由 分配的块。中的变量实际上指向一个 ,而不是一个 。insertStart
createLinkedList
temp
deleteAll
Position
ListNode
试试这个:
void deleteAll(LinkedList* list)
{
while (list->head != NULL)
{
ListNode* temp = list->head;
list->head = list->head->next;
free(temp->data);
free(temp);
}
free(list); // not sure if you want this or not
}
下面是使用该函数的完整示例。省略了返回值的错误检查:malloc
#include <stdlib.h>
#include <string.h>
typedef struct listNode ListNode;
struct listNode
{
struct listNode *next;
void *data;
};
typedef struct
{
ListNode *head;
ListNode *tail;
unsigned int size;
} LinkedList;
typedef struct
{
int row;
int col;
} Position;
LinkedList* createLinkedList(void)
{
LinkedList* newList;
newList = (LinkedList*)malloc(sizeof(LinkedList));
newList->head = NULL;
newList->tail = NULL;
newList->size = 0;
return newList;
}
void insertStart(LinkedList* list, void* entry)
{
void* newEntry = malloc(sizeof(Position));
ListNode* newNd = (ListNode*)malloc(sizeof(ListNode));
memcpy(newEntry, entry, sizeof(Position));
newNd->data = newEntry;
newNd->next = list->head;
list->head = newNd;
// I added the following bit to set list->tail ...
if (newNd->next == NULL)
{
list->tail = newNd;
}
list->size++;
}
void deleteAll(LinkedList* list)
{
while (list->head != NULL)
{
ListNode* temp = list->head;
list->head = list->head->next;
free(temp->data);
free(temp);
}
free(list);
}
int main(void)
{
LinkedList* undo = createLinkedList();
Position place = { .row = 1, .col = 2 };
insertStart(undo, &place);
deleteAll(undo);
return 0;
}
评论
void* newEntry = malloc(sizeof(Position));
考虑两个程序员,一个编写链表代码,另一个使用第一个程序员编写的链表代码,这是非常方便的。即使你同时做这两份工作,你也必须分开考虑它们。
有四种可能的有效方案。
- 使用列表代码的用户分配数据,他还负责在自己的代码中的某个位置释放数据。
- 链表的实现者分配数据(可能在分配列表节点的函数中的某个位置),他还负责释放数据(可能在释放列表节点的函数中的某个位置)。
- 用户分配数据,但将释放数据的责任移交给实现者。这种情况很少见,除非您确切地知道为什么需要它以及如何正确地做到这一点,否则不要这样做。
- 实现者分配数据,但用户负责释放数据。这在现实世界中是不存在的,永远不要那样做。
您的代码实现了第五种情况:实现者分配了数据,但完全忘记了释放数据。唉,这不是一个有效的。
实现第一个方案的代码如下所示:
void insertStart(LinkedList* list, void* entry)
{
ListNode* newNode = malloc(sizeof(*newNode));
newNode->next = list->head;
newNode->data = entry; // <---- pay attention to this
list->head = newNode;
list->size++;
}
就是这样。当然,用户需要确保他们调用的次数相同。请注意,实现者不知道也不关心列表中要存储的数据类型,因此指针。函数不会更改。malloc
free
void
deleteAll
实现第二种方案的代码看起来会大不相同。由于列表代码知道要存储的数据类型,因此最好在类型中反映此知识。
typedef struct node
{
Position* data;
struct node* next;
} ListNode;
void insertStart(LinkedList* list, Position* entry)
{
Position* newEntry = malloc(sizeof(*newEntry));
*newEntry = *entry;
// or: memcpy(newEntry, entry, sizeof(*newEntry));
ListNode* newNode = malloc(sizeof(*newNode));
newNode->data = newEntry;
newNode->next = list->head;
list->head = newNd;
list->size++;
}
请注意,没有指针。既然我们知道我们使用的是类型,我们不妨在代码中说出来。该函数需要有一两行额外的行void
Position
deleteAll
void deleteAll(LinkedList* list)
{
while (list->head != NULL)
{
ListNode* temp = list->head;
list->head = list->head->next;
free(temp->data); // <---- we allocated it, we free it
free(temp); // <---- we allocated it, we free it
}
free(list); // <---- we allocated it, we free it
}
现在是忏悔的好时机。我撒谎了。还有另一种有效的方案,即没有数据指针。列表节点按值存储数据。
typedef struct node
{
Position data; // <---- No pointer
struct node* next;
} ListNode;
void insertStart(LinkedList* list, void* entry)
{
ListNode* newNode = malloc(sizeof(*newNode));
newNode->next = list->head;
newNode->data = *entry; // <---- pay attention to this
list->head = newNode;
list->size++;
}
deleteAll
只是松开了线。就是这样。free(temp->data);
无指针方案是始终首选的方案。只有在绝对必要的情况下才使用指针(例如,你的教授告诉你要---或者你确实不知道你存储了什么样的数据)。
评论
newNode->data = *entry;
void* entry
评论
malloc
free
malloc
createLinkedList
void* entry
Position
sizeof(Position)
memcpy
sizeof(Position)
Position
Position
malloc
LinkedList
malloc()
malloc()