- sequenze di elementi di lunghezza non prefissata (liste nelle molte varianti...)

- alberi

- grafi ....

Il compilatore non puo' allocare memoria a compile time, perche' non sa quanta ne servira', e perche' la quantita' di memoria necessaria varia a run-time.

Si possono usare strutture statiche (es. vedremo liste con array), ma bisogna aver fissato dimensione max degli oggetti e si spreca della memoria (che viene allocata ma non utilizzata).

Soluzione migliore:

Allocazione dimanica della memoria. Memoria allocata a run-time, quanta ne serve, accresciuta o diminuita nel tempo a seconda delle necessita'.

Nei linguaggi tipo Pascal, la possibilita' di allocazione dinamica e' associata all'uso di un nuovo strumento per accedere ai dati: il puntatore.

Allocazione dinamica e puntatori

L'allocazione di una variabile è l'operazione con cui viene assegnata un'area della memoria alla variabile stessa. L'operazione inversa, detta deallocazione, consiste nel rendere di nuovo libera la memoria assegnata a una variabile in modo da poterla eventualmente usare per altri scopi. Le variabili viste finora usano i seguenti meccanismi di allocazione:

• le variabili globali usano una strategia di allocazione statica: la memoria viene assegnata alla variabile all'inizio del programma, e resta allocata fino al termine dell'esecuzione del programma stesso
• le variabili locali usano una strategia di allocazione automatica: l'allocazione avviene al momento della chiamata del sottoprogramma a cui appartengono le variabili, e la deallocazione avviene automaticamente al termine dell'esecuzione del sottoprogramma

Entrambi questi meccanismi presentano degli inconvenienti: l'allocazione statica mantiene la memoria occupata per tutta la durata del programma, anche se la variabile deve essere usata solo per una frazione di tempo ridotta; l'allocazione automatica rilascia la memoria al termine del sottoprogramma, e quindi non consente di condividere la variabile tra sottoprogrammi invocati successivamente. Per questo motivo è stato introdotto un terzo meccanismo di allocazione, detto allocazione dinamica:

• per le variabili che usano l'allocazione dinamica è il programmatore a decidere, con una opportuna istruzione, quando allocare la variabile; parimenti la deallocazione avviene in corrispondenza di una apposita istruzione di deallocazione

Per gestire un'informazione allocata dinamicamente, il programma ha bisogno di mantenere, in una variabile opportuna, un riferimento o puntatore a questa informazione, per poter localizzare nella memoria l'area riservata al momento dell'allocazione. Questo puntatore viene usato per le operazioni di allocazione e deallocazione, e consente di accedere alla variabile dopo la sua allocazione.
 

Altre operazioni definite sui puntatori

Le altre operazioni definite sui puntatori sono:

• assegnazione: assegnando a un puntatore il valore di un altro puntatore, entrambi conterranno il medesimo riferimento. In questo modo è possibile avere più puntatori che fanno riferimento a un'unica variabile dinamica. Nell'assegnazione è possibile inoltre usare la costante simbolica nil, che rappresenta un riferimento nullo, ovvero un puntatore che non contiene il riferimento di nessuna variabile
• confronto di uguaglianza (operatori e <>): due puntatori sono considerati uguali se contengono il riferimento alla medesima variabile dinamica

Si noti che nel corso di un programma un puntatore può essere usato per mantenere il riferimento a più variabili dinamiche distinte.
Gli errori più frequenti che si verificano nella gestione delle variabili dinamiche attraverso i puntatori sono:

• uso della variabile dinamica prima della sua allocazione; in questo caso, se il puntatore non era stato inizializzato con il valore nil, il programma andrà a manipolare un'area di memoria non riservata ad esso, con conseguenze imprevedibili
• uso della variabile dinamica dopo la sua deallocazione; se l'area di memoria precedentemente occupata dalla variabile è stata già riutilizzata per altri scopi, il programma può involontariamente modificare i valori di altre variabili, con conseguenze imprevedibili; per questo, dopo la deallocazione si raccomanda di inserire il valore nil nel puntatore
• non viene effettuata la deallocazione; sebbene questo errore sia meno grave dei precedenti, e in molti casi il programma funziona correttamente, la memoria viene mantenuta allocata anche quando non è più necessaria, e questo potrebbe portare alla mancanza di memoria per altre variabili .

