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.