Lista
. Come
tutti i contenitori, è conveniente utilizzare una struttura a
template per la lista, in modo da potere costruire liste di qualunque
tipo. L'unica piccola differenza con la struttura di lista già discussa
riguarda l'aggiunta del campo stringa nome
, che rappresenta il nome
della lista. L'unico file necessario alla compilazione di Lista è
lista.h
, trattandosi essa di un template; l'intestazione di
tale file è la seguente:
// lista.h // implementa una lista semplice tramite un template #include <string.h> template<class Tipo> class Lista { public: // costruttori, distruttore e operatore di assegnamento Lista (const char* Nome = 0); Lista (const Lista&); const Lista& operator= (const Lista&); ~Lista(); // funzioni di accesso bool listaVuota () const { if (testa == 0) return true; return false; } unsigned int numeroElementi () const { return n_elementi; } const char* nomeLista () const { return nome; } const char* rinomina (const char* Nome) { delete[] nome; if (Nome != 0) { nome = new char[strlen(Nome) + 1]; strcpy (nome, Nome); } else nome = 0; return nome; } // inserimento ed estrazione dati Lista& inserisciTesta (const Tipo& t); Lista& inserisciCoda (const Tipo& t); Lista& estraiTesta (); Lista& estraiCoda (); private: struct elem { Tipo* oggetto; // campo informazione elem* next; // puntatore all'elemento successivo // costruttore della struttura elem (const Tipo& Oggetto, elem* Next = 0) { next = Next; oggetto = new Tipo(Oggetto); } ~elem () { delete oggetto; } }; char* nome; // nome della lista (stringa) elem *testa, *coda; unsigned int n_elementi; // funzioni interne alla classe void distruggiLista (); void copiaLista (elem* sorgente); };
Le uniche funzioni che abbiamo definito all'interno della dichiarazione di
Lista
sono quelle di accesso ad alcuni campi dati:
listaVuota()
: restituisce true se la lista è
effettivamente vuota, false in caso contrario;numeroElementi()
: restituisce semplicemente il numero di
elementi, accedendo in lettura al campo dati privato n_elementi
;nomeLista()
: restituisce il nome della lista;rinomina (const char*)
: permette di assegnare alla lista un nuovo
nome, che viene infine restituito dalla funzione.
I costruttori, il distruttore, l'operatore di assegnamento e le due funzioni
interne distruggiLista()
e copiaLista(elem*)
sono definite come
segue:
template<class Tipo> Lista<Tipo>::Lista (const char* Nome) { if (Nome == 0) nome = 0; else { nome = new char[strlen(Nome) + 1]; strcpy (nome, Nome); } n_elementi = 0; testa = coda = 0; } template<class Tipo> Lista<Tipo>::Lista (const Lista& lista) { // la nuova lista non ha nome nome = 0; n_elementi = lista.n_elementi; copiaLista (lista.testa); } template<class Tipo> const Lista<Tipo>& Lista<Tipo>::operator= (const Lista& lista) { if (&lista != this) { // previene l'autoassegnamento // i nomi delle liste rimangono invariati n_elementi = lista.n_elementi. distruggiLista; copiaLista (lista.testa); } return *this; } template<class Tipo> Lista<Tipo>::~Lista () { distruggiLista(); delete[] nome; } template<class Tipo> void Lista<Tipo>::distruggiLista () { // puntatore ausiliario di scorrimento elem* p = testa; while (p != 0) { testa = p->next; delete p; p = testa; } testa = coda = 0; } template<class Tipo> void Lista<Tipo>::copiaLista (elem* sorgente) { // attenzione! se testa e coda non sono nulli // i dati ad essi collegati verranno mutati in garbage elem* p; // lista destinazione (*this) elem* q = lista.testa; // lista sorgente if (q != 0) { // lista sorgente non vuota p = testa = new elem (p->oggetto); while ((q = q->next) != 0) p = p->next = new elem (q->oggetto); coda = p; } else // lista sorgente vuota testa = coda = 0; }
Siccome l'operatore di assegnamento compie essenzialmente le medesime operazioni del costruttore di copia e del distruttore, abbiamo preferito programmare due funzioni private ausiliare:
distruggiLista()
: elimina dalla memoria l'intera lista e mette a
zero i puntatori di testa e di coda;copiaLista(elem* sorgente)
: copia nella lista un'altra lista
sorgente
; tale funzioni è da adoperare con estrema cautela perché
non effettua alcun controllo sulla memoria allocata da testa
e
coda
: nel caso essa non sia nulla, alla fine della procedura verrà
completamente mutata in garbage.Le funzioni di inserimento ed estrazioni sono le seguenti:
template<class Tipo> Lista<Tipo>& Lista<Tipo>::inserisciTesta (const Tipo& t) { n_elementi++; if (testa == 0) { // lista vuota testa = new elem (t); coda = testa; } else // lista non vuota testa = new elem (t, testa); return *this; } template<class Tipo> Lista<Tipo>& Lista<Tipo>::inserisciCoda (const Tipo& t) { n_elementi++; if (testa == 0) { // lista vuota testa = new elem (t); coda = testa; } else // lista non vuota coda = coda->next = new elem (t); return *this; } template<class Tipo> Lista<Tipo>& Lista<Tipo>::estraiTesta () { n_elementi--; if (testa == 0) // lista vuota n_elementi++; else if (testa == coda) { // lista unitaria delete testa; testa = coda = 0; } else { elem* p = testa; testa = testa->next; delete p; } return *this; } template<class Tipo> Lista<Tipo>& Lista<Tipo>::estraiCoda () { n_elementi--; if (testa == 0) // lista vuota n_elementi++; else if (testa == coda) { // lista unitaria delete testa; testa = coda = 0; } else { elem* p = testa; elem* q = p->next; while (q->next != 0) { p = p->next; q = q->next; } delete q; p->next = 0; coda = p; } return *this; }
Le funzioni di inserimento, in testa e in coda, sono piuttosto banali: isolato il caso di lista vuota, la procedura intera consiste di un unico statement. Le funzioni di estrazione invece sono leggermente più articolate: bisogna isolare due casi, di lista vuota e lista unitaria. Nel caso di estrazione in coda, è addirittura necessario scorrere tutta lista per non perdere la coerenza della struttura dati.
Inserire ed estrarre in coda è l'unica operazione ragionevole da effettuare
su di una lista, a meno di perdere notevolmente l'efficienza dell'operazione,
mentre in casi pratici è spesso utile accedere i dati compresi tra la testa
e la coda di una lista. A questo scopo esistono gli iteratori (eng.
``iterator''): oggetti classe che sono strettamente legati ad un particolare
contenitore ad accesso sequenziale, e che ne permettono lo scorrimento in un
verso o in entrambi. A scopo di esempio programmeremo un semplice iteratore
per la nostra Lista
, implementato come classe template,
friend di essa; lo scorrimento, a causa della struttura
unidirezionale della Lista
stessa, potrà avvenire solo dalla testa
alla coda. Si faccia attenzione a dichiarare la classe Iteratore
prima della Lista
:
template<class Tipo> class Iteratore; |
Lista
:
friend class Iteratore<Tipo>; |
Iteratore
:
template<class Tipo> class Iteratore { public: // costruttore e distruttore Iteratore (Lista<Tipo>* l); // ~Iteratore (); // membri non dinamici // funzioni di scorrimento Tipo& operator++ (); // prefisso Tipo& operator++ (int) { // postfisso return ++(*this); } Tipo& corrente (); bool ultimo (); private: // vietiamo l'uso del costruttore di copia // e dell'operatore di assegnamento Iteratore (const Iteratore&); const Iteratore& operator= (const Iteratore&); // oggetto Lista cui e` collegato l'iteratore Lista<Tipo>* lista; Lista<Tipo>::elem* p; // puntatore di scorrimento bool contatore; };
Il nostro iteratore, come si vede, contiene i seguenti campi dati:
lista
: un puntatore alla lista cui appartiene;p
: un puntatore di scorrimento unidirezionale all'interno della
lista;contatore
: si tratta di una variabile booleana di comodo che
utilizzeremo nella funzione ultimo()
.template<class Tipo> Iteratore<Tipo>::Iteratore (Lista<Tipo>* l) { lista = l; p = l->testa; contatore = false; } template<class Tipo> Tipo& Iteratore<Tipo>::operator++ () { if (p->next != 0) p = p->next; return *(p->oggetto); } template<class Tipo> Tipo& Iteratore<Tipo>::corrente () { return *(p->oggetto); } template<class Tipo> bool Iteratore<Tipo>::ultimo () { if (p->next == 0 && contatore == true) return true; else if (p->next == 0 && contatore == false) contatore = true; return false; }Il costruttore ha come unica funzione, quella di inizializzare i campi dati della classe; l'operatore di incremento unitario sposta verso la coda il puntatore si scorrimento
p
, prima di restituire l'oggetto da esso
puntator; la funzione corrente()
restituisce l'oggetto puntato da
p
; infine, la funzione ultimo()
restituisce true solo
se p
è arrivato in fondo alla lista ed è almeno la seconda volta
che ciò accade.
Un semplice programma di esempio è il seguente, nel quale sovrapponiamo l'operatore di uscita sullo stream standard di output:
// ex10_6_1.cpp #include "lista.h" #include <iostream.h> ostream& operator<< (ostream& os, Lista<int>& lista) { Iteratore<int> it(&lista); while (it.ultimo() == false) { os << it.corrente() << "\n"; it++; } return os; } void main() { Lista<int> a; for (int i = 0; i < 5; i++) a.inserisciTesta (i+1); for (int i = 0; i < 5; i++) a.inserisciCoda (i+6); a.estraiTesta(); a.estraiCoda(); cout << a << "\n"; }
output:
4
3
2
1
6
7
8
9
Lista
:
inserisci(const Tipo& t, unsigned pos)
: inserisce l'oggetto
t
in posizione pos
; se pos
è minore del numero totale
di elementi t
viene aggiunto in cima;elimina(unsigned p1, unsigned p2)
: elimina gli oggetti dalla
posizione p1
-esima alla p2
-esima;ordina()
: ordina la lista in ordine crescente, supponendo che sia
definito l'operatore di confronto <
in Tipo
(non banale);Lista
avente un puntatore non solo
in testa e in coda, ma anche sull'elemento centrale della lista; si
faccia attenzione ad isolare il giusto numero di casi particolari nelle
funzioni di inserimento ed estrazione;
ListaCircolare
ed un suo iteratore
unidirezionale;