DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Recap su: array e puntatori
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 20 Aprile 2015
Sui codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
2
Sui codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
3
Sui codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
4
Sui codici a lunghezza fissa
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
5
Ore extra
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Molti del 3zo anno non riesco a venire
al giovedì pomeriggio…
6
Ore extra
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Molti del 3zo anno non riesco a venire
al giovedì pomeriggio…
 Possiamo fregarcene
7
Ore extra
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Molti del 3zo anno non riesco a venire
al giovedì pomeriggio…
 Possiamo fregarcene
 O trovare una soluzione
8
Ore extra
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Molti del 3zo anno non riesco a venire
al giovedì pomeriggio…
 Possiamo fregarcene
 O trovare una soluzione
• Mar dalle 2pm alle 3pm
• Gio dalle 7am alle 8am
9
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Un ripasso generale sul C
• In particolare
 Array multi-dimensionali
 Dati strutturati e passaggio a funzioni
10
Problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperato un cubo di caratteri, dice
quante ‘a’ vi sono contenute.
 La dimensione del cubo è: 2x3x4
11
Sotto-problemi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperato un cubo di caratteri, dice
quante ‘a’ vi sono contenute.
 La dimensione del cubo è: 2x3x4
• Sotto-problemi
 P0: cubo di caratteri
 P1: Popolare il cubo di caratteri
 P2: Contare le ‘a’
12
Cubo di caratteri
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• La dimensione del cubo è: 2x3x4
#define dx 3
#define dy 2
#define dz 4
char data[dx][dy][dz];
13
Array in memoria
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
char data[dx];
array di dx char (dx:3)
09
00
01
data[0]
0A
02
data[1]
0B
03
data[2]
0C
04
0D
05
0E
06
0F
07
10
08
11
14
Matrice (array di array) in memoria
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
char data[dx];
char data[dx][dy];
array di dx char (dx:3)
array di dx array (dx:3)
array di dy char (dy:2)
09
00
01
02
03
04
05
06
[0]
data[0][0]
[0]
[1]
data[0][1]
0A
data[1][0]
[0]
[1]
data[1][1]
[1]
data[2][0]
[0]
[2]
data[2][1]
[1]
0C
0B
0D
0E
0F
07
10
08
11
15
Un array 3D
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
char data[dx];
array di dx char
char data[dx][dy]; array di dx array di dy char
char data[dx][dy][dz]
array di dx array (dx:3)
array di dy array (dy:2)
array di dz char (dz:4)
16
In memoria, macchina a 32bit, e.g. x86
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
char data[dx][dy][dz]
00
dx:3, dy:2, dz:4
09
data[1][0][0]
01
[0]
data[0][0][0]
0A
data[1][0][1]
02
data[0][0][1]
[0]
data[0][0][2]
0B
data[1][0][2]
0C
0D
05
data[0][0][3]
[0]
data[0][1][0]
data[1][0][3]
[1]
data[1][1][0]
0E
data[1][1][1]
06
data[0][1][1]
0F
data[1][1][2]
07
data[0][1][2]
10
data[1][1][3]
08
data[0][1][3]
11
data[2][0][0]
03
04
17
Torniamo al problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperato un cubo di caratteri, dice
quante ‘a’ vi sono contenute. La
dimensione del cubo è: 2x3x4
• Sotto-problemi
 P0: cubo di caratteri
 P1: Popolare il cubo di caratteri
 P2: Contare le ‘a’
18
P1: popolare il cubo di char
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Serve una funzione che
 Recuperato il cubo
void popola(char *p, int x, int y, int z);
 Permette l’inserimento dei caratteri
19
P2: contare le ‘a’
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Serve una funzione che
 Recuperato il cubo
int foo2(char p[][dy][dz], char x);
 Scorre gli elementi per cercare le ‘a’
20
Problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperati i cognomi di 5 studenti, li
ordina alfabeticamente
21
Sotto-problemi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperati i cognomi di 5 studenti, li
ordina alfabeticamente
• Sotto-problemi
 P0: rappresentare i cognomi
 P1: recuperare i cognomi
 P2: ordinare i cognomi alfabeticamente
22
P0: rappresentare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Vi sono diversi modi…
• Noi, per esercitarci,
 creiamo una struttura e
 definiamo un nuovo tipo di dato
23
dati
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dopo aver definito studente
• Dobbiamo creare 5 studenti
studente studenti[5];
24
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
25
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
26
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “l’array”
27
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “l’array”
p[i].cognome;
28
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “l’array”
p[i].cognome;
p: l’indirizzo base - [i]: la posizione
p[i]: è l’elemento di interesse
.: accedo a - cognome: il campo
29
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
30
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “il puntatore”
31
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “il puntatore”
(*(p+i)).cognome;
32
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare “il puntatore”
(*(p+i)).cognome;
p: l’indirizzo base - i: la posizione
(*(p+i)): è l’elemento di interesse
.: accedo a - cognome: il campo
33
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
34
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare veramente “il puntatore”
35
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare veramente “il puntatore”
 Con una “freccia”
