LinkedList - Как освободить память, выделенную с помощью malloc - PullRequest
Новая
       37

LinkedList - Как освободить память, выделенную с помощью malloc

32 голосов
/ 11 августа 2011

У меня есть очень простой C-код для построения списка односвязных соединений, как показано ниже, в котором я динамически распределяю память для каждого узла с помощью malloc.В конце кода я хочу освободить память для каждого выделенного узла, задавался вопросом, как это сделать - если я сначала начну с головного узла и освобожу его, указатели на последующие узлы будут потеряны и произойдет утечка памяти.

Другой способ - начать с головного узла и хранить указатель узла в отдельном массиве указателей или чего-то еще, проходить по списку до указателя хвоста при сохранении указателей узла и, как только достигнет узла, сохранитьтакже к другому массиву указателей и начните освобождать индекс этого массива назад, пока не освободится головной узел.

Это единственный способ достичь того, что я пытаюсь сделать?

Если я не хочу использовать второй буфер, как мне это сделать. 

#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 ]

65 голосов
/ 11 августа 2011

Обычный способ - с (сначала псевдокод): 

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.

Основная идея - запомнить узел для освобождения в отдельной переменной, а затем перейти к следующему, прежде чем освободить его.

Вам нужно помнить только один узел за раз, а не весь список, как вы предлагаете.

Что касается того, что вам нужно добавить в свой код, вы можете при удалении использовать 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.
}

Это немного короче, чем приведенный выше псевдокод, просто потому, что в некоторых операциях он использует "сокращенную запись" C.

9 голосов
/ 11 августа 2011

Я использую что-то вроде этого: 

for (p = curr; NULL != p; p = next) {
    next = p->next;
    free(p);
}
2 голосов
/ 11 августа 2011

Ваш бесплатный код должен быть следующим: 

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

Также я хотел бы добавить после вашего malloc, вы, вероятно, хотите проверить, был ли мем успешно распределен .. что-то вроде 

if(curr)
1 голос
/ 11 августа 2011

Вы просматриваете список, используя ту же логику, что и выше. Вы сохраняете curr-> next указатель где-нибудь, освобождаете структуру curr и назначаете curr с сохраненным curr-> next указатель

0 голосов
/ 02 января 2014

Содержимое сборщика мусора. Ч 

#include <stdlib.h>
#include <stdint.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__);

Пример some_program.c Постскриптум Заголовок systemIO - это группа из нескольких заголовков, как показано выше! :) 


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 ....
...