[C++] Unione Liste

[Zeldic]

Ciao!
Nel mio programma voglio semplicemente creare due liste di caratteri, per poi visualizzarle in un'unica lista. Utilizzo una classe per far ciò, l'inserimento dei caratteri termina quando si digita 'z' o 'Z'. Il problema che non riesco ancora a risolvere è che la funzione 'Union' non stampa a video la lista unita.. L'inserimento avviene credo correttamente, ma non visualizzo nulla, poi il programma si chiude.
Questa è la funzione 'Union' che dovrebbe unire le due liste e stamparle una accanto all'altra :

void UnionL::Union(UnionL* l1, UnionL* l2) {
  cout << "Gli elementi della lista 'unione' sono i seguenti : \n\n";
  while( l1->get_nxt() ) {                        /* Stampa gli elementi della 1-a lista. */
    cout << "[ " << l1->get_car() << " ] ";
    l1 = l1->get_nxt();
  }
  l2 = l1->get_nxt();                     /* E' corretta quest'assegnazione?? */
  while( l2->get_nxt() ) {                        /* Stampa gli elementi della 2-a lista. */
    cout << "[ " << l2->get_car() << " ] ";
    l2 = l2->get_nxt();
  }
  cout << "\n\n";
}

Io credo sia qui l'errore. Il metodo precedente, che non ho summenzionato è 'creaLista()', che ha il compito di popolare le 2 liste di caratteri; nel main() ho dichiarato 2 puntatori alla 1-a e 2-a lista ed un puntatore al primo elemento 'start' = NULL.
Chiamo le funzioni in questo modo :

  lista1 = new UnionL();
  lista1->creaLista(start);
  system("PAUSE");
  
  lista2 = new UnionL();
  lista2->creaLista(start);
  system("PAUSE");
  
  start->Union(lista1, lista2);

Qualche suggerimento?

[MItaly]

