Visualizzazione dei risultati da 1 a 4 su 4

Discussione: [C++] Sottolista

  1. #1

    [C++] Sottolista

    Buonasera a tutti..ho alcuni problemi con il seguente esercizio.
    In pratica, sono riuscita a fare la versione iterativa ma non riesco a fare una versione ricorsiva che non mi dia problemi..Vi posto il testo :

    Progettare un algoritmo ricorsivo sottoforma di function che date due linked list head1 e head2 (con campo info di tipo integer), restituisca TRUE se head2 è sottolista di head1, FALSE altrimenti.
    Ad es. se in input si ha
    head1= 2 -> 0 -> 10 -> 1 -> 21 -> 11
    head2= 0 -> 10 -> 1
    la function ritorna TRUE.
    Altrimenti se:
    head1= 2 -> 0 -> 10 -> 1 -> 21 -> 11
    head2= 0 -> 1 -> 21
    la function ritorna FALSE.

    Ho fatto tante prove una delle quali è la seguente. Il punto è che durante l'esecuzione il programma mi salta le chiamate alla funzione ricorsiva.

    codice:
    bool sottolista(list *head1,list *head2){
         if(head1->info != head2->info)
            sottolista(head1->next,head2);
         if(head1 != NULL && head2 != NULL){
          if(head1 -> info == head2 ->info)
            sottolista(head1->info,head2->info);
          else return false;}
         if(head2 == NULL) return true;
    }
    Spero possiate aiutarmi, grazie a tutti!

  2. #2
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    Gli if dove verifichi se non ci sono puntatori a NULL devono stare per primi.
    Altrimenti accedi ai campi anche se c'è un puntatore a NULL, causando segmentation fault.

  3. #3
    Non me n'ero accorta ma c'è un errore di distrazione nel codice precedente!
    Comunque grazie per la risposta ramy89..ho corretto il codice in questo modo:
    codice:
    bool sottolista(list *head1,list *head2){
         if(head1 != NULL && head2 != NULL){
           if(head1->info != head2->info)
            sottolista(head1->next,head2);
         else 
            sottolista(head1->next,head2->next);
         }
         if(head2 == NULL) return true;
         else return false;
    }
    Il punto è che così la funzione mi ritorna sempre vera, perchè la funzione mi trova sempre (attendendomi all'esempio che ho scritto sopra) che i 3 elementi di head2 sono presenti in head1 anche se non consecutivamente.
    Per ovviare a questo problema devo introdurre un altra variabile?

  4. #4
    Utente bannato
    Registrato dal
    Oct 2010
    Messaggi
    1,219
    Se gli elementi sono diversi devi ritornare false.
    Poi sta eseguendo la sottolista senza prenderne il risultato.
    Modificala così:

    codice:
    bool sottolista(list *head1,list *head2){
         if(head1 != NULL && head2 != NULL){
           if(head1->info != head2->info)
            return false;  // perchè chiamare ricorsivamente la sottolista?
         else                           // il confronto ha avuto esito negativo
            return sottolista(head1->next,head2->next);
         }
         if(head2 == NULL) return true;
         else return false;
    }

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.