Newsgroup: it.comp.lang.pascal
Titolo: Uso della variabili puntantore - URGENTE

Qualcuno per favore sa se esiste, online, un qualche documento che
spieghi l'uso dei puntatori (nel caso specifico per gestire strutture
ad albero, ma mi sarebbe molto utile anche una spiegazione in
generale). L'ambietne sarebbe il Borland TP 6.0, ma la cosa non č poi
cosě importante. Devo assolutamente imparare ad usarle entro Martedě,
quindi AIUTO!!!

quindi AIUTO!!!
Vedro' di fare del mio meglio per spiegarti cosa sono i puntatori :
Una variabile puntatore e' una variabile che contiene un indirizzo di
memoria.
Si dice, cioe', che esso "punta" alla prima locazione di memoria dove
e' presente l'oggetto puntato.
In Pascal un puntatore viene dichiarato mediante il carattere ^
anteposto al tipo di oggetto puntato.
Un esempio e' il seguente :
var int_ptr = ^integer ;
oppure
type  str20 = string [20] ;
var   str20_ptr = ^str20 ;
o ancora 
type mio_record = record
                    nome : string [20] ;
                    cognome : string [20] ;
                  end ;
var mio_puntatore = ^mio_record ;
La memoria "puntata" da un puntatore puo' appartenere a due tipi
diversi di locazioni, quelle appartenenti al segmento dati del
programma e quelle della memoria heap.
(questa definizione non e' precisa, ma non e' sbagliata)
La memoria heap, in parole semplici, e' tutta la memoria disponibile
al momento del lancio del programma.
In TP e' possibile venire a conoscenza di quanta memoria heap e'
disponibile al programma mediante la funzione "MemAvail".
Il numero restituito e' espresso in byte.
Ora, un esempio di utilizzo di un puntatore per puntare alla memoria
del segmento dati del programma e' il seguente :
var int_p = ^integer ;
    i : integer ;
begin
  i := 10 ;
  int_p := addr ( i ) ;
  int_p^ := 5 ;
end.
i, in quanto variabile di programma, appartiene al segmento dati dello
stesso.
La funzione addr ( i ) restituisce l'indirizzo dell'oggetto i che
viene appunto depositato in int_p.
La scrittura int_p^, invece, significa "l'oggetto puntato da int_p".
In questo modo la scrittura 
int_p^ := 5 ;
e' equivalente a 
i := 5 ;
in quanto int_p punta per l'appunto ad i e quindi l'oggetto puntato da
int_p e' proprio i.
Ora, le variabili puntatore trovano il loro vero utilizzo con la
memoria heap, in quanto ogni implementazione di linguaggio Pascal,
mette a disposizione routine apposite per "prendere in prestito"
dall'heap un "pezzo" di memoria, utilizzarlo per il proprio fine e
"restituirlo" al sistema.
L'operazione di "prestito" viene chiamata "allocazione" e il "pezzo"
di memoria allocato viene chiamato "blocco".
Generalmente un'operazione di allocazione deve conoscere "quanta"
memoria allocare, quantita' che viene espressa come numero di byte.
L'operazione di "restituzione" viene chiamata "deallocazione".
L'operazione di deallocazione, generalmente, non necessita di
conoscere quanta memoria deallocare, in quanto la precedente routine
di allocazione ha preso in prestito un po' piu' della memoria
richiesta, sufficiente per memorizzare informazioni circa l'avvenuta
occupazione del blocco e la sua misura in byte.
Sara' quindi possibile deallocare l'intero blocco semplicemente
leggendo le informazioni memorizzate all'inizio di esso.
La memoria in un sistema tipo PC e' strutturata in modo sequenziale,
cioe' una locazione di seguito all'altra ed e' probabile che in
seguito a molte allocazioni e deallocazioni, la memoria risulti
"frammentata".
Mi spiego : supponiamo che nel nostro minuscolo sistema ci siano 100
byte di memoria disponibile.
Per intenderci, MemAvail restituisce 100.
Supponiamo di allocarne prima 14, poi 63, poi 10.
Dopo la prima allocazione, MemAvail avra' restituito 100-14 = 86, dopo
la seconda 86-63 = 23 e dopo la terza 23-10 = 13.
Ora, supponendo che i tre blocchi allocati siano stati scelti l'uno di
seguito all'altro, come e' presumibile, si avra' la seguente
situazione :
A 
B
C
(13)
dove con A identifico il blocco di 14 byte, con B quello di 63 e con C
quello di 10.
Con (13) la memoria non allocata (ovvero disponibile).
A questo punto supponiamo di non voler piu' utilizzare il blocco B e
quindi lo deallochiamo.
La memoria deallocata ritorna al sistema come memoria disponibile per
una successiva allocazione.
Si avra' la seguente situazione :
A
(63)
C
(13)
Osservazione : sebbene adesso MemAvail restituisca 76 (63+13), non e'
possibile allocare un blocco di 70 byte.
Il motivo e' chiaro : un blocco e' una sequenza di byte contigui e non
e' possibile allocarne i primi 63 in una zona e i restanti 7
nell'altra.
La funzione di TP "MaxAvail" restituisce il massimo blocco allocabile.
In questo caso restituisce 63.
Le procedure adibite all'allocazione di memoria sono in TP New e
GetMem alle quali corrispondono rispettivamente le procedure Dispose e
FreeMem per la deallocazione.
New e' utile quando il compilatore conosce gia' quanta memoria
allocare.
GetMem quando lo si vuole specificare.
Ad esempio, se si scrive : 
var i : ^integer ;
    a : integer ;
