10 : Allocazione dinamica della memoria Vers . 9.0 – Ottobre 2024
Info ( P ) pNext ( P ) Generico Nodo P
TIPO Nodo = RECORD Info : < Tipo _ dato > pNext : PUNTATORE A Nodo
FINE RECORD
con < Tipo _ dato > semplice o strutturato a sua volta possibile anche se apparentemente sembra un riferimento circolare
Graficamente avremo :
NULL
P Testa |
P k-1 |
P k |
P k + 1 |
N . B . In una struttura dati concatenata ( o LISTA LINKATA ) la successione LOGICA dei nodi è arbitraria e non corrisponde in alcun modo a quella FISICA .
Infatti in queste strutture non è assolutamente necessario che la locazione ( fisica ) di memoria in cui si trova il nodo Pk generico debba essere successiva a quella dove si trova il nodo Pk-1 oppure debba essere precedente a quella dove si trova il nodo Pk + 1 ( come invece accadrebbe in un array ).
Il nodo Pk può essere memorizzato dovunque : l ’ importante è che il nodo Pk-1 contenga tra le sue informazioni l ’ indirizzo della locazione di memoria dove si trova il nodo Pk ( ossia “ punti al nodo ”
Pk ) e che quest ’ ultimo a sua volta contenga l ’ indirizzo della locazione di memoria dove si trova il nodo Pk + 1 ( ossia “ punti al nodo ” Pk + 1 )
Questa regola basilare va mantenuta per tutti i nodi della struttura concatenata ad eccezione dell ’ ultimo nodo della struttura che non deve puntare a nessun nodo in quanto non ha successori .
Con questa regola abbiamo visto che ogni nodo punta al successivo ( il primo al secondo , il secondo al terzo … il penultimo all ’ ultimo ) ma nessuno di essi è in grado di puntare al primo nodo della struttura .
N . B . L ’ indirizzo di memoria del primo nodo è infatti una informazione necessaria ma esterna alla struttura dati concatenata .
Esso dovrà essere memorizzato in un apposita variabile che chiameremo puntatore alla testa ( PTesta ) della struttura dati che conterrà il riferimento ( ossia il puntatore ) al primo nodo ed è “ esterno alla lista linkata ”, mentre l ’ ultimo nodo , che non ha successori , non dovrà fare riferimento ad alcunchè ( ossia “ punta a terra ” per convenzione avrà il valore NULL ).
Inoltre con le STRUTTURE DATI CONCATENATE non sarà possibile l ’ accesso diretto ma quello sequenziale che prevede la scansione di tutta la struttura a partire dal primo nodo fino ad arrivare a quello desiderato .
NOTA BENE
Le LISTE A PUNTATORI sono le strutture dati messe a disposizione dai linguaggi C e C ++ per poter implementare le LISTE LINKATE appena descritte , le cui funzionalità devono , al contrario di altri linguaggi di programmazione in cui sono già previste o built-in ( vedi PYTHON ), essere interamente sviluppate dal programmatore attraverso le apposite funzionalità per la gestione dinamica della memoria ( malloc ( ), calloc ( ), realloc ( ), etc .)
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 41