10 : Allocazione dinamica della memoria Vers . 9.0 – Ottobre 2024
IMPLEMENTAZIONE DELLE STRUTTURE DATI ASTRATTE LINEARI
A livello di codifica sono possibili due strategie implementative per le struttura dati astratte ( ADT ) descritte precedentemente :
a ) attraverso strutture dati SEQUENZIALI , AD ALLOCAZIONE STATICA ED AD ACCESSO DIRETTO del linguaggio di programmazione scelto ( ossia attraverso array o vettore );
b ) attraverso strutture dati NON SEQUENZIALI , AD ALLOCAZIONE DINAMICA ED AD ACCESSO SEQUENZIALE del linguaggio di programmazione scelto ( ossia attraverso le cosiddette liste linkate );
Limiti dell ’ utilizzo di strutture dati SEQUENZIALI , AD ALLOCAZIONE STATICA ED AD ACCESSO DIRETTO
L ’ allocazione statica della memoria presenta senza dubbio molti VANTAGGI tra i quali segnaliamo :
1 ) semplicità degli algoritmi che devono gestire la struttura dati così allocata ; 2 ) accesso diretto ai nodi ( poiché vengono utilizzati gli array o vettori ).
Nonostante ciò tale metodo di memorizzazione possiede degli innegabili SVANTAGGI in quanto è poco flessibile per quanto riguarda :
a ) occupazione di memoria : gli array in genere sono sovradimensionati non potendo stimare a priori la dimensione del problema ;
b ) velocità in fase di esecuzione : gli array sono strutture rigide e la loro gestione richiede a volte tempi che non sono accettabili ;
c ) linearità della soluzione : talvolta la soluzione offerta dall ’ allocazione statica della memoria per questo tipo di strutture dati fornisce un risultato negativo sia in relazione alla bontà dell ’ algoritmo , sia dal punto di vista del rispetto dei criteri generali della programmazione .
VANTAGGI nell ’ utilizzo di strutture dati NON SEQUENZIALI , AD ALLOCAZIONE DINAMICA ED AD ACCESSO SEQUENZIALE
L ’ utilizzo di strutture dati concatenate e dinamiche dette LISTE LINKATE ( al posto di quelle sequenziali , statiche ad accesso diretto ) permettono di gestire con molta più semplicità numerose operazioni di inserimento e di cancellazione .
Grazie al loro utilizzo non è più necessario neanche definire a priori la dimensione massima occupata in memoria dalla struttura dati in quanto esse hanno la caratteristica di essere dinamiche , ossia di potere modificare la dimensione occupata in memoria nel corso dell ’ esecuzione del programma che le utilizza .
LA LISTA LINKATA
DEF . La lista ( semplicemente ) concatenata o linkata è la struttura dati di base ad allocazione dinamica . Essa è formata da una successione di nodi che occupano in memoria posizioni qualsiasi . Ciascun nodo è legato o collegato o linkato al suo successivo mediante un puntatore .
In una lista linkata ogni nodo P ( quindi tutti i nodi hanno lo stesso formato ) possiamo immaginarlo formato da un tipo di dati strutturato ( RECORD ) costituito da due campi :
- un campo informativo ( che chiameremo Info ) che può contenere qualsiasi tipo di dato ( semplice o strutturato a sua volta );
- un campo puntatore ( che chiameremo pNext ) che contiene l ’ indirizzo di memoria in cui è possibile reperire il nodo successivo .
Autore : Rio Chierego ( email : riochierego @ libero . it - sito web : www . riochierego . it ) Pag . 40