7 Livello 5

Il presente capitolo introduce lo studio delle strutture dati lineari attraverso l’analisi degli array, esaminando i meccanismi di allocazione contigua in memoria RAM, le politiche di indicizzazione i vincoli architetturali legati alla manipolazione e alla copia dei vettori. In chiusura viene mostrato un esempio sull’uso di array bidimensionali (matrici).

7.1 Array monodimensionali

L’introduzione degli array monodimensionali (o vettori) estende significativamente le potenzialità di modellazione dei dati nel linguaggio C. Gli array costituiscono uno strumento estremamente potente. Qualora sia necessario gestire un insieme di variabili omogenee (tutte del medesimo tipo di dato), non è richiesto procedere alla loro dichiarazione individuale.

Analogamente a qualsiasi altra variabile, un array deve essere preventivamente dichiarato. La sintassi è la seguente:

int v[100];

Questa dichiarazione definisce un array monodimensionale denominato v, in cui ogni elemento condivide lo stesso identificatore e il medesimo tipo int. All’interno delle parentesi quadre [] è necessario indicare la dimensione. Nell’esempio proposto, verranno riservati nella memoria centrale 100 blocchi contigui della medesima dimensione (4 byte per ciascun intero).

Importante

È fondamentale evidenziare che tali blocchi sono fisicamente adiacenti all’interno della memoria RAM. Di conseguenza, noto l’indirizzo del primo elemento, è possibile accedere in modo sequenziale a tutti gli altri elementi semplicemente applicando una traslazione del corretto numero di byte per raggiungere l’elemento successivo. Torneremo su questo aspetto dopo l’introduzione del concetto di puntatore.

L’accesso o la selezione di uno specifico elemento avviene mediante l’utilizzo di un indice, secondo la notazione v[5] (che in questo caso identifica l’elemento associato all’indice 5). Si ricordi che nel linguaggio C l’indicizzazione è basata sullo zero. Il primo elemento dell’array è associato all’indice zero (ovvero, v[0]). Di conseguenza, se l’array è strutturato per contenere 100 elementi, l’ultimo di essi sarà accessibile tramite l’indice 99 (v[99]). È necessario prestare la massima attenzione a non effettuare accessi al di fuori dell’intervallo valido, il quale spazia da 0 a \(N\)-1 (dove \(N\) rappresenta la dimensione dell’array). Il compilatore di norma non segnala alcun errore in fase di compilazione, ma tale scenario genera un comportamento pericoloso, in quanto il programma andrebbe a operare sul contenuto di blocchi di memoria adiacenti di cui non si ha il controllo. Infine, si raccomanda di evitare l’uso di costanti numeriche fisse per specificare la dimensione dell’array all’interno del codice. È preferibile ricorrere alla direttiva al preprocessore #define N 100. Tale approccio permette di modificare centralmente la capacità dell’intera struttura dati qualora si renda necessario un successivo ridimensionamento.

Buona pratica: evitare i “Numeri Magici”

Scrivere direttamente valori numerici fissi nella dichiarazione degli array (es. int v[100];) è una pratica fortemente sconsigliata. Rende il codice rigido e costringe a modificare manualmente ogni singola occorrenza del numero qualora la dimensione debba variare in futuro.

La soluzione standard in C prevede l’uso della direttiva al preprocessore.

Si consideri il seguente semplice esempio volto a illustrare l’utilizzo di un array:

#include <stdio.h>
#define NVOTI 10
int main(void) {
    int i, n, voti[NVOTI], somma = 0;
    float media;
    printf("Quanti voti si desidera inserire? ");
    scanf("%d", &n);    
    for (i = 0; i < n; ++i) {
        printf("\nInserisci il voto #%d: ", i + 1);
        scanf("%d", &voti[i]);
        somma += voti[i];
    }    
    media = (float)somma / n;
    printf("\nLa media è pari a: %f\n", media);    
    return 0;
}

La differenza principale rispetto all’Esercizio 5 del capitolo precedente risiede nel fatto che, al termine del ciclo for, tutti i voti rimangono memorizzati all’interno dell’array, ciascuno in un blocco di memoria specifico e consecutivo.

È sempre compito del programmatore dimensionare l’array in modo che possa ospitare un numero sufficiente di elementi. Qualora la capacità definita inizialmente risultasse insufficiente, sarà sufficiente modificare il valore all’interno della direttiva #define.

Si ricordi che non è consentito assegnare direttamente un intero array a un altro array tramite un’istruzione di assegnamento diretto del tipo v = w;. Il nome di un array, infatti, è sinonimo dell’indirizzo del suo primo elemento e tale indirizzo non è modificabile. Qualora si renda necessario copiare il contenuto di un array in un altro, è obbligatorio procedere alla copia puntuale di ciascun elemento, operando all’interno di un ciclo.

Array e puntatori: la regola e le eccezioni

Nella quasi totalità dei contesti il nome dell’array decade automaticamente all’indirizzo del suo primo elemento.

Ci sono soltanto pochi contesti in cui il decadimento non avviene. Esempio:

sizeof(v) restituisce la dimensione dell’intero array (es. 400 byte), non quella di un puntatore (tipicamente 8 byte su 64 bit).
&v produce un puntatore di tipo int (*)[N], cioè un puntatore all’array nella sua interezza, non al primo elemento.

Per questo motivo, benché nella pratica il nome dell’array si comporti pressoché sempre come un puntatore costante al primo elemento, array e puntatori restano tipi distinti.

Per garantire un controllo sulle dimensioni dell’array, costituisce buona pratica verificare che il programma non accetti un numero di elementi superiore alla capacità massima allocata. Si analizzi il seguente esempio:

