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

Question

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

输入示例：

詹妮弗11约翰19Sarah 17标记24

输出示例：

(null(11约翰1917标记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无效。您应该在free(l);之后返回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;
}

Answer 2

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

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

正如"黄色方块引号的chqrlie"所回答的那样，还有其他问题，他在回答中已经解决了这些问题。你评论说它已经解决了，但我不知道你的固定代码是否能处理所有情况(第一个节点、最后一个节点、相邻节点…(。你可以用完整的解决代码更新你的问题。

Answer 3

函数具有未定义的行为，因为在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);
}

指针CCD_ 12在删除所指向的存储器之后具有无效值。

该功能可以通过以下方式实现

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