Dichiarazioni di tipi Puntatori in Pascal

La dichiarazione di tipo:

type TPTR = ^T; (dove T per ora possiamo pensarlo un tipo statico)

dichiara un nuovo tipo puntatore TPTR dove i valori di tipo TPTR sono indirizzi di

locazioni di tipo T, locazioni atte a contenere valori di tipo T.

Sapere il tipo dell'oggetto puntato permette di sapere

- la dimensione della cella puntata (e quindi la quantita' di memoria da allocare

quando viene richiesta l'allocazione dinamica)

- quali operazioni sono lecite sull'oggetto puntato (permette verifica di

correttezza statica, consistenza dei tipi)

E' una restrizione, ma permette un maggiore controllo di correttezza.

Nella dichiarazione type TPTR = ^T;

"^" e' un costruttore di tipo (parola chiave del linguaggio), come "array", "record".

In Pascal, se ho

type TPTR = ^T;

var p1: TPTR;

p2: ^T;

risulta che p1 e p2 hanno tipi fra loro incompatibili.

Differenza tra:

var x: T; x e' una variabile di tipo T.

x e' un nome simbolico che sta per l'indirizzo di una locazione di

tipo T. Il contenuto di x e' un valore

di tipo T. La memoria per x (= la locazione di tipo T il cui

indirizzo e' x) viene allocata staticamente dal compilatore.

var p: TPTR; p e' una variabile di tipo TPTR (puntatore a T).

p e' un nome simbolico che sta per l'indirizzo di una locazione

di tipo TPTR, ovvero una locazione che puo' ospitare indirizzi di locazioni di tipo T (le quali a loro volta potranno contenere valori di tipo T).

La memoria per p (= la locazione di tipo TPTR il cui indirizzo e' p e che conterra' indirizzi di locazioni di tipo T) viene allocata staticamente dal compilatore. Le locazioni di tipo T il cui

indirizzo sara' posto in p saranno allocare dinamicamente a run-time.

L'oggetto puntato da una variabile di tipo puntatore a T e' una variabile di tipo T.

Esistono dunque due tipi di variabili:

- variabili statiche:

dichiarate con var x: T; (T tipo qualsiasi, anche puntatore)

allocate staticamente e accedute per nome.

- variabili dinamiche:

non dichiarate, allocate dinamicamente e accedute tramite puntatori.

Dichiarazione e verifica di un puntatore in C

A seconda del compilatore, la dichiarazione di un puntatore potrebbe coincidere con la sua inizializzazione implicita al valore NULL. Per essere sicuri che un puntatore sia inizializzato, lo si può fare in modo esplicito, come nell'esempio seguente:

#include <stdio.h>

main

Dovendo gestire degli oggetti dinamici, prima di utilizzare l'area di memoria a cui dovrebbe fare riferimento un puntatore, è meglio verificare che questo punti effettivamente a qualcosa.

if ( pi != NULL ) else

Introduzione

Immaginate di sognare dei mostri che vi corrono dietro, con mille teste e la bocca aperta, con la voglia di mangiarvi: è quello che succede a Roberto, programmatore ingenuo, quando la notte va a dormire dopo aver mangiato pesante, e sa che il giorno dopo dovrà fare una verifica di informatica sui puntatori...

La mattina, a scuola, con la faccia distrutta si siede in classe davanti al computer senza neanche la forza di trascinare il mouse, inizia a programmare senza sapere il perché.Ma, se ormai i record non lo terrorizzano più di tanto, quello che non riesce a capire sono i puntatori. Le domande che si pone sono: funzionano veramente? Quando conviene usarli? Perché hanno una maniera così difficile di essere usati?

Studente Roberto V. Miccoli 4° Info B