next up previous contents index
Next: Inserzione in testa e Up: Memoria dinamica. Strutture. Liste Previous: Liste vs Array   Indice   Indice analitico

Liste semplici in C++

In C++ non esiste un tipo ``lista'', per cui dobbiamo costruire autonomamente una serie di funzioni le quali ci permettano di effetturare delle operazioni sulle nostre liste. In realtà ci sono numerose librerie, fornite a corredo di ogni distribuzione del C++, che forniscono una classe lista, ma ci sono due motivi per i quali non ne faremo uso: è un buon esercizio ``reinventare la ruota'', cioè costruire da zero buona parte delle funzioni permesse sulle liste; inoltre, non abbiamo ancora le conoscenza necessarie per affrontare lo studio di una classe complessa, come quelle fornite con i compilatori C++. Ovviamente le liste che utilizzeremo saranno a scopo esclusivamente didattico, nel senso che ogni loro utilizzo professionale è impensabile per scarsezza di flessibilità ed efficienza.

Nella sezione precedente abbiamo descritto una lista come costituita da elementi, ciascuno avente una struttura formata da un campo dati e un campo che riferisse l'elemento ad esso successivo. Cominciamo allora a costruire un elemento; utilizzeremo, come è ovvio, una struttura7.4, avente un costruttore che forzi l'utilizzatore ad inizializzare ogni elemento creato:


struct elem {
  int   info;
  elem* next;
  elem (int Info, elem* Next) {
    info = Info;
    next = Next;
  }
};
Si faccia bene attenzione alla struttura elem7.5: abbiamo un campo intero info che contiene l'informazione della cella, che in questo caso è un intero; in tutto il capitolo supporremo sempre di lavorare con liste di interi, ma nulla vieta che le liste possano contenere un qualunque tipo di dato, primitivo o derivato. Oltre all'informazione un elemento contiene, come detto, un puntatore all'elemento a esso successivo next; ovviamente nel caso di elemento terminale (ultimo nella lista) tale puntatore vale 0. Infine un elemento ha un costruttore che inizializza entrambi i campi della struttura; in tale maniera non è possibile costruire un elemento avente i campi fluttuanti, il che sarebbe pericoloso perché è presente un campo puntatore. Un esempio grafico di una lista è i seguente:
Il nome di una lista è dato da un puntatore di tipo elem*, che nel nostro esempio è chiamato lista; il valore di esso è l'indirizzo della prima cella. Essa d'altronde contiene, oltre al campo informazione, anche l'indirizzo della cella successiva, e così via fino all'ultima cella, che ha next nullo; nel grafico l'ultima cella risulta messa a terra, per indicare la sua posizione terminale. Un esempio che ci permette di costruire la lista disegnata (ovviamente gli indirizzi non corrispondono) è il seguente:

// ex7_7_1
// esempio di lista
// Si ricordi di copiare la definizione di elem
// in questo punto del programma

void main() {
  elem* lista;  // puntatore al primo elemento
  // gli elementi vanno creati in ordine inverso
  lista = new elem (4, 0); // l'elemento e` messo a terra
  lista = new elem (3, lista);
  lista = new elem (7, lista);
}

Vediamo ora alcuni gruppi di funzioni sulle liste.


Subsections
next up previous contents index
Next: Inserzione in testa e Up: Memoria dinamica. Strutture. Liste Previous: Liste vs Array   Indice   Indice analitico
Claudio Cicconetti
2000-09-06