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

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

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

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

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

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


}

Ответ 1

Обычным способом является (сначала псевдокод):

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.

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

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

if(curr)

Ответ 4

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

Ответ 5

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

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