如何在 C 语言中释放 linkedlist 中动态分配的内存

How to free dynamically allocated memory in a linkedlist in C

提问人:Cindy_ l 提问时间:10/24/2023 最后编辑:Cindy_ l 更新时间:10/24/2023 访问量:95

问:

我尝试在 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));

c 内存泄漏链接 列表 malloc

评论

2赞 001 10/24/2023
插入函数有 2 个调用 ,因此删除函数可能应该有 2 个调用。mallocfree
0赞 001 10/24/2023
并且不要忘记 in .malloccreateLinkedList
2赞 Bodo 10/24/2023
我建议编辑问题并显示一个最小的可重复示例。与内存泄漏无关:您传递给函数,但分配并复制 的大小。这意味着指针必须至少指向某些结构/数组/内存,以避免未定义的行为,并且不应超过避免数据丢失。所以它应该指向一个或相同大小的东西。如果要实现泛型函数,除了指针之外,可能还必须传递要存储的数据结构的大小。void* entryPositionsizeof(Position)memcpysizeof(Position)Position
0赞 n. m. could be an AI 10/24/2023
什么是以及为什么你会在通用实现中对它有一种记忆的冲动?PositionmallocLinkedList
1赞 Fe2O3 10/24/2023
旁白:在本问题顶部的代码块中,有 3 次调用......其中两个使用铸造,但一个不使用。您是否知道,在 C 中强制转换返回的指针是不必要的,并且被认为是一种不好的做法?(我们将把验证分配是否成功的时间留到另一天......malloc()malloc()

答:

3赞 Ian Abbott 10/24/2023 #1

deleteAll仅释放 分配的块之一。另外,我不知道你是否希望它也释放由 分配的块。中的变量实际上指向一个 ,而不是一个 。insertStartcreateLinkedListtempdeleteAllPositionListNode

试试这个:

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;
}

评论

0赞 Cindy_ l 10/24/2023
我试过这个,它奏效了,谢谢!
0赞 Cindy_ l 10/24/2023
我用了 valgrind 和另一次,现在它说内存泄漏来自void* newEntry = malloc(sizeof(Position));
2赞 Gerhardh 10/24/2023
@Cindy_l提供所要求的最小可重复示例将使我们能够提供更好的帮助。
0赞 Cindy_ l 10/24/2023
有人告诉我,编辑和删除部分问题不是首选,所以我只是添加了我的问题。应该重新安排我的问题,还是应该用MRE开始一个新问题
0赞 Gerhardh 10/24/2023
@Cindy_l 不,你不只是补充你的问题。重命名并删除了函数。你被要求什么意味着你应该添加缺失的部分,使其成为一个可编译的程序。您的更改使现有答案变得毫无用处。
0赞 n. m. could be an AI 10/24/2023 #2

考虑两个程序员,一个编写链表代码,另一个使用第一个程序员编写的链表代码,这是非常方便的。即使你同时做这两份工作,你也必须分开考虑它们。

有四种可能的有效方案。

  • 使用列表代码的用户分配数据,他还负责在自己的代码中的某个位置释放数据。
  • 链表的实现者分配数据(可能在分配列表节点的函数中的某个位置),他还负责释放数据(可能在释放列表节点的函数中的某个位置)。
  • 用户分配数据,但将释放数据的责任移交给实现者。这种情况很少见,除非您确切地知道为什么需要它以及如何正确地做到这一点,否则不要这样做。
  • 实现者分配数据,但用户负责释放数据。这在现实世界中是不存在的,永远不要那样做。

您的代码实现了第五种情况:实现者分配了数据,但完全忘记了释放数据。唉,这不是一个有效的。

实现第一个方案的代码如下所示:

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++;
}

就是这样。当然,用户需要确保他们调用的次数相同。请注意,实现者不知道也不关心列表中要存储的数据类型,因此指针。函数不会更改。mallocfreevoiddeleteAll

实现第二种方案的代码看起来会大不相同。由于列表代码知道要存储的数据类型,因此最好在类型中反映此知识。

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++;
}

请注意,没有指针。既然我们知道我们使用的是类型,我们不妨在代码中说出来。该函数需要有一两行额外的行voidPositiondeleteAll

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);

无指针方案是始终首选的方案。只有在绝对必要的情况下才使用指针(例如,你的教授告诉你要---或者你确实不知道你存储了什么样的数据)。

评论

0赞 Cindy_ l 10/24/2023
感谢您的回复,我认为我不能将 void 指针更改为 Position 指针,因为我必须保持 ListNode 结构的原样,因为它是由评估大纲给出的。我会试着通读并获得更好的理解。
0赞 Cindy_ l 10/24/2023
有没有其他解决方案,因为我无法更改虚空指针。
0赞 n. m. could be an AI 10/24/2023
我通常展示如何编程,而不是如何满足那些“教编程”的人。我对后者没有兴趣。
0赞 Ian Abbott 10/24/2023
当然,由于声明而行不通.newNode->data = *entry;void* entry
0赞 n. m. could be an AI 10/24/2023
@Cindy_l 话虽如此,如果你有一个评估大纲,你可以展示它,我可以尝试分析它,把它分解成碎片,并从中做出一些合理的东西(我的直觉是它不合理,但我知道我有时是错误的)。