#include <stdio.h>
#define N 10
int main(void) {
    int i, n, v[N], somma = 0;
    do {
        printf("Dimensione? ");
        printf("Deve essere compresa nell'intervallo 1-10! ");
        scanf("%d", &n);
    } while(n < 1 || n > N);
    for(i = 0; i < n; ++i) {
        printf("\nInserisci l'intero #%d: ", i + 1);
        scanf("%d", &v[i]);
        somma += v[i];
    }
    printf("\nLa somma è: %d\n", somma);    
    return 0;
}

Importante

Il C non effettua alcun controllo sui limiti degli array durante l’esecuzione. In altre parole, è possibile leggere o scrivere un elemento al di fuori dell’intervallo valido senza ricevere alcun messaggio di errore. Il programma accederà alla memoria adiacente, con conseguenze imprevedibili.

È compito del programmatore garantire che tutti gli accessi avvengano entro i limiti e che gli array siano abbastanza grandi da contenere ciò per cui sono stati creati.

7.1.1 Altra inizializzazione di un array

Un array può essere inizializzato contestualmente alla dichiarazione, elencando i valori tra parentesi graffe:

int v[5] = {3, 7, 12, 5, 9};

La sintassi prevede alcune varianti utili:

Inizializzazione parziale: se i valori elencati sono meno della dimensione dichiarata, gli elementi rimanenti vengono automaticamente posti a zero. La scrittura int v[100] = {0}; è quindi standard per ottenere un array interamente di zeri.
Dimensione implicita: omettendo il numero tra parentesi quadre, è il compilatore a dedurre la dimensione contando gli inizializzatori. La dichiarazione int v[] = {3, 7, 12}; definisce un array di 3 elementi.

7.1.2 Le stringhe

In C, le stringhe sono strutturate come array di elementi di tipo char la cui terminazione è marcata dal carattere nullo \0. Questo delimitatore consente di manipolare i flussi testuali scorrendoli in modo indipendente dalla dimensione allocata, ma impone di riservare sempre un byte aggiuntivo in fase di dichiarazione rispetto alla lunghezza effettiva del testo.

Sebbene sia possibile implementare manualmente le routine di copia e concatenazione mediante cicli iterativi che scansionano i vettori fino al raggiungimento del terminatore, la gestione ottimale e sicura della manipolazione testuale si affida alle funzioni native della libreria <string.h> (quali strcpy, strcat, strlen e strcmp).

7.2 Array bidimensionali

Le matrici nel linguaggio C estendono il concetto di array monodimensionale introducendo strutture dati bidimensionali, dichiarate tramite la sintassi M[NR][NC] e indicizzate specificando riga e colonna mediante la notazione M[i][j].

La manipolazione di tali strutture si realizza attraverso l’annidamento di cicli iterativi. Vediamo un esercizio che mostri il funzionamento di un array bidimensionale.

Esercizio 6

Scrivere un programma che calcoli la somma delle righe e delle colonne di una matrice quadrata di dimensione NxN

#include <stdio.h>
#define DIM 100
int main(void) {
    int i,j,m1[DIM][DIM],rsum[DIM],csum[DIM],n;
    do  {
      printf("Dimensione matrice quadrata: \n");
      scanf("%d", &n);
    } while(n<1 || n>DIM);
    printf("Inserisci elementi della matrice:\n");
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++) {
            printf("elemento - [%d],[%d] : ",i,j);
            scanf("%d",&m1[i][j]);
        }
    }
    for(i=0;i<n;i++) {
        rsum[i]=0;
        for(j=0;j<n;j++)
            rsum[i]=rsum[i]+m1[i][j];
    }
    for(i=0;i<n;i++) {
        csum[i]=0;
        for(j=0;j<n;j++)
            csum[i]=csum[i]+m1[j][i];
    }
    printf("La somma righe e colonne vale:\n");
    for(i=0;i<n;i++) {
        for(j=0;j<n;j++)
            printf("%4d",m1[i][j]);
        printf("%8d",rsum[i]);
        printf("\n");
    }
    printf("\n");
    for(j=0;j<n;j++) {
        printf("%4d",csum[j]);
    }
    printf("\n\n");
    return 0;
}

E in Python?

A livello sintattico, l’accesso a un elemento tramite indice appare identico in C e in Python (es. v[0]). Tuttavia, dal punto di vista della gestione della memoria RAM, i due linguaggi operano secondo paradigmi molto differenti. Il confronto che segue evidenzia il trade-off tra il controllo diretto dell’hardware (in C) e l’astrazione software (in Python).

L’approccio in C (allocazione contigua): che si tratti di un array statico (allocato sullo Stack) o di un array dinamico (allocato sull’Heap tramite malloc(), lo vedremo meglio in seguito), il linguaggio C garantisce sempre la contiguità fisica dei blocchi di memoria. Gli elementi adiacenti dell’array occupano celle adiacenti della RAM.
L’approccio in Python (struttura referenziale): una lista in Python non contiene direttamente i dati (i numeri o le stringhe), ma contiene una sequenza di puntatori contigui che indirizzano gli oggetti effettivi. I dati reali possono essere dislocati in zone della RAM completamente sparse e distanti tra loro.

Questa architettura del C impone che l’array sia rigidamente omogeneo (tutti gli elementi devono condividere lo stesso tipo di dato, es. int). Questo vincolo permette alla CPU di calcolare l’indirizzo di memoria di un qualsiasi elemento eseguendo una semplice operazione di aritmetica dei puntatori a livello hardware:

\[\text{Indirizzo}(v[i]) = \text{Indirizzo Base} + (i \times \text{dimensione\_tipo})\]

In Python, la lista è eterogenea perché potendo memorizzare puntatori a oggetti qualsiasi, una singola lista può contenere contemporaneamente interi, stringhe e float.