Tipi Strutturati
Ottenuti come aggregati di tipi atomici e/o strutturati sono caratterizzati da:
- Tipi componenti
- Possono a loro volta essere tipi atomici o tipi strutturati
- Metodo di costruzione
- Può essere il prodotto cartesiano o la sequenza
- Funzione d’accesso
- Può essere per posizione o per nome
- Operazioni applicabili
Tipi Strutturati
Tipi strutturati fondamentali (il cui costruttore è generalmente predefinito):
- Array
- Stringhe
- Record
- File (non trattati nel presente corso)
Array
Tipi componenti
- Omogeneità: tutti gli elementi di un array appartengono allo stesso tipo, che può essere un tipo atomico o un tipo strutturato
Metodo di costruzione
- Prodotto cartesiano: tipo array = cartesiano (T, T, …, T)
- Il valore di un array come unica variabile è quindi una n-pla di valori componenti;
( 2, 9, 0, -1, 24, 0, 9, 6 )
Funzione d’accesso
- Per posizione, e precisamente l’accesso al singolo elemento è casuale indicizzato: i singoli componenti sono accessibili allo stesso modo, mediante indici
Operazioni applicabili
- Ai singoli elementi. Ciò significa che in un linguaggio procedurale non sono in genere definiti operatori che lavorino globalmente su operandi di tipo array. Non sono disponibili l’operatore di assegnazione, né gli operatori relazionali = =, <, > etc..Dunque dati ad esempio due vettori v1 e v2 NON è possibile effettuare operazioni come: v1=v2
Gli array in memoria
Il compilatore linearizza la notazione A[i][j] trasformandola in una notazione ad unico indice, fissando un indirizzo base ed un impegno di M locazioni di memoria, in modo che l’elemento A[i][j] si trova nella posizione k dell’array linearizzato ottenuta come:
K=i*dimCol+j
dove dimCol è il numero di colonne.
Allocazione degli array
Allocazione statica
- Le dimensioni dell’array sono specificate a tempo di compilazione
- La memoria necessaria a contenere la variabile di tipo array viene dedicata a questo scopo per l’intero tempo di vita della variabile stessa
Allocazione dinamica
- Le dimensioni dell’array sono specificate a tempo di esecuzione
- La memoria necessaria a contenere la variabile di tipo array viene allocata subito prima dell’uso e de-allocata subito dopo l’uso della variabile stessa
Gli array nel linguaggio C++
- In C++ è possibile sia l’allocazione statica che quella dinamica.
- In questo corso tratteremo esclusivamente l’allocazione statica.
- Qualunque sia la tecnica di allocazione adoperata, esiste un ordinamento totale tra gli elementi di un array
- In C++ gli elementi sono ordinati per righe
- Gli elementi contigui sono memorizzati in “celle” di memoria adiacenti
- L’occupazione di memoria (in numero di byte) di ciascun elemento dipende dal tipo del dato componente
Dichiarazione di array
Occorre indicare il numero delle dimensioni e il numero di valori per ogni dimensione (lunghezza della n-pla):
tipo nome[lunghezza_1]…[lunghezza_n];
Esempi:
- int V[10]; // un vettore di 10 elementi di tipo intero
- float M[10][20]; // una matrice di 10 righe e 20 colonne di elementi di tipo reale (in tutto 200 elementi, 20 per riga)
- char Nome[20]; // un vettore di 20 elementi di tipo carattere
Funzione di accesso
- Gli elementi di un array sono in corrispondenza biunivoca con i numeri naturali
- I numeri associati agli elementi si dicono indici
- Funzione di accesso: operatore [ ] (notazione infissa)
- Operandi della funzione di accesso: array, indice
Esempio:
- int V[10];
- // l’indice del primo elemento di V è 0
- // l’indice del secondo elemento di V è 1
- // l’indice dell’ultimo elemento di V è 9
- cin >> V[1]; // accesso in scrittura al secondo elemento di V
- cout << V[4]; // accesso in lettura al quinto elemento di V
- cout << V[10]; // errore! L’elemento in posizione 10 non è definito
Esempi di accesso: vettori
int v[10], s[5];
int i, x;
v[3] = s[1] + x;
- all’elemento di v di indice 3 viene assegnato il valore ottenuto sommando all’elemento di s di indice 1 il valore della variabile x
x = v[i];
- alla variabile x viene assegnato l’elemento di v di indice i
v[i] = v[i] + 1
- all’elemento di v di indice i viene assegnato il valore ottenuto incrementando di 1 il suo valore corrente
v[i] = v[i+1]
- all’elemento di v di indice i viene assegnato l’elemento seguente (di indice i+1). Nota Bene: il valore di i non viene modificato.
Esempi di accesso: matrici
int m[10][10];
int s[5];
int i, j, x;
- cin >> m[2][3];
- accesso in scrittura all’elemento di riga 2 e colonna 3
- m[3][3] = s[1] + x;
- all’elemento di m di riga 3 e colomma 3 viene assegnato il valore ottenuto sommando all’elemento di s di indice 1 il valore della variabile x
- x = m[i][j];
- alla variabile x viene assegnato l’elemento di m di riga i e colonna j
- m[i][j] = m[i][j] + 1
- all’elemento di m di riga i e colonna j viene assegnato il valore ottenuto incrementando di 1 il suo valore corrente
- m[i][j]= m[i+1][j]
- all’elemento di m di riga i e colonna j viene assegnato l’elemento che si trova sulla riga seguente (di indice i+1) e nella stessa posizione di colonna (j). Nota Bene: il valore di i non viene modificato.
Esempio 1: scansione di un vettore
Specifica: Si scriva un programma C++ che stampa a video tutti gli elementi di un vettore di interi
Esempio 2: scansione di una matrice bidimensionale
Si scriva un programma C++ che stampa a video tutti gli elementi di una matrice di interi
Esempio 3: Somma degli elementi di una matrice
Dimensionamento degli array
- Un array allocato staticamente deve essere opportunamente dimensionato
- La dimensione che viene specificata all’atto della definizione è la dimensione massima della struttura dati
- In memoria verrà allocato lo spazio necessario per contenere l’array di dimensione massima
- Nella pratica normalmente è sufficiente un array di dimensioni inferiori
- L’informazione circa le reali dimensioni della struttura dati deve essere nota al fine di operare correttamente su tutti e soli gli elementi realmente “esistenti” dell’array
- Tale informazione viene spesso fornita mediante una variabile (una per ciascuna dimensione) il cui valore rapperesenta il reale il “riempimento” dell’array (lungo la relativa dimensione)
Esempio 4: riempimento
Scrivere un programma che inizializza un vettore di interi mediante n valori inseriti da tastiera dall’utente
Prossima lezione
Tipi strutturati
- Stringhe
- Record
- L’istruzione typedef