Puntatori e Array Multidimensionali in linguaggio C

Nella lezione precedente abbiamo visto che un array in linguaggio C è memorizzato in memoria come un blocco di celle contigue. Abbiamo anche visto che il nome di un array è in realtà un puntatore al primo elemento dell'array. Quindi esiste una stretta relazione tra array e puntatori.

In questa lezione andremo oltre e vedremo come utilizzare i puntatori per processare gli elementi di un array multidimensionale in linguaggio C.

Processare gli elementi di un array multidimensionale

Abbiamo visto nella lezione sugli array multidimensionali che il linguaggio C memorizza gli array multidimensionali in memoria come un array monodimensionale. In particolare, essi vengono memorizzati per righe.

Ciò significa che gli elementi della riga 0 vengono memorizzati in sequenza, seguiti dagli elementi della riga 1, e così via.

Prendiamo, ad esempio, un array bidimensionale di m righe ed n colonne. Da un punto di vista logico l'array ha la forma seguente:

Tuttavia, in memoria l'array viene memorizzato come un array monodimensionale di m * n elementi. In particolare, l'array viene memorizzato per righe, ossia gli elementi della riga 0 vengono memorizzati in sequenza, seguiti dagli elementi della riga 1, e così via. L'array monodimensionale corrispondente ha la forma seguente:

In altre parole, un array multidimensionale viene appiattito (in inglese flattened) in un array monodimensionale.

Quando lavoriamo con puntatori ad array multidimensionali possiamo trarre vantaggio da questo comportamento.

Infatti, se prendiamo un puntatore che punta all'elemento in riga 0 e colonna 0, ossia il primo elemento dell'array, possiamo incrementare il puntatore per accedere a tutti gli elementi successivi.

Per chiarire come fare, prendiamo un esempio. Abbiamo definito un array bidimensionale in questo modo:

int a[NUMERO_RIGHE][NUMERO_COLONNE];

Vogliamo inizializzare tutti gli elementi dell'array a 0. La prima tecnica più ovvia che possiamo adoperare è quella di impiegare due cicli for innestati, in questo modo:

/* Inizializzazione di un array Bidimensionale */
int riga, colonna;

for (riga = 0; riga < NUMERO_RIGHE; riga++)
    for (colonna = 0; colonna < NUMERO_COLONNE; colonna++)
        a[riga][colonna] = 0;

Tuttavia, possiamo ottenere lo stesso risultato utilizzando un solo ciclo for e un puntatore.

Possiamo, infatti, riscrivere il tutto in questo modo:

int *p;

for (p = &a[0][0]; p <= &a[NUMERO_RIGHE - 1][NUMERO_COLONNE - 1]; p++)
    *p = 0;

Il ciclo inizia assegnando a p l'indirizzo del primo elemento dell'array, ossia &a[0][0].

I successivi incrementi del puntatore p spostano l'indirizzo contenuto in esso dapprima all'elemento a[0][1], ossia il secondo elemento della prima riga, poi all'elemento a[0][2], poi all'elemento a[0][3], e così via.

Quando p raggiunge l'elemento a[0][NUMERO_COLONNE - 1], ossia l'ultimo elemento della prima riga, il ciclo incrementa p e lo sposta all'elemento a[1][0], ossia il primo elemento della seconda riga. Questo accade proprio perché l'array è appiattito in memoria.

Il ciclo continua a incrementare p fino a quando raggiunge l'ultimo elemento dell'array, ossia a[NUMERO_RIGHE - 1][NUMERO_COLONNE - 1]. L'appiattimento in memoria fa si che l'ultimo elemento dell'array sia effettivamente l'ultimo elemento dell'array monodimensionale appiattito.

Questo esempio ci porta ad un'importante conseguenza:

tipo array[m][n];
tipo *p = array;

int k = i * n + j;
p[k];

Inolre, abbiamo anche una seconda importante conseguenza:

tipo array[m][n];
tipo *p = array;

/* ERRORE */
p[i][j];

Conoscere il fatto che un array multidimensionale è memorizzato in memoria come un array monodimensionale è un concetto importante per lavorare con puntatori ad array multidimensionali. Inoltre, in alcuni casi può essere utile per ottimizzare il codice.