Stai facendo confusione a più livelli.
In primo luogo, stai mescolando di nuovo codice che contiene la logica del container dati (la lista) con codice per mostrare all'utente il suo contenuto, e le due funzioni dovrebbero essere ben distinte.
Inoltre, la linea grassettata non ha nessun senso, dato che stai cercando di assegnare a l2 un NULL, dato che nel codice subito sopra la lista passata è già stata scorsa fino alla fine. E anche se contenesse un valore sensato, non capisco perché assegnarlo alla prima lista (e peraltro questo avrebbe alcun effetto su lista2 all'esterno, dato che vai a modificare non ciò a cui punta quel puntatore, ma il puntatore stesso).
Poi, se vuoi fondere due liste, devi specificare in che lista vanno a finire tutti gli elementi: nella prima? Nella seconda? In una nuova? Sulla lista su cui è richiamato il metodo? E gli elementi delle liste passate devono continuare ad esistere indipendentemente o devono essere spostati nella nuova lista?
Infine, mi pare che la classe UnionL sia pensata male, dato che non modellizza una lista, ma un singolo elemento di essa. Una buona modellizzazione di una lista dovrebbe contenere una classe elemento solo al proprio interno, e non mostrare questi dettagli implementativi all'esterno; il concetto dovrebbe essere un po' come quello della classe coda su cui avevamo lavorato in passato.

[Zeldic]

In primo luogo, stai mescolando di nuovo codice che contiene la logica del container dati (la lista) con codice per mostrare all'utente il suo contenuto, e le due funzioni dovrebbero essere ben distinte.

...

Una buona modellizzazione di una lista dovrebbe contenere una classe elemento solo al proprio interno, e non mostrare questi dettagli implementativi all'esterno

Ciao, MItaly!! Seguendo la tua spiegazione ho quindi modificato il mio codice, la classe ora è 'Lista' ed è adibita solo a creare strutture di tipo 'Lista' ed ha come istanza un dato di tipo char ed un puntatore al successivo. Ho tardato però nel risponderti, perché purtroppo l'esito della mia modifica non è ancora positivo. Le funzioni 'creaL' e 'Union' non fanno più parte della classe ormai, ma sono funzioni che chiamo nel main. Il problema è ancora quello : quando chiamo 'Union(l1, l2)', e gli passo le 2 liste, non so che cosa in realtà gli sto passando, cioè quale valore assumono (credo nullo).. Visualizzo solo le parentesi quadre, nessun valore.. :051:

[MItaly]

Posta il codice attuale che ci ragioniamo.

[Zeldic]

Ok, grazie.. Ecco l'intero codice (ho infine sviluppato le funzioni di cui parlavo prima, nel 'main()', ma invano ) :

#include <iostream>                               
#include <stdlib.h>

using namespace std;

class List {                                     
  private :                                     
    char car;                                     
    List* nxt;                                  
    
  public :                                        
    List() { car = '\0'; nxt = NULL; }             
    ~List() { car = '\0'; nxt = NULL; }           
    void set(char new_car) { car = new_car; }     
    char get_car() { return car; }               
    void point_nxt(List* where_to_point) { nxt = where_to_point; }  
    List* get_nxt() { return nxt; }              
    void print(List*, List*);
};

void List::print(List* s, List* lista) {
  cout << "Gli elementi della 1-a lista sono i seguenti : \n\n";
  while(s != NULL) {
    cout << "[ " << s->get_car() << " ] ";
    s = s->get_nxt();
  }
  cout << "\n\n";
} 

    
main() {                                          
  List* st = NULL;
  List* l1;
  List* l2;
  List* nuovo;
  List* tmp;
  char c;
  
  cout << "******************   UNIONE  LISTE   ******************\n\n";
  l1 = new List();
  cout << "Popola 1-a lista di caratteri : ('x' per terminare) : \n\n";
  do {
        cin >> c;
        nuovo = new List();                       
        nuovo->set(c);
        nuovo->point_nxt(NULL);
  
        if(st == NULL)                           
          st = nuovo;
            else  
              tmp = st;                         
              tmp->point_nxt(nuovo);
  } while(c != 'x');
  
  st->print(st, l1);  
  
  l2 = new List();
  cout << "Popola 2-a lista di caratteri : ('x' per terminare) : \n\n";
  do {
        cin >> c;
        nuovo = new List();                       
        nuovo->set(c);
        nuovo->point_nxt(NULL);
  
        if(st == NULL)                                    
          st = nuovo;
            else {  
                    tmp = st;                       
                    tmp->point_nxt(nuovo);
            }
  } while(c != 'x');
    
  st->print(st, l2);
    
  cout << "Visualizzazione della lista 'unione' : \n\n";
  while( l1->get_nxt() ) {                       
    cout << "[ " << l1->get_car() << " ] ";
    l1 = l1->get_nxt();
  }
  while( l2->get_nxt() ) {                       
    cout << "[ " << l2->get_car() << " ] ";
    l2 = l2->get_nxt();
  }
  
cout << "Premi 'Invio' per terminare..";
cin.ignore();
return EXIT_SUCCESS;
}

Con la coda della scorsa volta sotto mano, non riesco tuttavia a trovare una relazione tra quel programma e questo e magari riutilizzare delle parti.. Ad esempio, nella classe coda avevamo dichiarato anche una funzione helper interna, che aveva il compito di restituire un puntatore all'ultimo elemento della coda.. Serve anche qui, per la creazione di una nuova lista?

[MItaly]

Stai ancora confondendo il concetto di lista con quello di suoi elementi. Una lista è il contenitore generale, mentre un suo elemento è una struttura con payload e puntatore all'elemento successivo.
Visto poi che la tua coda era di fatto implementata come una lista, la puoi riciclare praticamente in blocco, eventualmente sistemando un pochino quello che era elem in modo che sia gestibile dall'esterno:

class lista
{
  public:
    //Elementi memorizzati all'interno
    class elemento
    {
      private:
        // Payload
        char info;
        // Puntatore all'elemento successivo
        elemento * next;
        
      public:
        // Costruttore di default - inizializza la struttura a valori "neutri"
        elemento() :
            info('\0'),
            next(NULL)
        {
            return;
        };
        
        // Costruttore parametrico - inizializza la struttura con il valore desiderato
        elemento(char Info) :
            info(Info),
            next(NULL)
        {
            return;
        }; 
        
        // Getters/setters
        // payload
        char get_info() { return info; }
        void set_info(char Info) { info = Info; }

        // elemento successivo
        elemento * get_next() { return next; };
        void set_next(elemento * Next) { next = Next; }
        
        // ultimo elemento
        elemento * get_last()
        {
            if (next == NULL)
                return this;
            elemento * ret;
            for (ret = next; ret->get_next() != NULL; ret = ret->get_next())
                ;
            return ret;
        }
        
        // Qualche altro metodo di utilità generale
        
        // Attacca l'elemento passato e tutti gli elementi ad esso collegati
        // dopo l'elemento corrente, riattaccando il next attuale in fondo
        void append(elemento * elem)
        {
            if(get_next()!=NULL)
            {
                elemento * last=elem->get_last();
                last->set_next(next);
            }
            set_next(elem); // fine del gioco
        }
    };

  private:
    // Testa della lista; è un puntatore ad un oggetto 'elemento'
    elemento * testa;

  public:
    // Costruttore di default - inizializza una lista vuota
    lista()
    {
        testa = NULL;
    }

    // Distruttore - dealloca tutti gli elementi
    ~lista()
    {
        char dummy;
        while (testa != NULL)
        {
            remove(dummy);
        }
    }

    // Stampa il contenuto della lista
    void stampa(ostream & os);

    // Inserisce in fondo alla lista un valore
    void append(char dato);

    // Estrae dalla testa della lista un elemento; restituisce true se il dato è stato estratto, false se la lista è vuota
    bool remove(char & output);
    
    // Fornisce il primo elemento
    elemento * get_testa() { return testa; }
    // Fornisce l'ultimo elemento
    elemento * get_last()
    { 
        return testa==NULL?NULL:testa->get_last();
    }
};

void coda::append(char dato)
{
    elemento * nuovo = new elemento(dato);

    if (lista == NULL)
        lista = nuovo;
    else
        lastelem()->append(nuovo);
}

bool coda::remove(char & output)
{
    if (lista == NULL)
    {
        return false;
    }
    else
    {
        elemento * daRimuovere = testa;
        output = lista->get_info();
        testa = lista->get_next();
        delete daRimuovere;
        return true;
    }
}

void coda::stampa(ostream & os)
{
    if (testa == NULL)
    {
        os << "La coda e' vuota!\n";
    }
    else
    {
        os << "La coda contiene i seguenti elementi: \n\n";
        elemento * temp = get_testa();
        while (temp != NULL)
        {
            os << "---> [ " << temp->get_info() << " ] ";
            temp = temp->get_next();
        }
        os << "\n\n";
    }
}

Con questi strumenti ora diventa molto più facile scrivere una funzione di unione, ma, ribadisco, mi devi spiegare come deve funzionare questa fusione di liste: la nuova lista deve contenere tutti gli elementi delle due liste come copia degli elementi oppure deve semplicemente prenderne possesso e lasciare le altre due liste vuote?

[Zeldic]

mi devi spiegare come deve funzionare questa fusione di liste: la nuova lista deve contenere tutti gli elementi delle due liste come copia degli elementi oppure deve semplicemente prenderne possesso e lasciare le altre due liste vuote?

.. Eh, infatti.. Devo ammettere che ho un po' di difficoltà nel comprendere alla base ciò che mi dice di fare il mio Prof, anche se gli esercizi sono apparentemente stupidi.. Ti chiedo scusa se non sono stata chiara abbastanza. Dunque, ciò che devo esattamente fare è semplicemente creare 2 liste (chiamate ad esempio 'l1' ed 'l2'); poi devo 'scorrere' la prima lista, da 'st' (il primo elemento, start), sino all'ultimo elemento, che salverò in una variabile chiamata 'tmp'

tmp = st; (inizialmente)

dopo la lettura di l1, lui mi ha detto di porre :

tmp = l2; /* Ma tanto per cambiare anche questa assegnazione non l'ho capita molto bene.. */

.. e così collego l'ultimo elemento della prima lista al primo della seconda. Con la operazione di 'Union', l2 diviene parte integrante di l1.. Ovvero, il risultato finale è che ciascun elemento di l2 apparterrà ad l1. Il nome stesso della lista ottenuta sarà 'l1'.
Infine mi ha detto che si dovrebbe cancellare la seconda lista l2 ( delete l2; ), dato che l'abbiamo accorpata ad l1, ma se non lo so fare, è meglio che lascio perdere, per evitare che io faccia ulteriori disastri..

Chissà se non ci sia proprio il mio Prof. su questo forum.. Speriamo di no! Domani ho l'esame di Algo, dovrei sapere anche come si fa la visita di un grafo.. ed invece.. sono ancora qua, all'Unione delle liste.... :051:

[MItaly]

Originariamente inviato da Zeldic
.. Eh, infatti.. Devo ammettere che ho un po' di difficoltà nel comprendere alla base ciò che mi dice di fare il mio Prof, anche se gli esercizi sono apparentemente stupidi.. Ti chiedo scusa se non sono stata chiara abbastanza. Dunque, ciò che devo esattamente fare è semplicemente creare 2 liste (chiamate ad esempio 'l1' ed 'l2'); poi devo 'scorrere' la prima lista, da 'st' (il primo elemento, start), sino all'ultimo elemento, che salverò in una variabile chiamata 'tmp'

tmp = st; (inizialmente)

Semmai, tmp sarà uguale all'ultimo elemento a cui sei arrivata, non a st.

dopo la lettura di l1, lui mi ha detto di porre :

tmp = l2; /* Ma tanto per cambiare anche questa assegnazione non l'ho capita molto bene.. */

.. e così collego l'ultimo elemento della prima lista al primo della seconda.

Allora semmai sarà

tmp->next=l2;

in maniera tale da attaccare il primo elemento della seconda lista dopo l'ultimo della prima.

Con la operazione di 'Union', l2 diviene parte integrante di l1.. Ovvero, il risultato finale è che ciascun elemento di l2 apparterrà ad l1. Il nome stesso della lista ottenuta sarà 'l1'.

Certamente.

Infine mi ha detto che si dovrebbe cancellare la seconda lista l2 ( delete l2; ), dato che l'abbiamo accorpata ad l1, ma se non lo so fare, è meglio che lascio perdere, per evitare che io faccia ulteriori disastri.. :

In realtà non andrebbe cancellato, visto e considerato che l2 serve ancora ed è attaccato in fondo a l1.
Semmai si potrebbe fare l2=NULL per coerenza.

Chissà se non ci sia proprio il mio Prof. su questo forum.. Speriamo di no! Domani ho l'esame di Algo, dovrei sapere anche come si fa la visita di un grafo.. ed invece.. sono ancora qua, all'Unione delle liste.... :051:

Mai studiati i grafi, per cui non ti so aiutare; comunque, in bocca al lupo.

[Zeldic]

MItaly.. Mi sembra abbastanza riduttivo dirti solo un semplicissimo "grazie" per tutta la tua disponibilità! Devo rivedere però con più calma pezzo per pezzo la parte di codice che mi hai mandato e studiarmi meglio le funzioni della classe 'elemento', che è innestata alla classe 'lista' e dovrebbe essere dichiarata 'friend' per interagire con l'altra..
Comunque volevo dirti che grazie alla coda fatta assieme a te la volta precedente, ho superato brillantemente il II° esonero di Algoritmi.. La traccia era ovviamente diversa, anzi non era proprio una coda, ma seppi fare tesoro di tutto ciò che mi dicesti (il passaggio per reference, il tipo bool, la funzione 'lastelem()' per calcolare l'ultimo elemento... ).. Purtroppo quasi sicuramente credo che tutto il mio impegno e le prove precedenti superate non mi serviranno a superare la IIIa prova di domani sui grafi (e non è nemmeno l'ultima!) .. Sembra interminabile questo esame!
Spero gli admin non mi bannino, perché sono leggermente andata in OT!
Grazie ancora.. E buonanotte!!

[MItaly]

Originariamente inviato da Zeldic
MItaly.. Mi sembra abbastanza riduttivo dirti solo un semplicissimo "grazie" per tutta la tua disponibilità!

Non c'è di che.

Devo rivedere però con più calma pezzo per pezzo la parte di codice che mi hai mandato e studiarmi meglio le funzioni della classe 'elemento', che è innestata alla classe 'lista' e dovrebbe essere dichiarata 'friend' per interagire con l'altra..

In realtà no, visto che tutti i membri di Lista::Elemento su cui Lista ha bisogno di lavorare sono esposti come public.

Comunque volevo dirti che grazie alla coda fatta assieme a te la volta precedente, ho superato brillantemente il II° esonero di Algoritmi.. La traccia era ovviamente diversa, anzi non era proprio una coda, ma seppi fare tesoro di tutto ciò che mi dicesti (il passaggio per reference, il tipo bool, la funzione 'lastelem()' per calcolare l'ultimo elemento... )..

Lieto di esserti stato utile; so bene quanto possa essere prezioso fare bene i parziali ed evitarsi lo scrittone finale.

Purtroppo quasi sicuramente credo che tutto il mio impegno e le prove precedenti superate non mi serviranno a superare la IIIa prova di domani sui grafi (e non è nemmeno l'ultima!) .. Sembra interminabile questo esame!

Se ti consola, ho appena dovuto ridare lo scritto di un esame composto da 6 pezzi (prima relazione, prova scritta, schede di laboratorio, prova pratica, relazione finale, prova orale), c'è chi sta peggio in quanto a esami interminabili.
In bocca al lupo (retrospettivo ) per oggi!

Spero gli admin non mi bannino, perché sono leggermente andata in OT!

Non si banna per così poco, non siamo mica su HWUpgrade...