next up previous contents index
Next: Liste semplici in C++ Up: Memoria dinamica. Strutture. Liste Previous: Puntatori a strutture   Indice   Indice analitico

Liste vs Array

All'interno del nostro corso abbiamo fatto la conoscenza di alcuni tipi di dati; i primi che abbiamo incontrato sono stati i tipi primitivi (interi, caratteri, reali, booleani), poi abbiamo visto come lavorare con tipi di dati più complessi, come array, stringhe e strutture. Nella restante parte di questo capitolo vedremo come costruire ed utilizzare un nuovo tipo di dati, ancora più complesso di quelli fino ad ora presentati: il tipo lista. Tale struttura dati è simile all'array, in quanto essa consente di immagazzinare in memoria un insieme di dati omogenei, i quali possono essere acceduti a piacimento; c'è tuttavia una differenza fondamentale: la lista è una struttura dati dinamica, cioè il numero degli elementi contenuti in una lista può aumentare o dimininuire a piacimento in fase di esecuzione; al contrario, se creiamo un array (anche dinamico) noi allochiamo un certo quantitativo di memoria tutto insieme e non possiamo aggiungere o togliere elementi dall'array, a meno di costruirne uno nuovo e copiarvi tutti gli elementi. Vediamo un esempio che mostra l'inefficienza della struttura dati array nel caso si vogliano aggiungere o togliere celle ``on the fly'' (lett. ``al volo''); supponiamo di volere un oggetto array contenente dei numeri interi, immessi dall'utente in numero arbitrario, e di volerne infine calcolare la media:

// ex7_6_1
#include <iostream.h>

void generaArray (int*& array, int x, int nElem) {
  // crea un array temporaneo
  int* temp = new int[nElem];
  // copia i `vecchi' dati nell'array temporaneo
  for (int i = 0; i < nElem - 1; i++)
    temp[i] = array[i];
  // inserisce in temp il nuovo dato
  temp[nElem - 1] = x;
  // distrugge il vecchio array
  delete[] array;
  array = temp;
}

void main() {
  int nElem = 0;   // numero degli elementi dell'array
  int* array = 0;  // puntatore all'array dinamico
  // contenente i numeri sui quali calcolare la media
  int x;
  cout << "immetti un numero negativo per terminare\n";
  for ( ; ; ) {  // infinite loop
    cout << "? "; cin >> x;
    if (x < 0)
      break;
    nElem++; // incrementa il numero di elementi dell'array
    generaArray (array, x, nElem);
  }
  // calcola la media
  int somma = 0;
  for (int i = 0; i < nElem; i++) {
    somma += array[i];
  }
  cout << "media: " << (double)somma / (double)nElem << "\n";
}

esempio di output:
? 7
? 5
? 6
? 6
? 9
? -1
media: 6.6

Come è ovvio la struttura dati array per questo problema è totalmente inefficiente: il programma ad ogni inserimento di un nuovo dato deve allocare nuova memoria, copiare tutti gli elementi del vecchio array nel nuovo e deallocare questo stesso array; si tratta di operazioni molto pesanti, che è impensabile di dovere affrontare ogni qual volta vogliamo aggiungere un nuovo elemento. Certo, una soluzione potrebbe essere quella di allocare un array molto grande capace di contenere ragionevolmente il numero di dati che l'utente immette; non è una buona idea in generale, perché di solito il programmatore non ha una idea chiara di come utilizzare le strutture dati che egli crea, specialmente se il programma cui sta dedicandosi è relativamente vasto o fa parte di un progetto che coinvolge altri suoi colleghi. Una strada decisamente migliore è quella di allocare e deallocare la memoria dell'array ``a pacchetti'', cioè creare di volta in volta un array più grande non di una unità ma di un certo numero, il quale varia in base alle esigenze; vedremo alla fine di questo testo un esempio di struttura dati basata su tale metodo di allocazione della memoria. Comunque, ci farebbe comodo avere una struttura simile all'array, che abbia la capacità di crescere e decrescere ``a tempo costante'', cioè impiegando un tempo (breve) che non dipenda dal numero di elementi già presenti; un tipo di dati del genere esiste, ed è proprio la lista (eng. list).

Una lista è costituita dal unità elementare, che noi chiameremo celle o elementi o unità, come abbiamo già fatto per l'array; i dati che le celle possono contenere sono del tutto arbitrari, ma devono essere omogenei: si possono avere liste di interi, di reali, di stringhe, di array, di oggetti strutture, ma non liste di cui alcuni elementi siano di un tipo e altri di uno diverso da esso. Inoltre le liste non sono indicizzate, come l'array; ovvero non è possibile accedere in maniera diretta un singolo elemento di una lista, ma bisogna scorrere necessariamente tutti gli elementi che lo precedono; una lista è dunque un dato ad accesso sequenziale.

Per capire le liste è molto importante avere bene fissato un modello mentale cui fare riferimento; per le liste semplici 7.3 possiamo immaginare di avere delle celle, ognuna delle quali contiene un dato di un certo tipo, collegate l'un l'altra tramite una freccia la quale può portarci solo in un senso; il primo elemento ha una freccia che indica il nome della lista, la freccia dell'ultimo elemento punta 0:

Ciascun elemento è dunque costituito da due zone: una contenente l'informazione della cella, l'altra che permette di identificare l'elemento a essa successivo; un caso particolare è dato dall'ultimo elemento della lista, il quale non riferisce nessun ulteriore elemento. Definiamo infine come lista vuota quella che non ha alcun elemento.

Una lista dunque ha come scopo quello di rappresentare un insieme di dati, la cui dimensione varia fortemente durante l'esecuzione del programma; tale struttura dati è infatti intrinsecamente dinamica: ogni volta che un nuovo elemento viene aggiunto alla lista si alloca nuova memoria nello heap, facendo in modo che un puntatore a tale zona di memoria venga inserito all'interno della lista, nella maggior parte dei casi all'inizio o alla fine di essa. Tale flessibilità richiede tuttavia un prezzo da pagare: le liste non sono efficaci come gli array per la ricerca all'interno di esse, non consentendo esse modalità di accesso diretto; notiamo infatti che una lista è costituita da celle fondamentali, in ognuna delle quali è esclusivamente contenuto l'indirizzo della cella successiva: per accedere un elemento di una lista bisogna necessariamente accedere tutti i precedenti.


next up previous contents index
Next: Liste semplici in C++ Up: Memoria dinamica. Strutture. Liste Previous: Puntatori a strutture   Indice   Indice analitico
Claudio Cicconetti
2000-09-06