9.3 Implementazione delle operazioni elementari sugli array
9.3.6 Conteggio ed esistenza
Per contare quanti elementi di a godono di una determinata proprietà (nell'esempio essere pari) si usa un contatore
conta=0;
for(i=0; i<n; i++) if(a[i]%2==0) conta++;
Per controllare se esiste un elemento che gode di una proprietà (nell'esempio sempre essere pari), si può usare una variabile bool e l'istruzione break
bool trovato=false; for(i=0;i<n;i++) if(a[i]%2==0) { trovato=true; break; }
Per controllare se tutti gli elementi godono della proprietà è sufficiente controllare che non esiste un elemento che gode della proprietà contraria (essere dispari)
bool tutti=true; for(i=0;i<n;i++)
if(a[i]%2!=0) { // trovato un elemento dispari tutti=false;
break; }
9.3.7 Filtro
Per copiare in un array b (di dimensione n) solo gli elementi di a che godono di una certa proprietà (nell'esempio sempre essere pari)
j=0;
for(i=0; i<n; i++) if(a[i]%2==0) {
b[j]=a[i]; j++;
}
In questa operazione gli elementi di a sono copiati in posizioni consecutive in b senza lasciare spazi vuoti.
Ad esempio se A contiene gli elementi (5,4,2,8,7,9,10,1), b conterrà (4,2,8,10) mentre le altre posizioni saranno vuote (o meglio inalterate). Gli elementi effettivamente inseriti in b sono j, in questo caso 4.
9.4 Array multidimensionali
Gli array multidimensionali sono una generalizzazione degli array visti fino ad adesso, che sono appunto monodimensionali. Tratteremo solo gli array bidimensionali (che chiameremo per brevità matrici), comunque le caratteristiche di array a più di due dimensioni sono molto simili.
Una matrice ha due dimensioni e viene rappresentata graficamente mediante una tabella, in cui la prima dimensione rappresenta il numero di righe e la seconda il numero di colonne. Ogni elemento è identificato dal numero di riga e di colonna (una sorta di coordinate cartesiane).
indici delle colonne
indici delle righe 0 1 2 3
0 7 8 -5 2
1 5 2 1 9
2 4 -3 -1 0
Una matrice si dichiara con la sintassi
tipo identificatore “[“ costante_intera_senza_segno “]” “[“ costante_intera_senza_segno “]” Ad esempio con
int a[3][4];
si dichiara una variabile a, matrice di interi di 3 righe e 4 colonne.
Per accedere agli elementi di una matrice si usa l'operazione di indicizzazione che opera con due indici. Ad esempio l'istruzione
r = a[1][2];
assegna alla variabile r il valore 1.
for(i=0;i<n;i++) {
for(j=0;j<m;j++) {
// fai qualcosa con a[i][j] }
}
Ad esempio per scrivere sullo schermo il contenuto della matrice a for(i=0; i<3; i++) {
for(j=0; j<4; j++)
cout << a[i][j] << “ “; cout << endl;
}
Tutte le altre operazioni elementari viste per gli array monodimensionali possono essere facilmente modificate per lavorare su array bidimensionali, inserendo sempre un doppio ciclo for.
Gli array bidimensionali sono in realtà visti dal C++ come array di array. Ad esempio double b[3][2];
dichiara un array b di 3 elementi (le righe) che a loro volta sono array di 2 double ciascuno. Per cui
b[0] 3 -2
b[1] 7 4
b[2] -1 0
Ciò spiega la notazione a[i][j] che in altri linguaggi, come in Pascal, è invece a[i,j]. Infatti a[i][j] andrebbe interpretato come (a[i])[j]. Ovvero con a[i] si seleziona la riga e con il secondo indice j si seleziona l'elemento all'interno della riga.
9.5 Le stringhe
Le stringhe, come abbiamo visto nel capitolo X, possono essere considerate sia come tipi elementari, sia come tipi strutturati. Le stringhe in C++ possono essere viste come array illimitati di char.
Le operazioni supportate dal linguaggio sono tante, tra le più importanti troviamo 1. assegnamento con =
2. confronto con <, >, >=, <=, == e !=
una stringa s è minore di una stringa t se s precede t nell'ordine lessicografico: se s è un prefisso di t (ovvero se t inizia con s, ad esempio “ba” < “bar”) oppure se nella prima posizione in cui s e t differiscono, s presenta un carattere che viene di quello di t nell'ordine ASCII, ad esempio “carota” < ”carta” dato che
| | | c a r t a e 'o' < 't'
3. concatenazione con +, ad esempio “car”+”te” ha come risultato “carte”
4. lunghezza con il metodo length, ad esempio se s vale “informatica”, s.length() ha come risultato 11
5. estrazione di sottostringa con il metodo substr, in cui si indica la posizione del primo carattere e il numero di caratteri da estrarre, ad esempio s.substr(2,5) ha come risultato “forma”
6. lettura da tastiera e scrittura sullo schermo come gli altri tipi di dato
Combinando length e substr si possono estrarre parti significative di una stringa. Ad esempio
s.substr(s.length( )-1,1) restituisce una stringa formata dal solo ultimo carattere di s
(nell'esempio “a”), mentre s.substr(0,s.length( )-1) restituisce una stringa uguale a s tranne l'ultimo elemento (nell'esempio “informatic”).
E' comunque possibile accedere, sia in lettura, sia in scrittura, all'i-esimo elemento di una stringa mediante l'indicizzazione, come se la stringa fosse un array. Ad esempio s[3] vale 'o'. Mentre
s[10]='o' fa sì che s diventi “informatico”.
Si noti che le stringhe sono implementate in C++ mediante una classe.
9.6 Le strutture (record)
Una struttura è un aggregazione di dati eterogenei per tipo. Per usare un tipo struttura bisogna elencare il nome ed il tipo di ciascuno degli elementi della struttura, detti campi.
La sintassi per indicare un tipo struttura è tipo_struttura ::= “struct” [ identificatore ] “{“ campi_stesso_tipo “;” { campi_stesso_tipo “;” } “}”
campi_stesso_tipo ::= tipo identificatore {, identificatore }
Ad esempio per dichiarare una variabile di nome p e di tipo struttura, avente i campi nome, cognome, età ed altezza si scrive
struct {
string nome, cognome; int eta;
double altezza; } p;
Si possono dichiarare sia più variabili aventi stessa struttura e anche array di strutture, come vedremo nella sezione successiva.
Per inizializzare una variabile di tipo struct si usa una sintassi simile a quella vista per inizializzare una variabile di tipo array:
struct {
string nome, cognome; int eta;
double altezza;
} q={“Mario”, “Rossi”, 35, 1.80};
E' possibile dare un nome alla struttura, in tal caso si può usare successivamente tale nome per dichiarare variabili di tale tipo di struttura.
Ad esempio
struct persona {
string nome, cognome; int eta;
double altezza; };
A questo punto nel sistema dei tipi utilizzabili in C++ è stato aggiunto il tipo persona. Si noti che in tale caso è obbligatorio chiudere la definizione con il punto e virgola.
A questo punto è possibile dichiarare delle variabili di tipo persona persona p1,p2;
La selezione di un campo di una variabile di tipo struttura avviene con la notazione punto: ad esempio p1.nome è un riferimento al campo nome della variabile p1.
Come per gli elementi di un array, anche per i campi di una struttura la selezione permette di leggere e di scrivere il valore in essi contenuto.
p1.nome=”Marco”; cout << p1.cognome;
La differenza più evidente tra la selezione degli elementi di un array e quelli prevista per le strutture è che nella prima l'indice può essere il risultato di un'espressione, cioè noto a tempo di esecuzione, mentre nella seconda il nome del campo è “costante”, cioè invariabile. Ciò è necessario perché avendo una struttura campi di tipo diverso un'eventuale indicizzazione non sarebbe un'operazione con un tipo definito. Si immagini p1[i]: è una stringa, un numero intero o un numero reale ?
Il dominio del tipo struct è il prodotto cartesiano dei domini dei rispettivi campi
Il C++ offre un minimo di operazioni in più rispetto agli array, infatti oltre alla selezione, è possibile anche effettuare assegnamenti su variabili di tipo struct e definire funzioni il cui risultato è di tipo struct, come vedremo nel capitolo 11.
L'assegnamento tra struct equivale ad un assegnamento tra campi corrispondenti. Ad esempio p1=p2; equivale a p1.nome=p2.nome; p1.cognome=p2.cognome; p1.eta=p2.eta; p1.altezza=p2.altezza;
9.7 Array di strutture
Array e strutture si possono comporre in modo arbitrario.
Ad esempio una struct può contenere altre struct e array, come nel seguente caso
struct studente { int matricola;
string nome, cognome; struct data {
int giorno, mese, anno; } data_nascita;
int voti[num_materie]; int num_esami;
};
Per accedere ai dati di una variabile s di tipo studente si userà, ad esempio, s.data_nascita.anno o s.voti[5].
Un'utile composizione tra array e strutture è data dagli array di strutture, ovvero dagli array i cui elementi sono strutture.
Partendo dalla struttura
struct persona {
string nome, cognome; int eta;
double altezza; };
è possibile dichiarare un array di elementi di tipo persona persona p[100];
La variabile p è rappresentabile come una tabella, con colonne identificate dai nomi dei campi della strutture e le righe dagli indici dell'array
indice nome cognome eta altezza
0 Mario Rossi 39 1,78
1 Lucia Verdi 32 1,7
...
99 Marisa Gialli 44 1,67
Per operare con gli elementi di p si deve specificare l'indice (della riga) e il nome del campo, ovvero della colonna. Ad esempio
cout << p[1].cognome;
Gli array di strutture sono particolarmente interessanti perché consentono di memorizzare l'equivalente di una tabella (ovvero di una relazione di un database relazionale), seppur con la limitazione del numero massimo di elementi. Alcuni esercizi di questo capitolo saranno dedicati proprio a questo tipo di impiego.
9.8 Le unioni
Le unioni sono una variante particolarissima delle struct. Infatti solo un campo alla volta di una union può contenere un valore. In altri termini appena si assegna un valore ad un campo di una union, tutti gli altri campi perdono di significato e non possono essere utilizzati.
La sintassi di union è praticamente identica a quella di struct. Ad esempio dichiarando una variabile
union { int a; double b; string c; } u;
non si può dare contemporaneamente un valore a due (o a tre) dei campi: il secondo assegnamento distruggerebbe il primo. Pertanto è come se u avesse (a scelta) solo uno tra i possibili campi a,b e c. Ad esempio
u.a=10;
cout << u.a << endl;
cout << u.b << endl; // illegale cout << u.c << endl; // illegale u.b=4.3;
cout << u.a << endl; // ora è illegale cout << u.b << endl;
cout << u.c << endl; // illegale u.c=”abc”;
cout << u.c << endl;
Il motivo di tale comportamento è che tutti i campi di una unione usano la stessa zona di memoria. Una variabile di tipo unione è utile in situazione estremamente particolari. Ad esempio si usa quando si vuole avere una variabile che può assumere valori appartenenti a tipi diversi e incompatibili tra di loro: infatti il dominio di un tipo union è l'unione dei domini dei campi che ne fanno parte.
Un'altra situazione in cui ha senso usare una union è quella di simulare i record con varianti, che sono presenti in altri linguaggi, ad esempio in Pascal.
Ad esempio se vogliamo avere dati diversi per uomini e per donne si possono definire
struct persona {
string nome, cognome; int eta;
double altezza;
char sesso; // M oppure F union {
// dati per gli uomini struct {
bool } dati_uomo;
// dati per le donne struct {
} dati_donna; };
};
%%% completare l'esempio
Sta al programmatore di usare i campi ... solo quando sesso è M o i campi ... quando sesso è F.