Newsgroup: it.comp.lang.c++
Titolo: visualizzazione lista dinamica ordinata

ciao a tutti,
ho qualche problema ad implementare una funzione che visualizzi gli elementi
(inseriti prec. tramite un'altra funzione) di una lista dinamica.
L č una lista di interi:
struct Record;
typedef int E;
struct Record {
       E elem;
       Record* punt;
       };
typedef Record* L;
ecco la mia funzione di visualizzazione, ancora incompleta:
void visualizza(const L& l){
  cout<<"3)Visualizza la lista"<<endl;
  cout<<"Elemento:"<<l->elem<<endl;
  visualizza(l->punt);
}
il problema č che non so quale sia la condizione che possa rendere il codice
ricorsivo...
questa invece č la funzione di inserimento:
l=0;//solo all'inizio del programma, non viene piů modificata dal main ma
solo dalle funzioni
void inserimento(L& l){
  E e;
  cout<<"1)Inserimento di un elemento"<<endl;
  cout<<"Elemento:";
  cin>>e;
  inserisci(l,e);
}
ciao!


 * @version 14/04/2003
 */
class LinkedList {
public:
    /**
     * Costruisce una lista vuota.
     * Chiama il costruttore dell'oggetto membro <code>Node</code>
inizializzandolo
     * con un valore nullo.
     */
    LinkedList() : head(0) { }
    /**
     * Distrugge la lista.
     *
     * @see destructList();
     */
    ~LinkedList();
    /**
     * Aggiunge un nuovo elemento alla lista.
     * Il dato per l'inizializzazione viene richiesto all'utente da
tastiera.
     * @see push()
     */
    void add();
    /**
     * Rimuove dalla lista un elemento.
     * Viene eliminato l'elemento in testa.
     *
     * @see deleteHeadNode()
     */
    void remove();
    /**
     * Restituisce il numero di elementi nella lista.
     */
    int length() const;
    /**
     * Visualizza sullo standard output la lista.
     * Si appoggia al metodo di utilità ricorsivo <code>print()</code>
     *
     * @see print()
     */
    void show() const;
    /**
     * Indica se la lista è vuota.
     *
     * @return  <code>true</code> se la lista è vuota, <code>false</code>
     *          altrimenti.
     */
    bool empty() const { return length() == 0; }
    /**
     * Indica se la lista è piena.
     *
     * @return  sempre <code>false</code> dal momento che non abbiamo
imposto
     *          dei limiti sul numero massimo di elementi nella lista.
     */
    bool full() const { return false; }
private:
    /** Il nodo in testa alla lista */
    Node* head;
    /**
     * Visita posticipata della lista in cui l'azione svolta sul singolo
nodo
     * è la stampa sullo standard output.
     */
    void print(Node* node) const;
    /**
     * Inserisce un elemento in testa alla lista mediante 3 passi:
     * <ul>
     * <li> Crea un nodo col valore passato come parametro
     * <li> Imposta il suo campo <code>next</code> all'elemento attualmente
     *      in cima alla lista.
     * <li> Imposta il campo <code>head</code> con l'indirizzo del nuovo
nodo
     * </ul>
     *
     * @param   data    il dato con cui creare il nodo da aggiungere alla
lista
     *                  [<b>INPUT</b>]
     */
    void push(const T data);
    /**
     * Cancella l'elemento in testa alla lista (l'ultimo inserito).
     */
    void deleteHeadNode();
    /**
     * Visita posticipata della lista dove l'azione svolta è quella di
rilascio
     * della memoria allocata dinamicamente.
     */
    void destructList(Node* node);
};
#endif
Mi sembrerebbe offensivo postare anche l'implementazione dei metodi che
dovrebbe essere molto semplice, una volta compreso il problema.
Se dovessi incontrare altri problemi sono disponibile in privato al mio
indirizzo di posta.
--
Domenico Testa - Studente

 ricorsivo...
Provo di correggerla al volo...
void Visualizza(const L l){
    if(l){
        cout << "Elemento: " << l->elem << endl;
        Visualizza(l->punt);
    }
}
se l non e' null, cioe' non hai raggiunto la fine della lista,
allora scrivi "Elemento: x\n"
e poi chiama la stessa funzione con l'elemento dopo.
vale il solito discorso che iterativa sarebbe meglio...
il reference & (in const L& l) non ti serve, ma se lo metti non guasta
molto...
fammi sapere.
Tommy

 vale il solito discorso che iterativa sarebbe meglio...
Nella programmazione reale, quand'č secondo te che č necessario preferire la
ricorsione alla struttura iterativa?
Dopotutto se non sbaglio, si puň risolvere iterativamente quasi tutti, se
non tutti i problemi risolvibili ricorsivamente.
Se č vero che una serie di chiamate ricorsive sono piů onerose di una
chiamata iterativa e che una funzione inline ricorsiva non viene sempre
sostituita dal compilatore come dovrebbe, mi sfugge il motivo della
ricorsione.

 e poi chiama la stessa funzione con l'elemento dopo.
logicamente non fa una piega anch'io cercavo di farla come l'hai fatta tu,
purtroppo però quando "lancio" la funzione visualizza non stampa
nulla....forse perchè inizializzo l=0???

 nulla....forse perchè inizializzo l=0???
ehm..dovevo mettere solo un getchar()...;-))
ciao!