(p+i)->cognome;
36
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Studenti è un array… si passa per
indirizzo
void ins_alunno(studente *p, int dimensione);
• studente è “strutturato” come accedo ai
campi attraverso un puntatore?
 Posso sfruttare veramente “il puntatore”
 Con una “freccia”
(p+i)->cognome;
p+i: è l’indirizzo dell’elemento di interesse
->: accedo a, tramite ind. - cognome: il campo
37
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
38
P2: ordinare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Come faccio ad ordinare i cognomi?
 Vi è differenza nell’ordinare studente rispetto
ad ordinare int?
• Ma quindi il problema è…
 Come ordino N interi???
39
Ordiniamo N interi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 Dati: 4, 3, 1, 2
 Voglio ottenere: 1, 2, 3, 4
• Iniziamo ad ipotizzare una soluzione
 Confronto gli elementi a due a due e se non
sono nell’ordine corretto, inverto i valori
40
Ordino 4, 3, 1, 2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Confronto gli elementi a due a due e se
non sono nell’ordine corretto, inverto i
valori
Dati: 4, 3, 1, 2
4 > 3?
Si, inverto: 3, 4, 1, 2
4 > 1?
Si, inverto: 3, 1, 4, 2
4 > 2?
Si, inverto: 3, 1, 2, 4
41
Da 4, 3, 1, 2 a 3, 1, 2, 4…
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Problema
 3, 1, 2, 4 è ordinato?
 Basta confrontare a due a due gli
elementi?
NO!!!
Devo confrontare a due a due
TUTTI (quasi vero) gli elementi
42
Facciamolo su tutti
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dato vet[4]={4, 3, 1, 2}
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
ci porta da 4, 3, 1, 2
a 3, 1, 2, 4
Ma questo vogliamo farlo su tutti gli elementi
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
43
E quindi… i=0
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dato vet[4]={4, 3, 1, 2}
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
i=0, vario j
ci porta da 4, 3, 1, 2 a 3, 1, 2, 4
j=0: 4 > 3?
Si, inverto: 3, 4, 1, 2
j=1: 4 > 1?
Si, inverto: 3, 1, 4, 2
j=2: 4 > 2?
Si, inverto: 3, 1, 2, 4
44
E quindi… i=1
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dato vet[4]={4, 3, 1, 2}
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
i=0, vario j
ci porta da 4, 3, 1, 2 a 3, 1, 2, 4
i=1, vario j
ci porta da 3, 1, 2, 4 a 1, 2, 3, 4
j=0: 3 > 1?
Si, inverto: 1, 3, 2, 4
j=1: 3 > 2?
Si, inverto: 1, 2, 3, 4
j=2: 3 > 4?
No, non faccio nulla: 1, 2, 3, 4
45
E quindi… i=2
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dato vet[4]={4, 3, 1, 2}
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
i=0, vario j
ci porta da 4, 3, 1, 2 a 3, 1, 2, 4
i=1, vario j
ci porta da 3, 1, 2, 4 a 1, 2, 3, 4
i=2, vario j
ci porta da 1, 2, 3, 4 a 1, 2, 3, 4
j=0: 1 > 2?
No, non faccio nulla: 1, 2, 3, 4
j=1: 2 > 3?
No, non faccio nulla: 1, 2, 3, 4
j=2: 3 > 4?
No, non faccio nulla: 1, 2, 3, 4
46
E quindi… i=3
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Dato vet[4]={4, 3, 1, 2}
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
i=0, vario j
ci porta da 4, 3, 1, 2 a 3, 1, 2, 4
i=1, vario j
ci porta da 3, 1, 2, 4 a 1, 2, 3, 4
i=2, vario j
ci porta da 1, 2, 3, 4 a 1, 2, 3, 4
i=3, vario j
ci porta da 1, 2, 3, 4 a 1, 2, 3, 4
j=0: 1 > 2?
No, non faccio nulla: 1, 2, 3, 4
j=1: 2 > 3?
No, non faccio nulla: 1, 2, 3, 4
j=2: 3 > 4?
No, non faccio nulla: 1, 2, 3, 4
47
Ordinamento, qualche osservazione
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Si può migliorare?
for(i=0;i<dimensione;i++)
for(j=0;j<dimensione-1;j++)
è vero che vet[j]>vet[j+1]?
•Nel for innestato
 Mi serve davvero arrivare a dimensione-1?
•Nel for esterno,
 mi serve veramente arrivare a dimensione?
48
P2: ordinare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come faccio ad ordinare i cognomi?
49
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 Tutte le slide precedenti del corso di IEIM 2013/2014
50