Per studiare queste strutture dobbiamo sapere usare i puntatori, giacchè le strutture dati dinamiche sono basate sull’utilizzo di questi.

Sono definite dinamiche perchè posso allocare e deallocare gli elementi man mano che servono, i loro collegamenti possono cambiare durante l’esecuzione del programma.

Vengono definite astratte perchè sono strutture la cui realizzazione interna è nascosta al main attraverso funzioni di libreria che permettono di operare sulla struttura, inserendo o estraendo dati, senza toccarla direttamente.

Le strutture dati dinamiche possono adattarsi a qualsiasi situazione.

La lista è un insieme di nodi collegati linearmente. I nodi sono divisi in due parti, da una parte contengono il dato e dall’altra un puntatore all’elemento successivo della lista.

testa

Un nodo funge da testa della lista, e da questo si accede a tutti gli altri nodi della lista. Conoscendo un nodo interno alla lista, è possibile accedere ai nodi successivi, ma non a quelli precedenti.

DATO PUNTATORE NULL

Se la lista è vuota, la testa punterà a NULL. testa

La lista è strutturata nella seguente maniera:

typedef struct nodo{

int dato;

struct nodo * next;

}Nodo;

Con questo creo il primo nodo.

Il dato è un valore intero e next è un puntatore alla struttura nodo.

NULL

Ci sono diverse operazioni che si possono effettuare sulle liste: L’inserimento in testa e la cancellazione

L’inserimento in mezzo e la cancellazione

L’inserimento in coda e la cancellazione

La ricerca di nodi

Nel blog potete trovare alcuni esempi di come effettuare queste operazioni.

I nodi contengono un puntatore sia verso il nodo precedente che verso quello successivo.

datopunt punt

Ogni nodo contiene due (o più) puntatori ad altri nodi che sono detti suoi "figli”: dato un nodo, è possibile accedere a tutti i suoi discendenti.

Un albero non deve avere cicli, un nodo non può ritornare al nodo di partenza

Ciascun nodo deve essere figlio di un solo padre.

Ogni albero è formato da una radice, nodi intermedi e foglie.

LIVELLO 1

LIVELLO 2

LIVELLO 3

Nodi intermedi

Foglie

La radice viene generata in questa maniera:

typedef struct NodoAlbero{

int radice;

struct NodoAlbero * sx, *dx;

} nodo;