1
Variabili statiche e dinamiche
Un programma è un processo in esecuzione a cui il
sistema operativo assegna una certa zona di memoria.
Tale zona può essere suddivisa in quattro grandi blocchi:
STACK
HEAP
DATI
CODICE
Stack: zona di memoria che costituisce un’area di appoggio temporaneo
Heap: zona di memoria libera di essere utilizzata sul momento
Dati: contiene tutte le variabili e le costanti definite nel programma
Codice: contiene il codice macchina del programma
2
Il blocco stack è utilizzato principalmente dalle procedure e funzioni
richiamate dal programma; in particolare lo stack conserva le
variabili locali, i valori dei parametri formali passati per valore e gli
indirizzi di quelli passati per riferimento, l’indirizzo di ritorno della
procedura.
Il blocco heap è riservato alle variabili dinamiche.
STACK
HEAP
DATI
CODICE
Lo spazio occupato dai dati e dal codice è fisso.
3
Allocazione statica.
Memoria viene allocata automaticamente in un processo
mediante una dichiarazione esplicita di un identificatore
che rappresenta una variabile o una costante che
appare nella lista dei parametri di una function.
Tale memoria viene automaticamente deallocata quando
il processo termina.
4
Allocazione dinamica.
La memoria è allocata e/o deallocata in un processo
mediante delle istruzioni particolari definite in quel
processo. Di norma, tale memoria non è disponibile
prima che l’opportuna istruzione sia posta in essere e
potrebbe continuare o meno ad esistere dopo che il
processo è terminato.
5
Una variabile allocata dinamicamente è detta variabile
dinamica: per introdurre una tale variabile è necessario
servirsi di un puntatore.
6
Puntatori
Come è noto in un computer la memoria è organizzata in
celle consecutive, ciascuna della grandezza di un byte.
Queste celle possono essere gestite singolarmente (ad
esempio, per oggetti di tipo char che occupano un 1 byte, o
a gruppi (ad esempio, per oggetti di tipo float che occupano
4 byte, …).
Ad ogni oggetto viene associato un indirizzo di memoria che
rappresenta il primo byte della zona ad esso riservata.
7
Puntatori
Definiamo puntatore una variabile che contiene l’indirizzo di
un’altra variabile: la variabile p conservata, ad esempio a
partire dall’indirizzo 0x0064fd0, contiene l’indirizzo
0x0064fef del primo byte della variabile float pi che è un
numero reale.
Questa situazione viene descritta scrivendo
0x0064fef
float pi=3.1415;
float* p;
pi=3.14
p
8
Puntatori
Per identificare una variabile di tipo puntatore si usa un *
come suffisso al tipo che la variabile rappresenta, come
mostrato di seguito:
0x0064fef
float pi=3.1415;
float* p, float* q;
pi=3.14
p
p = π
L’istruzione float* p associa alla variabile puntatore di nome p un indirizzo
a partire dal quale si prevede un’occupazione di memoria necessaria per il
tipo float.
Per associare alla variabile p ad esempio il valore contenuto in pi si pone
9
p=&pi. Ovviamente pi deve essere dello stesso tipo di p.
Puntatori
float pi=3.1415;
float* p, float* q;
p = π
Se ora scriviamo
q = p;
0x0064fef
q
pi=3.14
p
Abbiamo che anche la variabile q punta allo stesso indirizzo
purchè sia dello stesso tipo di p: l’assegnazione sta ad
indicare che l’indirizzo contenuto in p viene copiato in q (che
vale ancora 0x0064fef) e che punta, quindi, allo stesso
contenuto.
10
…………..
0x0064fd0
Ad esempio se alla variabile float n=44.5 è stata
0x0064fd1
0x0064fd2
assegnata la cella 0x0064fd5 (in esadecimale) in
0x0064fd3
memoria si avrà la situazione mostrata a sinistra.
0x0064fd4
0x0064fd5
0x0064fd6
44.5
0x0064fd7
0x0064fd8
0x0064fd9
0x0064fda
0x0064fdb
0x0064fd5
float n
44.5
0x0064fdc
0x0064fdd
0x0064fde
0x0064fdf
0x0064fe0
0x0064fe1
0x0064fe2
0x0064fe3
0x0064fe4
11
…………..
0x0064fd0
Se ora dichiariamo la variabile puntatore
0x0064fd1
float* pn avremo che in memoria verrà
0x0064fd2
allocato un byte per pn.
0x0064fd3
0x0064fd5
0x0064fd4
0x0064fd3
0x0064fd5
0x0064fd6
44.5
0x0064fd5
float* pn
0x0064fd7
0x0064fd8
0x0064fd9
0x0064fda
0x0064fdb
0x0064fd5
44.5
float n
0x0064fdc
0x0064fdd
0x0064fde
0x0064fdf
0x0064fe0
float n=44.5;
float* pn;
pn= &n;
0x0064fe1
0x0064fe2
0x0064fe3
0x0064fe4
12
0x0064fd0
float* p
0x0064fef
………………………………….
& è l’operatore di indirizzo
0x0064fef
4 byte
………………………………….
p = &pi
pi=3.1415
Ricapitolando definiamo puntatore
una variabile che contiene l’indirizzo
di un’altra variabile: la variabile p
conservata a partire dall’indirizzo
0x0064fd0, contiene l’indirizzo
0x0064fef del primo byte della
variabile float pi che è un numero 13
reale.
Definite due variabili puntatore p e q ad un float;
float* p, float* q;
Supponiamo che esse abbiano come indirizzo (ad es. 0x0064fd0 e
0x0064fd9).
Inizialmente il valore di p è nullo.
Posto p = π
alla variabile puntatore p viene associato l’indirizzo della variabile pi
ottenendo la situazione vista prima ( l’operatore & è l’operatore di
indirizzo );
Posto q = p;
Nell’indirizzo della variabile puntatore q, che deve essere dello stesso
tipo di p, viene scritto lo stesso indirizzo contenuto in p (che vale
ancora 0x0064fef ) e che punta allo stesso contenuto.
14
Il simbolo * posto vicino al tipo della variabile è l’operatore di
dichiarazione di puntatore;
la scrittura Tipo* p indica che p è una variabile di tipo puntatore che
punta a una variabile di tipo Tipo;
poiché il puntatore fornisce l’indirizzo soltanto del primo byte, il sistema
conosce esattamente la sua lunghezza soltanto attraverso il tipo.
È assolutamente vietato far puntare un puntatore ad un oggetto che
non sia dello stesso tipo di quello proposto nella dichiarazione;
per esempio, tenendo presente le dichiarazioni float* p; int* q
compilatore segnala errore ad una assegnazione del tipo q=p
il
ATTENZIONE alla istruzione float* p, q;
p è un puntatore ad un float mentre q è una variabile float.
15
Assegnato un puntatore, come si fa ad ottenere l’oggetto da
esso puntato?
Se ap punta ad a, possiamo ottenere il valore di a direttamente
da ap: l’espressione *ap calcola il valore di a.
Tale operatore viene detto operatore di direzione o operatore di
derenferenziazione.
16
L’istruzione cout<<*p stamperà il contenuto dell’oggetto
puntato da p, cioè 3.1415,
Mentre
cout<<p
stamperà il valore del puntatore p in esadecimale, cioè
l’indirizzo a cui punta p (es. 0x0064fef in esadecimale ).
Es. il codice che segue produce l’output di figura.
int main() {
int a;
int *ap;
cout<<"a=";
cin>>a;
ap=&a;
cout<<"indirizzo di a = "<<&a<<" valore di a = "<<a<<endl;
cout<<"indirizzo di ap = "<<&ap<<" valore di ap = "<<ap<<endl;
cout<<" valore a cui punta ap = "<<*ap<<endl;
system(“pause”)
}
17
Le operazioni che avvengono in memoria sono illustrate in figura.
*ap
ap
0x22ff72
0x22ff73
44
………….
………….
………….
0x22ff78
a=44
0x22ff74
0x22ff75
0x22ff76
0x22ff77
&a
0x22ff74
&ap
0x22df70
int a; int *ap;
cin>>a;
ap=&a;
cout<<"indirizzo di a = "<<&a<<" valore di a = "<<a<<endl;
18
cout<<"indirizzo di ap = "<<&ap<<" valore di ap = "<<ap<<endl;
cout<<" valore a cui punta ap = "<<*ap<<endl;
E’ possibile assegnare ad un puntatore il valore 0 (o la
costante simbolica NULL) in tal caso il puntatore non punta a
nulla.
L’indirizzo è di norma composto da tutti zeri e non viene
allocata memoria.
int* p=0;
oggetto.
// p è un puntatore nullo che non punta a nessun
Il puntatore nullo non può essere dereferenziato: i risultati
sono imprevedibili ed il programma potrebbe andare in crash.
19
E’ possibile definire puntatori a vari livelli come mostrato di seguito:
{ int n=44;
cout<<" n= "<<n<<endl;
cout<<" &n= "<<&n<<endl;
int* pn=&n;
// pn contiene l'indirizzo di n
cout<<" pn= "<<pn<<endl;
cout<<" &pn= "<<&pn<<endl;
cout<<" *pn= "<<*pn<<endl;
int** ppn=&pn ;
//ppn contiene l'indirizzo di pn
cout<<" ppn= "<<ppn<<endl;
cout<<" &ppn= "<<&ppn<<endl;
cout<<" *ppn= "<<*ppn<<endl;
cout<<" **ppn= "<<**ppn<<endl;
}
0x22ff68
n
0x22ff64
0x22ff60
44
int
pn
int*
ppn
int**
20
Un puntatore si dice costante se l’indirizzo non può essere
modificato.
int n,m,n1=10;
int * const p1= &n1 ;
p1 = &m ;
// l’indirizzo di p1 non può essere modificato: ERRATO
*p1=m;
//ma il suo contenuto può essere modificato: CORRETTO
const int* const p2=&n1;
// non è possibile modificare né
l’indirizzo di p2 né il suo contenuto
Allegato puntatori
21
Puntatori ed array
Quando il compilatore incontra un’espressione tipo a[i] , dove a è un
array di n elementi ed i il suo indice, genera il codice per calcolare
l’indirizzo di a[i] .
Ad esempio, per controllare l’espressione
a[i] < a[i+1]
il compilatore deve prima calcolare gli indirizzi di a[i] e di a[i+1] e poi
eseguire il confronto tra i due valori.
22
Puntatori ed array
Vediamo il calcolatore come opera.
Innanzitutto l’array deve essere di un Tipo dichiarato (per
es. int o double).
Poiché l’array è rappresentato in memoria come una
sequenza di byte, il nome a dell’array rappresenta il suo
indirizzo-base, cioé l’indirizzo del suo primo elemento, a[0].
Inoltre, tutte le componenti dell’array hanno la stessa
lunghezza in byte (che possiamo determinare con
sizeof(Tipo)), per cui gli indirizzi dei vari elementi dell’array
possono essere calcolati come
a + i x sizeof(Tipo)
per i=0, 1, 2 ………., n
23
Il compilatore sostituisce ogni riferimento ad a[i] con il
calcolo precedente eseguendo le operazioni di addizione
e moltiplicazione.
Una maniera più efficiente di operare è quello di inizializzare
una variabile puntatore all’indirizzo-base dell’array e poi
aggiungere la quantità sizeof(Tipo) ad ogni passo del
ciclo.
Ciò può essere ottenuto in maniera semplice scrivendo
*(a + i)
il compilatore:
1. determina l’indirizzo del primo elemento dell’array a;
2. aggiunge i volte la grandezza del Tipo dell’elemento;
3. restituisce l’indirizzo totale.
24
Il codice mostrato a destra
e l’output sottostante
mostrano gli indirizzi e il
contenuto dell’array
sommato passo passo.
Allegato scorrArrayPuntatori
int main()
{ const int Size=3;
short a[Size]={22,33,44};
cout<<“a “<<a<<endl;
cout<<“size of short “<<sizeof(short)<<endl;
short* end=a+Size;
short sum=0;
for (short* p=a;p<end;p++)
{
sum+=*p;
cout<<“\t p= “<<p;
cout<<“\t *p= “<<*p;
cout<<“\t sum= “<<sum<<endl;
}
}
25
A titolo esemplificativo riscriviamo le function inserite nel
file InsertArray.h.
Ricordiamo che la chiamata del vettore deve essere fatta
con un puntatore.
Allegato InsertArray.h
26
void LeggeVettore(int [],const int,char,
int=100,bool=true);
void StampaVettore (const int [],const int,
char);
void LeggeVettore (int vet[],const int n,
char nome, int nr, bool Acaso)
{ int i;
if (Acaso){
srand(time(0));
for (i=0; i<n; i++) {
vet[i]=rand() % nr - nr/2;
cout<<nome<<"["<<i<<"]="<<vet[i]<<" ";
}
cout<<endl;}
else {
for (i=0; i<n; i++) {
cout<<nome<<"["<<i<<"]=";
cin>>vet[i];
}
}
}
void StampaVettore (const int vet[], const
int n, char nome)
{ int i;
cout<<nome<<"={";
for (i=0; i<n; i++)
if (i<n-1)
cout<<vet[i]<<",";
else
cout<<vet[i]<<"}"<<endl;
È necessario introdurre il simbolo di
puntatore in entrambi i casi evidenziati:
int * in luogo di int [ ]
L’istruzione in grassetto va sostituita con
*(vet+i)=rand() % nr - nr/2;
che risulterà essere più veloce.
In generale, ogni occorrenza di
vet[i]
deve essere sostituita con
*(vet+i)
27
void LeggeVettore(int [],const int,char,
int=100,bool=true);
void StampaVettore (const int [],const int,
char);
void LeggeVettore(int*,const int, char,
int=100, bool=true);
void StampaVettore (const int*,const int,
char);
void LeggeVettore (int vet[],const int n,
char nome, int nr, bool Acaso)
{ int i;
if (Acaso){
srand(time(0));
for (i=0; i<n; i++) {
vet[i]=rand() % nr - nr/2;
cout<<nome<<"["<<i<<"]="<<vet[i]<<" ";
}
cout<<endl;}
else {
for (i=0; i<n; i++) {
cout<<nome<<"["<<i<<"]=";
cin>>vet[i];
}
}
}
void StampaVettore (const int vet[], const
int n, char nome)
{ int i;
cout<<nome<<"={";
for (i=0; i<n; i++)
if (i<n-1)
cout<<vet[i]<<",";
else
Allegato InsertArrayPunt.h
cout<<vet[i]<<"}"<<endl;
void LeggeVettore(int *vet,const int n,
char nome,int nr,bool Acaso)
{ int i;
if (Acaso){
srand(time(0));
for (i=0; i<n; i++) {
*vet[i+]=rand() % nr - nr/2;
cout<<nome<<"["<<i<<"]="<<vet[i]<<" ";
}
cout<<endl;}
else {
for (i=0; i<n; i++) {
cout<<nome<<"["<<i<<"]=";
cin>>*vet[i+];
}
}
}
void StampaVettore(const int *vet,
const int n, char nome)
{ int i;
cout<<nome<<"={";
for (i=0; i<n; i++)
if (i<n-1)
cout<<*vet[i+]<<",";
else
28
cout<<*vet[i+]<<"}"<<endl;
Il codice riscritto è illustrato a
destra.
Allegato InsertArrayPunt.h
// Selection sort con puntatori
sortPuntatori2
Esercizio
Scrivere una procedura ricorsiva che su un array ordinato ricerca
Un determinato valore utilizzando la ricerca binaria utilizzando i puntatori.
Esercizio
Scrivere una procedura ricorsiva che ordini con l’inserction sort un array
assegnato da tastiera utilizzando i puntatori.
29
Se si vuole che la cella puntata non possa essere modificata,
allora è utile introdurre la clausola const davanti alla definizione
ottenendo il puntatore a costante.
…………….
int n=3;
const int* p1;
// p1 punta ad un intero costante
p1=&n;
// viene segnalato un errore perché
la cella n non può essere modificata
Dall’esempio si trae inoltre che un oggetto dichiarato costante
può essere puntato soltanto da un puntatore costante.
Scarica

ppt