Lezione 3 - Lunedì 3 marzo 2014 (180 min)
Argomenti: Aritmetica dei puntatori, tipi array.
Descrizione dettagliata:
- Aritmetica dei puntatori∞: somma puntatore-intero e differenza di puntatori.
- Uso di v[i] come espressione equivalente a *(v+i).
- Puntatori generici void* e conversioni fra puntatori∞.
- Regole di compatibilità tra puntatori∞
- Tipi array∞:
- LValue che denotano oggetti array sono non modificabili
- Parametri formali di tipo array interpretati come puntatori
- Conversione automatica di una variabile array a un RValue di tipo puntatore
Appunti della lezione
Aritmetica dei puntatori
In C è possibile sommare o sottrarre un intero a un puntatore, o fare la differenza di due puntatori.
Differenza fra puntatori: se p e q sono due puntatori dello stesso tipo T*, allora p-q denota la differenza degli indirizzi di p e di q, divisa per sizeof(T). In altre parole, p-q restituisce il numero di oggetti di tipo T compresi tra gli indirizzi p e q, con il segno meno se p<q.
Esempio: se p è un puntatore di tipo int* che vale 1000 e q è un puntatore di tipo int* che vale 1024, allora p-q è un intero che vale (1000-1024)/4 = -6.
Somma puntatore+intero: se p è un puntatore di tipo T* che denota un indirizzo x ed i è un intero, allora p+i è un puntatore di tipo T* che denota l'indirizzo x+i*sizeof(T). In altre parole, p+i denota l'indirizzo dell'i-esimo oggetto di tipo T che si incontra partendo dall'indirizzo p. Questa operazione viene usata per indicizzare array di oggetti.
Esempio: se p è un puntatore di tipo int* che vale 1000, allora p+6 è un puntatore di tipo int* che vale 1000+6*4 = 1024.
In base a quanto detto finora, l'aritmetica dei puntatori consente di usare un qualsiasi blocco di memoria come se fosse un array!
Esempio: se p è un puntatore di tipo int* che vale 1000, allora *(p+6) è il sesto oggetto int a partire dall'indirizzo 1000.
Si noti che in C l'espressione v[i] è equivalente a *(v+i). Inoltre, per la commutatività della somma, v[i] e i[v] sono equivalenti!
Il seguente esempio mostra come allocare dinamicamente un array di 100 interi, che viene poi azzerato:
int i, *v; // dichiara una variabile intera i e un puntatore a intero v
v = malloc(100*sizeof(int)); // alloca un blocco contenente spazio per 100 int
for (i=0; i<100; i++) // scorre i 100 int del blocco e li mette tutti a zero
v[i] = 0;
v = malloc(100*sizeof(int)); // alloca un blocco contenente spazio per 100 int
for (i=0; i<100; i++) // scorre i 100 int del blocco e li mette tutti a zero
v[i] = 0;
Compatibilità tra puntatori
A meno di cast espliciti, in C si hanno le seguenti regole:
- Un oggetto puntatore di tipo T* può essere assegnato con:
- la costante 0 (NULL)
- un puntatore a un oggetto di tipo compatibile con T
- un puntatore di tipo void*
- Un oggetto puntatore di tipo void* può essere assegnato con:
- la costante 0 (NULL)
- un puntatore a un oggetto di qualsiasi tipo
Esempi:
int x;
float y;
void* p = &x; // ok, si può assegnare un int* a un void*
int* q = &x; // ok, si può assegnare un int* a un int*
int* r = NULL; // ok, si può assegnare NULL (0) a qualsiasi oggetto puntatore
int* s = &y; // errore, non si può assegnare un float* a un int*
int* t = (int*)&y; // ok, l'espressione a destra è di tipo int*
void* u = t; // ok, si può assegnare un puntatore di qualsiasi tipo a un oggetto void*
int* v = u; // ok, si può assegnare void* a un oggetto puntatore di qualsiasi tipo (in C, non in C++)
float y;
void* p = &x; // ok, si può assegnare un int* a un void*
int* q = &x; // ok, si può assegnare un int* a un int*
int* r = NULL; // ok, si può assegnare NULL (0) a qualsiasi oggetto puntatore
int* s = &y; // errore, non si può assegnare un float* a un int*
int* t = (int*)&y; // ok, l'espressione a destra è di tipo int*
void* u = t; // ok, si può assegnare un puntatore di qualsiasi tipo a un oggetto void*
int* v = u; // ok, si può assegnare void* a un oggetto puntatore di qualsiasi tipo (in C, non in C++)
Tipo array
Vediamo ora il primo tipo non primitivo in C: l'array. L'array è un tipo composto che denota una sequenza di oggetti dello stesso tipo, disposti in modo consecutivo in memoria.
Dichiarazione variabile array: Una variabile v di tipo array di oggetti di tipo T si dichiara così:
T v[D]
dove D è un intero che denota la dimensione dell'array, cioè il numero di oggetti di tipo T in esso contenuto. Secondo lo standard ANSI C (ISO C90), D deve essere una costante determinabile a tempo di compilazione. Nel C99, può essere invece un valore determinato a tempo di esecuzione, come ad esempio il contenuto di una variabile intera.
Esempio:
int v[10];
In questo caso, v è una variabile che denota un array di 10 int.
Particolarità degli Lvalue di tipo array. Un'espressione Lvalue di tipo array di T è un Lvalue non modificabile.
Ne consegue che non è possibile copiare un array su un altro mediante un assegnamento, come illustrato dal seguente esempio:
int a[10];
int b[10];
...
a=b; // errore di compilazione qui
int b[10];
...
a=b; // errore di compilazione qui
Si noti che l'assegnamento a=b non è ammesso, essendo a un'espressione Lvalue che denota un oggetto di tipo array.
Conversione automatica da array a puntatore: in ogni contesto in cui ci si aspetta un Rvalue, ogni Lvalue di tipo array di oggetti di tipo T viene automaticamente convertito a un Rvalue di tipo T* che denota l'indirizzo del primo oggetto dell'array. Eccezione a questa regola è l'argomento dell'operatore sizeof.
Esempi:
int x[10];
int* p=x; // viene assegnato a p l'indirizzo del primo oggetto di x (equivalente a p=&x[0])
printf("%lu\n", sizeof(x)); // stampa 40, ottenuto come 10*sizeof(int)
int* p=x; // viene assegnato a p l'indirizzo del primo oggetto di x (equivalente a p=&x[0])
printf("%lu\n", sizeof(x)); // stampa 40, ottenuto come 10*sizeof(int)
Non esistono parametri formali di tipo array: se un parametro formale è dichiarato dal programmatore di tipo array di T, il parametro è trattato dal compilatore come se fosse stato dichiarato di tipo T*. Non esistono quindi parametri formali che denotano Lvalue di tipo array.
Esempio:
void foo(int v[10]) { // parametro formale v è di tipo int*
int x[10]; // variabile locale x è di tipo array di 10 int
printf("%lu\n", sizeof(v)); // stampa 8, cioè il numero di byte di un puntatore (su sistemi operativi a 64 bit)
printf("%lu\n", sizeof(x)); // stampa 40, ottenuto come 10*sizeof(int)
}
int x[10]; // variabile locale x è di tipo array di 10 int
printf("%lu\n", sizeof(v)); // stampa 8, cioè il numero di byte di un puntatore (su sistemi operativi a 64 bit)
printf("%lu\n", sizeof(x)); // stampa 40, ottenuto come 10*sizeof(int)
}
Si noti che la dimensione dell'array in una dichiarazione di parametro formale viene ignorata. E' possibile quindi scrivere:
void foo(int v[]) { // v è di tipo int*
}
}
Passaggio di parametro di tipo array: in base alla regola di conversione automatica da array a puntatore, passare come parametro attuale un Lvalue di tipo array di T equivale a passare l'indirizzo del primo oggetto dell'array. Non è possibile quindi passare array per copia a una funzione e il passaggio è sempre per indirizzo:
void foo(int q[]) { // q è di tipo int*
q[1]=971;
}
int main() {
int v[20];
foo(v); // passaggio per indirizzo dell'array
printf("%d\n", v[1]); // stampa 971
}
q[1]=971;
}
int main() {
int v[20];
foo(v); // passaggio per indirizzo dell'array
printf("%d\n", v[1]); // stampa 971
}
Questo è coerente con il fatto che non è possibile assegnare un array ad un altro. Infatti, il passaggio dei parametri implica un assegnamento automatico dei parametri attuali ai corrispondenti parametri formali.
Materiale didattico per la lezione
- Appunti della lezione
- [T5] Aritmetica dei puntatori∞
- Compatibilità tra puntatori∞
- Tipi array in C∞
Esercizi del giorno
Esercizio 1
Sia x una variabile di tipo int, p una variabile di tipo int* e q una variabile di tipo int**. Per ciascuna delle seguenti espressioni C:
- x
- x+1
- &x
- &(x+1)
- &&x
- *x
- *&x
- &*q
- *&*&x
- &p
- *p
- *p+x
- **q
- &**q
- &q
dire:
- se è una espressione valida
- in caso affermativo determinarne:
- la categoria (LValue o RValue∞).
- il tipo (es. int, int*, ecc.)
Ad esempio, l'espressione *p-5 è un Rvalue di tipo int.
Esercizio 2
Scrivere una funzione C get_min che, dato un array di interi e la sua dimensione, restituisce l'indirizzo del primo byte della cella contenente il minimo dell'array. La funzione deve avere il seguente prototipo:
int* get_min(int* v, int n);
Dove v è l'array e n la sua dimensione.
Scrivere inoltre un main di prova che alloca dinamicamente un array di n=1000 elementi, lo inizializza in modo tale che v[i]=55+(n-i) % 100, chiama la funzione get_min e stampa il valore del minimo calcolato. Verificare con memcheck che non ci siano errori nell'uso della memoria.
Esercizio 3
Scrivere una funzione get_bit_array che, dato un numero x a 64 bit senza segno, restituisce un array v di 64 char allocato dinamicamente tale che v[i] vale 1 se e solo il bit i-esimo di x, con i compreso tra 0 (bit meno significativo) e 63 (bit più significativo), è settato a 1, e 0 altrimenti. Scrivere il programma in modo da poter compilare correttamente il seguente programma di prova:
#include <stdio.h>
#include <stdlib.h>
// inserire qui la definizione della funzione get_bit_array
int main() {
int i;
unsigned long x = 5234971543233487563;
char* v = get_bit_array(x);
for (i=63; i>=0; i--) printf("%d", v[i]);
printf("\n");
free(v);
return 0;
}
#include <stdlib.h>
// inserire qui la definizione della funzione get_bit_array
int main() {
int i;
unsigned long x = 5234971543233487563;
char* v = get_bit_array(x);
for (i=63; i>=0; i--) printf("%d", v[i]);
printf("\n");
free(v);
return 0;
}
Il programma deve stampare: 0100100010100110010110101110000111101011101101011110001011001011.
Esercizio 4
Scrivere una funzione int cerca(int* v, int n, int x) che, dato un array ordinato di interi v di dimensione n e un intero x, restituisce 1 se x è presente nell'array, e 0 altrimenti. La funzione deve richiedere tempo O(log n). Scrivere un main di prova per testare la correttezza della funzione realizzata. Produrre una variante iterativa e una ricorsiva della funzione.
Esercizio 5
Scrivere una funzione void bubblesort(int* v, int n) che ordina l'array v di n interi passato come parametro usando l'algoritmo di ordinamento a bolle (bubblesort∞). Scrivere un main di prova per testare la correttezza della funzione realizzata.
Esercizio 6
Scrivere una funzione void merge(int* v, int i, int m, int j, int* temp) che, dato un array v, fonde le due porzioni da v[i] a v[m-1] e da v[m] a v[j-1], che si assume siano internamente ordinate, in modo che i j-i interi inizialmente presenti nelle due porzioni appaiano alla fine ordinati nella porzione dell'array che va da v[i] a v[j-1]. Usare come appoggio l'array temp, che si assume sia di dimensione almeno j-i. La realizzazione di questo esercizio è preliminare all'esercizio 8. Scrivere un main di prova per testare la correttezza della funzione realizzata.
Ad esempio, consideriamo l'array:
v={5, 6, 9, 12, 1, 4, 7}
e gli indici i=0, m=4 e j=7. Le due porzioni internamente ordinate sono {5, 6, 9, 12} (indici da 0 a 3) e {1, 4, 7} (indici da 4 a 6). Dopo l'esecuzione della funzione merge, l'array deve essere:
v={1, 4, 5, 6, 7, 9, 12}
La funzione deve richiedere tempo O(j-i).
Esercizio 7
Scrivere una funzione void mergesort(int* v, int n) che ordina l'array v di n interi passato come parametro usando l'algoritmo di ordinamento per fusione (mergesort∞). Scrivere un main di prova per testare la correttezza della funzione realizzata.
Esercizio 8
Scrivere una funzione void get_freq(int* v, int n, int* most_freq, int* less_freq) che, dato un array v di interi di dimensione n, restituisce in most_freq l'elemento più frequente di v (cioè quello che occorre il maggior numero di volte) e in less_freq l'elemento meno frequente. L'algoritmo deve essere il più possibile efficiente asintoticamente e certamente meno che quadratico. Scrivere un programma di prova per testare la correttezza della funzione scritta.
Esercizio 9
Confrontare sperimentalmente il tempo richiesto dalla soluzione all'esercizio 8 compilata:
- senza ottimizzazioni
- con ottimizzazione -O1
- con ottimizzazione -O2
usare il comando time per misurare le prestazioni, facendo la media dei tempi real ottenuti su esecuzioni diverse e verificando che il tempo speso da processi in background è il più basso possibile. L'array di input dovrebbe contenere almeno 1 milione di interi. Riportare insieme alle misurazioni le caratteristiche software/hardware della piattaforma usata (CPU, memoria, sistema operativo, compilatore, ecc.)
Esercizio 10
Scrivere una funzione int codifica(short a, short b) che, dati due short a e b, restituisce un opportuno int da cui sia possibile in seguito ricostruire i due interi a e b. Scrivere poi una seconda funzione void decodifica(int x, short* ap, short* bp) che, dato un intero x precedentemente restituito da codifica, restituisce in *ap e in *bp gli interi a e b originari codificati in x.
Si assuma che sizeof(int)==2*sizeof(short).
Si consideri ad esempio il seguente programma di prova:
main.c
#include <stdio.h>
int main(){
short a, b;
int x = codifica(971, 1080);
decodifica(x, &a, &b);
printf("a=%hd, b=%hd\n", a, b); // stampa a=971, b=1080
}
int main(){
short a, b;
int x = codifica(971, 1080);
decodifica(x, &a, &b);
printf("a=%hd, b=%hd\n", a, b); // stampa a=971, b=1080
}
Esercizio 11
Scrivere una funzione int** allocaMatriceInt(unsigned int r, unsigned int c) che alloca dinamicamente una matrice di interi con r righe e c colonne e restituisce l'indirizzo della matrice. Allocare separatamente le righe e restituire un array di puntatori alle righe. Scrivere la corrispondente funzione void deallocaMatriceInt(int** m, int r) che libera la memoria precedentemente allocata con allocaMatriceInt, assumendo che la matrice abbia r righe. Scrivere un programma di prova per verificare la correttezza delle funzioni scritte.
Esercizio 12
Si scrivano le seguenti funzioni per la gestione di matrici di oggetti di dimensione arbitraria:
- void* newMatrix(unsigned r, unsigned c, unsigned k) che alloca dinamicamente una matrice con r righe e c colonne avente celle di k byte e restituisce l'indirizzo della matrice. I byte della matrice devono essere consecutivi (rappresentazione row-major∞) e devono essere inizializzati a zero.
- void deleteMatrix(void* m) che libera la matrice m precedentemente allocata con newMatrix;
- void setCell(void* m, unsigned i, unsigned j, const void* buf) che, data una matrice m, assegna alla cella (i,j) il valore all'indirizzo buf;
- void getCell(void* m, unsigned i, unsigned j, void* buf) che, data una matrice m, assegna all'indirizzo buf il valore della cella (i,j);
- void* cellAt(void* m, unsigned i, unsigned j) che, data una matrice m, restituisce l'indirizzo della cella (i,j).
Si consideri ad esempio il seguente programma di prova:
testMatrici.c
int main(){
void* m = newMatrix(10, 20, sizeof(double));
double x = 3.14, y;
setCell(m, 2, 4, &x);
getCell(m, 2, 4, &y);
printf("la cella (2,4) contiene il valore: %f\n", y);
printf("la cella (2,4) contiene il valore: %f\n", *(double*)cellAt(m, 2, 4));
*(double*)cellAt(m, 3, 1) = 2.56;
getCell(m, 3, 1, &y);
printf("la cella (3,1) contiene il valore: %f\n", y);
deleteMatrix(m);
return 0;
}
void* m = newMatrix(10, 20, sizeof(double));
double x = 3.14, y;
setCell(m, 2, 4, &x);
getCell(m, 2, 4, &y);
printf("la cella (2,4) contiene il valore: %f\n", y);
printf("la cella (2,4) contiene il valore: %f\n", *(double*)cellAt(m, 2, 4));
*(double*)cellAt(m, 3, 1) = 2.56;
getCell(m, 3, 1, &y);
printf("la cella (3,1) contiene il valore: %f\n", y);
deleteMatrix(m);
return 0;
}
Suggerimento: in newMatrix allocare un unico blocco contiguo di 2*sizeof(unsigned)+r*c*k byte contenente:
- primi sizeof(unsigned) byte: numero c di colonne della matrice;
- successivi sizeof(unsigned) byte: numero k di byte per cella;
- a seguire le celle della matrice disposte in ordine row-major∞.
Nota: unsigned è equivalente in C a unsigned int.