LinkedList -如何释放使用malloc分配的内存。

I have a very simple C code for constructing a Singly Linked list as below, in which I allocate memory for each node dynamically using malloc. At the end of code, I want to free the memory for each node allocated, was wondering how to go about it - If I start from head node first and free it, the pointers to the subsequent nodes are lost and memory leak happens.

我有一个非常简单的C代码来构造一个单独的链表，如下所示，我为每个节点动态地使用malloc分配内存。在代码的最后，我想要释放每个分配的节点的内存，我想知道如何去做——如果我先从head节点开始并释放它，那么指向后续节点的指针就会丢失，内存泄漏就会发生。

Other way is start from head node and keep storing the node pointer in a separate array of pointers or something, traverse the list till the tail pointer while storing the node pointers, and once reach the tail node, store that also to the other array of pointers and start freeing from that array index backwards until the head node is free'ed.

其他方法是从头开始节点和存储节点指针保存在一个单独的数组的指针,直到尾指针遍历列表,存储节点的指针,而一旦到达尾节点,存储也到另一个数组的指针和向后从数组索引开始释放,直到头节点是“*”。

Is that the only way to achieve what I am trying to do?

这是实现我想做的事情的唯一途径吗?

In case if I dont want to use second buffer, how do I go about it.

如果我不想使用第二个缓冲区，我该怎么做呢?

#include "stdio.h"
#include "stdlib.h"

struct lnk_lst 
{
   int val;
   struct lnk_lst * next;
};

typedef struct lnk_lst item;


main()
{
   item * curr, * head;
   int i,desired_value;

   head = NULL;

   for(i=1;i<=10;i++) 
   {
      curr = (item *)malloc(sizeof(item));
      curr->val = i;
      curr->next  = head;
      head = curr;
   }

   curr = head;


   while(curr) {
      printf("%d\n", curr->val);
      curr = curr->next;
   }

  //How to free the memory for the nodes in this list?
   for(i=1;i<=10;i++)
   {
       free()//?? What logic here
   }


}

5 个解决方案

#1

The usual way is with (pseudo-code first):

通常的方式是(伪代码优先):

node = head              # start at the head.
while node != null:      # traverse entire list.
    temp = node          # save node pointer.
    node = node.next     # advance to next.
    free temp            # free the saved one.
head = null              # finally, mark as empty list.

The basic idea is to remember the node to free in a separate variable then advance to the next before freeing it.

基本的思想是记住节点在一个单独的变量中释放，然后在释放它之前提前到下一个变量。

You only need to remember one node at a time, not the entire list as you propose.

您只需要一次记住一个节点，而不是您建议的整个列表。

