next up previous contents index
Next: Stack Up: Alcuni tipi di dati Previous: Alcuni tipi di dati   Indice   Indice analitico

Lista bilaterale

Abbiamo già accennato brevemente alle liste bilaterali nel capitolo riguardante l'accesso alla memoria dinamica; affrontiamo nuovamente l'argomento presentando una più matura struttura dati, sotto forma di template class. Una lista bilaterale è difficilmente utilizzabile direttamente in un programma: molto più comune è l'utilizzo di essa come struttura di fondo in una classe che rappresenti qualcosa di più specifico. Se ad esempio abbiamo intenzione di gestire una rubrica tramite una lista, possiamo creare la classe 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:

Una lista bilaterale è degenere quando è vuota, nel qual caso i puntatori primo e ultimo sono entrambi nulli, oppure quando è unitaria:
Ricordiamo che è sempre necessario all'interno di liste effettuare controlli sui casi degeneri.


/**
   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:

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

Earle Horton
Jef Poskanzer
Vern Paxson
Van Jacobson

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      

ex-2
si programmi la classe Elenco, rappresentata tramite una ListaBilaterale di Stringa, all'interno della quale siano definite (almeno) le seguenti funzioni:


next up previous contents index
Next: Stack Up: Alcuni tipi di dati Previous: Alcuni tipi di dati   Indice   Indice analitico
Claudio Cicconetti
2000-09-06