Post on 07-Jul-2015
description
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;