что делает эта свободная рекурсивная функция списка связанных списков?

Question

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

typedef struct listint_s
{
    char *a;
    char *b;
    struct listint_s *next;
} listint_t;

void free_list(listint_t *head)
{
    if (head)
    {
        if (head->next)
            free_list(head->next);
        free(head->a);
        free(head);
    }
}

Answer 1

Если вы хотите узнать, что делает free(), посмотрите Как работает malloc и free . Что касается free_list():

Это рекурсивная функция, потому что структура связанного списка (то есть listin_s) является рекурсивной. То есть *next сам по себе listint_s. Следовательно, он пригоден для рекурсивной операции. Если мы можем определить структуру как «вещь, содержащую два символа * и указатель на остальную часть списка», мы можем определить операцию освобождения как «освободить оставшуюся часть списка, а затем освободить эту вещь, которая имеет два char * и указатель на остальную часть списка ". Аннотированный:

void free_list(listint_t *head)
{
    if (head) // If this thing is not null
    {
        if (head->next) // If the rest of the list is not null (i.e. we have not reached the end of the list yet)
            free_list(head->next); // Free the rest of the list
        free(head->a); // Then, free the thing pointed to by *a (note for some reason we are not freeing b?)
        free(head); // Then, free this thing
    }
}

Answer 2

Это освобождает все узлы в списке, а также то, на что они указывают от своих a членов (но не * b членов).

Рекурсивные вызовы сначала проходят через узлы списка, пока не достигнут узла, элемент head->next которого равен NULL.

В каждом рекурсивном вызове head указывает на текущий элемент. После возврата рекурсивного вызова он освобождает то, на что указывает head->a, а затем освобождает текущий элемент с помощью free(head);.

Тест if (head->next) является избыточным, поскольку free_list() проверяет, вызывается ли он по нулевому указателю с помощью if (head).

Большинство людей пишут такие циклы итеративно, а не рекурсивно, поскольку вы можете получить переполнение стека при попытке освободить действительно длинный список.

while (head) {
    free(head->a);
    listint_s *temp = head;
    head = head->next;
    free(temp);
}

Answer 3

Рекурсия здесь используется для бесплатного вызова для каждого элемента списка.Первый вызов free_list должен обработать головной узел.Второй вызов действует на head-> next и так далее.Обратите внимание, что входной узел освобождается только после вызова free_list (head-> next).Если бы это было не так, связанный список не смог бы освободить элементы, следующие за заголовком.

То же самое можно сделать с помощью цикла while вместо рекурсии:

{
    listint_t *next;
    while (head)
    {
        next = head->next;
        free(head);
        head = next;
    }
    return;
}