Рекурсивно найти минимальное четное число в списке

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

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

Эта строка ошибочная:

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), и это слишком сложно, вам не нужен рекурсивный вызов, просто чтобы go выбросить список, например:

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;
}

Поскольку ваш отредактированный topi c требует рекурсивного вызова, который вы можете сделать, например:

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;
  }
}

как видите, это просто, я проверяю только один раз в программе, если valore нечетное или нет et c

с использованием полной программы для проверки:

#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 %d\n", 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

если вам нужно использовать рекурсию, вы должны сначала попробовать записать это на псевдоязыке:

• если текущий список имеет только один элемент
  • -> вернуть его, если даже, иначе return null
• , если в списке больше элементов
  • получить минимум остатка списка
  • если текущий элемент нечетный
    • вернуть rest-minimum
  • else, если rest равен нулю
    • вернуть этот элемент
  • иначе, если rest не равен нулю
    • вернуть меньшее

Я бы не go с отговоркой по этому поводу. С действительно длинными списками вы превратите sh свой стек.

Простой l oop будет еще проще и менее сложным:

• минимум инициализации до NULL
• итератор инициализации со списком
• while итератор! = Null
  • если итератор четный и минимум == Null
    • минимум = итератор
  • иначе, если даже и итератор <минимум <ul>
  • минимум = итератор
• расширенный итератор

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 %d\n", minimo->valore );
    }
    else
    {
        puts( "there is no minimo pari valore" );
    }
    
    struct nodo *massimo = MassimoPariListaRic( top );
    
    if ( massimo != NULL )
    {
        printf( "Massimo pari valore is %d\n", 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);

, NULL в следующем операторе if

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