[STRACUT]
ciao grazie mille per le dritte. Purtroppo io seguo il corso della
Prof.Vittorini e siamo un pņ indietro col programma, ha solo introdotto le
classi! Quindi al momento non sono ancora in grado di usarle a dovere! In
ogni caso i tuoi consigli mi serviranno a breve...;-))
grazie!
ciao!

 ricorsione.
E' verissimo che una sola chiamata iterativa e' meno "costosa" di migliaia
di chiamate ricorsive.... Certo!
La ricorsione esiste perche', so che non pare ovvio all'inizio, ma in molti
casi e' molto piu' semplice della iterazione. La ricorsione gestisce
automaticamente un mucchio di cose. Inoltre molte "cose" matematiche sono
espresse in termini ricorsivi etc....
Io non sto condannando la ricorsione, anzi mi piace molto... dico solo che
nei casi come quello di Fibonacci oppure dove si puo' tradurre in iterazione
con un semplice loop (caso della lista), non andrebbe mai usata! (la
ricorsione).
Ciao.
Tommy

 ricorsione).
Elegante ma non efficiente. Non ci avevo mai riflettuto.
Grazie mille. Sei chiarissimo.

 In generale la ricorsione e' piu' lenta e dispendiosa.
questo e` vero solo parzialmente; in generale si distinguono due tipi di
ricorsione: tail-recursion e non-tail-recursion; si ha una tail-recursion
quando la chiamata ricorsiva e` l'ultima istruzione della nostra funzione,
come ad esempio abbiamo nel classico esempio del calcolo del fattoriale:
int fact(int n)
{
        if (n<=1) return 1;
        return n*fact(n-1);
}
in casi come questi in genere i compilatori sono abbastanza intelligenti da
ottimizzare e trasformare in iterativa la funzione (in effetti si chiama
proprio tail-recursion optimization). Ho appena provato a compilare con gcc
3.1 a livello -O3 ed in effetti nel codice assembler prodotto non c'e`
traccia di ricorsione. Quindi in questo caso, che e` di gran lunga il piu`
comune, il costo della ricorsione e` paragonabile a quello dell'iterazione.
Quando invece abbiamo piu` di una chiamata ricorsiva (come nel quicksort)
oppure questa chiamata non e` in coda l'ottimizzazione non e` cosi`
semplice: se vogliamo farlo manualmente dobbiamo per forza gestirci un
nostro stack dove memorizzare i risultati intermedi. In questi casi in
genere la versione iterativa e` piu` veloce ma anche molto piu` complessa
di quella ricorsiva, per cui bisogna valutare attentamente se ne vale
davvero la pena (come, del resto, per tutte le ottimizzazioni).
Tra le variabili da tenere in considerazione c'e` anche l'efficienza del
nostro stack gestito manualmente: quando facciamo una chiamata ricorsiva
utilizziamo lo stack di sistema, per cui le push e le pop si limitano ad
incrementare/decrementare un puntatore; se implementiamo il nostro stack in
modo da usare, ad esempio, allocazione dinamica della memoria, dubito che
la versione iterativa possa essere molto piu` veloce della ricorsiva.
ciao Anto
-- 
"Computer science is not about computers any more than astronomy
is about telescopes." -- EW Dijkstra

 questo e` vero solo parzialmente;
