链表 - 如何释放使用malloc分配的内存

Question

我有一个非常简单的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
   }


}

- goldenmean

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

基本思想是在释放节点之前将要释放的节点记入一个单独的变量，然后再移动到下一个节点。

你只需要一次记住一个节点，而不是像你提出的那样记住整个列表。

在代码方面，你可以在删除时使用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 语言中某些操作的简写方式。

- paxdiablo

Answer 2

我使用类似这样的代码：

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

- cnicutar

Answer 3

您的免费代码应该如下:

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

我想补充一点，在你使用malloc之后，你可能需要检查内存是否成功分配..类似于：

if(curr)

- Baz1nga

---

不行。你不能在释放后访问head。 - duedl0r

你不能访问“head”指向的内存，但是将新值分配给“head”本身是完全可以的。 - Spacechild1

Answer 4

您可以使用与上面相同的逻辑遍历列表。您可以将 curr->next 指针保存在某个地方，释放 curr 结构并将 curr 分配给保存的 curr->next 指针。

- duedl0r

Answer 5

Garbage Collector.h 的内容

#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 的示例 P.S. header 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 .... 

- CCC