Crea sito

Home » Senza categoria » Le liste dinamiche

Le liste dinamiche

È 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):

pila
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 elementi 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): 

coda
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:

lista_ordinata
Titolo: lista_ordinata (0 click)
Etichetta:
Filename: lista_ordinata.pdf
Dimensione: 34 KB

Archivi

Ottobre: 2019
L M M G V S D
« Gen    
 123456
78910111213
14151617181920
21222324252627
28293031