Utilizzo avanzato di array e puntatori
1
Anno accademico 2010-2011
Sommario
• Utilizzo avanzato di array e puntatori
 Gli array multidimensionali
 Gli array di puntatori
 I puntatori a puntatori
 Allocazione dinamica della memoria
2
Anno accademico 2010-2011
Gli array multidimensionali  1
• Un array di array è un array multidimensionale e viene
dichiarato per mezzo di una sequenza di coppie di parentesi
quadre
/* x è un array di tre elementi costituiti
* da array di cinque elementi (interi)
*/
int x[3][5];
• Anche se un array multidimensionale viene memorizzato come
una sequenza di elementi, può essere manipolato come un
array di array
• Per accedere ad un elemento di un array multidimensionale
occorre specificare tanti indici quante sono le dimensioni
dell’array
3
Anno accademico 2010-2011
Gli array multidimensionali  2
• Gli array multidimensionali sono memorizzati con precedenza
delle righe, cioè l’ultimo indice varia più velocemente
• Esempio:
int ar[2][3]{{0,1,2},
{3,4,5}
};
Nell’inizializzazione, ogni riga di
valori è racchiusa fra parentesi
graffe (in questo caso, servono
per migliorare la leggibilità)
1000
1004
1008
100C
1010
1014
ar[0][0]
0
1
2
ar[0][1]
3
4
5
ar[1][1]
ar[0][2]
ar[1][0]
ar[1][2]
1018
4
Anno accademico 2010-2011
Gli array multidimensionali  3
• L’accesso all’elemento ar[1][2] viene interpretato come
*(ar[1]2), ovvero *(*(ar1)2)
• Poiché ar è un array di array, viene effettuato un doppio scaling:
…quando si valuta *(ar1), “1” rappresenta un array di tre interi (12
byte sulla macchina di riferimento)
 …quando si valuta *(*(ar1)2), “2” rappresenta 2 interi (8 byte)
 complessivamente si ha uno spostamento di 20 byte rispetto all’indirizzo
base (si ottiene l’indirizzo esadecimale 1014)

