DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Recap sul C
Marco D. Santambrogio – [email protected]
Ver. aggiornata al 11 Aprile 2013
Feedback
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• NUOVO, per le exe:
http://tinyurl.com/IEIMExe2013
• Per i lab:
http://tinyurl.com/Feedback-LabIEIM2013
• Per le lezioni:
http://tinyurl.com/Feedback-IEIM2013
2
WAT
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• 8 Maggio, sospesione lezione!
 No homework!!
W
A
T
3
WAT
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Da feedback
 l'esercitatore era troppo veloce.... ahahah
4
Obiettivi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Un ripasso generale sul C
• In particolare
 Array multi-dimensionali
 Dati strutturati e passaggio a funzioni
5
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
6
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’
7
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];
8
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
9
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
10
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)
11
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
12
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’
13
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
14
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’
15
Problema
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Si scriva in C un programma che,
recuperati i cognomi di 5 studenti, li
ordina alfabeticamente
16
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
17
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
18
dati
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Dopo aver definito studente
• Dobbiamo creare 5 studenti
studente studenti[5];
19
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?
 Con una “freccia”
p->cognome;
20
P1: recuperare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
21
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???
22
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
23
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
24
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
25
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++)
26
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
27
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
28
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
29
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
30
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?
31
P2: ordinare i cognomi
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
Come faccio ad ordinare i cognomi?
32
Fonti per lo studio + Credits
DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE
• Fonti per lo studio
 Tutte le slide precedenti del corso di IEIM 2012/2013
33