[C++] Ricerca ricorsiva di un elemento

[minidiable]

Allora la domanda è: come faccio ad implementare la funzione ricerca della seguente traccia, in modo ricorsivo, io l'ho svolta in maniera iterativa...vi scrivo di seguito tutto:

TRACCIA
Testo della Prova

Si realizzi in C++ una classe Lista che consente la gestione di una rubrica telefonica.
La Lista è realizzata mediante una lista linkata. Ogni elemento della lista è una struttura i cui campi sono:

char * Nome
char * Cognome
int Telefono


La classe Lista deve prevedere (oltre al costruttore e al distruttore) i seguenti metodi:
- Inserimento in testa;
- Ricerca numero da cognome; (e’ preferibile l’implementazione ricorsiva)
- Stampa a video;
- Stampa su file;


Il mio file di specifica rubrica.h:

struct nodo;
typedef struct nodo* puntnodo;
typedef struct nodo{
        char* nome;
        char* cognome;
        int telefono;
        puntnodo punt;
        };

class lista{
      puntnodo l;
public:
       lista():l(0){}
       ~lista();
       void push(char*,char*,int);
       void ricerca(char* cogn);
//La funzione cancella non c'era nella traccia
       void cancella(char* cogn);
       void stampavideo();
       void stampafile();
};

Il mio file di implementazione rubrica.cpp(di cui riporto solo la funzione ricerca in forma iterativa):

/*Ricerca del numero di una persona dato il cognome(se ci sono cognomi uguali 
mi da il numero della persona inserita più di recente),questa è una versione
iterativa*/ 
void lista::ricerca(char* cogn){
     puntnodo temp=l;
     bool trovato=false;
     while(temp){
                 if(!strcmp(temp->cognome,cogn)){
                 trovato=true;
                 cout<<"Il numero dell'utente "<<temp->cognome;
                 cout<<" e' "<<temp->telefono<<"\n";
                 break;
                 }
                 else temp=temp->punt;
                 }           
     if(!trovato)cout<<"Il cognome non e' presente nella lista!\n";
     }

Il main penso sia inutile riportarlo allo scopo della domanda...

vi ringrazio in anticipo per le risposte!

Grazie mille!

[Stoicenko]

e la domanda quale sarebbe? farti la funzione ricorsiva?

[minidiable]

ehhh
....purtroppo non c riesco...perchè la prof ha scritto...si preferirebbe la versione ricorsiva...
ma non la so fare!!!

[oregon]

E le darai una funzione ricorsiva fatta interamente da un altro al posto tuo, oppure tenti di scriverla qui e ti diamo solo "suggerimenti"?

(Una sola risposta e' quella giusta)

[minidiable]

ooook....ci proverò!!!!

[minidiable]

ragazzi...innanzitutto grazie per il consiglio di provare da solo a trovare la soluzione alla mia domanda...io ci ho provato e forse ci sono riuscito...

compila...e mi da il risultato voluto...ma non son sicuro...della mia forma di ricorsione...perchè cambia poco dal codice iterativo, ecco il codice:

void lista::ricerca(char* cogn){
puntnodo temp=l;
bool trovato=false;
if(!strcmp(temp->cognome,cogn)){
                 trovato=true;
                 cout<<"Il numero dell'utente "<<temp->cognome;
                 cout<<" e' "<<temp->telefono<<"\n";
                 }
                 else {
                       temp=temp->punt;
                       ricerca(cogn);
                       }
                 }

Fatemi sapere

[KrOW]

Ciao . . . Sei sicuro che quel codice funzioni??? Hai provato a ricercare un cognome non presente nella lista??? Comunque . . . :
1) La variabile 'temp' deve sopravvivere alle varie chiamate del metodo, quindi deve essere dichiarata static
2) Siccome il cognome da cercare potrebbe non trovarsi nella lista devi verificare (prima di ogni comparazione delle stringhe) di non essere arrivato alla fine della lista (ovvero 'temp == NULL' ) altrimenti rischi un errore a run-time di violazione di accesso
3) Non appena trovi la stringa o arrivi alla fine della lista, devi assegnare alla variabile 'temp' l' indirizzo del nodo iniziale della lista ( 'l' ). Questo per permettere ad una successiva ricerca di incominciare quest' ultima dal nodo iniziale.
4) A cosa serve la variabile 'trovato' ???
Sei hai problemi chiedi pure . . .

[minidiable]

Ho modificato il codice:

//Versione ricorsiva del ricerca     
void lista::ricerca(char* cogn){
static puntnodo temp=l;
if(temp==0)cout<<"L'elemento non e' presente nella lista!\n";
else if(!strcmp(temp->cognome,cogn)){
                 cout<<"Il numero dell'utente "<<temp->cognome;
                 cout<<" e' "<<temp->telefono<<"\n";
                 }
                 else {
                       temp=temp->punt;
                       ricerca(cogn);
                       }
                 }

Così mi funziona...prima non funzionava se:

1)Cercavo un elemento che non era presente nella lista(non c'era nessuna condizione temp==0)Grazie a te...
2)Cercavo un elemento che non stesse in testa alla lista(il motivo penso sia lo static)Grazie e a te...

Ti ringrazio...secondo te ora va bene??e più che altro secondo te ho risposto alla domanda della traccia=???

[KrOW]

Allora ... Come ti ho già detto, una volta finita la ricerca (cioè quando trovi il cognome o quando arrivi a fine lista) devi assegnare nuovamente a 'temp' l' indirizzo del primo nodo per fare in modo che una successiva ricerca riparti dal primo nodo. Comunque ho commesso un errore: E' vero che dichiarando 'temp' static elimini un problema ma ne crei un' altro ossia, la ricerca verrà fatta sempre nella prima lista che invoca il metodo 'ricerca()' e non credo che è quello che vuoi. Potresti risolvere aggiungendo un dato-membro alla classe lista che rappresenta il nodo corrente della ricerca (quindi ha lo stesso significato di 'temp')... Es:

class lista
{
private:
puntnodo l;
puntnodo currNode;
public:
// Metodi ...
}

quindi utilizzare currNode al posto di temp nel metodo ricerca() :

void lista::ricerca( const char* cogn )
{
if( currNode != NULL )
{
if( strcmp(currNode->cognome, cogn) == 0 )
{
cout << "Il numero dell\' utente " << cogn << " e\' "<< currNode->telefono << endl;
// Questa istruzione è fondamentale per fare in modo che una successiva ricerca
// riparta dal nodo iniziale
currNode = l;
}
else
{
currNode = currNode->punt;
ricerca( cogn );
}
}
else
// come sopra
currNode = l;
}

In più ho notato soltanto ora che manca il distruttore di lista (ricordati che ogni nodo viene allocato dinamicamente). Mi scuso se c' è qualche errore di sintassi ma al momento, non posso provare il codice ...

[Stoicenko]

ma aggiungere alla chiamata ricorsiva il current node no?