Rubrica
, contenente all'interno di
essa un oggetto di tipo ListaBilaterale
e uno o più iteratori di
essa.
Sorge però un problema, comune a tutte le strutture contenitori: gli
oggetti memorizzati nella nostra lista ``appartengono'' ad essa? Se
aggiungiamo la stringa "Bjarn"
alla nostra lista, qualora intendessimo
rimuoverla dobbiamo liberare la memoria da essa occupata, senza preoccuparci
di una eventuale condivisione con altre strutture dati? Siccome a priori non
possiamo sapere con l'utente utilizzerà la nostra classe
ListaBilaterale
utilizzeremo un flag 11.1,
che indicheremo con possiede
, il quale ci segnalerà se l'oggetto di
tipo ListaBilaterale
possiede o meno gli oggetti che contiene.
A differenza della lista semplice e degli array mostrati in precedenza,
passeremo gli oggetti alla ListaBilaterale
tramite puntatore; sebbene
tale pratica possa sembrare scomoda in fase di utilizzo, in realtà bisogna
tenere conto del fatto che una ListaBilaterale
verrà utilizzata
prevalentemente all'interno di altre classi, le quali provvederanno poi a
fornire una interfaccia più semplice.
La struttura tipo di una lista bilaterale non degenere è la seguente:
primo
e ultimo
sono entrambi nulli, oppure quando è unitaria:
/** listabilaterale.h template classe: ListaBilaterale */ #ifndef _LISTA_BILATERALE_H_ #define _LISTA_BILATERALE_H_ #include <iostream.h> enum Posizione { TESTA = 0, CODA = 1 }; template<class T> class IteratoreLB; // solo dichiarazione template<class T> class ListaBilaterale { friend class IteratoreLB; public: // costruttori, operatore di assegnamento e distruttore ListaBilaterale (bool Possiede = true); ListaBilaterale (const ListaBilaterale&); const ListaBilaterale& operator= (const ListaBilaterale&); ~ListaBilaterale (); // funzioni di accesso unsigned int quanti() const { return n_elem; } bool vuota() const { if (primo == 0) return true; return false; } bool unitaria() const { if (!vuota() && primo == ultimo) return true; return false; } bool possesso() const { return possiede; } // funzioni di inserimento ed estrazione T* inserisci (T* nuovo_oggetto, Posizione pos = TESTA); T* elemento (Posizione pos = TESTA); int estrai (Posizione pos = TESTA); private: // struttura di un elemento della lista struct elem { elem* dx; // puntatore all'elemento a destra elem* sx; // puntatore all'elemento a sinistra T* oggetto; // costruttore elem (T* Oggetto, elem* Sx = 0, elem* Dx = 0) { oggetto = Oggetto; dx = Dx; sx = Sx; } }; bool possiede; elem *primo, *ultimo; unsigned int n_elem; // numero di elementi // funzioni interne void distruggiLista (); void copiaLista (const ListaBilaterale&); }; template<class T> ListaBilaterale<T>::ListaBilaterale (bool Possiede) { possiede = Possiede; primo = ultimo = 0; n_elem = 0; } template<class T> ListaBilaterale<T>::ListaBilaterale (const ListaBilaterale& lista) { possiede = false; n_elem = lista.n_elem; copiaLista (lista); } template<class T> const ListaBilaterale<T>& ListaBilaterale<T>::operator= (const ListaBilaterale& lista) { if (&lista != this) { distruggiLista(); possiede = false; n_elem = lista.n_elem; copiaLista (lista); } return *this; } template<class T> ListaBilaterale<T>::~ListaBilaterale () { distruggiLista(); } template<class T> void ListaBilaterale<T>::distruggiLista () { if (vuota()) ; else if (unitaria()) delete primo; else { elem* p = primo; elem* q; while (p != 0) { q = p->dx; if (possiede == true) delete p->oggetto; delete p; p = q; } } primo = ultimo = 0; } template<class T> void ListaBilaterale<T>::copiaLista (const ListaBilaterale& sorg) { if (sorg.vuota()) primo = ultimo = 0; else if (sorg.unitaria()) primo = ultimo = new elem(sorg.primo->oggetto); else { primo = new elem(sorg.primo->oggetto); elem* p = primo; for (elem* q = sorg.primo->dx; q != 0; q = q->dx) p = p->dx = new elem(q->oggetto, p, 0); ultimo = p; } } template<class T> T* ListaBilaterale<T>::inserisci (T* nuovo_oggetto, Posizione pos) { n_elem++; if (vuota()) ultimo = primo = new elem(nuovo_oggetto); else if (pos == TESTA) { primo->dx->sx = primo = new elem(nuovo_oggetto, 0, primo); } else { // pos == CODA ultimo = ultimo->dx = new elem(nuovo_oggetto, ultimo, 0); } return nuovo_oggetto; } template<class T> T* ListaBilaterale<T>::elemento (Posizione pos) { if (vuota()) return 0; if (pos == TESTA) return primo->oggetto; return ultimo->oggetto; } template<class T> int ListaBilaterale<T>::estrai (Posizione pos) { if (vuota()) return -1; if (unitaria()) { if (possiede == true) delete primo->oggetto; delete primo; primo = ultimo = 0; n_elem = 0; return 0; } else { if (pos == TESTA) { elem* q = primo; if (possiede == true) delete primo->oggetto; primo = primo->dx; primo->sx = 0; delete q; } else { elem* q = ultimo; if (possiede == true) delete ultimo->oggetto; ultimo = ultimo->sx; ultimo->dx = 0; delete q; } return --n_elem; } } #endif // _LISTA_BILATERALE_H_
Alcune note:
inserisci
e elemento
restituiscono un
puntatore all'oggetto che hanno, rispettivamente, inserito e acceduto in
lettura;estrai
restituisce il numero di elementi della lista
successivamente all'estrazione; se essa non ha luogo viene tornato il codice
di errore -1
.
Le liste bilaterali sono molto più efficienti di quelle semplici per due
motivi essenziali: operare in testa e in coda ha lo stesso peso
computazionale, è possibile scorrere una lista bilaterale sia dalla testa
alla coda che viceversa. Sfruttiamo quest'ultima proprietà per programmare
un iteratore (IteratoreLB
), il quale ci permetta in realtà di
utilizzare la struttura dati appena creata11.2.
template<class T> class IteratoreLB { public: IteratoreLB (ListaBilaterale<T>& Lista, Posizione pos = TESTA); // IteratoreLB (const IteratoreLB&); // const IteratoreLB& operator= (const IteratoreLB&); // ~IteratoreLB(); T* operator++ (int) { // post-fisso return ++(*this); } T* operator++ (); // prefisso T* operator-- (int) { // post-fisso return --(*this); } T* operator-- (); // prefisso T* attuale (); bool inizio () const; bool fine () const; T* inserisci (T* nuovo_oggetto); T* estrai (); private: ListaBilaterale<T>::elem *corrente; ListaBilaterale<T>* lista; }; template<class T> IteratoreLB<T>::IteratoreLB (ListaBilaterale<T>& Lista, Posizione pos) { lista = &Lista; if (pos == TESTA) corrente = Lista.primo; else // pos == CODA corrente = Lista.ultimo; } template<class T> T* IteratoreLB<T>::operator++ () { if (!fine()) corrente = corrente->dx; return corrente->oggetto; } template<class T> T* IteratoreLB<T>::operator-- () { if (!inizio()) corrente = corrente->sx; return corrente->oggetto; } template<class T> T* IteratoreLB<T>::attuale () { return corrente->oggetto; } template<class T> bool IteratoreLB<T>::inizio() const { if (corrente->sx == 0) return true; return false; } template<class T> bool IteratoreLB<T>::fine() const { if (corrente->dx == 0) return true; return false; } template<class T> T* IteratoreLB<T>::inserisci(T* nuovo_oggetto) { lista->n_elem++; if (fine()) { corrente = corrente->dx = new ListaBilaterale<T>::elem (nuovo_oggetto, corrente, 0); lista->ultimo = corrente; } else { ListaBilaterale<T>::elem* q = corrente->dx; corrente = corrente->dx = new ListaBilaterale<T>::elem (nuovo_oggetto, corrente, corrente->dx); q->sx = corrente; } return nuovo_oggetto; } template<class T> T* IteratoreLB<T>::estrai() { // ATTENZIONE: non separati i casi di lista degenere lista->n_elem--; ListaBilaterale<T>::elem* q = corrente; if (inizio()) { corrente = corrente->dx; corrente->sx = 0; } else if (fine()) { corrente = corrente->sx; corrente->dx = 0; } else { // corrente si sposta verso destra ListaBilaterale<T>::elem* p = corrente->sx; corrente = corrente->dx; p->dx = corrente; corrente->sx = p; } if (lista->possesso() == true) delete q->oggetto; delete q; return corrente->oggetto; }
Gli iteratore in una classe contenitore solitamente vengono utilizzati in brevi porzioni di codice e poi distrutti, essendo oggetti molto ``leggeri'' dal punto di vista della memoria occupata e delle operazioni necessarie al funzionamento di essi; per questo motivo, spesso un iteratore viene utilizzato solo per alcune funzioni specifiche oppure solo per oggetti con determinate caratteristiche, nel nostro caso solo per liste bilaterali aventi almeno due elementi.
Un semplice programma di esempio che utilizzi una lista bilaterale di stringhe
è il seguente; abbiamo utilizzato l'iteratore per programmare l'operatore di
uscita della ListaBilaterale<Stringa>
// ex11_1_1.cpp #include "listabilaterale.h" #include "stringa.h" ostream& operator<< (ostream& os, ListaBilaterale<Stringa>& lista) { IteratoreLB<Stringa> it(lista); while (!it.fine()) { cout << *it.attuale() << endl; it++; } cout << *it.attuale() << endl; return os; } void main() { ListaBilaterale<Stringa> a; a.inserisci(new Stringa("Vern Paxson")); a.inserisci(new Stringa("Van Jacobson"), CODA); a.inserisci(new Stringa("Jef Poskanzer")); a.inserisci(new Stringa("Esmond Pitt"), CODA); a.inserisci(new Stringa("Earle Horton")); a.inserisci(new Stringa("Benson Margulies"), CODA); a.inserisci(new Stringa("Fred Burke")); cout << a << endl; cout << "\ntesta: " << *a.elemento(TESTA) << "\n"; cout << "coda: " << *a.elemento(CODA) << "\n"; ListaBilaterale<Stringa> b = a; cout << b.estrai(TESTA) << "\t" << b.estrai(CODA) << "\t" << b.estrai(CODA) << "\n"; cout << b << "\n"; }
output:
Fred Burke
Earle Horton
Jef Poskanzer
Vern Paxson
Van Jacobson
Esmond Pitt
Benson Margulies
testa: Fred Burke
coda: Benson Margulies
4 | 5 | 6 |
Gli iteratori vengono spesso utilizzati per programmare funzioni, membri di altre classi in generale, che agiscano su strutture come le liste; vediamo nel seguente esempio come è possibile programmare facilmente due funzioni che inseriscano o estraggano elementi in posizione arbitraria in una lista bilaterale.
// ex11_1_2.cpp #include "listabilaterale.h" ostream& operator<< (ostream& os, ListaBilaterale<int>& lista) { IteratoreLB<int> it(lista); while (!it.fine()) { cout << *it.attuale() << "\t"; it++; } cout << *it.attuale(); return os; } // inserisce un nuovo oggetto in posizione // arbitraria in una ListaBilaterale<int> void inserisci(ListaBilaterale<int>& lista, int* nuovo_oggetto, unsigned int pos) { IteratoreLB<int> it(lista); if (pos <= 1) lista.inserisci(nuovo_oggetto, TESTA); else if (pos >= lista.quanti()) lista.inserisci(nuovo_oggetto, CODA); else { for (int i = 2; i < pos; i++) it++; it.inserisci(nuovo_oggetto); } } // estrae un elemento da una ListaBilaterale<int> void estrai(ListaBilaterale<int>& lista, unsigned int pos) { IteratoreLB<int> it(lista); if (pos <= 1) lista.estrai(TESTA); else if (pos >= lista.quanti()) lista.estrai(CODA); else { for (int i = 2; i < pos; i++) it++; it.estrai(); } } void main() { ListaBilaterale<int> a; int i; for (i = 1; i <= 3; i++) a.inserisci(new int(i)); for (i = 4; i <= 6; i++) a.inserisci(new int(i), CODA); cout << a << "\n\n"; IteratoreLB<int> it(a); inserisci(a, new int(-1), 1); inserisci(a, new int(-2), 4); inserisci(a, new int(-3), 99); cout << a << "\n\n"; estrai(a, 1); estrai(a, 4); estrai(a, 99); cout << a << "\n\n"; }
3 | 2 | 1 | 4 | 5 | 6 | ||||
-1 | 3 | 2 | -2 | 1 | 4 | 5 | 6 | -3 | |
3 | 2 | 1 | 4 | 5 | 6 |
Elenco
, rappresentata tramite una
ListaBilaterale
di Stringa
, all'interno della quale siano
definite (almeno) le seguenti funzioni:
Elenco()
: costruttore defaultElenco(const Elenco&)
: costruttore di copiaconst Elenco& operator= (const Elenco&)
: sovrapposizione
dell'operatore di assegnamento~Elenco()
: distruttoreinserisci(const Stringa& s)
: funzione che inserisce il nome
s
all'elenco (in cima all'elenco)elimina(const Stringa& s)
: funzione che cerca la primo occorrenza
nell'elenco della stringa s
ed elimina l'elemento ad esso associatoelimina(unsigned int n)
: elimina i primi n
elementi dell'elencoordina()
: funzione che ordina gli elementi dell'elenco in ordine
alfabetico crescente (nota: non banale)raddoppia()
: funzione che raddoppia il numero degli elementi
dell'elenco, creando una copia di ciascuna stringa