2 4 3 0 / 1 - Politoelite.polito.it/files/courses/06AZN/lucidi/C/L6.4-up.pdf · Title: L6.4_v8...
7
Click here to load reader
Transcript of 2 4 3 0 / 1 - Politoelite.polito.it/files/courses/06AZN/lucidi/C/L6.4-up.pdf · Title: L6.4_v8...
Matrici – Vettori di stringhe
2
Vettori di stringhe
Matrici di caratteri
Vettori di stringhe
I/O di vettori di stringhe
Vettori di stringhe
4
Matrici di caratteri
Nel definire una matrice, è ovviamente possibile usare il tipo base charcharcharchar
Permette di memorizzare una tabella NxM di caratteri ASCII
Ogni posizione [i][j] deve contenere un carattere
Non può essere vuota
Non può contenere più di un carattere
charcharcharchar tris[3][3] ;....X..XO
210
210
5
Esercizio “Verifica Sudoku”
Si realizzi un programma in C che verifichi la corretta soluzione della griglia di un “Sudoku”
Il programma acquisisce da tastiera la griglia 9x9, in cui ciascun elemento è un carattere tra 1 e 9
Il programma deve verificare se il Sudoku è stato correttamente risolto
6
Esempio
971682543
536914782
482735169
658429317
197358624
324167958
765243891
843591276
219876435
7
Analisi
Tutti i valori devono essere singoli caratteri tra ‘1’ e ‘9’
Su ciascuna delle 9 righe, non devono esserci valori ripetuti
Su ciascuna delle 9 colonne, non devono esserci valori ripetuti
In ciascuno dei 9 blocchi 3x3, non devono esserci valori ripetuti
8
Soluzione (1/10)
const int const int const int const int N = 9 ;
char char char char sudoku[N][N] ;
intintintint i, j, k ; /* indici dei cicli */intintintint r1, c1, r2, c2 ;charcharcharchar ch ;intintintint err, good ; /* flag */
printf("Verifica Sudoku\n") ;
sudoku.c
9
Soluzione (2/10)
forforforfor(i=0; i<N; i++){
printf("Riga %d:\n", i+1) ;forforforfor(j=0; j<N; j++){
sudoku[i][j] = ch ;}
}
sudoku.c
Acquisisci un caratterech tra ‘1’ e ‘9’
10
Soluzione (2/10)
forforforfor(i=0; i<N; i++){
printf("Riga %d:\n", i+1) ;forforforfor(j=0; j<N; j++){
sudoku[i][j] = ch ;}
}
sudoku.c
Acquisisci un caratterech tra ‘1’ e ‘9’
dodododo {printf(" Colonna %d: ", j+1) ;ch = getchar() ;ifififif( ch<'1' || ch>'9' )
printf("Errata - ripeti\n") ;
/* elimina fino fine linea */whilewhilewhilewhile( getchar()!='\n')
/*nop*/ ;
} whilewhilewhilewhile( ch<'1' || ch>'9') ;
11
Soluzione (3/10)
/* Stampa il tabellone */forforforfor(i=0; i<9; i++){
forforforfor(j=0; j<9; j++){
printf("%c ", sudoku[i][j]) ;
ifififif(j==2 || j==5)printf(" ") ;
}printf("\n");
ifififif(i==2 || i==5)printf("\n") ;
}
sudoku.c
12
Soluzione (4/10)
good = 1 ; /* flag generale *//* flag generale *//* flag generale *//* flag generale */
/* Verifica le righe */forforforfor(i=0; i<N; i++){
printf("Riga %d: ", i+1) ;err = 0 ;
/* ricerca duplicati su col. j,k */forforforfor(j=0; j<N; j++)
forforforfor(k=j+1; k<N; k++)ifififif(sudoku[i][j]==
sudoku[i][k])err = 1 ;
sudoku.c
13
Soluzione (5/10)
ifififif(err==0)printf("OK\n");
elseelseelseelse{
printf("Errore!\n");good = 0 ;
}}
sudoku.c
14
Soluzione (6/10)
forforforfor(i=0; i<N; i++) /* Colonne */{ printf("Colonna %d: ", i+1) ;
err = 0 ; /* ricerca dupl. su righe j,k */forforforfor(j=0; j<N; j++)forforforfor(k=j+1; k<N; k++)ifififif(sudoku[j][i]==sudoku[k][i])err = 1 ;
ifififif(err==0) printf("OK\n");elseelseelseelse{ printf("Errore!\n");
good = 0 ;}
}
sudoku.c
15
Ricerca per blocchi
971682543
536914782
482735169
658429317
197358624
324167958
765243891
843591276
219876435
16
Ricerca per blocchi
971682543
536914782
482735169
658429317
197358624
324167958
765243891
843591276
219876435
i
j
i+2
j+2
17
Ricerca per blocchi
971682543
536914782
482735169
658429317
197358624
324167958
765243891
843591276
219876435
i
j
i+2
j+2
r1,c1
r2,c2
18
Soluzione (7/10)
forforforfor(i=0; i<N; i=i+3){forforforfor(j=0; j<N; j=j+3){printf("Blocco (%d,%d)-(%d,%d): ",
i+1, j+1, i+3, j+3) ;
/* ricerca duplicati nel blocco *//* Confronta [r1][c1]
con [r2][c2] */
err = 0 ;
sudoku.c
19
Soluzione (8/10)
forforforfor(r1=i; r1<i+3; r1++)forforforfor(c1=j; c1<j+3; c1++){ /* elemento [r1][c1]... */
forforforfor(r2=i; r2<i+3; r2++)forforforfor(c2=j; c2<j+3; c2++){
/* ..rispetto a [r2][c2] */ifififif( ((r1!=r2)||(c1!=c2)) &&
sudoku[r1][c1]==sudoku[r2][c2] )
{err = 1 ;
}} /*r2,c2*/
} /*r1,c1*/
sudoku.c
20
Soluzione (9/10)
ifififif(err==0)printf("OK\n");
elseelseelseelse{
printf("Errore!\n");good = 0 ;
}} /*j*/
} /*i*/
sudoku.c
21
Soluzione (10/10)
ifififif(good==1)printf("Sudoku valido!\n");
elseelseelseelseprintf("Sudoku errato...\n");
sudoku.c
Vettori di stringhe
23
Vettori di stringhe
Una matrice di caratteri può anche essere vista come:
Un vettore di vettori di caratteri, cioè
Un vettore di stringhe
Si tratta di un metodo diverso di interpretare la stessa struttura dati
24
Esempio
charcharcharchar tris[3][3] ;....X..XO
210
210
charcharcharchar nomi[5][10] ;
u\0anitsirCZ.\0oinotnA
ve
l
\05
\0
e\0
o
da
i
in
v
al
u
DE
F
ed
w
2r
!
$g
x
21
43
0210 6543 987
25
Caratteristiche
charcharcharchar nomi[5][10] ;
u\0anitsirCZ.\0oinotnA
ve
l
\05
\0
e\0
o
da
i
in
v
al
u
DE
F
ed
w
2r
!
$g
x
21
43
0210 6543 987
5 stringhe di lunghezza variabile
Lunghezza max 9 caratteri Terminatore
nullo in ogni stringa (riga)
26
Sintassi
Definizione
charcharcharchar vett[MAX][LUN] ;
Nome del vettore di stringhe
Lunghezzza massima di ciascuna stringa (compreso terminatore nullo)
Numero di stringhe
27
Sintassi
Definizione
Accesso al singolo carattere
charcharcharchar vett[MAX][LUN] ;
Carattere (j+1)-esimo della stringa (i+1)-esima, da usarsi per
l’elaborazione carattere-per-carattere
vett[i][j]
28
Sintassi
Definizione
Accesso al singolo carattere
Accesso all’intera stringa
charcharcharchar vett[MAX][LUN] ;
vett[i][j]
vett[i]
Stringa (i+1)-esima, da usarsi con le funzioni di libreria
29
Esempio 1
Dato un vettore di stringhe, determinare quante volte è presente la lettera ‘A’ (maiuscola o minuscola)
cont = 0 ;forforforfor(i=0; i<MAX; i++){
forforforfor(j=0; vett[i][j]!=0; j++){
ifififif(toupper(vett[i][j])=='A')cont++ ;
}}
30
Esempio 2
Dato un vettore di stringhe, determinare se esistono due stringhe identiche
uguali = 0 ;forforforfor(i=0; i<MAX; i++){
forforforfor(k=i+1; k<MAX; k++){
ifififif(strcmp(vett[i], vett[k])==0)uguali=1 ;
}}
31
Occupazione variabile
In un vettore di stringhe, ogni riga (ogni stringa) è intrinsecamente un vettore di caratteri ad occupazione variabile
Terminatore nullo per indicare la lunghezza effettiva
Il numero di stringhe effettivamente memorizzato potrebbe non riempire l’intero vettore
Variabile intera che indica l’effettiva occupazione del vettore
32
Esempio
constconstconstconst intintintint MAX = 5 ;constconstconstconst intintintint LUN = 9 ;
charcharcharchar nomi[MAX][LUN+1] ;int N ;
u\0anitsirCZ.\0oinotnA
<1
l
g5
\0
e\0
o
da
i
d)
v
%4
u
1e
F
ed
w
2r
!
$g
x
21
43
0210 6543 987
N=3
33
Errore frequente
Confondere una stringa (vettore di caratteri) con un vettore di stringhe (matrice di caratteri)
charcharcharchar s[LUN+1] ; charcharcharchar v[MAX][LUN+1] ;
• s[i] è un singolo carattere
• s è l’intera stringa
• v[i][j] è il singolo carattere
• v[i] è un’intera stringa• v è l’intera matrice
Vettori di stringhe
35
Stampa (1/2)
La stampa del contenuto di un vettore di stringhe si ottiene semplicemente stampando ciascuno degli elementi
Si può utilizzare puts oppure printf
36
Stampa (2/2)
forforforfor(i=0; i<N; i++){
puts(vett[i]) ;}
vettstr.c
37
Lettura
Acquisire da tastiera un vettore di stringhe
Un ciclo per ciascuna delle stringhe da leggere
Lunghezza nota a priori
Lunghezza determinata dalla lettura di un certo dato (es.: “FINE”)
Acquisizione, nel ciclo, di ciascuna delle stringhe
Utilizzo della funzione gets
Eventualmente, lettura in una stringa d’appoggio per la verifica di correttezza, prima di ricopiare nel vettore destinazione
38
Dimensione nota a priori (1/2)
charcharcharchar vett[MAX][LUN+1] ;charcharcharchar s[250] ;. . .. . .. . .. . .
dodododo {printf("Quante stringhe? ") ;gets(s) ;N = atoi(s) ;ifififif(N<1 || N>MAX)
printf("Valore errato: deve essere tra 1 e %d\n", MAX) ;
} whilewhilewhilewhile(N<1 || N>MAX) ;
vettstr.c
39
Dimensione nota a priori (2/2)
forforforfor(i=0; i<N; i++){ printf("Stringa %d: ", i+1) ;
gets(s) ;ifififif (strlen(s)==0){ printf("Vuota - ripeti\n");
i-- ;}else else else else ifififif(strlen(s)>LUN){ printf("Troppo lunga –
max %d chr\n", LUN) ;i-- ;
}elseelseelseelse
strcpy(vett[i], s) ;}
vettstr.c
40
Lettura terminata da “FINE”
N = 0 ;end = 0 ;dodododo {
printf("Stringa %d: ", N+1) ;gets(s) ;ifififif (strlen(s)==0)
printf("Vuota - ripeti\n");else else else else ifififif(strlen(s)>LUN)
printf("Troppo lunga\n") ;else else else else ifififif(strcmp(s, "FINE")==0)
end = 1 ;elseelseelseelse{ strcpy(vett[N], s) ;
N++ ;}
} whilewhilewhilewhile(end==0) ;
vettstr.c
