PDA

Visualizza la versione completa : [C] Portare in ultima posizione l'elemento di una lista tramite ricorsione


Tallid
02-05-2011, 17:45
chi sa risolvere il seguente quesito?

Definire una procedura ricorsiva FirstLast che, data una lista semplice di interi, porta in ultima poszione il primo elemento.

la firma deve essere del tipo lista
lista FirstLast(lista lst)

grazie:)

valia
02-05-2011, 18:33
prima che il moderatore ti chiuda il thread, mi dici cosa ti viene difficile in questo? cio hai provato a farlo e non riesci? hai qualche problema?o proprio non ti va di farla da te?

Tallid
02-05-2011, 18:46
ho provato a farla ...




lista FirstLast(lista l){
if(l->next==NULL)return l;
lista l2=FirstLast(l->next);
l2->next=l;
l=l2;
return l;
}




per non ho idea di come scriverla...avevo provato a ribaltarla : 1->2->3 diventa 3->2->1
in modo da tentare comunque di spostare il primo elemento in coda ma la funzione che ho scritto fa questo: 3->1->2 con in input la lista 1->2->3

valia
02-05-2011, 18:56
ti d un suggerimento, prendi il primo elemento (la testa della lista). Controlla se l'ultimo (sei gi arrivato), in caso contrario chiama lo stesso metodo passando come parametri la lista restante.
All'ultimo passo ovviamente devi fare l'assegnamento, non so se sono stata chiara

Tallid
02-05-2011, 19:01
ok giustamente se la lista ha un solo elemento(caso base)questo anche l'ultimo
altrimenti richiamo la funzione ma come assegnamento cosa intendi?

Celebron
02-05-2011, 19:46
intende dire che quando arrivi a fine lista devi andare a "collegarci" il primo elemento che hai preso e vuoi mettere in quella posizione

nel fare ci ricorda che devi aggiornare (nel giusto ordine) anche il puntatore a testa che dovr puntare a primoElemento->next;

Tallid
02-05-2011, 19:49
non capisco come tenere quel riferimento, sono in una funzione ricorsiva e mi concesso solo un parametro :confused:

Celebron
02-05-2011, 20:00
non necessario che lo tieni
prima della chiamata alla funzione ricorsiva vera e propria fai un check se la lista composta da 1 solo elemento (o se vuota)

se vuota non puoi fare nulla, e non richiami la funzione ricorsiva
se ha un solo elemento il caso banale e non fai nulla e non richiami la funzione ricorsiva
se ha pi di un elemento, estrai il primo elemento e te lo salvi in un puntatore temp a parte, quindi fai puntare il riferimento head a primoElemento->next e, a seguire e solo a seguire, fai partire la funzione ricorsiva passandogli la lista (puntatore head aggiornato) e il puntatore temp a quello che prima era il primo elemento della lista

Tallid
02-05-2011, 20:10
quindi tu intendi una cosa di questo tipo

lista FirstLast(lista l){
if(l==NULL)return NULL; //se vuota non faccio nulla
if(l->next==NULL)return l; //se ha 1 elemento ho finito
else {
lista temp=l; //salvo il primo elemento
l=l->next; //sposto il puntatore al successivo
//....richiamo la funzione
}
}

ma poi come faccio a concatenare alla fine il primo elemento?

Celebron
02-05-2011, 20:12
quando trovi che l'elemento attualmente in esame ha un next == NULL, ci metti
elementoAttuale->next = temp;
return;

e sei apposto. Come noti funziona sia se la lista ha 2 elementi (appena entra nella funzione ricorsiva gi sull'elemento che ha next==NULL in quanto il primo stato estratto) sia nel caso ne abbia un numero imprecisato X

if(elementoAttuale->next == NULL) la tua cosiddetta "condizione di terminazione della ricorsione"

se l'elemento successivo non a null
funzioneRicorsiva(elementoAttuale->next, temp);

Loading