begin
  a := 5 ;
  New ( i ) ;
  i^ := a ;
end.
Il compilatore sa gia' che la quantita' di memoria da allocare e'
sizeof ( i ) che sul mio sistema equivale a 2 byte.
Se invece si scrive :
type str20 = string [20] ;
var i : ^str20 ;
begin
  GetMem ( i, 10 ) ;
  i^ := 'andrea' ;
end.
si fa in modo che la memoria allocata per contenere l'oggetto puntato,
anche se si prevede che l'oggetto puntato possa raggiungere 20 byte
come lunghezza, sia solo di 10 byte, perche' tanti ne servono
evidentemente.
Esiste in Pascal, e quindi anche in TP, la possibilita' di assegnare
ad un puntatore il valore "nullo", ovvero di non farlo puntare a
nessuna locazione.
Questo valore si chiama "nil".
scrivere 
var a : ^integer ;
begin
  a := nil ;
end.
e' legale ed equivale a dire "a non punta a nessuna locazione".
E' bene sapere, pero', che questa condizione non e' affatto implicita
dopo la dichiarazione del puntatore e che esso va sempre
inizializzato, per evitare crolli del sistema, a locazioni di memoria
che possano contenere dati senza produrre problemi.
Scrivere, cioe' :
var a : ^integer ;
begin
  a^ := 4 ;
end.
e' errato, in quanto a non viene inizializzato e potrebbe persino
andarsi a sovrascrivere una parte del sistema operativo, causando un
errore di protezione sui sistemi protetti e, ancora peggio, un blocco
del sistema su quelli che non lo sono.
L'operazione corretta e' 
var a : ^integer ;
begin
  new ( a ) ;
  a^ := 4 ;
  dispose ( a ) ;
end.
In questo modo, a viene inizializzato tramite new() e viene deallocata
la sua memoria puntata tramite dispose() alla fine dell'elaborazione .
Una delle applicazioni molto utili dei puntatori e' quella, appunto,
dell'implementazione di alberi binari.
Un albero binario e' una struttura dati ricorsiva, nel senso che esso
puo' essere definito in funzione di se' stesso.
Un albero binario e' un puntatore a un record contenente dati generici
(chiamato "nodo") ed almeno due puntatori (ramo sinistro e ramo
destro), entrambi alberi binari o nulli.
Ad esempio :
type p_nodo_albero = ^nodo_albero ; 
     nodo_albero = record
                     dato : integer ;
                     ramo_sinistro : p_nodo_albero ;
                     ramo_destro   : p_nodo_albero ;
                   end ;
     albero = p_nodo_albero ;
Il modo in cui sono disposti i nodi nell'albero puo' dipendere da
tanti fattori, ad esempio da una relazione d'ordine.
Ad esempio si puo' affermare che un albero binario che contenga interi
possa ospitare, per ogni nodo, sul ramo sinistro un albero binario
contenente i valori minori del valore dello stesso nodo e su quello
destro i valori maggiori.
Essendo una struttura dati ricorsiva e' indispensabile trattarla per
mezzo della ricorsivita' offerta dal pascal (e dal TP).
Una possibile implementazione della routine di inserimento di un nuovo
valore in un albero definito come sopra puo' essere :
procedure inserimento ( x : integer ; var a : albero ) 
begin
  if ( a = NIL ) then
  begin
    new ( a ) ;
    a^.dato := x ;
    a^.ramo_sinistro := NIL ;
    a^.ramo_destro := NIL ;
  end
  else
  if ( x < a^.dato ) then 
     inserimento ( x, a^.ramo_sinistro ) 
  else
     inserimento ( x, a^.ramo_destro ); 
end ;
La navigazione nell'albero puo' seguire lo stesso principio.
 

Vedro' di fare del mio meglio per spiegarti cosa sono i puntatori [...]
Grazie davvero. Anche a nome del resto della mia classe alla quale ho
prontamente distribuito il tuo mex... sappi che sei riuscito a fare in
296 righe quel che il prof di info che ci è capitato quest'anno (un
folle) in 14 ore di lezione non ha potuto.
Cose che capitano al liceo quando a certi laureati in matematica viene
data l'abilitazione ad insegnare informatica :(