LinkedList - Cách giải phóng bộ nhớ được cấp phát bằng cách sử dụng malloc

Question

Tôi có một mã C rất đơn giản để xây dựng một danh sách Liên kết đơn như dưới đây, trong đó tôi cấp phát bộ nhớ cho mỗi nút động bằng cách sử dụng malloc. Ở cuối mã, tôi muốn giải phóng bộ nhớ cho mỗi nút được phân bổ, đã tự hỏi làm thế nào để đi về nó - Nếu tôi bắt đầu từ đầu nút đầu tiên và miễn phí nó, các con trỏ đến các nút tiếp theo bị mất và rò rỉ bộ nhớ xảy ra. Cách khác là bắt đầu từ nút đầu và tiếp tục lưu trữ con trỏ nút trong một mảng riêng biệt của con trỏ hoặc một cái gì đó, đi qua danh sách cho đến khi con trỏ đuôi trong khi lưu trữ các nút con trỏ, và một khi đạt đến nút đuôi, lưu trữ mà còn để các mảng con trỏ khác và bắt đầu giải phóng từ chỉ mục mảng đó trở lại cho đến khi nút đầu được miễn phí.

Đó có phải là cách duy nhất để đạt được những gì tôi đang cố gắng làm không?

Trong trường hợp nếu tôi không muốn sử dụng bộ đệm thứ hai, tôi làm cách nào để thực hiện.

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


} 

Answer 1

Cách thông thường là với (mã giả trước):

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. 

Ý tưởng cơ bản là nhớ nút để giải phóng trong một biến riêng biệt rồi chuyển sang nút tiếp theo trước khi giải phóng nó.

Bạn chỉ cần nhớ một nút cùng một lúc, không phải toàn bộ danh sách như bạn đề xuất.

Về những gì bạn cần thêm vào mã của mình, bạn có thể, trong khi xóa, sử dụng head làm đầu danh sách cập nhật liên tục (có nghĩa là) và curr để lưu trữ mục bạn hiện đang xóa:

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

Đây ngắn hơn một chút so với mã giả ở trên đơn giản chỉ vì nó tận dụng "viết tắt" C cho một số thao tác.

Answer 2

mã miễn phí của bạn nên thực hiện như sau:

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

Ngoài ra tôi muốn thêm sau malloc của bạn, bạn có thể muốn kiểm tra xem các mem đã được phân bổ thành công .. cái gì đó như

if(curr) 

Answer 3

Bạn duyệt qua danh sách bằng cùng một logic như trên. Bạn lưu curr-> trỏ tới nơi nào đó, giải phóng struct Curr và gán Curr với lưu curr-> trỏ tới

Answer 4

tôi sử dụng một cái gì đó như thế này:

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

Answer 5

Hàm lượng rác 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__); 

Ví dụ về some_program.c PS header systemIO là nhóm nhiều tiêu đề như thế này! :)

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