• Se vengono specificati meno indici rispetto alle dimensioni, il risultato
è un puntatore al tipo base dell’array; per esempio…
ar[1] è equivalente a &ar[1][0]
e fornisce come risultato un puntatore ad int
• Lo standard ANSI non impone limiti al numero di dimensioni degli
array; è comunque richiesto di gestire almeno array a sei dimensioni
5
Anno accademico 2010-2011
L’inizializzazione di
array multidimensionali  1
• In fase di inizializzazione di un array multidimensionale,
occorre specificare ogni riga tra parentesi graffe
• Se i valori iniziali non sono sufficienti, e l’array è static, gli
elementi mancanti vengono inizializzati a zero
• Esempio:
static int examp[5][3] { {1,2,3},
{4},
{5,6,7}
};
( )
1
4
5
0
0
2
0
6
0
0
3
0
7
0
0
• In modo analogo al caso dei vettori, se viene “parzialmente”
omessa la dichiarazione della dimensione di un array
multidimensionale, il compilatore la calcola sulla base del
numero dei valori iniziali specificati
Anno accademico 2010-2011
6
L’inizializzazione di
array multidimensionali  2
• Nel caso degli array multidimensionali, infatti, può essere
omessa la dimensione dell’array più esterno, mentre è
obbligatorio specificare le altre
• Esempio:
static int a_ar[][2]  {{1,1},{0,0},{1,2}};
produce un array di dimensione 32, perché sono presenti 6
valori iniziali
• Esempio:
static int b_ar[][]{{1,2,3},{4,5,6}}; /*SCORRETTO*/
Non si può determinare se l’array è 32 o 23 (il
raggruppamento dei dati di inizializzazione non è sufficiente!):
specificare la seconda dimensione avrebbe risolto ogni
ambiguità
Anno accademico 2010-2011
7
Array multidimensionali come
argomenti di funzione  1
• Per passare un array multidimensionale come argomento di funzione
è sufficiente specificarne il nome: il valore passato è un puntatore
all’elemento iniziale dell’array che è ancora un array
• Nella funzione chiamata, l’argomento deve essere dichiarato in modo
appropriato
int f1()
{
static int ar[5][6];
… … …
f2(ar);
… … …
}
void f2(received_arg)
int received_arg[][6];
{
… … …
}
int (*received_arg)[6];
• È possibile omettere la dimensione dell’array che viene passato, ma
è necessario specificare la dimensione di ogni elemento dell’array
Anno accademico 2010-2011
8
Array multidimensionali come
argomenti di funzione  2
• Una modalità alternativa consiste nel passare esplicitamente un
puntatore al primo elemento e la dimensione dell’array
int f1()
{
static int ar[5][6];
… … …
f2(ar,5,6);
… … …
}
void
f2(received_arg,dim1,dim2)
int **received_arg;
int dim1,dim2;
{
… … …
}
È un puntatore a un puntatore a int
• Il vantaggio di questo approccio è la flessibilità: non occorre
conoscere a priori la dimensione degli elementi dell’array; occorre
però
calcolare
manualmente
l’aritmetica
degli
indici:
received_arg[x][y] è memorizzato all’indirizzo
received_arg  xdim2  y
Anno accademico 2010-2011
9
Esempio  1
• Scrivere una funzione che determina il tipo del risultato di
un’espressione binaria in base ai tipi degli operandi
include <stdio.h>
typedef enum {SPECIAL2, ILLEGAL, INT, FLOAT,
DOUBLE, POINTER, LAST} TYPES;
TYPES type_needed(type1,type2)
TYPES type1, type2;
{
static TYPES result_type[LAST][LAST]  {
/*
int
float
double
pointer
/*int*/
/*float*/
/*double*/
/*pointer*/
};
TYPES
INT,
FLOAT,
DOUBLE,
POINTER,
FLOAT,
FLOAT,
DOUBLE,
ILLEGAL,
DOUBLE,
DOUBLE,
DOUBLE,
ILLEGAL,
POINTER,
ILLEGAL,
ILLEGAL,
SPECIAL
*/
La funzione riceve
due argomenti interi
che rappresentano i
tipi degli operandi e
fornisce un intero che
rappresenta il tipo
del risultato
result  result_type[type1][type2];
(result  ILLEGAL)
printf(“Operazione scorretta su puntatori\n”);
return result;
if
}
Anno accademico 2010-2011
10
Esempio  2
• La parte principale del programma è costituita dalla
dichiarazione ed inizializzazione dell’array result_type:
 Ogni tipo di dati viene fatto corrispondere ad un valore intero
per mezzo della dichiarazione enum
• In base alle modalità di definizione dell’array bidimensionale, i
due valori di ingresso sono indici, che individuano
univocamente l’elemento dell’array corrispondente al tipo del
risultato
• La dichiarazione enum assicura che ogni costante venga
associata ad un unico valore intero e che LAST rappresenti il
numero totale di tipi (viene usato nella dichiarazione
dell’array)
11
Anno accademico 2010-2011
Esempio  3
• La stessa dichiarazione (almeno per il compilatore) avrebbe
potuto essere scritta per mezzo di interi
char result_type[4][4]{0,1,2,3,1,1,2,1,2,2,2,1,3,1,1,2};
diminuendo sensibilmente la comprensibilità e la mantenibilità
del programma
• Nel caso SPECIAL, l’operazione è corretta solo se i puntatori
riferiscono oggetti dello stesso tipo e l’operatore è il segno
meno: il risultato è un int
12
Anno accademico 2010-2011
Errori di accesso ad array multidimensionali
ar[1,2]  0;
ar[1][2]  0;
/* Lecito, ma probabilmente scorretto */
/* Corretto */
• Nella prima istruzione…
 …la virgola viene interpretata come operatore, si valuta quindi
espressione1, che vale 1 ed il cui risultato non viene utilizzato e,
successivamente, espressione2, che vale 2 (le due espressioni
sono costanti)
 …si ottiene l’accesso ad ar[2]
• Se ar è un array bidimensionale di int, ar[2] è un puntatore
ad int (costante, ma potrebbe anche essere non valido)
 Viene segnalato un errore di incompatibilità di tipo: fuorviante
