Esercizi sulle liste

di il
10 risposte

Esercizi sulle liste

Ho la seguente lista:

struct nodo
{
int valore;
nodo *succ;
};

class lista
{
nodo *l;

nodo* insert(nodo *p,int x);
bool find(nodo *, int);
nodo* split(nodo *l1);
nodo* Merge(nodo *l1, nodo *l2);
nodo* MergeSort(nodo *list);

public:
lista(){l=0;}
~lista();
void push(int);
bool cancella(int);
void stampa();
bool trova(int);
void ordina();
};

Queste funzioni sono già implementate e nei vari esercizi mi si chiede di aggiungerne altre, ad esempio:
1) realizzazione classe derivata che implementi una lista ordinata
2) definizione del costruttore di copia e di assegnazione
Come posso fare?

10 Risposte

  • Re: Esercizi sulle liste

    Inizia a leggere il regolamento. Sezione 4: Formattazione del codice.
    4. Formattare il codice sorgente
    Visto gli argomenti trattati in questo forum vengono spesso inseriti stralci di codice sorgente.
    Per rendere facilmente leggibile tale codice bisogna formattarlo utilizzando il pulsante "Code".
  • Re: Esercizi sulle liste

    struct nodo
    {
    int valore;
    nodo *succ;
    };
    
    class lista
    {
    nodo *l;
    
    nodo* insert(nodo *p,int x); 
    bool find(nodo *, int);
    nodo* split(nodo *l1);
    nodo* Merge(nodo *l1, nodo *l2);
    nodo* MergeSort(nodo *list);
    
    public:
    lista(){l=0;}
    ~lista();
    void push(int);
    bool cancella(int);
    void stampa();
    bool trova(int);
    void ordina();
    };
    ecco ho formattato il codice. Qualcuno adesso sa risp alle mie domande???
  • Re: Esercizi sulle liste

    Puoi crearti una classe ListaOrdinata che deriva da Lista e ridefinirti la funzinoe di inserimento in lista.
  • Re: Esercizi sulle liste

    Ok ho capito e come faccio a definire il costruttore di copia e quello di assegnazione per la classe lista? Posso vedere un esempio di codice?
  • Re: Esercizi sulle liste

    class foo
    {
         foo(const foo& rhs);
         foo & operator=(const foo& rhs);
    };
    Assignment operator


    Copy Constructor
    http://en.wikipedia.org/wiki/Copy_constructo
  • Re: Esercizi sulle liste

    Nel mio caso come devo implementare? Perché nella classe lista ho solo una variabile di tipo puntatore a nodo
  • Re: Esercizi sulle liste

    Quindi? il costruttore di copia deve costruire una nuova lista partendo dalla lista passata come parametro. Siccome l'unico dato che tu hai nella lista è un puntatore al nodo iniziale devi semplicemente assegnare a questo nodo il valore del nodo iniziale della lista passata come parametro.
    
    foo::foo(const foo& rhs)
    : l(rhs.l)
    {
    }
    
    Per quanto riguarda l'operatore di assegnazione la storia non cambia di molto. Devi solo vedere se stai assegnando la stessa lista allo stesso oggegtto.
    
    foo & foo::operator=(const foo & rhs)
    {
         if(this != &rhs) // protezione contro auto assegnazione.
         {
             l = rhs.l;
          }
         return *this;
    }
    
  • Re: Esercizi sulle liste

    Ti ringrazio!! Sembra una cosa banale ma devo fare l'esame prossimamente e non è che sia molto pratico! Ho anche altre funzioni possibili da implementare e mi servirebbe una mano... ad esempio:
    definizione di una fz membro della classe lista che riceva un'altra lista come argomento ed elimini gli elementi comuni
    Grazie!!!
  • Re: Esercizi sulle liste

    Magari fare qualcosa tu? Tutto ciò che hai postato è codice di altri. Fai vedere che anche tu ti impegni.
  • Re: Esercizi sulle liste

    Parlando di costruttori di copia e di assegnamento credo che tu conosca già la differenza tra 'copia profonda' (o logica) e 'copia superficiale' (il non conoscerlo potrebbe voler dire non superare l' eseme ) ma è meglio ripeterlo.

    Il problema si pone quando un oggetto contiene dei puntatori a dati dinamici (come nel caso della tua lista), la copia superficiale copia semplicemente i puntatori, la copia profonda crea delle nuove istanze degli oggetti puntati.

    In pratica se fai una copia superficiale della tua lista da A a B, questi oggetti condivideranno i nodi della lista (in quanto copi solo il puntatore iniziale) per cui le modifiche fatte in un oggetto saranno comuni anche all' altro.

    Se fai una copia profonda della lista da A a B verrà creata una copia di tutti i nodi, per cui le modifiche fatte nel primo oggetto non si rifletteranno nel secondo.

    La copia profonda (detta anche logica) è quella che più si avvicina a quello che ti spetti da una copia, quando fai A = B
    non ti aspetti che alterando A modifichi anche B. Può però essere dispendiosa in termini di risorse (copiare una grossa lista può richiedere molto tempo e memoria).

    Come la implementi? Ti conviene aggiungere un costruttore di copia alla classe nodo, poi iterando sulla lista da copiare ne ricrei un' altra duplicando i nodi.

    Ciao
Devi accedere o registrarti per scrivere nel forum
10 risposte