CAPITOLO 16
description
Transcript of CAPITOLO 16
![Page 1: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/1.jpg)
![Page 2: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/2.jpg)
I PUNTATORI
Allocazione StaticaDato un blocco ogni variabile è allocata in memoria quando inizia l’elaborazione del blocco e deallocata quando l’elaborazione di tutto il blocco termina.
Allocazione DinamicaQuando ogni variabile è allocata o deallocata in memoria durante l’elaborazione del blocco.
Il puntatoreUn puntatore è una variabile il cui valore rappresenta un indirizzo di memoria. Esso serve per creare o eliminare una variabile dinamica.
Variabile dinamicaE’ una variabile alla quale si assegna spazio in memoria durante l’elaborazione di un blocco.
![Page 3: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/3.jpg)
identificatore type= ^ESEMPIO
TYPE DataType = RECORD
Giorno:1..31;Mese:1..12;
Anno:integer END;DataPunt=^DateType;IntPunt=^integer;
VAROggi: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
![Page 4: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/4.jpg)
PuntatoriNome Type
DataPunt=^ Record
IntPunt=^ Integer……………...
……………...
Run-TimeHeap
Oggi
ABC
……………...
NomeVariabile
Oggi^
A^B^C^
……………...
Memoria
……………...
Indirizzidi memoria
00010101………….………….………….
………….
………….………….
10101011
TYPE DataType = RECORD
Giorno:1..31;Mese:1..12;
Anno:integer END;DataPunt=^DateType;IntPunt=^integer;
VAROggi:DataPunt;A,B:IntPunt;Domani:DataType;
![Page 5: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/5.jpg)
Per assegnare un indirizzo a una variabile puntatore si usa la procedura new:es. new(Oggi)
TYPE DataType = RECORD
Giorno:1..31;Mese:1..12;
Anno:integer END;DataPunt=^DateType;IntPunt=^integer;
VAROggi:DataPunt;A,B:IntPunt;
Spazio di memoria assegnatoPrima di fare la chiamata new(Oggi)Oggi^ ?
Dopo la chiamata new(Oggi)Oggi^ ? ? ?
Per assegnare dei valori alla variabile dinamica Oggi
new(Oggi)Oggi^ ? ? ?
21 11 2000
read(Oggi^.Giorno, Oggi^.Mese, Oggi^.Anno)Enter 21 11 2000
Oggi^ .Giorno .Mese .Anno
![Page 6: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/6.jpg)
TYPE DateType = RECORD
Giorno:1..31;Mese:1..12;
Anno:integer END;
DataPunt=^DateType;IntPunt=^integer;VAROggi: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
21 11 2000Oggi^
5A^
7B^
![Page 7: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/7.jpg)
Gli unici operatori che si applicano alle variabili puntatori sono:
operatore di assegnazione :=
operatori booleani = <>
TYPE DataType = RECORD
Giorno:1..31;Mese:1..12;
Anno:integer END;DataPunt=^DateType;IntPunt=^integer;
VAROggi:DataPunt;A,B,C:IntPunt;Domani:DataType;
L’operazione C :=B
12C^
7B^
X garbage
7L’operazione A^ :=B^
5A^
7B^
12C^
![Page 8: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/8.jpg)
TYPEIntPunt=^integer;
VARA,B,C:IntPunt;
7A^
7B^
A^ : =5B^ := 7A^ :=B^IF (A^ = B^) AND (A <> B) THEN writeln(‘ I puntatori sono diversi ma i valori delle variabili puntate sono eguali’)
5A^
7B^
A^ : =5B^ := 7A :=BIF (A^ = B^) AND (A <> B) THEN
writeln(‘ I puntatori sono eguali e anche i valori delle variabili puntate sono eguali’)
![Page 9: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/9.jpg)
TYPEIntPunt=^integer;
VARA,B,C:IntPunt;
C :=BIF (C = B) THEN writeln(‘ I puntatori puntano alla stessa variabile’)
12C^
7B^
X garbage
dispose(C)C :=BIF (C = B) THEN writeln(‘ I puntatori puntano alla stessa variabile’)
7B^
C^ ?
7B^
C^
Come eliminare la spazzatura
![Page 10: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/10.jpg)
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. A B C D
![Page 11: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/11.jpg)
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.
Si possono fare test per vedere se il puntatore è libero di essere associato ad una variabile dinamica.
Attenzione NIL non è assegnato per default.
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.
Attenzione se a un puntatore è assegnato NIL, es. D:= NIL, non è possibile fare dispose(D).
![Page 12: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/12.jpg)
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
![Page 13: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/13.jpg)
PROGRAM ArrayPuntatori(input, output, Semester); CONSTMaxStu=100;TotaleProve=100;TYPEStringa4 = 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;
StuRecNome Nascita Matricola AnnoCorso Risultati Media
![Page 14: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/14.jpg)
PROBLEMALeggere 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.
1
mid
TotalStu
1
mid
TotalStu
ByName ByMat
050/714 21 22 23 30 27Abate Carlo 30/11/76 2000 25
050/734 28 22 28 30 27Carlini Anna 30/11/72 1999 27
050/514 30 21 23 30 27Zucchi Ugo 03/01/75 2000 24
![Page 15: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/15.jpg)
PROGRAM ArrayPuntatori(input, output, Semester); CONSTMaxStu=100;TotaleProve=100;TYPEStringa4 = 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;
PuntatoriNome Type
StuPointer=^ StuRec
PointArr=^ Array OF
Run-TimeHeap
By Name
ByMat
NomeVariabile
By Name ^
ByMat ^
……………...
Memoria
……………...
Indirizzidi memoria
00010101………….………….………….
………….
StuFile=FILE OF StuRec;StuPointer=^StuRec;PointArr=ARRAY[0.. MaxStu] OF StuPointer;VAR
Semester: StuFile; ByName, ByMat: PointArr;TotalStu:integer;
Matr:Stringa10;
![Page 16: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/16.jpg)
PROCEDURE OrganizzaDati(VAR ByName,ByMat:PointerArray;VAR TotalStu:integer; VAR StuOnFile:StuFile);
VAR AStu:StuPointer;BEGINreset(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;
PROCEDURE Insert(NewElement:StuPointer; Candidate: integer; VAR ByMatP:PointerArray);BEGINWHILE (ByMatP[Candidate-1]^.Matricola > NewElement^.Matricola ) DOBEGIN
ByMatP[Candidate]:= ByMatP[Candidate-1]; Candidate:=Candidate-1
END;ByMatP[Candidate]:=NewElementEND;
![Page 17: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/17.jpg)
FUNCTION CercaStudente(VAR ByMatP: PointerArray;Numero:Stringa10; Lo,Hi:integer): StuPointer;
VARJ: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;
![Page 18: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/18.jpg)
{******************** MAIN ******************}
BEGINassign(semester,'a:\probe.dat');OrganizzaDati(ByName,ByMat, TotalStu, Semester);readln;write('Dammi la matricola cercata: ');readln(Matr);Risultati(CercaStudente(ByMat,Matr,1,TotalStu));readlnEND.
![Page 19: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/19.jpg)
Esercizio
Scrivere il programma completo per la gestione dei records attraverso array di puntatori ordinati per Nome, Matricola, Data di Nascita, Media.
![Page 20: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/20.jpg)
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.
![Page 21: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/21.jpg)
PROGRAM TestChiamatePuntatori;TYPEIntP=^integer;VARAnIntP:IntP;PROCEDURE ValCall(XP:IntP);BEGIN
XP^:=7;END;PROCEDURE VarCall(VAR XP:IntP);BEGIN
XP^:=7;END;
BEGINnew(AnIntP);AnIntP^:=5;ValCall(AnIntP);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^.
BEGINnew(AnIntP);AnIntP^:=5;ValCallVar(AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
Output= 7
Il valore resta lo stesso essendo la chiamata precedente equivalente ad una chiamata per VAR su XP^.
![Page 22: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/22.jpg)
PROGRAM TestChiamatePuntatori;TYPEIntP=^integer;VARAnIntP:IntP;PROCEDURE ValCall(XP:IntP);BEGINdispose(XP);END;PROCEDURE VarCall (VAR XP:IntP);BEGINdispose(XP);END;
BEGINnew(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.
BEGINnew(AnIntP);AnIntP^:=5;VarCall (AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
Output= non predicibile Come prima.
![Page 23: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/23.jpg)
PROGRAM TestChiamatePuntatori;TYPEIntP=^integer;VARAnIntP:IntP;PROCEDURE ValCall(XP:IntP);BEGINdispose(XP);new(XP);END;PROCEDURE VarCall (VAR XP:IntP);BEGINdispose(XP);new(XP);END;
BEGINnew(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. Inoltre la memoria allocata da new diventa spazzatura non appena si esce dal blocco.
BEGINnew(AnIntP);AnIntP^:=5;VarCall (AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
Output= non predicibile Come prima. Solo che ora non si crea spazzatura.
![Page 24: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/24.jpg)
PROGRAM TestChiamatePuntatori;TYPEIntP=^integer;VARAnIntP:IntP;PROCEDURE ValCall(XP:IntP);BEGINXP:=NIL;END;PROCEDURE VarCall (VAR XP:IntP);BEGINXP:=NIL;END;
BEGINnew(AnIntP);AnIntP^:=5;ValCall(AnIntP);writeln(‘Output= ‘,AnIntp^:1);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.
BEGINnew(AnIntP);AnIntP^:=5;VarCall (AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
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.
![Page 25: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/25.jpg)
PROGRAM TestChiamatePuntatori;TYPEIntP=^integer;VARAnIntP:IntP;PROCEDURE ValCall(XP:IntP);BEGINnew(XP);XP^:=7writeln(‘OutputCall ‘,XP^:1)END;PROCEDURE VarCall (VAR XP:IntP);BEGINnew(XP);XP^:=7writeln (‘OutputCall ‘, XP^:1)END;
BEGINnew(AnIntP);AnIntP^:=5;ValCall(AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
OutputCall=7Output= 5 Qui si alloca un nuovo indirizzo per la variabile che prima aveva indirizzo AnInt. L’effetto della assegnazione XP:=7 è ristretto solo agli scopi della procedura ValCall.Ora XP e AnIntP rappresentano due diverse variabili puntatore, quando usciamo dalla procedura AnIntP^ vale sempre 5, mentre il valore di XP^ è perduto come spazzatura.
BEGINnew(AnIntP);AnIntP^:=5;VarCall (AnIntP);writeln(‘Output= ‘,AnIntp^:1);END.
OutputCall=7Output= 7 L’istruzione new(XP) fa sì che AnIntP diventa spazzatura. Quindi il valore 7 è mostrato due volte poiché tramite la Call VAR restituisce detto valore a AnIntp^.
![Page 26: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/26.jpg)
ESERCIZI SULLA RICORSIONE
![Page 27: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/27.jpg)
Sia data una stringa di lunghezza N e una sottostringa di lunghezza Kcon K sottomultiplo di N. Scrivere una funzione ricorsiva che conti tuttele sottostringhe di N che non sono uguali a K.
PROGRAM ESERCIZIO3 (input, output);TYPEString30=STRING[30];VARCarat:char;S1: String30;S2: String30;M1,M2,Numstr,C:integer;
{*********** MAIN *********}BEGINS1:='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))+1END;
![Page 28: CAPITOLO 16](https://reader035.fdocumenti.com/reader035/viewer/2022062409/5681512f550346895dbf49ef/html5/thumbnails/28.jpg)
PROGRAM Esercizio4(output);CONST MaxSucc=50;TYPESuccNoArr=ARRAY[0..MaxSucc] OF real;VARSuccNos:SuccNoArr;VARNo,I:integer;K:real;
PROCEDURE SetSuccNo(N:integer; VAR SuccNos:SuccNoArr);{ritorna l'N-esimo valore della successione}BEGINIF 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]; ENDEND;
{MAIN}BEGINwrite(' Dammi N ');readln(No);SetSuccNo(No+1,SuccNos);K:=SuccNos[No+1]*SuccNos[No-1]
-2*SuccNos[No]* SuccNos[No];writeln;writeln('K= ',K:20:0);readlnEND.
Sia data la successione:a0=0a1=1a2=1a3=2an= an-1+ an-2* an-3 - an-4
Scrivere una PROCEDURA ricorsiva che, assegnato un N, calcoli il numero Kdato da: K=an+1 *an-1 - 2*a2
n