dato che la causa dell’errore è l’uso della virgola
13
Anno accademico 2010-2011
Gli array di puntatori  1
• Si consideri la dichiarazione:
char *ar_of_p[5];
La variabile ar_of_p è un array di cinque elementi di tipo
puntatore a carattere e non un puntatore ad un array di
cinque caratteri
• L’operatore di accesso all’elemento di un array “[]” ha
precedenza superiore all’operatore di accesso all’indirizzo
contenuto in un puntatore
• I puntatori non sono stati inizializzati, per cui puntano a
posizioni di memoria qualsiasi
14
Anno accademico 2010-2011
Gli array di puntatori  2
996
• Esempio:
char *ar_of_p[5];
char c0=‘a’;
char c1=‘b’;
ar_of_p[0]
2000
1000
ar_of_p[1]
2001
1004
ar_of_p[2]
non definito
1008
ar_of_p[3]
non definito
100C
ar_of_p[4]
non definito
1010
ar_of_p[0]=&c0;
ar_of_p[1]=&c1;
1014
1FFF
c0
a
2000
c1
b
2001
2002
15
Anno accademico 2010-2011
Esempio array di puntatori  1
• Gli array di puntatori vengono usati per gestire array di stringhe
• Esempio: Realizzare una funzione che, dato un intero compreso fra
1 e 12, in ingresso, stampa il nome del mese corrispondente
include <stdio.h>
include <stdlib.h>
char *month_text(m)
int m;
{
static char *month[13]  {“Badmonth”, “January”, “February”, “March”, “April”,
“May”, “June”, “July”, “August”, “September”, “October”,
“November”, “December”
};
if (m>12)
{
printf(“Valore scorretto”);
exit(1);
}
return month[m];
}
16
Anno accademico 2010-2011
Esempio array di puntatori  2
• La variabile month è un array di puntatori a char costituito
da 13 elementi: come conseguenza dell’inizializzazione, ogni
puntatore fa riferimento all’elemento iniziale di una stringa
• La motivazione dell’uso di un puntatore aggiuntivo con un
valore inutile consiste nel non voler effettuare sottrazioni
dall’indice: è comune non utilizzare l’elemento iniziale di un
array quando il valore dell’indice comincia logicamente da 1
• Non definendo “Badmonth”, si dovrebbe cambiare l’istruzione di ritorno al chiamante in
return month[m1];
17
Anno accademico 2010-2011
Esempio array di puntatori  3
Nota:
•
•
I caratteri che costituiscono
una stringa devono essere
consecutivi
Le stringhe corrispondenti ai
nomi dei mesi vengono
memorizzate dal compilatore
in qualunque posizione libera
della memoria
‘B’
2000
‘F’
2011
‘a’
2001
‘e’
2012
‘d’
2002
‘b’
2013
‘m’
2003
‘r’
2014
‘o’
2004
‘u’
2015
‘n’
2005
‘a’
2016
month[0]
2000
1000
month[1]
2009
1004
month[2]
2011
1008
month[3]
2500
100C
month[4]
2800
1010
‘t’
2006
‘r’
2017
month[5]
3000
1014
‘h’
2007
‘y’
2018
month[6]
3006
1018
‘\0’
2008
‘\0’
2019
month[7]
300A
101C
‘J’
2009
month[8]
300F
1020
‘a’
200A
‘M’
2500
month[9]
4000
1024
‘n’
200B
‘a’
2501
month[10]
400A
1028
‘u’
200C
‘r’
2502
‘a’
200D
‘c’
4011
102C
2503
‘r’
200E
‘h’
2504
401A
1030
‘y’
200F
‘\0’
2505
‘\0’
2010
month[11]
month[12]
18
Anno accademico 2009-2010
I puntatori a puntatori  1
• I puntatori a puntatori sono costrutti usati in programmi
sofisticati: per dichiarare un puntatore a puntatore occorre
far precedere il nome della variabile da due asterischi
consecutivi
int **p;
dichiara p come puntatore ad un puntatore ad int
• Per accedere al valore dell’int, è necessario utilizzare i doppi
asterischi:
assegna un intero a j
j  **p;
19
Anno accademico 2010-2011
I puntatori a puntatori  2
• Esempio:
4 byte
int r  5;
int *q  &r;
int **p  &q;
r
5
99C
q
99C
1004
p
1004
100C
È possibile assegnare valori ad r come:
r10;
/*Assegnamento diretto*/
*q10; /*Assegnamento con un livello di indirezione*/
**p10; /*Assegnamento con due livelli di indirezione*/
20
Anno accademico 2010-2011
Esempio 1: Matrice identità
/* Codice per la costruzione di I (matrice identità) */
#include<stdlib.h>
#include<stdio.h>
main()
{
int id[100][100];
int n, i, j;
printf(“Introdurre la dimensione della matrice identità\n”);
scanf(“%d”, &n);
for (i0; in; i)
for (j0; jn; j)
id[i][j]  (ij)?1:0;
exit(0);
}
21
Anno accademico 2010-2011
Esempio 2: Matrice simmetrica
/* Si legge una matrice quadrata
** composta da numeri reali
** e si stabilisce se è simmetrica
*/
#include <stdio.h>
#include <stdlib.h>
#define DIM 100
main()
{
char r, c, sim;
float a[DIM][DIM];
/* Lettura della matrice a */
for(r0;rDIM;r)
{
for(c0;c<DIM;c)
scanf(“%f”,&a[r][c]);
}
/* Si valuta se a è simmetrica… */
sim  1;
r  0;
do
{
c  r  1;
do
{
if (a[r][c] ! a[c][r])
sim  0;
c;
} while (c<DIM && sim1);
r;
} while (r<DIM1 && sim1);
if (sim1)
printf(“Matrice simmetrica”);
else
printf(“Matrice non simmetrica”);
exit(0);
}
Anno accademico 2010-2011
22
Esempio 3: Prodotto matricevettore
/*
**
**
**
**
*/
Funzione per il calcolo di Ab, con…
A: matrice mn di float (in input)
b: vettore di dimensione n di float (in input)
m, n: interi, numero di righe e colonne di A (in input)
x: vettore di float di dimensione m, risultato (in output)
float *prod_mv(a, b, m, n, x)
float a[][100], b[], x[]; /* ma, nella funzione, sono puntatori */
int m, n;
{
int i, j;
for (i0; im; i)
{
x[i]  0.0;
for (j0; jn; j)
x[i]  a[i][j]b[j];
}
return x;
}
Anno accademico 2010-2011
23
Esempio 4: Prodotto matricematrice
• Problema
Calcolo della matrice prodotto AB, con A e B matrici
rettangolari di dimensioni, rispettivamente, mn e nc 
24
Anno accademico 2010-2011
L’allocazione dinamica della memoria  1
• Dichiarare array equivale a fare un’ipotesi (una stima) sulla
dimensione massima possibile dei vettori che potranno essere
fonte di elaborazione per il particolare programma
 Si suppone di conoscere la quantità di memoria da allocare
