Array, matrici e stringhe in C

Quasi tutti i programmi lavorano su molti dati dello stesso tipo: i campioni di un segnale, i voti di una classe, i pixel di un’immagine, i caratteri di un messaggio. L’array è la struttura che li raccoglie in celle consecutive della memoria, accessibili con un indice. In questa lezione vediamo array a una e più dimensioni, come si passano alle funzioni, le stringhe di caratteri e i pericoli di uscire dai limiti.

Gli array

#define N 5
int voti[N] = {28, 30, 24, 27, 30};       /* N interi consecutivi in memoria */

int somma = 0;
for (int i = 0; i < N; i++) {
    somma += voti[i];
}
printf("Media: %.2f\n", (double)somma / N);   /* Media: 27.80 */

• La dimensione deve essere nota e non cambia: un array non si allunga (per questo serve la memoria dinamica della lezione sui puntatori).
• Gli indici vanno da 0 a N - 1.
• Gli elementi stanno in celle contigue: l’indirizzo di voti[i] è quello di voti[0] più i volte la dimensione di un int. Per questo l’accesso a qualsiasi elemento costa lo stesso tempo, .
• Usare una costante (#define N 5) invece di ripetere il numero 5 ovunque evita di dimenticarne uno quando la dimensione cambia.

Uscire dai limiti

Il C non controlla che l’indice sia valido. Scrivere voti[5] in un array di 5 elementi non dà errore: legge o scrive la cella che c’è dopo, che appartiene a un’altra variabile. Il risultato è un comportamento imprevedibile, che magari si manifesta molto più tardi in un punto lontano del programma. È la causa dei buffer overflow, la vulnerabilità di sicurezza più sfruttata della storia: un attaccante scrive oltre la fine di un array e sovrascrive l’indirizzo di ritorno sulla pila, facendo eseguire codice suo. Il worm Morris del 1988 e moltissimi attacchi successivi usavano proprio questo.

Le regole di difesa: tenere sempre la dimensione accanto all’array, controllare gli indici che vengono dall’esterno, compilare durante lo sviluppo con -fsanitize=address, che segnala gli accessi fuori dai limiti.

Array e funzioni

Un array passato a una funzione non viene copiato: la funzione riceve l’indirizzo del primo elemento. Per questo deve ricevere anche la dimensione, e può modificare l’array del chiamante.

/* restituisce l'indice del valore massimo */
int indice_massimo(const int v[], int n)
{
    int imax = 0;
    for (int i = 1; i < n; i++) {
        if (v[i] > v[imax]) imax = i;
    }
    return imax;
}

Il const dichiara che la funzione non modifica l’array: il compilatore lo verifica, e chi legge il prototipo lo sa subito.

Le matrici

Un array a due dimensioni è un array di righe, memorizzate una dopo l’altra (ordine per righe):

double m[3][4];           /* 3 righe, 4 colonne */
m[1][2] = 5.0;            /* riga 1, colonna 2 */

/* prodotto matrice per vettore: y = A x */
void mat_vet(int r, int c, const double a[r][c], const double x[c], double y[r])
{
    for (int i = 0; i < r; i++) {
        y[i] = 0.0;
        for (int j = 0; j < c; j++) {
            y[i] += a[i][j] * x[j];
        }
    }
}

Scorrere una matrice riga per riga (con l’indice di colonna nel ciclo interno) è molto più veloce che scorrerla per colonne, perché si leggono celle contigue e la cache lavora bene: con matrici grandi la differenza può essere di dieci volte.

Le stringhe

In C una stringa è un array di char terminato dal carattere nullo '\0' (il numero 0). La stringa "ciao" occupa 5 byte: ‘c’, ‘i’, ‘a’, ‘o’, ‘\0’. Il terminatore è il modo in cui le funzioni sanno dove finisce la stringa.

#include <stdio.h>
#include <string.h>

int main(void)
{
    char nome[20] = "Ada";               /* spazio per 19 caratteri più il terminatore */
    printf("%s ha %zu lettere\n", nome, strlen(nome));     /* Ada ha 3 lettere */

    char saluto[40];
    snprintf(saluto, sizeof saluto, "Ciao, %s!", nome);    /* mai oltre la dimensione */
    printf("%s\n", saluto);

    if (strcmp(nome, "Ada") == 0) {      /* le stringhe si confrontano con strcmp, non con == */
        printf("Nomi uguali\n");
    }
    return 0;
}

Le funzioni di <string.h> (strlen, strcpy, strcat, strcmp) si appoggiano tutte al terminatore. Se manca, o se la destinazione è troppo piccola, si esce dai limiti dell’array: strcpy e gets sono le cause storiche di molti buffer overflow. Le versioni che ricevono la dimensione, come snprintf, vanno preferite. == tra due stringhe confronta gli indirizzi, non il contenuto: per il contenuto serve strcmp, che restituisce 0 se sono uguali.

Un esempio dall’elettronica: la media mobile

Per ripulire la lettura di un sensore si fa la media degli ultimi campioni, tenuti in un array usato in modo circolare: il nuovo campione sostituisce il più vecchio, e l’indice torna a 0 dopo l’ultima cella.

#define N 8
static int buffer[N];
static int pos = 0;
static long somma = 0;

int media_mobile(int nuovo)
{
    somma -= buffer[pos];       /* tolgo il campione più vecchio */
    buffer[pos] = nuovo;
    somma += nuovo;
    pos = (pos + 1) % N;        /* indice circolare */
    return (int)(somma / N);
}

Mantenendo la somma aggiornata, ogni nuovo campione costa poche operazioni, qualunque sia : invece di . È un filtro FIR passa basso, come quelli della lezione sulla trasformata Zeta.