PDA

Visualizza la versione completa : [C++] Sottolista


progrina
17-02-2012, 01:26
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.


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!

ramy89
17-02-2012, 01:59
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.

progrina
17-02-2012, 10:59
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:


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?

ramy89
17-02-2012, 14:53
Se gli elementi sono diversi devi ritornare false.
Poi sta eseguendo la sottolista senza prenderne il risultato.
Modificala cos:



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

Loading