???
Tommy

 comune, il costo della ricorsione e` paragonabile a quello
dell'iterazione.
No! Nel caso che hai fatto del fattoriale non e' detto che il compilatore
ottimizzi la ricorsione rimuovendola ed introducendo l'iterazione.
Non sono cosi' sicuro che siano in tanti gli optimiser a farlo... Se dici
che hai provato con il gcc e la toglie, bene, mi fido, ma sappi che molti
altri non la rimuovono e sappi inoltre che il caso da te riportato non e'
propriamente tail-recursion.
Quello che dici sulla tail recursion invece (che non e' propriamente il caso
del fattoriale che hai citato), e' vero; dando per scontato che l'optimiser
faccia il suo lavoro, e concordo sul fatto che oggi quasi tutto lo facciano
(ma nei casi di vera tail-recursion).
Ad ogni modo ci vuole poco per fare in modo che la ricorsione non venga piu'
ottimizzata a dovere... anche tu lo fai capire dal tuo testo.
questa viene probabilemente ottimizzata in iterazione:
void Recursion1(int x)
{
    if(x>0){
        cout << x << " ";
        Recursion1(x-1);
    }
}
questa era una VERA tail-recursion....
questa probabilmente NO:
void Recursion2(int x)
{
    if(x>0){
        Recursion2(x-1);
        cout << x << " ";
    }
}
questa nemmeno:
int Recursion3(int x)
{
    if(x>0){
        cout << Recursion3(x-1) << " ";
    }
    return x;
}
Ricorda inoltre che tail-recursion e' solo un caso e poi ripeto quando si
parla di ricorsione io intendo ricorsione non ottimizzata in iterazione,
altrimenti, ok, l'optimiser fa il lavoro per te, ma e' comunque iterazione.
Quindi una tail-recursion compilata e' veloce "come" l'iterzione perche' E'
iterazione! Non e' piu' ricorsione! E, per cio' che riguarda il C++, non
esiste uno standard di ottimizzazione ;-)
Nel caso della tail-recursion poi non e' che l'optimiser sia di grosso
aiuto.. quello e' il caso piu' semplice da trasformare in iterazione. Un
uomo puo' farlo banalmente a mente e... la ricorsione non ha ragione di
esistere in tale caso visto che non semplifica nulla e non rende nulla piu'
elegante.
Gli ultimi due esempi che ho fatto non vengono (di solito) trasoformati in
iterazione dall'optimiser, ma sarebbe banale farlo a mente!
Se l'optimiser non riesce ad aiutarci su cose simili, immaginiamo su casi
piu' complessi! (quicksort, minimax, fibonacci, solo per citare i piu'
comuni). (fibonacci e' pero' semplice da fare a mano).
Tommy


Quanto dici non invalida quanto detto da Tommy, aggiunge solo un concetto:
il compilatore ha l'ultima parola sull'efficienza di un codice scritto in C
(infatti ancora si programma in ASSEMBLER). Inoltre il caso del calcolo di
un fattoriale non mi sembra molto calzante, in quanto l'efficienza di questo
codice e' talmente bassa (troppe chiamate) da sconsigliarlo a priori e
magari  il compilatore e' stato progettato per ottimizzare questo tipo di
codice.
A parte il fatto che le prestazioni di un codice possono variare da
compilatore a compilatore, non mi piace l'idea di scrivere un codice
affidandomi solo al compilatore per ottimizzarlo. Inoltre una compilazione
con ottimizzazione di livello 3 con il gcc, su progetti piuttosto grandi
puo' creare delle situazioni spiacevoli. Non conosco i casi di compilatori
tradizionali, ma alcuni CrossCompiler gcc generano vari problemi con queste
ottimizzazioni.
L'eleganza della ricorsione e', comunque, fuori discussione, e quando ci si
muove per alberi il codice che si riesce a scrivere e' molto compatto.
Ciao
Emanuele