I PUNTATORI
Allocazione Statica
Dato un blocco ogni variabile è allocata in memoria quando inizia
l’elaborazione del blocco e deallocata quando l’elaborazione di
tutto il blocco termina.
Allocazione Dinamica
Quando ogni variabile è allocata o deallocata in memoria durante
l’elaborazione del blocco.
Variabile dinamica
E’ una variabile alla quale si assegna spazio in memoria durante
l’elaborazione di un blocco.
Il puntatore
Un puntatore è una variabile il cui valore rappresenta un
indirizzo di memoria. Esso serve per creare o eliminare una
variabile dinamica.
identificatore
=
^
type
ESEMPIO
TYPE
DataType = RECORD
Giorno:1..31;
Mese:1..12;
Anno:integer
END;
DataPunt=^DateType;
IntPunt=^integer;
VAR
Oggi:DataPunt;
A,B:IntPunt;
Domani:DataType;
Si noti che la variabile Oggi, così come la variabile
IntPunt, non assume i tre valori del record, o il
valore di intero, a cui fa riferimento ma solo quello
dell’indirizzo di memoria a partire dal quale vi sono
eventualmente i valori
Variabile Anonima: una variabile alla quale si accede solo tramite un puntatore
Variabile Nominata: una variabile alla quale si accede tramite un nome
Indirizzi
di memoria
Puntatori
Nome
Type
Run-Time
Heap
00010101
………….
………….
………….
DataPunt=^ Record
Oggi
Oggi^
IntPunt=^ Integer
……………...
A
B
C
A^
B^
C^
………….
……………...
10101011
TYPE
DataType = RECORD
Giorno:1..31;
Mese:1..12;
Anno:integer
END;
DataPunt=^DateType;
IntPunt=^integer;
VAR
Oggi:DataPunt;
A,B:IntPunt;
Domani:DataType;
Memoria
……………...
……………...
………….
………….
Nome
Variabile
……………...
Per assegnare un indirizzo a una variabile puntatore si usa la procedura new:
es. new(Oggi)
Spazio di memoria assegnato
Prima di fare la chiamata new(Oggi)
Oggi^  ?
Dopo la chiamata new(Oggi)
Oggi^ 
?
?
?
TYPE
Per assegnare dei valori alla variabile dinamica Oggi
new(Oggi)
Oggi^ 
?
?
?
read(Oggi^.Giorno, Oggi^.Mese, Oggi^.Anno)
Enter 21 11 2000
Oggi^ 
21
.Giorno
11
.Mese
2000
.Anno
DataType = RECORD
Giorno:1..31;
Mese:1..12;
Anno:integer
END;
DataPunt=^DateType;
IntPunt=^integer;
VAR
Oggi:DataPunt;
A,B:IntPunt;
new(A);
new(B);
new(Oggi);
A^:=5;
B^:=7;
write(‘Dammi la data (giorno mese anno): ‘);
WITH Oggi^ DO
readln(Giorno, Mese, Anno)
Dammi la data (giorno mese anno) : 21 11 2000
Oggi^ 
21
11
A^ 
5
B^ 
7
2000
TYPE
DateType = RECORD
Giorno:1..31;
Mese:1..12;
Anno:integer
END;
DataPunt=^DateType;
IntPunt=^integer;
VAR
Oggi:DataPunt;
A,B:IntPunt;
Gli unici operatori che si applicano alle variabili puntatori sono:
operatore di assegnazione
:=
operatori booleani
=
L’operazione
A^ :=B^
A^ 
7
5
B^ 
7
C^ 
12
L’operazione
C^
B^
<>
TYPE
DataType = RECORD
Giorno:1..31;
Mese:1..12;
Anno:integer
END;
DataPunt=^DateType;
IntPunt=^integer;
VAR
Oggi:DataPunt;
A,B,C:IntPunt;
Domani:DataType;
C :=B
X
12
7
garbage
A^ : =5
B^ := 7
A^ :=B^
IF (A^ = B^) AND (A <> B) THEN
writeln(‘ I puntatori sono diversi ma i valori delle variabili puntate sono eguali’)
A^ 
7
B^ 
7
TYPE
IntPunt=^integer;
A^ : =5
B^ := 7
A :=B
IF (A^ = B^) AND (A <> B) THEN
VAR
A,B,C:IntPunt;
writeln(‘ I puntatori sono eguali e anche i valori delle variabili puntate sono eguali’)
A^ 
5
B^
7
Come eliminare la spazzatura
TYPE
IntPunt=^integer;
VAR
A,B,C:IntPunt;
C :=B
IF (C = B) THEN
writeln(‘ I puntatori puntano alla stessa variabile’)
C^
X
B^
garbage
12
7
dispose(C)
C :=B
IF (C = B) THEN
writeln(‘ I puntatori puntano alla stessa variabile’)
B^
C^
7
?
B^
C^
7
In memoria esiste una speciale area detta run-time-heap dove sono allocate le variabili
puntatore.
Nello heap ci sono le variabili puntatori create da new ad es.
ABCD
L’istruzione C:=B mostra che possiamo assegnare memoria ad un puntatore senza fare uso
di new questo ci permette di avere due puntatori che puntano alla stessa variabile dinamica,
riducendo così lo spazio di memoria usato.
Possiamo quindi scrivere
new(B);
B^:=18;
C:=B
Questa istruzione è valida solo se il puntatore C esiste.
Vi è un solo valore che una variabile puntatore può assumere e che non punta a nulla:
NIL.
Es: D:= NIL;
Questa assegnazione serve per informare che per ora la variabile puntatore non è stata
ancora associata a una variabile dinamica.
Attenzione se a un puntatore è assegnato NIL, es. D:= NIL, non è possibile fare dispose(D).
Si possono fare test per vedere se il puntatore è libero di essere associato ad una variabile
dinamica.
Attenzione NIL non è assegnato per default.
Se abbiamo allocato memoria es.
new(D);
D^:=5;
D:= NIL
resta spazzatura
bisogna invece fare come di seguito
new(D);
D^:=5;
dispose(D);
D:= NIL;
NIL non elimina la spazzatura
PROGRAM ArrayPuntatori(input, output, Semester);
CONST
MaxStu=100;
TotaleProve=100;
TYPE
Stringa4 = STRING[4];
Stringa10 = STRING[10];
Stringa25 = STRING[25];
RisultatiArray=ARRAY[1..TotaleProve] OF integer;
StuRec = RECORD
Cognome,
Nome : Stringa25;
Nascita:Stringa10;
Matricola:Stringa10;
AnnoCorso:Stringa4;
Risultati:RisultatiArray;
Media:real;
END;
StuFile=FILE OF StuRec;
StuPointer=^StuRec;
PointArr=ARRAY[0.. MaxStu] OF StuPointer;
VAR
Semester: StuFile;
ByName, ByMat: PointArr;
TotalStu:integer;
Matr:Stringa10;
StuRec
Nome Nascita
Matricola
AnnoCorso
Risultati
Media
PROBLEMA
Leggere il file Semester e realizzare due array di puntatori uno ordinato per nome
(ByName) ed uno per matricola (ByMat).
L’array ByName contiene i puntatori agli studenti ordinati per nome.
Vogliamo scrivere una funzione che faccia una ricerca di uno studente per numero di
matricola sull’array ByMat.
ByName
1
ByMat
Abate
Carlo 30/11/76 050/714 2000 21 22 23 30 27
25
Carlini
Anna 30/11/72 050/734 1999 28 22 28 30 27
27
mid
mid
TotalStu
1
Zucchi
Ugo
03/01/75 050/514 2000 30 21 23 30 27 24
TotalStu
PROGRAM ArrayPuntatori(input, output, Semester);
CONST
MaxStu=100;
TotaleProve=100;
TYPE
Stringa4 = STRING[4];
Stringa10 = STRING[10];
Stringa25 = STRING[25];
RisultatiArray=ARRAY[1..TotaleProve] OF integer;
StuRec = RECORD
StuFile=FILE OF StuRec;
Cognome,
StuPointer=^StuRec;
Nome : Stringa25;
PointArr=ARRAY[0.. MaxStu] OF StuPointer;
Nascita:Stringa10;
VAR
Matricola:Stringa10;
Semester: StuFile;
AnnoCorso:Stringa4;
ByName, ByMat: PointArr;
Risultati:RisultatiArray;
TotalStu:integer;
Media:real;
Matr:Stringa10;
END;
Indirizzi
di memoria
00010101
………….
………….
………….
………….
Puntatori
Nome
Type
StuPointer=^ StuRec
Run-Time
Heap
Nome
Variabile
By Name
By Name ^
ByMat
ByMat ^
Memoria
PointArr=^ Array OF
……………...
……………...
PROCEDURE Insert(NewElement:StuPointer; Candidate: integer; VAR ByMatP:PointerArray);
BEGIN
WHILE (ByMatP[Candidate-1]^.Matricola > NewElement^.Matricola ) DO
BEGIN
ByMatP[Candidate]:= ByMatP[Candidate-1];
Candidate:=Candidate-1
END;
ByMatP[Candidate]:=NewElement
END;
PROCEDURE OrganizzaDati(VAR ByName,ByMat:PointerArray;VAR TotalStu:integer;
VAR StuOnFile:StuFile);
VAR AStu:StuPointer;
BEGIN
reset(StuOnFile);
TotalStu := 0;
new(ByMat[0]);
ByMat[0]^.Matricola:='00000';
WHILE NOT eof(StuOnFile) DO
BEGIN
new(AStu);
read(StuOnFile, AStu^);
TotalStu := TotalStu + 1;
ByName[TotalStu] := AStu;
Insert(AStu, TotalStu, ByMat)
END;
close(StuOnFile)
END;
FUNCTION CercaStudente(VAR ByMatP: PointerArray;
Numero:Stringa10; Lo,Hi:integer): StuPointer;
VAR
J:integer;
BEGIN
IF Lo > Hi THEN
CercaStudente :=NIL
ELSE
BEGIN
J:=(Lo+Hi) DIV 2;
IF ByMatP[J]^.Matricola = Numero THEN
CercaStudente:= ByMatP[J];
ELSE
IF ByMatP[J]^.Matricola < Numero THEN
CercaStudente:= CercaStudente(ByMat, Numero, J+1,Hi)
ELSE
CercaStudente:= CercaStudente(ByMat, Numero, Lo,J-1)
END
END;
PROCEDURE Risultati(MatrCand:Stupointer);
BEGIN
writeln(Matrcand^.Cognome,' ', MatrCand^.Nome,' ', MatrCand^.Matricola);
END;
{******************** MAIN ******************}
BEGIN
assign(semester,'a:\probe.dat');
OrganizzaDati(ByName,ByMat, TotalStu, Semester);
readln;
write('Dammi la matricola cercata: ');
readln(Matr);
Risultati(CercaStudente(ByMat,Matr,1,TotalStu));
readln
END.
Esercizio
Scrivere il programma completo per la gestione dei records attraverso
array di puntatori ordinati per Nome, Matricola, Data di Nascita,
Media.
Alcuni suggerimenti sui puntatori
Per il passaggio di parametri relativi ai puntatori valgono le stesse regole che si
applicano per gli altri tipi di variabili.
Quando un puntatore è chiamato per valore viene fatta una copia locale del
suo valore, cioè dell’indirizzo.
Quando un puntatore è chiamato per variabile viene prodotto un alias locale
per il suo valore attuale, ricordando sempre che si tratta di indirizzi.
PROGRAM TestChiamatePuntatori;
TYPE
IntP=^integer;
VAR
AnIntP:IntP;
PROCEDURE ValCall(XP:IntP);
BEGIN
XP^:=7;
END;
PROCEDURE VarCall(VAR XP:IntP);
BEGIN
BEGIN
new(AnIntP);
XP^:=7;
BEGIN
AnIntP^:=5;
END;
new(AnIntP);
ValCall(AnIntP);
AnIntP^:=5;
writeln(‘Output= ‘,AnIntp^:1);
ValCallVar(AnIntP);
END.
writeln(‘Output= ‘,AnIntp^:1);
END.
Output= 7
Questo accade perché l’indirizzo passato
dalla chiamata rimane lo stesso mentre il
valore della variabile dinamica è cambiato.
Questa chiamata equivale ad una chiamata
per VAR su XP^.
Output= 7
Il valore resta lo stesso essendo la chiamata
precedente equivalente ad una chiamata per
VAR su XP^.
PROGRAM TestChiamatePuntatori;
TYPE
IntP=^integer;
VAR
AnIntP:IntP;
PROCEDURE ValCall(XP:IntP);
BEGIN
dispose(XP);
END;
PROCEDURE VarCall (VAR XP:IntP);
BEGIN
dispose(XP);
BEGIN
END;
new(AnIntP);
BEGIN
new(AnIntP);
AnIntP^:=5;
ValCall(AnIntP);
writeln(‘Output= ‘,AnIntp^:1);
END.
Output= non predicibile
Questo accade perché l’indirizzo passato
dalla chiamata viene deallocato. Poiché
questo indirizzo nel main corrisponde
anche a quello di AnInt^ il valore di
AnInt^ ora non è più predicibile.
AnIntP^:=5;
VarCall (AnIntP);
writeln(‘Output= ‘,AnIntp^:1);
END.
Output= non predicibile
Come prima.
PROGRAM TestChiamatePuntatori;
TYPE
IntP=^integer;
VAR
AnIntP:IntP;
PROCEDURE ValCall(XP:IntP);
BEGIN
dispose(XP);
new(XP);
END;
PROCEDURE VarCall (VAR XP:IntP);
BEGIN
BEGIN
BEGIN
new(AnIntP);
dispose(XP);
new(AnIntP);
AnIntP^:=5;
new(XP);
AnIntP^:=5;
ValCall(AnIntP);
END;
VarCall (AnIntP);
writeln(‘Output= ‘,AnIntp^:1);
writeln(‘Output= ‘,AnIntp^:1);
END.
END.
Output= non predicibile
Questo accade perché l’indirizzo passato
Output= non predicibile
dalla chiamata viene deallocato. Poiché
Come prima. Solo che ora non si
questo indirizzo nel main corrisponde
crea spazzatura.
anche a quello di AnInt^ il valore di
AnInt^ ora non è più predicibile. Inoltre la
memoria allocata da new diventa
spazzatura non appena si esce dal blocco.
PROGRAM TestChiamatePuntatori;
TYPE
IntP=^integer;
VAR
AnIntP:IntP;
PROCEDURE ValCall(XP:IntP);
BEGIN
XP:=NIL;
END;
PROCEDURE VarCall (VAR XP:IntP);
BEGIN
BEGIN
XP:=NIL;
BEGIN
new(AnIntP);
END;
new(AnIntP);
AnIntP^:=5;
AnIntP^:=5;
ValCall(AnIntP);
VarCall (AnIntP);
writeln(‘Output= ‘,AnIntp^:1);
writeln(‘Output= ‘,AnIntp^:1);
END.
END.
Output= 5
Questa istruzione riassegna un valore a XP.
Ora XP e AnInt hanno valori differenti.
Quando si esce da ValCall XP è perso e
quindi AnInt resta =5. Non c’è spazzatura
perché abbiamo usato il NIL.
Output= non predicibile
Questa istruzione riassegna a AnIntP il
valore NIL. Quindi quando si esce da
VarCall AnIntP^ non è predicibile inoltre a
AnIntP è stato assegnato un nuovo valore
per cui il precedente contenente 5 è
diventato spazzatura.
PROGRAM TestChiamatePuntatori;
TYPE
IntP=^integer;
VAR
AnIntP:IntP;
PROCEDURE ValCall(XP:IntP);
BEGIN
new(XP);
XP^:=7
writeln(‘OutputCall ‘,XP^:1)
END;
BEGIN
PROCEDURE VarCall (VAR XP:IntP);
new(AnIntP);
BEGIN
BEGIN
AnIntP^:=5;
new(XP);
new(AnIntP);
ValCall(AnIntP);
XP^:=7
AnIntP^:=5;
writeln(‘Output= ‘,AnIntp^:1); writeln (‘OutputCall ‘, XP^:1)
VarCall (AnIntP);
END.
END;
writeln(‘Output= ‘,AnIntp^:1);
OutputCall=7
END.
Output= 5
OutputCall=7
Qui si alloca un nuovo indirizzo per la variabile
Output= 7
che prima aveva indirizzo AnInt. L’effetto della
L’istruzione new(XP) fa sì che AnIntP
assegnazione XP:=7 è ristretto solo agli scopi
diventa spazzatura. Quindi il valore 7 è
della procedura ValCall.
mostrato due volte poiché tramite la
Ora XP e AnIntP rappresentano due diverse
Call VAR restituisce detto valore a
variabili puntatore, quando usciamo dalla
AnIntp^.
procedura AnIntP^ vale sempre 5, mentre il
valore di XP^ è perduto come spazzatura.
ESERCIZI SULLA RICORSIONE
Sia data una stringa di lunghezza N e una sottostringa di lunghezza K
con K sottomultiplo di N. Scrivere una funzione ricorsiva che conti tutte
le sottostringhe di N che non sono uguali a K.
PROGRAM ESERCIZIO3 (input, output);
TYPE
String30=STRING[30];
VAR
Carat:char;
S1: String30;
S2: String30;
M1,M2,Numstr,C:integer;
{*********** MAIN *********}
BEGIN
S1:='ababababa';
S2:='aba';
M1:=length(S1);
M2:=length(S2);
writeln('Prima stringa
',S1);
writeln('Seconda stringa
',S2);
NumStr:=Cerca(S1,S2,M1,M1,M2,C);
Writeln(' Diverse ',Numstr,' Uguali ',C:5);
FUNCTION Cerca(VAR S1,S2:String30;i,L1,L2:integer):integer;
BEGIN
IF (i=length(S2)-1) THEN
Cerca:=0
ELSE
IF (L2=0) THEN
BEGIN
Cerca:=Cerca(S1,S2,i-1,i-1,length(S2));
END
ELSE
IF S1[L1]=S2[L2] THEN
Cerca:=Cerca(S1,S2,i,L1-1,L2-1)
ELSE
Cerca:=Cerca(S1,S2,i-1,i-1,length(S2))+1
END;
Sia data la successione:
a0=0
a1=1
a2=1
a3=2
an= an-1+ an-2* an-3 - an-4
Scrivere una PROCEDURA ricorsiva che, assegnato un
N, calcoli il numero K
dato da: K=an+1 *an-1 - 2*a2n
{MAIN}
BEGIN
PROGRAM Esercizio4(output);
write(' Dammi N ');readln(No);
CONST MaxSucc=50;
SetSuccNo(No+1,SuccNos);
TYPE
K:=SuccNos[No+1]*SuccNos[No-1]
SuccNoArr=ARRAY[0..MaxSucc] OF real;
-2*SuccNos[No]* SuccNos[No];
VAR
writeln;
SuccNos:SuccNoArr;
writeln('K= ',K:20:0);
VAR
readln
No,I:integer;
END.
K:real;
PROCEDURE SetSuccNo(N:integer; VAR SuccNos:SuccNoArr);
{ritorna l'N-esimo valore della successione}
BEGIN
IF N=3 THEN
BEGIN
SuccNos[3]:=2;
SuccNos[2]:=1;
SuccNos[1]:=1;
SuccNos[0]:=0;
END
ELSE
BEGIN
SetSuccNo(N-1,SuccNos);
SuccNos[N]:=SuccNos[N-1]+SuccNos[N-2]*SuccNos[N-3]-SuccNos[N-4];
END
END;