nel momento in cui si scrive il codice sorgente
 Generalmente si sovrastima, quindi si spreca memoria
 Se la stima è sufficientemente stringente per la situazione
corrente, può essere una sottostima per il futuro (occorre
aggiornare il sorgente)
• Di norma, l’occupazione di memoria dipende strettamente dai
dati in ingresso
25
Anno accademico 2010-2011
L’allocazione dinamica della memoria  2
• In C, esistono quattro funzioni della libreria di runtime
(stdlib.h) che permettono l’allocazione dinamica della
memoria
 malloc()  alloca un numero specificato di byte in memoria e
restituisce un puntatore all’inizio del blocco allocato
 calloc()  come malloc(), ma inizializza a zero i byte
allocati; consente di allocare la memoria per più di un oggetto
alla volta
 realloc()  cambia la dimensione di un blocco precedentemente allocato
 free()  libera la memoria che era stata allocata con
malloc(), calloc() o realloc()
26
Anno accademico 2010-2011
L’allocazione dinamica della memoria  3
• Esempio:
include <stdio.h>
include <stdlib.h>
•
main()
{
extern void bubble_sort();
int *list, j, sort_num;
•
printf(“Numero dei valori da introdurre:”);
scanf(“%d”, &sort_num);
list(int *)malloc(sort_numsizeof(int));
for (j0; j<sort_num; j)
scanf(“%d”, listj);
bubble_sort(list, sort_num);
exit(0);
L’argomento di malloc() è la dimensione in byte del blocco da allocare
Usando calloc(), l’istruzione di allocazione della memoria sarebbe
list=(int*)calloc(sort_num,sizeof(int));
•
•
La funzione calloc() accetta due argomenti: il primo è il numero di oggetti a
cui riservare memoria, il secondo è la
dimensione di ciascun oggetto
Le funzioni malloc() e calloc() memorizzano gli elementi in modo contiguo
in un singolo blocco
}
27
Anno accademico 2010-2011