Processare le righe di un array multidimensionale

Abbiamo visto che un array multidimensionale è appiattito in memoria, quindi, dal punto di vista della memoria e del processore, si tratta a tutti gli effetti di un array monodimensionale.

Ma come possiamo processare una singola riga di un array multidimensionale? Possiamo farlo utilizzando un puntatore.

In particolare, supponiamo di avere un array bidimensionale a di dimensioni m righe e n colonne:

int a[m][n];

Possiamo creare un puntatore p che punta alla riga i dell'array a in questo modo:

int *p = a[i];

Oppure, in modo equivalente:

int *p = &a[i][0];

La prima espressione funziona perché in sostanza a[i] è un puntatore alla riga i dell'array a. Infatti, a[i] è equivalente a &a[i][0].

Inoltre, ogni riga dell'array è a sua volta un array, per cui a[i] è un array e può essere trattato come un puntatore al primo elemento.

Per convincerci che le due espressioni di sopra funzionano basta ricordare la relazione che lega l'indicizzazione di un array all'aritmetica dei puntatori. Infatti vale che:

a[i] == *(a + i)

Ossia, a[i] è equivalente a *(a + i), che è un puntatore alla riga i dell'array a.

Una volta ottenuto il puntatore p alla riga i dell'array a, possiamo processare gli elementi della riga i utilizzando un ciclo for che scorre tutti gli elementi della riga.

Ad esempio, supponiamo di voler azzerare tutti gli elementi della riga i dell'array a. Possiamo farlo in questo modo:

int *p = a[i];

for (int j = 0; j < n; j++)
    p[j] = 0;

Dove n è il numero di colonne dell'array a.

Il vantaggio di questo approccio è che possiamo trattare le righe di un array multidimensionale come array monodimensionali, e quindi possiamo eventualmente passarle a funzioni che si aspettano un array monodimensionale.

Ad esempio, supponiamo di avere una funzione trova_massimo che trova il massimo di un array monodimensionale:

int trova_massimo(int *array, int n) {
    int massimo = array[0];

    for (int i = 1; i < n; i++)
        if (array[i] > massimo)
            massimo = array[i];

    return massimo;
}

Possiamo utilizzare questa funzione per trovare il massimo di ogni riga di un array bidimensionale a in questo modo:

int massimi[m];

for (int i = 0; i < m; i++)
    massimi[i] = trova_massimo(a[i], n);

Dove m è il numero di righe dell'array a.

Poi, possiamo addirittura trovare il massimo di tutti i massimi delle righe passando l'array massimi alla funzione trova_massimo:

int massimo_globale = trova_massimo(massimi, m);

tipo a[m][n];

tipo *p = a[i];

Processare le colonne di un array multidimensionale

A differenza delle righe, processare direttamente le colonne di un array multidimensionale non è altrettanto semplice.

La motivazione sta proprio nell'appiattimento in memoria degli array multidimensionali. L'appiattimento semplifica il processamento delle righe, ma rende più complesso il processamento delle colonne.

Esiste, tuttavia, un trucchetto che ci permette di processare le colonne di un array multidimensionale. Ma la sintassi si complica. Vediamo come fare.

Supponiamo di avere un array bidimensionale a di dimensioni m righe e n colonne:

int a[NUMERO_RIGHE][NUMERO_COLONNE];

Vogliamo scrivere un ciclo che, dato in ingresso l'indice della colonna j, azzeri tutti gli elementi della colonna j dell'array a.

Il primo metodo consiste nell'utilizzare lo schema visto sopra. Sapendo che l'elemento in posizione i e j dell'array a è accessibile tramite l'indice k = i * n + j, possiamo scrivere un ciclo for in questo modo:

/* j è l'indice della colonna da azzerare */
int j;
int *p = a;

for (int i = 0; i < NUMERO_RIGHE; i++)
    p[i * NUMERO_COLONNE + j] = 0;

In questo modo, il ciclo scorre tutte le righe dell'array a e azzerare l'elemento in posizione i e j dell'array.

Il secondo modo consiste nell'usare la seguente sintassi:

/* j è l'indice della colonna da azzerare */
int j;

int (*p)[NUMERO_COLONNE] = a;

