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