Pages: [1]   Go Down
Print
Author Topic: problema ricorsione e linked list  (Read 1058 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
ciccio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 143



« on: 23-05-2009, 18:57:48 »

Cari colleghi buonasera,
mentre voi tutti (o quasi) siete gia' da un po alle prese con alberi, complessita, ecc., il sottoscritto sbatte ancora la testa su linked list e ricorsione. Il fatto e' che ho cominciato a studiare progII da 2 settimane circa (con comodo!! dira' qualcuno... ), ma il punto e' proprio che vista l'imminenza dell'esame non vorrei perdere troppo tempo con cose "banali" come queste... Vado al sodo: ho provato a svolgere alcuni esercizi dalle slide "Esercizi_proveItinereprec1.pdf" e uno in particolare (il 6) mi sta dando un sacco di problemi. Posto il codice, che a mio avviso sembra essere corretto, ma non vuole funzionare. Funziona solo quando inserisco una particolare istruzione (righe 14 e 15), ma non me ne spiego il motivo.
Code:
/*
Dare un metodo ricorsivo per invertire una linked list semplice
in modo che l’ordine dei nodi diventi opposto a quello iniziale.
*/
class Es6 {
public static Lista inverti (Lista M) {
if (!M.isEmpty() ) {
int aux = M.deleteHead();
inverti (M);
M.insertTail(aux);
//con il seguente codice funziona, senza NO...
//il motivo e' a me oscuro
/*
Nodo cursore = null;
M.getNextElement();
*/
}
return M;
}

public static void main (String[] args) {
Nodo cursore; //puntatore agli elementi della lista
int i, j; //variabili di supporto per l'inizializzazione di una lista

Lista LOrd = new Lista();

//inizializzo una lista con valori casuali
for (i = 3; i > 0; i--) {
j = (int)(Math.random() * 10);
LOrd.insertOrdered(j); //inserimento ordinato
}
//stampo la lista prima dell'inversione
System.out.print ("\nLISTA ORDINATA:\t\t");
do {
cursore = LOrd.getNextElement();
System.out.print (cursore.getInfo() + " ");
} while (cursore.getNext() != null);

//chiamo il metodo inverti
inverti(LOrd);

//stampo la lista invertita
System.out.print ("\nLISTA ORDINATA (INVERTITA):\t");
do {
cursore = LOrd.getNextElement();
System.out.print (cursore.getInfo() + " ");
} while (cursore.getNext() != null);
}
}

Che questo codice funziona solo con quelle due istruzioni l'ho scoperto per caso...proprio non capisco testate. Se qualcuno ci capisce qualcosa mi faccia sapere e se sono stato poco chiaro...chiedete pure!!
GRAZIE   ciao ciao
Logged

"Non importa quanto vai piano, l' importante è che non ti fermi" (CONFUCIO)
k1r4
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 375


Il mio nick si pronuncia cappaunoerrequattro!!


WWW
« Reply #1 on: 25-05-2009, 07:22:20 »

a dire il vero funziona perfettamente questo metodo, ho provato con la mia struttura dati e non ci sono problemi:

Code:
    public static void inverti(SLinkedList L) {
        if(!L.isEmpty()) {
            Node aux = L.deleteHead();
            inverti(L);
            L.insertTail(aux.getElement());
        }
    }

Cerca di essere magari più specifico per quanto riguarda l'errore così evitiamo di scervellarci a vicenda :p

P.S. ovviamente è inutile che ritorni la lista visto che l'algoritmo lavora in loco (forse è questo il tuo problema)
« Last Edit: 25-05-2009, 07:25:39 by k1r4 » Logged

ciccio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 143



« Reply #2 on: 25-05-2009, 21:17:07 »

Cerca di essere magari più specifico per quanto riguarda l'errore così evitiamo di scervellarci a vicenda :p
te lo spiego nel modo piu' semplice possibile...ecco un mio output:
Code:
LISTA ORDINATA:           123
LISTA ORDINATA (INVERTITA):  123


P.S. ovviamente è inutile che ritorni la lista visto che l'algoritmo lavora in loco (forse è questo il tuo problema)
ineffetti inizialmente lo avevo scritto di tipo "void", quello di mettere un valore di ritorno è stato uno dei tanti tentativi di capire cosa generasse l'errore...
ciao ciao
Logged

"Non importa quanto vai piano, l' importante è che non ti fermi" (CONFUCIO)
k1r4
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 375


Il mio nick si pronuncia cappaunoerrequattro!!


WWW
« Reply #3 on: 25-05-2009, 21:22:30 »

comunque hai potuto notare che funziona no?
Logged

ciccio
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 143



« Reply #4 on: 25-05-2009, 22:14:57 »

comunque hai potuto notare che funziona no?
...eh si...sai una cosa ho appena risolto il problema e come immaginavo l'errore era di una stupidita' abnorme: prima di stampare la lista nel main (dopo l'inversione), dimenticavo di invocare il metodo rewind() che nella mia struttura dati fa puntare il cursore alla testa della lista instanziata;
in altre parole il metodo invertiva perfettamente la lista, solo che dopo aver stampato la lista non ancora invertita, il cursore puntava a un nodo che durante l'inversione viene cancellato (o meglio non esistera' piu' alcun riferimento a tale nodo, tranne che 'cursore'), ma in memoria la lista e' pur sempre presente!!
L'errore e' banale, spiegarlo un po meno. Ecco il codice corretto
Code:
/*
Dare un metodo ricorsivo per invertire una linked list semplice
in modo che l'ordine dei nodi diventi opposto a quello iniziale.
*/
class Es6 {
public static void inverti (Lista M) {
if (!M.isEmpty() ) {
int aux = M.deleteHead();
inverti (M);
M.insertTail(aux);
}
}

public static void main (String[] args) {
Nodo cursore; //puntatore agli elementi della lista
int i, j; //variabili di supporto per l'inizializzazione di una lista

Lista LOrd = new Lista();

//inizializzo una lista con valori casuali
for (i = 3; i > 0; i--) {
j = (int)(Math.random() * 10);
LOrd.insertOrdered(j); //inserimento ordinato
}
//stampo la lista prima dell'inversione
System.out.print ("\nLISTA ORDINATA:\t\t");
do {
cursore = LOrd.getNextElement();
System.out.print (cursore.getInfo() + " ");
} while (cursore.getNext() != null);

//chiamo il metodo inverti
inverti(LOrd);

//stampo la lista invertita
LOrd.rewind(); //-------------------------------------------------------------------------ECCOLO IL MALEDETTO!!
System.out.print ("\nLISTA ORDINATA (INVERTITA):\t");
do {
cursore = LOrd.getNextElement();
System.out.print (cursore.getInfo() + " ");
} while (cursore.getNext() != null);
}
}
Grazie comunque per l'aiuto. ok Ciao ciao
Logged

"Non importa quanto vai piano, l' importante è che non ti fermi" (CONFUCIO)
Pages: [1]   Go Up
Print
Jump to: