Блог

Допустим, у меня следующая структура

 typedef struct node {
    unsigned long data;
    struct node* next;
} node;

typedef struct queue {
    node* head;
    node* tail;
    int size;
    int capacity;
} queue;

queue* buildar()
{
    queue* arr = malloc(num * sizeof(queue));
    int i;
    for (i = 0; i < num; i  )
    {
        queue* r = malloc(sizeof(queue));
        r->head = NULL;
        r->tail = NULL;
        r->size = 0;
        r->capacity = assoc;
        arr[i] = *r;
    }
    return arr;
}
 

Как я могу освободить все элементы в очереди?
Я уже пытался это сделать

     for (size_t i = 0; i < numberofsets; i  )
    {
        node* temp = arr[i].head;
        arr[i].head = arr[i].head->next;
        free(temp);
    }
    free(arr);
 

но, похоже, это не работает. Любая помощь приветствуется.

Вы ищете массив массивов (я думаю / надеюсь). По сути, вы хотите создать n очереди, которые все индексируются (это слово?) Из одного «главного» массива.

Итак, вы смотрите на это так:

 idx
of
big
arry
_________________________________  
|000|   ----->  [ one big queue ]  
|001|   ----->  [ one big queue ]  
|002|   ----->  [ one big queue ]  
|003|   ----->  [ one big queue ]  
|004|   ----->  [ one big queue ]  
|...|   ----->  .................   
|nth|   ----->  [ one big queue ]  
_________________________________  
 

 #include <stdlib.h>


typedef struct node
{
    unsigned long data;
    struct node*  next;
}
node;

typedef struct queue
{
    int   size;
    int   capacity;
    node* head;
    node* tail;
    
}
queue;


queue** build_queue(int num  ,
                    int assoc
                   )
{
    //here you create an array of arrays
    //result is an array of pointers, each pointer going to a separate array 
    queue** result = malloc(num * sizeof(queue*));
    
    int i;
    for (i = 0; i < num; i  )
    {
        queue* q    = malloc(sizeof(queue));  //memory for actual queue
        result[i]   = q;

        q->head     = NULL;
        q->tail     = NULL;
        q->size     = 0;
        q->capacity = assoc;
    }

    return resu<
}



void free_queues(int     num_queues,
                 queue** qs
                )
{
    int i;
    for (i = 0; i < num_queues; i  )
    {
       /*
        * NOTE: you must use a while loop here to FIRST free the linked list qs[i]
        * node* head = qs[i]->head;
        * while(head != qs[i]->tail)
        * {
        *     node* temp = head->next;
              free(head);
              head = temp;
        * }
        * free(qs[i]->tail);
        */
       free(qs[i]);  //frees the actual queue struct   
    }
    free(qs);        //frees the array of pointers to queues
}



int main(void)
{
   int num   = 5;
   int assoc = 4;
 
   queue** qs = build_queue(num, assoc);
   free_queues(num, qs);

   return 1;
}
 

Наконец, используйте valgrind для проверки наличия утечек. Для приведенного выше решения:

 $ gcc please_work.c
$ valgrind ./a.out 
==5974== Memcheck, a memory error detector
==5974== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==5974== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==5974== Command: ./a.out
==5974== 
==5974== 
==5974== HEAP SUMMARY:
==5974==     in use at exit: 0 bytes in 0 blocks
==5974==   total heap usage: 6 allocs, 6 frees, 160 bytes allocated
==5974== 
==5974== All heap blocks were freed -- no leaks are possible
==5974== 
==5974== For lists of detected and suppressed errors, rerun with: -s
==5974== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

 

Трудно догадаться, что означает «похоже, не работает», но есть несколько проблем с кодом.

В buildar() вы используете две неопределенные переменные. Они могут быть у вас как глобальные переменные, но вы, вероятно, хотите, чтобы они были аргументами функции. Вы также допускаете утечку памяти, потому что вы malloc() создаете новую ссылку, инициализируете ее, копируете значения там в массив, а затем выбрасываете выделенную память, которая теперь никогда не будет освобождена.

 // added num amp; assoc here--assuming it should be a parameter
queue* buildar(int num, int assoc) 
{
    queue* arr = malloc(num * sizeof(queue));
    int i;
    for (i = 0; i < num; i  )
    {
        // This will leak memory. You allocate a root
        // that you initialise, then you copy the data
        // and then you throw away the allocated memory
        // when you update r, or it goes out of scope
        queue* r = malloc(sizeof(queue));
        r->head = NULL;
        r->tail = NULL;
        r->size = 0;
        r->capacity = assoc;
        arr[i] = *r;
    }
    return arr;
}
 

Поскольку у вас уже есть корневые ссылки в массиве, вы можете просто обновить их и избежать malloc() :

 queue* buildar(int num, int assoc) 
{
    queue* arr = malloc(num * sizeof *arr);
    for (int i = 0; i < num; i  )
    {
        arr[i].head = NULL;
        arr[i].tail = NULL;
        arr[i].size = 0;
        arr[i].capacity = assoc;
    }
    return arr;
}
 

В коде освобождения, если корневые узлы недавно инициализированы, их head указатель NULL . Это будет проблемой, когда вы разыменуете их, чтобы получить head->next . Технически разыменование NULL — это неопределенное поведение, но на практике это будет ошибка сегментации, которая приведет к сбою вашей программы. Если на запись приходится более одного узла, произойдет утечка памяти. Вы освобождаете первый после корня, затем указываете заголовок корня на следующий, а затем освобождаете массив, содержащий корень.

Насколько я вижу, код будет работать по назначению, если для каждого индекса есть ровно один узел (после корня), но сбой, если есть ноль, и утечка, если их больше. Если предполагается, что число узлов должно быть переменным, это один из источников «похоже, не работает». Может ли это быть так?

 void free_queues(queue *arr, int numberofsets)
{
  for (size_t i = 0; i < numberofsets; i  )
  {
    node* temp = arr[i].head;
    // if the queue was empty, arr[i].head->next
    // dereferences a NULL pointer, which is
    // undefined behaviour
    arr[i].head = arr[i].head->next;
    // This only removes one link from the queue.
    // If there are more, you leak memory when you
    // free arr below
    free(temp);
  }
  free(arr);
}
 

Если это так, вам может понадобиться что-то вроде:

 void free_queues(queue *arr, int numberofsets)
{
  for (size_t i = 0; i < numberofsets; i  ) {
    node* temp = arr[i].head, *next;
    while (temp) {
      next = temp->next;
      free(temp);
      temp = next;
    }
  }
  free(arr);
}