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