Рекурсивно удалить узел с несколькими полями в одном связанном списке в C

Question

Я пытаюсь удалить все узлы пользователей, возраст которых меньше указанного предела. Проблема в том, что реализация этой функции неверна. Алгоритм должен быть рекурсивным.

Пример ввода:

Jennifer 11
John 19
Sarah 17
Mark 24

Пример вывода:

(null) 11
John 19
 17
Mark 24

Вот код:

struct list *delete_node(struct list *l, int limit) {
    if (l != NULL) {
        if (l->age < limit) {
            struct list *tmp;
            tmp = l->next;
            free(l);
        }
        if (l->next != NULL)
            l->next = delete_node(l->next, limit);
        else
            return l;
    }
}

Answer 1

У вашей функции несколько проблем:

• вы ничего не возвращаете, если l равно NULL или l->next равно NULL.
• l недействителен после удаления узла. Вы должны вернуть delete_node(tmp, limit) после free(l);. Чтобы иметь один оператор return, вы можете установить l на это значение.

Вот модифицированная версия:

struct list *delete_node(struct list *l, int limit) {
    if (l != NULL) {
        if (l->age < limit) {
            struct list *tmp;
            tmp = l->next;
            free(l);
            l = delete_node(tmp, limit);
        } else {
            l->next = delete_mode(l->next, limit);
        }
    }
    return l;
}

Answer 2

Функция имеет неопределенное поведение, потому что ничего не возвращает в случае, если l->next не равно NULL.

//...
if (l->next != NULL)
    l->next = delete_node (l->next, limit);
else
    return l;
}

Также в этом фрагменте кода

if (l->age < limit){
    struct list* tmp;
    tmp = l->next;
    free(l);
}

указатель l имеет недопустимое значение после удаления указанной памяти.

Функция может быть реализована следующим образом

struct list * delete_node( struct list *l, int limit )
{
    if ( l != NULL )
    {
        if ( l->age < limit )
        {
            struct list *tmp = l;
            l = l->next;
            free( tmp );
            l = delete_node( l, limit );
        }
        else
        {
            l->next = delete_node( l->next, limit );
        }
    }

    return l;
}

Вот демонстрационная программа. Функция, которая отображает список, также записывается как рекурсивная функция.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct list
{
    int age;
    struct list *next;
};

struct list * delete_node( struct list *l, int limit )
{
    if ( l != NULL )
    {
        if ( l->age < limit )
        {
            struct list *tmp = l;
            l = l->next;
            free( tmp );
            l = delete_node( l, limit );
        }
        else
        {
            l->next = delete_node( l->next, limit );
        }
    }

    return l;
}

void display( struct list *l )
{
    if ( l == NULL )
    {
        puts( "null" );
    }
    else
    {
        printf( "%d -> ", l->age );
        display( l->next );
    }
}

int push_front( struct list **l, int age )
{
    struct list *current = malloc( sizeof( struct list ) );
    int success = current != NULL;

    if ( success )
    {
        current->age = age;
        current->next = *l;
        *l = current;
    }

    return success;
}

int main(void) 
{
    enum { Lower = 7, Upper = 20 };

    struct list *head = NULL;

    srand( ( unsigned int )time( NULL ) );

    for ( int i = Lower; i < Upper; ++i )
    {
        int age = rand() % ( Upper - Lower + 1 ) + Lower;
        push_front( &head, age );
    }

    display( head );

    head = delete_node( head, ( Upper + Lower ) / 2 );

    display( head );

    head = delete_node( head, Upper + 1 );

    display( head );

    return 0;
}

Вывод программы может выглядеть как

14 -> 11 -> 8 -> 15 -> 8 -> 13 -> 16 -> 18 -> 11 -> 8 -> 18 -> 13 -> 12 -> null
14 -> 15 -> 13 -> 16 -> 18 -> 18 -> 13 -> null
null

Answer 3

Похоже, что в коде отсутствует одна строка, отмеченная в комментарии:

    if (l->age < limit){
        struct list* tmp;
        tmp = l->next;
        free(l);
        l = tmp;                   // fix
    }

На вопрос "chqrl ie для желтых цитат" есть и другие проблемы, которые он исправил в своем ответе. Вы прокомментировали, что это было решено, но я не знаю, обрабатывает ли ваш фиксированный код все случаи (первый узел, последний узел, смежные узлы, ...). Вы можете обновить свой вопрос с полным решенным кодом.