In terms of what you need to add to your code, you can, during deletion, use head as the continuously updating list head (as it's meant to be) and curr to store the item you're currently deleting:

在您需要添加到代码的内容方面，您可以在删除期间使用head作为连续更新列表头(这意味着是)和curr来存储当前正在删除的项:

while ((curr = head) != NULL) { // set curr to head, stop if list empty.
    head = head->next;          // advance head to next element.
    free (curr);                // delete saved pointer.
}

This is a little shorter than the pseudo-code above simply because it takes advantage of C "shorthand" for some operations.

这比上面的伪代码稍短一些，因为它利用了一些操作的C“速记”。

#2

I use something like this:

我用这样的东西:

for (p = curr; NULL != p; p = next) {
    next = p->next;
    free(p);
}

#3

Your free code should be as follows:

您的免费代码如下:

lnk_lst temp = null;
while(head) 
{
  temp = head->next;
  free(head);
  head = temp;
}

Also I would like to add after your malloc you probably want to check whether the mem was allocated successfully.. something like

另外，我还想添加您的malloc，您可能想要检查mem是否被成功分配。类似的

if(curr)

#4

You traverse the list using the same logic as above. You save the curr->next pointer somewhere, free the curr struct and assign curr with the saved curr->next pointer

您使用与上面相同的逻辑遍历列表。您将curr->的下一个指针保存在某个地方，释放curr struct并将curr与保存的curr->下一个指针进行分配。

#5

Content of Garbage Collector.h

内容的垃圾Collector.h

#define Stack struct _stack
#define _MALLOC_S(type,num) (type *)_GC_malloc(sizeof(type)*num)
#pragma pack(1)

//Structure for adressing alocated memory into.

Stack {

    int *adress_i;
    char *adress_c;
    float *adress_f;
    double *adress_d;
    Stack *next;
};

//Safe malloc

void *_GC_malloc(size_t size)
{
    void* ptr = malloc(size);
    if(ptr == NULL)
        return _GC_malloc(size);
    else
        return ptr;
}

//Push new element on Stack after every malloc

void Add_New(int *i, float *f , double *d , char *c , Stack *p)
{
    Stack *q =  _MALLOC_S(Stack,1);

        q->adress_i = i;
        q->adress_f = f;
        q->adress_c = c;
        q->adress_d = d;

        q->next = p->next;
        p->next = q;
        q = NULL;
}

//before ending program remove adresses that was allocated in memory, and pop entire Stack

void Free_All(Stack *p)
{
    //free head (dummy element)
    Stack *Temp = p->next;
    Stack *_free = p;
    free(_free);

    void *oslobodi;

    while(Temp != NULL)
    {
        _free = Temp;
        Temp = _free->next;

        if(_free->adress_i != NULL){
            oslobodi = _free->adress_i;
            free((int *)oslobodi);
        }
        else if(_free->adress_c != NULL){
            oslobodi = _free->adress_c;
            free((char *)oslobodi);
        }
        else if(_free->adress_f != NULL){
            oslobodi = _free->adress_f;
            free((float *)oslobodi);
        }
        else{
            oslobodi = _free->adress_d;
            free((double *)oslobodi);
        }

        free(_free);
    }

    _free = p = Temp;
}

/*  
    declare variable (var) and dinamicly alocate memory with simple macro, 
    and add to stack of linked list
*/

#define obj_int(var)        int *var = _MALLOC_S(int,1);        *var = 0;   Add_New(var, NULL, NULL, NULL, Head); 
#define obj_char(var)       char *var = _MALLOC_S(char,1);  *var = 0;   Add_New(NULL, NULL, NULL, var, Head);
#define obj_float(var)      float *var = _MALLOC_S(float,1);    *var = 0;   Add_New(NULL, var, NULL, NULL, Head);
#define obj_double(var)     double *var = _MALLOC_S(double,1);  *var = 0;   Add_New(NULL, NULL, var, NULL, Head);
#define obj_struct(_type,_name) struct _type _*name = (struct _type *)malloc(sizeof(struct _type));

#define _INIT_ROW(var,num)  for(int i = 0; i < num; i++) var[i] = 0;

/*
    same, but for row!

*/

#define row_int(var, num)   int *var =  _MALLOC_S(int,num);     _INIT_ROW(var,num)  Add_New(var, NULL, NULL, NULL, Head); 
#define row_char(var, num)  char *var =  _MALLOC_S(char,num);       _INIT_ROW(var,num)  Add_New(NULL, NULL, NULL, var, Head);
#define row_float(var, num) float *var =  _MALLOC_S(float,num);     _INIT_ROW(var,num)  Add_New(NULL, var, NULL, NULL, Head);
#define row_double(var, num)    double *var =  _MALLOC_S(double,num);   _INIT_ROW(var,num)  Add_New(NULL, NULL, var, NULL, Head);
#define string(var, value)  row_char(var, (strlen(value)+1)) strcpy(var, value);

/* with this you create a Stack and allocate dummy element */

#define Main(_type) _type main(void) { Stack *Head = _MALLOC_S(Stack,1); Head->next = NULL; Stack *_q_struct;

/* with this macro you call function for dealocate memory (garbage collecting)*/

#define End         Free_All(Head); }

/*same thing for the other functions*/

#define Function(name_function, _type, ...) _type name_function(##__VA_ARGS__) { Stack *Head = _MALLOC_S(Stack,1); Head->next = NULL;
#define End_Ret(ret_var)            Free_All(Head); return (ret_var); }
#define Call(name_function, ...)        name_function(##__VA_ARGS__)

#define Define_Function(name_function, _type, ...) _type name_function(##__VA_ARGS__);

Example of some_program.c P.S. header systemIO is group of more headers like this above! :)

some_program的例子。header systemIO是这样一组更多的头文件!:)

#include <systemIO.h>

    Main(void)          

         int num_elements = 10;

         row_int(row_elements, num_elements); //alocating row_elements object

         for(int i = 0; i < num_elements; i++)
              row_elements[i] = i; //initializing row_elements

    End //Garbage delete row_elements and end of program

    // row_int[0] = 0, row_int[1] = 1 ....