c-递归地查找列表中的最小偶数

Question

我已经编写了这个函数：

struct nodo * MinimoPariListaRic(struct nodo * top) {
struct nodo * minimo_p = NULL; //this should be the minimum even number
//list have one or no one element
if(top) {
if(!top->next) 
if(top->valore % 2 == 0) return top; // valore(italian) = value
else return NULL;
}
else return NULL;

if(top->next)
minimo_p = MinimoPariListaRic(top->next);
if (top->valore % 2 == 0)
{
if(minimo_p->valore < top->valore) return minimo_p;
else return top;
}
else return minimo_p;
}

如果列表中的元素都是偶数，那么函数将返回最小值，这是可以的。但是，如果出现奇数，则说明函数无法正常工作。若所有的数字都是奇数，函数应该返回NULL。

Answer 1

因为如果列表在最后一个位置包含奇数整数并且

任何位置至少包含一个偶数整数这一行是错误的：

if(minimo_p->valore < top->valore) return minimo_p;

你可以在这里添加空条件：

if(minimo_p && minimo_p->valore < top->valore) return minimo_p;

Answer 2

你的算法是错误的，如果递归调用返回NULL，你可能会有未定义的行为，因为将minimo_p设置为NULL，如果(top->valore % 2 == 0)，你会取消引用它，而且它太复杂了，你不需要递归调用，只需要抛出列表，例如：

struct nodo * MinimoPariListaRic(struct nodo * l) {
struct nodo * minimo_p = NULL; //this should be the minium even number
while (l != NULL) {
if (l->valore % 2 == 0) {
if ((minimo_p == NULL) || (l->valore < minimo_p->valore))
minimo_p = l;
}
l = l->next;
}
return minimo_p;
}

因为您编辑的主题需要递归调用，所以您可以执行以下操作：

struct nodo * MinimoPariListaRic(struct nodo * l) {
if (l == NULL)
return NULL;
else {
struct nodo * minimo_p = MinimoPariListaRic(l->next);
return ((l->valore % 2 == 0) &&
((minimo_p == NULL) || (l->valore < minimo_p->valore)))
? l :  minimo_p;
}
}

正如你所看到的，这很简单，我在程序中只检查了一次价格是否奇数等

---

使用完整程序检查：

#include <stdio.h>
#include <stdlib.h>
struct nodo {
struct nodo * next;
int valore;
};
struct nodo * MinimoPariListaRic(struct nodo * l) {
if (l == NULL)
return NULL;
else {
struct nodo * minimo_p = MinimoPariListaRic(l->next);
return ((l->valore % 2 == 0) &&
((minimo_p == NULL) || (l->valore < minimo_p->valore)))
? l :  minimo_p;
}
}
int main(int argc, char ** argv)
{
/* make a list from the args */
struct nodo * l = NULL;

while (argc > 1) {
struct nodo * r = malloc(sizeof(*r));

r->next = l;
if (sscanf(argv[--argc], "%d", &r->valore) != 1) {
puts("invalid number");
return 0;
}
l = r;
}

/* show list well made */
struct nodo * ll;

for (ll = l; ll != NULL; ll = ll->next)
printf("%d ", ll->valore);
putchar('n');

/* */

ll = MinimoPariListaRic(l);

if (ll == NULL)
puts("no even value");
else
printf("min even value is %dn", ll->valore);

/* free resources */
while (l) {
ll = l->next;
free(l);
l = ll;
}

return 0;
}

编译和执行：

pi@raspberrypi:/tmp $ gcc -Wall l.c
pi@raspberrypi:/tmp $ ./a.out 1 4 2 7 8
1 4 2 7 8 
min even value is 2
pi@raspberrypi:/tmp $ ./a.out
no even value
pi@raspberrypi:/tmp $ ./a.out 3
3 
no even value
pi@raspberrypi:/tmp $ ./a.out 3 3 1 5
3 3 1 5 
no even value
pi@raspberrypi:/tmp $ valgrind ./a.out 3 4 5 2 0
==16881== Memcheck, a memory error detector
==16881== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==16881== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
==16881== Command: ./a.out 3 4 5 2 0
==16881== 
3 4 5 2 0 
min even value is 0
==16881== 
==16881== HEAP SUMMARY:
==16881==     in use at exit: 0 bytes in 0 blocks
==16881==   total heap usage: 6 allocs, 6 frees, 1,064 bytes allocated
==16881== 
==16881== All heap blocks were freed -- no leaks are possible
==16881== 
==16881== For lists of detected and suppressed errors, rerun with: -s
==16881== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
pi@raspberrypi:/tmp $ 