for (p = &a[0]; p < &a[NUMERO_RIGHE]; p++)
    (*p)[j] = 0;

In questo caso, p è un puntatore a un array di NUMERO_COLONNE elementi. Quindi, quando incrementiamo p, incrementiamo il puntatore di NUMERO_COLONNE elementi, ossia di una riga.

In questo modo, il ciclo scorre tutte le righe dell'array a e azzerare l'elemento in posizione i e j dell'array.

Lo svantaggio di questo approccio è che la sintassi è più complessa rispetto al primo metodo e, inoltre, bisogna conoscere a priori il numero di colonne dell'array.

Puntatori ad Array Multidimensionali a Lunghezza Variabile in C99

A partire dallo standard C99, è possibile definire array multidimensionali a lunghezza variabile, ossia array le cui dimensioni vengono calcolate a partire da un'espressione in fase di esecuzione.

Possiamo adoperare dei puntatori per puntare a questi array ma dobbiamo prestare alcune attenzioni.

Infatti, quando un array a lunghezza variabile ha più di una dimensione, il tipo del puntatore dipende dalla lunghezza di ciascuna dimensione eccetto la prima.

Prendiamo l'esempio di un array bidimensionale:

void funzione(int m, int n) {
    int a[m][n];
    int (*p)[n];

    p = a;

    /* ... */
}

In questo caso, p è un puntatore a un array di n elementi, ossia un puntatore ad una singola riga dell'array.

Questo codice funziona perché la variabile n viene adoperata sia per definire l'array a che per definire il tipo del puntatore p.

C'è un dettaglio, però, che non è immediatamente evidente. Il tipo del puntatore p è int (*)[n], ossia un puntatore a un array di n elementi. Ma questo tipo non è fisso e dipende, anzi, da n. In questo caso si parla di tipo modificato da variabile o variably modified type.

Un tipo modificato da variabile è un tipo il cui significato dipende da una variabile. In questo caso, il tipo int (*)[n] è un tipo modificato da variabile perché il numero di colonne n è una variabile.

Sebbene lo standard C99 consenta questi tipi, non sempre i compilatori sono in grado di verificare la correttezza di un assegnamento.

Ad esempio, il codice che segue viene compilato correttamente ma funziona solo se m e n sono uguali:

int a[m][n];
int (*p)[m];

/* FUNZIONA SOLO SE m == n */
p = a;

In caso contrario, se m e n sono diversi, il compilatore non segnala alcun errore ma il programma potrebbe comportarsi in modo imprevedibile.

Per questo motivo, i tipi modificati da variabile sono consentiti solo in determinate circostanze:

• Possono essere usati solo nel corpo di una funzione;
• Oppure, possono essere usati nel prototipo di una funzione.

Detto in altri termini, variabili di questo tipo possono essere solo variabili locali.

Per quanto riguarda il resto, i puntatori ad array multidimensionali a lunghezza variabile si comportano come i puntatori ad array multidimensionali statici. Pertanto, possiamo adoperare l'aritmetica dei puntatori allo stesso identico modo.

Ad esempio, possiamo scrivere un ciclo che scorre tutti gli elementi di un array multidimensionale a lunghezza variabile e li imposta a zero in questo modo:

int m = 5;
int n = 3;
int a[m][n];

int *p = a;

/* Imposta tutti gli elementi dell'array a 0 */
for (int i = 0; i < m * n; i++)
    p[i] = 0;

In Sintesi

In questo articolo abbiamo visto come processare gli elementi di un array multidimensionale utilizzando puntatori.

Abbiamo visto che un array multidimensionale è memorizzato in memoria come un array monodimensionale. Questa caratteristica prende il nome di appiattimento o flattening.

Attraverso l'appiattimento, possiamo processare gli elementi di un array multidimensionale utilizzando un solo ciclo for e un puntatore.

Inoltre, abbiamo visto come processare le righe di un array multidimensionale utilizzando un puntatore. Abbiamo visto che possiamo trattare le righe di un array multidimensionale come array monodimensionali.

Ciò, invece, non è possibile per le colonne. Tuttavia, abbiamo visto un trucchetto che ci permette di processare le colonne di un array multidimensionale.