在C中递归地删除单个链表中具有多个字段的节点

Question

我正在尝试删除年龄小于给定限制的所有用户节点。问题是这个函数的实现不正确。算法必须是递归的。

输入示例：

詹妮弗 11
约翰 19
莎拉 17
马克 24

输出示例：

（空）11
约翰 19
 17
马克 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

好像代码少了一行，注释中指出：

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

正如 "chqrlie for yellow blockquotes" 所回答的，还有其他问题，他已经在他的回答中解决了。您评论说它已解决，但我不知道您的固定代码是否可以处理所有情况（第一个节点，最后一个节点，相邻节点，...）。您可以使用完整的已解决代码更新您的问题。

Answer 2

该函数具有未定义的行为，因为它 returns 在 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

你的函数有多个问题：

如果 l 是 NULL 或者 l->next 是 NULL，你就不会 return 任何东西。
l删除节点后无效。你应该在 free(l); 之后 return delete_node(tmp, limit)。要有单个 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;
}

在C中递归地删除单个链表中具有多个字段的节点

Delete a node with multiple fields in a single Linked List recursively in C

c

recursion

linked-list

singly-linked-list

function-definition