Il linguaggio C
Puntatori e dintorni
Puntatori : idea di base
• In C è possibile conoscere e denotare
l’indirizzo della cella di memoria in cui è memorizzata una variabile (il puntatore)
• es :
int a = 50; /* una var intera */
int * b; /* una var puntatore a interi */
...
b = &a; /* assegna a b l’indirizzo della cella in cui è memorizzata a */
Puntatori : idea di base (2)
• In C è possibile conoscere e denotare
l’indirizzo della cella di memoria in cui è memorizzata una variabile (il puntatore)
• es :
int a = 50;
int * b;
…
b = &a;
50 350
a è memorizzata nella cella 350
...
450
Puntatori : idea di base (3)
• nometype *
– è il tipo degli indirizzi delle variabili di tipo nometype
• es :
int a = 50;
int * b;
…
b = &a;
50 350
b è memorizzata nella cella 450 (&b) ...
450
Puntatori : idea di base (4)
• Operatore &
– denota l’indirizzo della cella di memoria in cui è memorizzata una variabile (il puntatore)
• es :
int a = 50;
int * b;
…
b = &a;
50 350
Dopo questo assegnamento in b è memorizzato l’indirizzo di a
350 450
Puntatori : idea di base (5)
• Operatore di dereferenziazione ‘ * ’
– è possibile conoscere e/o modificare il contenuto di una variabile manipolando direttamente il suo puntatore
• es :
int a = 50;
int * b = &a;
…
*b = *b + 4;
54 350
Dopo questo assegnamento in a è memorizzato il valore 50 + 4
350 450
Denota la variabile
Puntatori : idea di base (6)
• NULL
– costante predefinita (in stdio.h) che denota il puntatore nullo
• È possibile definire puntatori per tutti i tipi base e le strutture con (*)
– double *a, *b; /* ripetere ‘*’ */
– int *a, b, c[4], **d;
– struct studente *t1;
• Segnaposto ( %p )
– stampa il valore dell’indirizzo in notazione
Aritmetica dei puntatori
• È possibile scrivere espressioni puntatore usando alcuni degli usuali operatori
aritmetici (+, -, --, ++)
– int a[3], *p = &a[0]; IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
p contiene l’indirizzo IN
Aritmetica dei puntatori (2)
• È possibile scrivere espressioni puntatore usando alcuni degli usuali operatori
aritmetici
int a[3], *p = &a[0];
p = p + 1;
IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
p contiene l’indirizzo IN + 4
Aritmetica dei puntatori (3)
• È possibile scrivere espressioni puntatore usando alcuni degli usuali operatori
aritmetici
int a[3], *p = &a[0];
p = p + 1;
p--;
IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
p contiene l’indirizzo IN
Aritmetica dei puntatori (4)
• È possibile scrivere espressioni puntatore usando alcuni degli usuali operatori
aritmetici (+, -, --, ++)
int a[3], *p = &a[0];
p = p + 1;
p--;
p += 3;
IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
p contiene l’indirizzo IN + 12 (sizeof(int) == 4…..)
Aritmetica dei puntatori (5)
• È possibile scrivere espressioni puntatore usando alcuni degli usuali operatori
aritmetici (+, -, --, ++)
int a[3],*p = &a[0],*q;
p = p + 1;
p--;
q = p;
p += 3;
a[0] = p - q;
IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
a[0] contiene 3, numero di int memorizzabili fra p e q
Puntatori e array…
• Il nome di un array è il puntatore (costante) al primo elemento dell’array
int a[3], *p = &a[0], *q;
q = a; IN+12 ……
IN+8 IN+4 IN
a[2]
a[1]
a[0]
q contiene l’indirizzo IN a == IN
Puntatori e array… (2)
• L’operatore [-] è una abbreviazione …
int a[3], *p = &a[0], *q, tmp;
/* i due stm che seguono sono equivalenti */
tmp = a[2];
tmp = *(a+2);
a+3 ……
a+2 a+1 a
a[2]
a[1]
a[0]
Puntatori e array… (3)
• L’operatore [–] è una abbreviazione … e può essere usato con una qualsiasi
variabile puntatore
int a[3],*p = a,*q,tmp;
tmp = a[2];
tmp = p[2];
a+3 ……
a+2 a+1 a
a[2]
a[1]
a[0]
Puntatori e array… (4)
• I seguenti frammenti di codice sono equivalenti
int a[N], *p = a, *q, tmp;
int sum = 0;
/* versione 1 */
for(i = 0; i < N; i++) sum += a[i];
/* versione 2 */
for(i = 0; i < N; i++) sum += *(a+i);
Puntatori e array… (5)
• I seguenti frammenti di codice sono equivalenti (segue)
int a[N], *p = &a[0], *q, tmp;
int sum = 0;
/* versione 3 */
for(i = 0; i < N; i++) sum += p[i];
/* versione 4 */
for(p = a; p < (a+N); p++) sum += *p;
Puntatori e array… (6)
• Una riflessione sulle stringhe
– le stringhe sono array di caratteri char a[7] = “ciao”;
– le stringhe costanti possono essere definite anche come
const char * pp = “ciao”;
char * pp = “ciao”;
• attenzione! Se a questo punto cercate di modificare un elemento di pp (es. pp[2] = `f`;) avete un errore a run time
• mentre a[2] = `f`; è completamente corretto
Passaggio di parametri per riferimento
• Tutti i parametri delle funzioni C sono passati per valore
– il loro valore viene copiato sullo stack
– ogni modifica al parametro nel corpo della funzione non modifica l’originale
• È possibile realizzare passaggi per riferimento utilizzando i puntatori
– i passaggi per riferimento permettono di modificare il valore di una variabile
nell’ambiente del chiamante
Passaggio di parametri per riferimento (2)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– si potrebbe pensare di programmarla come ...
void scambia (int x, int y){
int tmp;
tmp = x;
x = y;
y = tmp;
}
– e poi chiamare scambia(a,b)
Passaggio di parametri per riferimento (3)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– si potrebbe pensare di programmarla come ...
void scambia (int x, int y){
int tmp;
tmp = x;
x = y;
y = tmp;
}
– non funziona! Perché lo scambio viene fatto sulle copie
Passaggio di parametri per riferimento (3.1)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– esempio di chiamata
int a = 4, b = 5;
scambia(a,b);
45
45
Frame
chiamante
&a
&b
Frame scambia
&x
&y
stack
Passaggio di parametri per riferimento (3.2)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– alla fine dell’esecuzione di scambia (prima di ritornare al chiamante)
int a = 4, b = 5;
scambia(a,b); 4
5
54
Frame
chiamante
&a
&b
Frame scambia
&x
&y
Passaggio di parametri per riferimento (3.3)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– al momento di eseguire la printf (il frame di scambia non è più significativo)
int a = 4, b = 5;
scambia(a,b);
printf(“%d,%d”,a,b);
45 Framechiamante
&a
&b
Passaggio di parametri per riferimento (4)
• Esempio : la funzione che scambia fra loro i valori di due variabili
– la versione corretta è ...
void scambia (int *x, int *y){
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
– con chiamata scambia(&a,&b)
Passaggio di parametri per riferimento (4.1)
• Versione corretta di scambia ...
– esempio di chiamata
int a = 4, b = 5;
scambia(&a,&b);
45
&a
&b
Frame
chiamante
&a
&b
Frame scambia
&x
&y
stack
Ogni modifica a
*x modifica
il valore di a nell’ambiente
Passaggio di parametri per riferimento (4.2)
• Esempio : versione corretta di scambia ...
– alla fine dell’esecuzione di scambia (prima di ritornare al chiamante)
int a = 4, b = 5;
scambia(&a,&b);
54
&a
&b
Frame
chiamante
&a
&b
Frame scambia
&x
&y
Passaggio di parametri per riferimento (4.3)
• Esempio : versione corretta di scambia ...
– al momento di eseguire la printf (il frame di scambia non è più significativo)
int a = 4, b = 5;
scambia(&a,&b);
printf(“%d,%d”,a,b);
54 Framechiamante
&a
&b
Passaggio di parametri per riferimento (5)
• ATTENZIONE : gli array sono passati
sempre per riferimento perché quello che si passa è il nome dell’array
void assegna (int x[ ]) { x[0] = 13;
}
– con chiamata
int a[10];
assegna(a);
/* qua a[0] vale 13 */
Passaggio di parametri per riferimento (6)
• Inoltre : le due scritture
void assegna (int x[ ]){
x[0] = 13;
}
e
void assegna (int *x){
x[0] = 13;
}
– sono del tutto equivalenti
– si preferisce usare la prima per leggibilità
Passaggio di parametri per riferimento (7)
• Tipicamente le funzioni che lavorano su array hanno un secondo parametro che fornisce la lunghezza
int somma (int x[ ], int l){
int i, s = 0;
for(i = 0; i < l; i++) s += x[i];
return s;
}
– somma tutti gli elementi di un array intero di lunghezza l
Passaggio di parametri per riferimento (8)
• Per gli array multidimensionali la cosa è più complessa!!!!
int somma (int x[ ][4], int l){
int i, j, s = 0;
for(i = 0; i < l; i++) for(j = 0; j < 4; j++) s += x[i][j];
return s;
}
– invece di 4 posso usare N costante
Passaggio di parametri per riferimento (9)
• Perché dobbiamo specificare l’ampiezza di una seconda dimensione di un array ?
– Dipende dalla strategia di memorizzazione per gli array multidimensionali
• es: int a[2][3]={{1,2,3},{4,5,6}};
1 2 3 4 5 6 a
&a[0][1]
&a[0][2]
&a[1][0]
&a[1][1]
&a[1][2]
a[i][j]
ha come indirizzo a+i*3+j
100 104 108 112 116 120
Passaggio di parametri per riferimento (10)
• Se non conosco la lunghezza della seconda dimensione il compilatore non riesce a
generare codice corretto
int somma (int x[ ][4], int l){
int i, j, s = 0;
for(i = 0; i < l; i++) for(j = 0; j < 4; j++) s += x[i][j];
return s;
}
Passaggio di parametri per riferimento (11)
• Esiste un modo migliore di quello appena
esaminato per la rappresentazione degli array
multidimensionali in C : lo vedremo in seguito
E le strutture ???
• Le strutture vengono sempre passate per valore
• Se una struttura contiene un array, allora l’array viene copiato!
– Attenzione quando si passano strutture con campi array molto grandi!
• Se voglio modificare una struttura devo
sempre utilizzare i puntatori!
E le strutture ??? (2)
• Esempio
typedef struct studente { char nom_cogn[40];
unsigned int matricola;
} studente;
void scambia (studente * s1, studente * s2);
E le strutture ??? (3)
• Esempio
void scambia (studente * s1, studente * s2) {
…
(*s1).matricola = 4;
s1->matricola = 4;
/*sono equivalenti */
}
E le strutture ??? (4)
• Esempio : Come si dichiara una lista in C ?
– Usando i puntatori
typedef struct nodo { struct nodo * next;
int info;
} nodo;
Mi serve il nome della struttura !
Allocazione dinamica della memoria
• La creazione di nuove variabili a run time (tipo new in Java) viene effettuata in C
utilizzando le funzioni di libreria standard che permettono l’allocazione dinamica di porzioni contigue di memoria
– malloc, calloc, realloc – #include <stdlib.h>
Con queste primitive è possibile creare
dinamicamente variabili e array di dimensione non nota a priori
Array dinamici -- malloc( )
• Vediamo come creare dinamicamente un array di 10 posizioni
int * a; /*conterrà il puntatore al primo elemento dell’array*/
a = malloc(10*sizeof(int));
heap 40 byte
Punta allʼindirizzo iniziale della nuova
area allocata 100
96
Array dinamici -- malloc( ) (2)
• Vediamo come creare dinamicamente un array di 10 posizioni
int * a; /*conterrà il puntatore al primo elemento dell’array*/
a = malloc(10*sizeof(int));
if (a == NULL) printf(“fallimento!\n”);
heap
Se malloc non riesce ad allocare
lʼarea di memoria richiesta restituisce NULL (verificare…)
Array dinamici -- malloc( ) (3)
• Vediamo come creare dinamicamente un array di 10 posizioni
int * a; /*conterrà il puntatore al primo elemento dell’array*/
a = malloc(10*sizeof(int));
if (a == NULL) printf(“fallimento!\n”);
else {
a[4] = 345;
… }
Lʼarray si può accedere con i consueti heap
40 byte
100 96
Array dinamici -- malloc( ) (4)
• malloc non inizializza la memoria a 0!
– Possiamo inizializzarla esplicitamente o – usare calloc
int * a; /*conterrà il puntatore al primo elemento dell’array*/
a = calloc(10*sizeof(int));
If (a == NULL) printf(“fallimento!\n”);
else {
a[4] = 345;
… }
Array dinamici -- realloc( )
• realloc modifica la lunghezza di un’area allocata precedentemente
int * a, * b; /*puntatori al primo elemento dell’array*/
a = malloc(10*sizeof(int));
…
b = realloc(a,20*sizeof(int));
/* adesso b punta ad un array di 20 elementi */
Array dinamici -- realloc( ) (2)
• Meglio usare sempre due puntatori diversi (a,b) !
– Altrimenti in caso di fallimento NULL sovrascrive il vecchio puntatore
Array dinamici -- free( )
• Lo spazio allocato sullo heap non viene deallocato all’uscita delle funzioni
• La deallocazione deve essere richiesta esplicitamente usando free
int * a;
a = malloc(10*sizeof(int));
…
free(a);
/* se qua accedo di nuovo ad a può succedere di tutto */
tipo puntatore generico: void *
• non si può dereferenziare
• è necessario un cast prima di manipolare la variabile puntata
– Es.
void * c;
int a;
c = &a;
*c = 5; /* scorretto*/
*(int *)c = 5; /* corretto*/
tipo puntatore generico: void * (2)
• Serve a scrivere funzioni ‘polimorfe’ in una maniera un po’ brutale
• Esempio
– il tipo della malloc è
void * malloc (unsigned int size);
– quando scrivo
int * a;
a = malloc(10*sizeof(int));
viene effettuato un cast implicito a (int *)
tipo puntatore generico: void * (3)
• Tipi delle altre funzioni di allocazione e deallocazione
void * calloc (unsigned int size);
void * realloc (void * ptr,
unsigned int size);
void free (void * ptr);
I puntatori a funzione
• Consideriamo la funzione
int somma (int x, int y) { return x + y;
}
– se proviamo ad eseguire
printf(“%p”, somma);
otteniamo un valore esadecimale che
rappresenta un indirizzo legale del nostro programma
– ??????????????????????????
I puntatori a funzione (2)
• Consideriamo la funzione
int somma (int x, int y) { return x + y;
}
Codice compilato
di somma IND
somma è un puntatore costante con valore pari a IND
I puntatori a funzione (3)
• Consideriamo la funzione
int somma (int x, int y) { return x + y;
}
/* variabile di tipo funzione (int,int)->int */
int (*fun) (int,int);
int a;
fun = somma;
a = fun(3,5);
I puntatori a funzione (4)
• Consideriamo la funzione
int somma (int x, int y) { return x + y;
}
/* variabile di tipo funzione (int,int)->int */
int (*fun) (int,int);
int a;
fun = somma;
a = fun(3,5);
Ma a che serve
????????????
I puntatori a funzione (5)
• Serve a definire funzioni che prendono come argomenti altre funzioni (di ordine superiore)
void map (int (*fun) (int), int x[ ], int l) { for(i = 0; i < l; i++) x[i] = fun(x[i]);
}
è un iteratore che applica la funzione fun a tutti gli elementi dell’array x
I puntatori a funzione (6)
• Esempio di uso della map
int piu_uno (int x) { return x+1;}
int quad (int x) { return x*x;}
…
int a[3] = {3,4,5};
map(piu_uno,a,3); /* somma uno a tutti gli elementi */
map(quad,a,2); /* eleva al quadrato i primi due elementi */
Argomenti della linea di comando
• Gli argomenti della linea di comando sono accessibili all’interno della funzione main
– il SO li inserisce sullo stack prima di attivare il processo
– il formato in cui sono resi disponibili è fisso
int main (int argc, char * argv[ ]) { …
}
Numero di argomenti nella linea di comando
Array di puntatori agli argomenti
(ciascuno è una stringa, tipo char*)
Argomenti della linea di comando (2)
• Esempio
%> a.out una stringa per a.out
5 argc
argv p e r \O
a . o u t \O
s t r i n g
u n a \O
a \O
a . o u t \O
argv[0]
Argomenti della linea di comando (3)
• Esempio : Schema di programma che stampa gli argomenti sulla linea di comando
int main (int argc, char * argv[ ]) { …
for(i = 0; i < argc; i++)
printf(“arg %d: %s”, i, argv[i]);
… }
Array multidimensionali come array di puntatori
• Vogliamo permettere la definizione di
funzioni su array multidimensionali che non dipendono dal valore delle dimensioni
successive alla prima
int sum_mat (int ** MAT,
int n, int m) { …
}
Nome della matrice
Numero di righe, colonne
Array multidimensionali come array di puntatori (2)
• Vogliamo accedere agli elementi dell’array usando la solita notazione [-][-]
int sum_mat (int ** MAT,
int n, int m) { …
MAT[i][j] = …;
}
*(MAT + i*m + j) Il compilatore
dovrebbe conoscere il legame fra questi due oggetti
Array multidimensionali come array di puntatori (3)
• Una alternativa: abbandonare l’allocazione contigua per righe
MAT
7 2 6 2
1 2 3 4
4 6 1 2
4 5 1 2
MAT[0]
MAT[1]
3 5 7 9
MAT[2]
MAT[3]
MAT[4]
MAT[2][2]
Array multidimensionali come array di puntatori (4)
• Una alternativa: vediamo i tipi ...
MAT
7 2 6 2
1 2 3 4
4 6 1 2
4 5 1 2
MAT[0]
MAT[1]
3 5 7 9
MAT[2]
MAT[3]
MAT[4]
MAT[2][2]
int**
int*[5]
int[4]
Array multidimensionali come array di puntatori (5)
• Una alternativa: in memoria non ho più aree contigue ...
MAT
1 2 3 4
4 6 1 2
MAT[0]
3 5 7 9
40 44 48 52
40 120140400 4
70 74 78 82 86
120 124 128 132 140 144 148 152 indirizzo
valore
Array multidimensionali come array di puntatori (6)
• Perché funziona?
int sum_mat (int ** MAT,
int n, int m) { …
MAT[i][j] = …;
}
*(*(MAT + i) + j) Questo legame non interessa più!
Array multidimensionali come array di puntatori (7)
• Funzione di allocazione
int ** mat_new(unsigned int m, unsigned int n) {
int i, ** a, errore = FALSE;
a = malloc(m*sizeof(int*));
if (a == NULL) return NULL;
for(i = 0; (i < m) && (!errore); i++) { a[i] = malloc(n*sizeof(int));
if (a[i] == NULL) errore = TRUE;
}
if (errore) /* gestione errori */
else return a;
Array multidimensionali come array di puntatori (8)
• Funzione di deallocazione
void mat_free(int ** a, unsigned int m) {
int i;
/* dealloco tutte le righe */
for(i = 0; i < m; i++) free(a[i]);
/* dealloco l’array dei puntatori alle righe */
free(a);
assert( )
• Permettono di fare controlli di consistenza a tempo di esecuzione
– prevenire meglio che curare …
– esempio: un indice i è davvero dentro i limiti dell’array?
int x, a[N], i;
……
assert(i < N);
x = a[i];
assert( ) (2)
#include <assert.h>
…
assert(expr);
– se expr è falsa il sistema stampa un messaggio di errore e termina
– se expr è vera non ha alcun effetto!
assert( ) (3)
• Le assert costano!
• Quando usarle
– per effettuare controlli di consistenza dopo chiamate a codice complesso
• tipicamente non abbiamo i sorgenti (se è scritto da altri)
• … e comunque anche se li abbiamo non è mai garantita la correttezza!
– si controlla se i valori risultanti sono rispondenti alle specifiche fornite
– si controllano invarianti noti dell’applicazione