next up previous contents index
Next: Alcuni tipi di dati Up: Dettagli sulle classi. Templates Previous: Templates   Indice   Indice analitico

Un esempio concreto: lista semplice con iteratore

Un tipico contenitore è la lista, che abbiamo introdotto precedentemente; nella presente sezione, conclusiva del capitolo, implementeremo una lista semplice con puntatore in coda all'interno della classe 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:

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:

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;
e a inserire la seguente dichiarazione all'interno di Lista:

friend class Iteratore<Tipo>;
Ecco l'intestazione di 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:

Si noti che abbiamo dichiarato privati il costruttore di copia e l'operatore di assegnamento, perché un loro uso improprio è facilmente causa di errori a scarsa rilevabilità. Le definizioni delle funzioni membro sono:

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

ex-2
si programmino le seguenti funzioni membro aggiuntive della classe Lista:
ex-3
si programmi una nuova classe 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;
ex-4
si programmi una classe ListaCircolare ed un suo iteratore unidirezionale;


next up previous contents index
Next: Alcuni tipi di dati Up: Dettagli sulle classi. Templates Previous: Templates   Indice   Indice analitico
Claudio Cicconetti
2000-09-06