Answer 3

如果你必须使用递归，你应该先用伪语言写下来：

• 如果当前列表只有一个元素
  • ->如果为偶数则返回，否则返回null
• if列表包含更多元素
  • 获取列表其余部分的最小值
  • 如果当前元素为奇数
    • 返回剩余最小值
  • 否则，如果rest为null
    • 返回此元素
  • 否则，如果rest不为null
    • 返回较小的

我不会回避这个问题。对于非常长的列表，你会崩溃你的堆栈。

一个简单的循环会更简单，也不那么令人费解：

• 初始化最小值为NULL
• 带列表的init迭代器
• while迭代器！=无效的
  • 如果迭代器偶数且最小==空
    • 最小=迭代器
  • else if和迭代器<最低限度
    • 最小=迭代器
  • 高级迭代器

Answer 4

我的五美分。我还包含了一个递归函数，用于查找具有最大偶数值的节点。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct nodo
{
int valore;
struct nodo *next;
};
int push_front( struct nodo **top, int valore )
{
struct nodo *nodo_nuovo  = malloc( sizeof( struct nodo ) );
int success = nodo_nuovo != NULL;

if ( success )
{
nodo_nuovo->valore = valore;
nodo_nuovo->next = *top;
*top = nodo_nuovo;
}

return success;
}
FILE * display( struct nodo *top, FILE *fp )
{
for ( ; top != NULL; top = top->next )
{
fprintf( fp, "%d -> ", top->valore );
}

fputs( "null", fp );

return fp;
}
struct nodo * MinimoPariListaRic( struct nodo * top )
{
if ( !top )
{
return top;
}
else
{
struct nodo *minimo = MinimoPariListaRic( top->next );


if ( minimo == NULL )
{
minimo = top->valore % 2 == 0 ? top : minimo;
}
else if ( top->valore % 2 == 0 )
{
minimo = minimo->valore < top->valore ? minimo : top;
}
return minimo;
}
}
struct nodo * MassimoPariListaRic( struct nodo * top )
{
if ( !top )
{
return top;
}
else
{
struct nodo *massimo = MassimoPariListaRic( top->next );


if ( massimo == NULL )
{
massimo = top->valore % 2 == 0 ? top : massimo;
}
else if ( top->valore % 2 == 0 )
{
massimo = top->valore < massimo->valore ? massimo : top;
}
return massimo;
}
}
int main(void) 
{
struct nodo *top = NULL;
enum { N = 10 };

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

for ( int i = 0; i < N; i++ )
{
push_front( &top, rand() % N );     
}
fputc( 'n', display( top, stdout ) );

struct nodo *minimo = MinimoPariListaRic( top );

if ( minimo != NULL )
{
printf( "Minimo pari valore is %dn", minimo->valore );
}
else
{
puts( "there is no minimo pari valore" );
}

struct nodo *massimo = MassimoPariListaRic( top );

if ( massimo != NULL )
{
printf( "Massimo pari valore is %dn", massimo->valore );
}
else
{
puts( "there is no massimo pari valore" );
}
return 0;
}

程序输出可能看起来像

8 -> 9 -> 9 -> 9 -> 7 -> 9 -> 7 -> 3 -> 1 -> 2 -> null
Minimo pari valore is 2
Massimo pari valore is 8

至于函数定义，则需要检查指针呼叫返回的minimo_p

if(top->next)
minimo_p = MinimoPariListaRic(top->next);

在下一个if语句中等于NULL

if (top->valore % 2 == 0)
{
if(minimo_p->valore < top->valore) return minimo_p;
else return top;
}