1

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

输入示例：

詹妮弗 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;
    }
}
4

3 回答 3

1

您的函数有多个问题：

  • l如果isNULL或 if l->nextis ，您不会返回任何内容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;
}
于 2020-03-29T18:49:22.330 回答
0

该函数具有未定义的行为，因为在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
于 2020-03-29T18:15:59.260 回答
0

似乎代码缺少一行，注释中指出：

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

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

于 2020-03-29T17:56:29.930 回答