Strutture dati dinamiche

Pagina 1

Strutture dati dinamiche - Liste concatenate - Pile -> LIFO (last in first out) - Code -> FIFO (first in first out) - Alberi binari: gestione dati in algoritmi complessi Liste Concatenate Formata da elementi creati dinamicamente il cui numero cambia durante l’esecuzione. Ogni elemento, o nodo, contiene un puntatore all’elemento successivo, mentre il primo elemento, chiamato testa, contiene il puntatore alla lista. L’ultimo elemento contiene come puntatore all’elemento successivo il valore NULL per indicare che è la fine della lista. La lista è una struttura dati ricorsiva che viene definita utilizzando anche un puntatore a sé stesso. Per definire delle strutture dati ricorsive si usa il TAG, ovvero mette il nome dopo struct. struct nodo { int dato; struct nodo *next; }; struct nodo *newnodo; Si può dichiarare un nodo anche attraverso un tipodato (typedef): typedef struct N { int dato; struct N *next; } nodo; da ciò posso fare operazioni del tipo: typedef nodo* Ptrnodo; nodo n1,n2; La possibilità di creare un nuovo nodo per la lista in run-time (ovvero durante l’esecuzione), è offerta dalla funzione malloc (memory alloc) che riceve come parametro una dimensione in bit (dimensione da riservare nella memoria dinamica del calcolatore) e ritorna un puntatore a tale spazio. Utile a questo scopo è la funzione sizeof, che riceve in ingresso un tipo di dato e ne ritorna la corrispondente dimensione in bit. L’unione di queste due funzioni permette la giusta allocazione in memoria del nodo per la lista. Definito Ptrnodo un puntatore ad un nodo, l’allocazione in memoria la eseguiamo nel seguente modo: Ptrnodo ptr = (Ptrnodo) malloc(sizeof(nodo)); Dopo questa istruzione la variabile ptr conterrà l’indirizzo di memoria del nodo appena creato; tramite ptr è possibile quindi andare a…