È possibile realizzare strutture dati in grado di allocare memoria solo quando è necessaria, per ogni singola informazione da memorizzare. Un esempio sono le liste dinamiche, in cui ogni elemento è associato a un puntatore contenente l’indirizzo dell’elemento successivo. Nella figura seguente, è rappresentata una lista concatenata avente quattro elementi detti anche nodi; la variabile dato contiene l’informazione, mentre la variabile puntatore punta al nodo successivo. L’ultimo nodo contiene un indirizzo speciale per il puntatore, detto NULL che non punta a nulla.
Il dato può essere una variabile elementare o un insieme di variabili elementari che, insieme al puntatore, rappresenteranno la struttura record. Particolare importanza sono alcuni tipi di liste come la pila e la coda.
In alcuni casi è utile disporre di strutture dati che hanno un solo punto di accesso per inserire e reperire i dati. Ad esempio, una pila di libri.
In una struttura di questo tipo i dati (i libri) vengono inseriti solo in cima (Push) e possono essere estratti solo dalla cima (Pop). Le strutture di questo tipo prendono il nome di Stack o LIFO (Last-In-First-Out).
Vediamo in dettaglio le procedure in C++ per la gestione di una pila (push, pop e visualizza):
-
-
Titolo: pila (0 click)
Etichetta:
Filename: pila.pdf
Dimensione: 36 KB
La coda è una lista dinamica in cui l’inserimento di nuovi elementi (push) viene effettuato ad un estremo (fondo o rear) e l’estrazione degli elementi (pop) all’altro estremo (testa o front). La coda detta anche queue realizza il principio FIFO (First-In-First-Out) perché gli elem
enti possono essere estratti solo nell’ordine in cui sono stati inseriti, così come avviene in una coda di auto in un garage dotato di un solo ingresso e una sola uscita.
Vediamo in dettaglio le procedure in C++ per la gestione di una coda (push, pop e visualizza):
-
-
Titolo: coda (0 click)
Etichetta:
Filename: coda.pdf
Dimensione: 36 KB
Terminiamo con una procedura che utlizza una lista e l’inserimento degli elementi avviente in modo ordinato crescente:
-
-
Titolo: lista_ordinata (0 click)
Etichetta:
Filename: lista_ordinata.pdf
Dimensione: 34 KB