Riepilogo le strutture dati principali e le loro caratteristiche
Indice dei contenuti
Array
Struttura dati composta da un indice ordinato e un elemento.
| 0 | Elem1 |
|---|---|
| 1 | Elem2 |
| 2 | Elem3 |
| 3 | Elem4 |
| 4 | Elem5 |
Tipicamente l'indice va da zero a n-1, quindi in un array di 5 elementi gli indici sono 0, 1, 2, 3, 4.
L'array ha dimensioni fisse, quindi non è possibile aggiungere o togliere elementi; inoltre gli indici sono attribuiti automaticamente, quindi non è possibile assegnare loro dei valori.
Record
Struttura composta da un indice e un elemento.
A differenza degli array, l'indice non è ordinato, ma assegnato dalla macchina, che generalmente usa un indirizzo di memoria virtuale.
Per questo motivo, mentre due array nello stesso programma hanno un indice = 0 che si riferisce a due zone di memoria diverse - perché sono di due array diversi - nel caso dei record l'indirizzo di memoria è unico per il programma.
Questo comporta che un record possa essere inserito e eliminato, "allungando" e "accorciando" la dimensione della struttura in cui è utilizzato.
In una lista ogni elemento deve contenere il proprio indice, l'elemento e un indice che punta all'elemento successivo.
I record possono essere concatenati in vari modi, dando luogo a strutture dati diverse:
- lista semplice (solo avanti)
- lista doppia (avanti e indietro)
- lista circolare semplice e doppia
Nella lista semplice ogni elemento contiene un puntatore all'elemento successivo, per questo può essere scorsa solo in avanti.
Nella lista doppia ogni elemento contiene anche un puntatore all'elemento precedente, così è possibile scorrerla sia in avanti sia indietro.
Nella lista circolare non esiste un ultimo elemento, perché quello che "sarebbe" l'ultimo elemento è collegato con il primo, da cui la struttura circolare.
Pila / Coda
La pila e la coda sono due strutture dati in cui è possibile inserire e rimuovere un elemento in una lista ordinata.
La differenza tra pila e coda è che la pila è una lista di tipo LI-FO (last-in, first-out): come in un ascensore, l'ultimo a entrare è il primo a uscire, mentre la coda è una lista FI-FO (first-in, first-out): come alle poste, il primo che entra è il primo che esce.
Alberi
Un albero è una struttura dotata di nodi e archi; gli archi collegano tra loro nodi.
I nodi sono organizzati secondo una gerarchia, per cui esiste un nodo radice, che può avere uno o più figli.
Ogni nodo può avere più nodi figli, ma un solo nodo padre (in questo sistema la "madre" non è contemplata :-))
Se un nodo non ha figli, è chiamato foglia.
La profondità è il numero di archi che bisogna attraversare per raggiungere il nodo:
- La radice ha profondità zero
- Se un nodo ha profondità k, tutti i suoi figli hanno profondità k+1
Rappresentazioni degli alberi
Per implementare un albero è possibile scegliere tra queste strutture, tutte con pro e contro:
- vettore padri: ogni elemento contiene la propria informazione e un puntatore al padre (null se l'elemento è radice). Risalire al padre ha tempo O(1), mentre risalire ai figli O(n)
- vettore posizionale: se ogni nodo ha un numero fissato di figli, è possibile rappresentare l'albero come un semplice vettore e calcolare la posizione di un nodo tramite la sua posizione nell'array. Per esempio in un albero binario la radice è 1, i due figli sono 2, 3, i nipoti sono 4, 5, 6, 7 eccetera, e tutto questo non presenta ambiguità, poiché ogni nodo ha esattamente due figli
- rappresentazioni collegate: contengono, oltre all'informazione, un puntatore al nodo padre e un accesso ai figli di vario tipo:
- se sappiamo a priori quanti figli massimi può avere un nodo, possiamo predisporre per ogni nodo un numero di puntatori ai figli
- se NON sappiamo il numero dei figli, possiamo aggiungere un puntatore a una lista di puntatori ai figli. Questo occupa più memoria, ma permette di estendere il numero dei figli in modo illimitato
- se NON sappiamo il numero dei figli, possiamo aggiungere due puntatori per ogni nodo, uno al primo figlio e un altro al fratello successivo. La struttura è più snella dal punto di vista della memoria ma leggermente più lenta perché per accedere a un figlio è possibile dover scorrere tutta la lista di fratelli.
Heap
Gli heap sono alberi binari in cui vale sempre la proprietà che un nodo ha valore maggiore (max-heap) o minore (min-heap) di ciascuno dei suoi sotto-nodi.
Non esistono vincoli di tipo destra-sinistra, l'unico aspetto che deve essere sempre rispettato è che il padre, se esiste è maggiore del figlio e se non esiste è il nodo massimo (per max-heap; per min-heap vale il discorso contrario).