Le basi del C: guida completa ai fondamenti dell'informatica

Il C è il linguaggio da cui derivano direttamente C++, Java, C# e moltissimi altri: chi lo impara acquisisce una comprensione profonda di come funziona davvero un calcolatore, perché a differenza dei linguaggi più moderni non nasconde quasi nulla. Variabili, memoria, puntatori: tutto è esplicito e sotto il tuo controllo. Proprio per questo il C resta il punto di partenza classico dei corsi di informatica, dalle scuole superiori all'università.

Questa guida è più ampia del solito: non parte dalla sintassi, ma da ciò che sta sotto, cioè da come è fatto un calcolatore e da come rappresenta le informazioni. Poi si passa agli algoritmi, al linguaggio C vero e proprio, alle strutture dati fondamentali (array, puntatori, struct, liste) e infine a come si valuta se un programma è corretto ed efficiente. È un percorso lungo ma organico: ogni argomento si appoggia sul precedente.

Come funziona un calcolatore#

Prima di scrivere anche solo una riga di codice, conviene capire su cosa gira davvero un programma. Un calcolatore (il tuo PC, ma anche uno smartphone o la centralina di un'automobile) è una macchina che esegue istruzioni molto semplici, una alla volta e a velocità altissima. Tutta la sua potenza nasce dalla combinazione di componenti elementari organizzati secondo un'architettura precisa.

L'architettura di von Neumann#

La maggior parte dei calcolatori segue ancora oggi lo schema proposto da John von Neumann negli anni '40: dati e istruzioni condividono la stessa memoria, ed eseguono un ciclo continuo chiamato fetch-decode-execute (preleva, decodifica, esegui). I componenti principali sono questi:

• ›CPU (Central Processing Unit) — il "cervello" del calcolatore. Contiene la Control Unit, che coordina l'esecuzione, e la ALU (Arithmetic Logic Unit), che fa i calcoli aritmetici e logici. Al suo interno ha anche dei registri, piccolissime memorie velocissime che contengono i dati usati in quel preciso istante.
• ›Memoria centrale (RAM) — contiene i dati e le istruzioni dei programmi in esecuzione. È veloce, ma volatile: si svuota quando spegni il calcolatore.
• ›Memoria di massa — hard disk o SSD. Più lenta della RAM, ma conserva i dati anche a calcolatore spento.
• ›Bus — i "cavi" (elettrici, ma ormai spesso concettuali) che collegano CPU, memoria e periferiche, permettendo lo scambio di dati e indirizzi.
• ›Periferiche di input/output — tastiera, mouse, schermo, rete: permettono al calcolatore di comunicare con l'esterno.

Ogni singola istruzione che scriverai in C, alla fine, si traduce in milioni di questi cicli fetch-decode-execute: la CPU preleva un'istruzione dalla memoria, la decodifica per capire cosa fare, la esegue, e passa alla successiva.

La rappresentazione dell'informazione#

Un calcolatore, a livello elettronico, riconosce solo due stati: corrente che passa o non passa. Per questo ogni informazione — numeri, testo, immagini, suoni, video — deve essere ridotta a sequenze di 0 e 1, chiamati bit (binary digit). Otto bit messi insieme formano un byte, l'unità base con cui si misura quasi tutta la memoria.

Numeri, caratteri e ogni altro dato sono quindi solo convenzioni per interpretare sequenze di bit. Un carattere come 'A', ad esempio, viene memorizzato come il numero 65 secondo la codifica ASCII; il carattere minuscolo 'a' corrisponde invece a 97. Un'immagine è una sequenza di numeri che rappresentano il colore di ogni pixel. È sempre e solo una questione di come si interpretano quei bit.

Il sistema operativo#

Il sistema operativo (Windows, macOS, Linux, Android...) è il software che sta tra l'hardware e i programmi che usi, incluso quello che scriverai tu. Senza, ogni singolo programma dovrebbe sapere come parlare direttamente con ogni componente hardware: un lavoro enorme e ripetuto per ogni sviluppatore.

• ›Gestione dei processi — decide quale programma (processo) usa la CPU in ogni istante, dando l'illusione che più programmi girino contemporaneamente anche con una sola CPU.
• ›Gestione della memoria — assegna a ogni programma un'area di memoria propria, evitando che uno possa leggere o scrivere accidentalmente sui dati di un altro.
• ›File system — organizza i dati su disco in file e cartelle, offrendo un modo semplice per salvarli e ritrovarli.
• ›Gestione delle periferiche — fa da intermediario con tastiera, schermo, rete e disco, offrendo ai programmi funzioni pronte all'uso invece di doverle far parlare direttamente con l'hardware.

Quando lanci un programma scritto in C, è il sistema operativo a caricarlo in memoria, assegnargli tempo di CPU e mettere a disposizione le funzioni di libreria (come printf) che, dietro le quinte, si appoggiano proprio ai servizi del sistema operativo.

Aritmetica binaria#

Abbiamo detto che tutto, nel calcolatore, è rappresentato in bit. Per lavorarci in modo consapevole conviene sapere come funziona il sistema di numerazione binario, cioè in base 2, invece del decimale (base 10) a cui siamo abituati.

Nel sistema decimale ogni cifra vale una potenza di 10 in base alla posizione (unità, decine, centinaia...). Nel sistema binario, allo stesso modo, ogni cifra (0 o 1) vale una potenza di 2. Per convertire un numero binario in decimale basta sommare le potenze di 2 corrispondenti alle cifre a 1:

1101 (binario)
= 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0
= 8 + 4 + 0 + 1
= 13 (decimale)

Per il procedimento inverso, da decimale a binario, si divide ripetutamente per 2 e si annotano i resti dal basso verso l'alto:

13 / 2 = 6 resto 1
 6 / 2 = 3 resto 0
 3 / 2 = 1 resto 1
 1 / 2 = 0 resto 1

Leggendo i resti dal basso: 1101

Con n bit si possono rappresentare 2^n combinazioni diverse: un byte (8 bit) rappresenta quindi 256 valori, da 0 a 255 se consideriamo solo numeri positivi (interi senza segno). Per rappresentare anche i numeri negativi, il C usa quasi sempre il complemento a due: il bit più a sinistra assume peso negativo, così un int a 32 bit può rappresentare valori da -2.147.483.648 a 2.147.483.647.

Un aspetto da tenere a mente è l'overflow: se un calcolo supera il valore massimo rappresentabile con quel numero di bit, il risultato "gira" e riparte dal valore minimo, senza che il C segnali automaticamente l'errore. È una delle differenze più importanti tra l'aritmetica "di carta" e quella di un calcolatore reale.

Dal codice sorgente all'eseguibile: la compilazione#

Il C è un linguaggio compilato: il codice che scrivi (il codice sorgente, in un file .c) non viene eseguito direttamente, ma prima tradotto in linguaggio macchina, l'unico che la CPU capisce davvero. È diverso da un linguaggio interpretato (come Python), dove un altro programma legge ed esegue il codice riga per riga a ogni avvio.

Le fasi della compilazione#

Il passaggio da codice sorgente a programma eseguibile avviene in più fasi distinte, di solito invisibili a chi programma perché il compilatore (in genere gcc o clang) le esegue tutte in sequenza con un solo comando:

• ›Preprocessore — elabora le righe che iniziano con #, come #include e #define, sostituendole con il loro contenuto prima ancora che inizi la vera compilazione.
• ›Compilazione — traduce il codice C in linguaggio assembly, una rappresentazione simbolica delle istruzioni macchina.
• ›Assemblaggio — trasforma l'assembly in codice oggetto (file .o), cioè istruzioni binarie vere e proprie, ma non ancora eseguibili da sole.
• ›Linking — unisce il codice oggetto con quello delle librerie usate (come le funzioni di <stdio.h>), producendo il file eseguibile finale.

Scriviamo il primo programma, quello che tradizionalmente si scrive per primo in ogni linguaggio:

#include <stdio.h>

int main(void) {
    printf("Ciao, mondo!\n");
    return 0;
}

#include <stdio.h> chiede al preprocessore di includere le dichiarazioni per l'input/output standard, tra cui printf. main è la funzione da cui parte sempre l'esecuzione; (void) indica esplicitamente che non riceve parametri (in C, main() senza void ha un significato leggermente diverso e meno preciso, quindi è buona abitudine specificarlo sempre). return 0; comunica al sistema operativo che il programma è terminato senza errori.

Per compilare ed eseguire questo file da terminale (salvato come programma.c) bastano due comandi:

gcc programma.c -o programma
./programma

Il primo comando invoca il compilatore gcc, che esegue tutte le fasi viste sopra e produce un eseguibile chiamato programma; il secondo lo lancia. Se c'è un errore di sintassi, il compilatore si ferma e mostra riga e descrizione del problema, senza produrre alcun eseguibile.

Che cos'è un algoritmo#

Prima ancora di tradurlo in C, ogni programma nasce come algoritmo: una sequenza finita, ordinata e non ambigua di passi che risolve un problema, trasformando dei dati in ingresso (input) in un risultato (output). "Non ambigua" è la parola chiave: ogni passo deve essere così preciso da poter essere eseguito da chi, o cosa, non ha alcuna capacità di interpretazione — compreso un calcolatore.

La specifica di un algoritmo#

Prima di progettare un algoritmo bisogna specificarlo con chiarezza: cosa riceve in ingresso (precondizioni, cioè cosa deve essere vero sui dati perché l'algoritmo funzioni) e cosa garantisce in uscita (postcondizioni). Per un algoritmo che cerca il massimo in un array, ad esempio, la precondizione è che l'array non sia vuoto, e la postcondizione è che il valore restituito sia maggiore o uguale a tutti gli elementi dell'array.

Le qualità di un buon algoritmo#

• ›Correttezza — produce il risultato giusto per ogni input valido, non solo per i casi più semplici.
• ›Efficienza — usa il minor tempo e la minor memoria possibile; ne parleremo più avanti con la notazione O grande.
• ›Chiarezza — è comprensibile da altre persone, e da te stesso tra sei mesi.
• ›Generalità — risolve l'intera classe di problemi, non solo un caso particolare.

Rappresentare un algoritmo: pseudocodice e diagrammi di flusso#

Prima di scrivere codice in un linguaggio specifico, è utile descrivere un algoritmo in modo indipendente dalla sintassi. Due strumenti classici sono lo pseudocodice, una via di mezzo tra linguaggio naturale e codice, e i diagrammi di flusso, la loro versione grafica (ovali per inizio e fine, rettangoli per le operazioni, rombi per le decisioni).

Ecco lo pseudocodice per trovare il massimo di un array:

ALGORITMO MassimoArray(A, n)
    max <- A[0]
    PER i DA 1 A n-1
        SE A[i] > max ALLORA
            max <- A[i]
    RESTITUISCI max

Da qui in poi tradurremo direttamente in C questo tipo di ragionamento, ma il procedimento mentale — pensare prima all'algoritmo, poi al codice — resta lo stesso per qualunque linguaggio userai in futuro.

I mattoni del linguaggio C#

Con le basi teoriche a posto, possiamo dedicarci al linguaggio vero e proprio. Il C è un linguaggio imperativo: un programma è una sequenza di istruzioni che modificano lo stato della memoria, eseguite una dopo l'altra salvo indicazioni diverse.

Struttura di un programma#

Abbiamo già visto lo scheletro minimo di un programma C: direttive #include, la funzione main, e istruzioni terminate da un punto e virgola. Le istruzioni si raggruppano in blocchi delimitati da parentesi graffe { }, che definiscono anche l'ambito (scope) di validità delle variabili dichiarate al loro interno.

Variabili, costanti e tipi di dato#

Una variabile è uno spazio di memoria con un nome, che contiene un valore che può cambiare durante l'esecuzione. Per crearla si indica il tipo e poi il nome; le si può anche assegnare subito un valore iniziale.

int eta = 17;            // numero intero
double altezza = 1.75;   // numero con la virgola, doppia precisione
float peso = 68.5f;      // numero con la virgola, precisione singola
char sezione = 'B';      // un singolo carattere

eta = 18;                // il valore può cambiare

A differenza del C++, il C "classico" non ha un tipo bool né un tipo string nativi: il vero e il falso si rappresentano con interi (0 significa falso, qualunque altro valore significa vero), mentre il testo si gestisce con array di char, che vedremo più avanti. Questi sono i tipi fondamentali:

• ›int — numeri interi (es. -5, 0, 42), tipicamente 4 byte.
• ›double — numeri con la virgola a doppia precisione (es. 3.14), tipicamente 8 byte; è il tipo da preferire per i calcoli.
• ›float — numeri con la virgola a precisione singola, tipicamente 4 byte; occupa meno memoria ma è meno preciso.
• ›char — un singolo carattere, racchiuso tra apici singoli (es. 'A'); in realtà è un numero intero a 1 byte interpretato come carattere.

Puoi verificare quanto spazio occupa un tipo con l'operatore sizeof, utile soprattutto quando dovremo allocare memoria dinamicamente:

printf("Un int occupa %zu byte\n", sizeof(int));

Una costante è una variabile il cui valore non può più cambiare dopo l'inizializzazione. In C si può ottenere con const, oppure con una direttiva #define gestita dal preprocessore, che sostituisce il nome con il valore prima ancora della compilazione:

const double PI = 3.14159;
#define GIORNI_SETTIMANA 7

// PI = 4;   // ERRORE: non si può modificare una costante

Input e output con printf e scanf#

printf stampa a video usando specificatori di formato che indicano il tipo di dato da mostrare: %d per gli interi, %f per i numeri con la virgola, %c per un carattere, %s per una stringa. scanf legge un valore da tastiera e lo salva in una variabile; richiede l'operatore & (indirizzo di) davanti al nome della variabile, perché deve sapere in quale punto della memoria scrivere il valore letto.

int eta;

printf("Quanti anni hai? ");
scanf("%d", &eta);

printf("Hai %d anni\n", eta);

Dimenticare la & davanti alla variabile in scanf è uno degli errori più comuni e più insidiosi per chi inizia: il programma spesso compila lo stesso, ma si comporta in modo imprevedibile in esecuzione. Capiremo meglio il perché quando parleremo di puntatori.

Le istruzioni strutturate: sequenza, selezione, iterazione#

Un risultato fondamentale dell'informatica dice che qualunque algoritmo, per quanto complesso, può essere espresso combinando solo tre strutture di controllo: la sequenza (istruzioni eseguite una dopo l'altra), la selezione (scegliere quale blocco eseguire in base a una condizione) e l'iterazione (ripetere un blocco più volte). In C, selezione e iterazione si scrivono rispettivamente con if/switch e con while/do-while/for.

Selezione: if, else if, switch#

if esegue un blocco solo se una condizione è vera; else indica cosa fare altrimenti. Le condizioni si costruiscono con operatori di confronto (==, !=, <, >, <=, >=) e logici (&& cioè E, || cioè O, ! cioè NON).

int voto = 6;

if (voto >= 6) {
    printf("Promosso!\n");
} else {
    printf("Insufficiente.\n");
}

Attenzione alla differenza tra = (assegnazione) e == (confronto): scrivere if (voto = 6) è un errore classico, perché assegna 6 a voto invece di confrontarlo, e in C il risultato di un'assegnazione è comunque un valore (diverso da zero, quindi "vero"), per cui il compilatore spesso non segnala nulla.

Con else if concateniamo più condizioni in sequenza, valutate dall'alto verso il basso fino alla prima vera:

int voto = 8;

if (voto >= 9) {
    printf("Ottimo\n");
} else if (voto >= 7) {
    printf("Buono\n");
} else if (voto >= 6) {
    printf("Sufficiente\n");
} else {
    printf("Insufficiente\n");
}

Quando dobbiamo confrontare una stessa variabile intera (o char) con molti valori precisi, lo switch è più ordinato di una lunga catena di else if. break interrompe lo switch; se lo dimentichi, l'esecuzione "scivola" nei case successivi. default gestisce i casi non previsti.

int giorno = 3;

switch (giorno) {
    case 1:
        printf("Lunedi\n");
        break;
    case 2:
        printf("Martedi\n");
        break;
    case 3:
        printf("Mercoledi\n");
        break;
    default:
        printf("Altro giorno\n");
}

Iterazione: while, do-while, for#

while ripete il blocco finché la condizione resta vera, controllandola prima di ogni ripetizione: se è già falsa, il blocco non viene eseguito nemmeno una volta.

int i = 1;

while (i <= 5) {
    printf("%d ", i);
    i++;             // senza questo il ciclo non finisce mai
}
// Stampa: 1 2 3 4 5

do-while è simile, ma controlla la condizione alla fine: garantisce quindi che il blocco venga eseguito almeno una volta, utile ad esempio per validare un input finché non è corretto.

int numero;

do {
    printf("Inserisci un numero positivo: ");
    scanf("%d", &numero);
} while (numero <= 0);

for è il ciclo ideale quando conosci in anticipo quante ripetizioni servono: raccoglie in un'unica riga inizializzazione, condizione e aggiornamento del contatore.

for (int i = 0; i < 5; i++) {
    printf("%d ", i);
}
// Stampa: 0 1 2 3 4

break esce subito dal ciclo, continue salta alla ripetizione successiva: funzionano allo stesso modo in tutti e tre i cicli.

Funzioni e prototipi#

Una funzione è un blocco di codice con un nome, richiamabile quando serve: evita ripetizioni e permette di dividere un problema grande in problemi più piccoli. Ha un tipo di ritorno (o void se non restituisce nulla), un nome, e dei parametri tra parentesi.

int somma(int a, int b) {
    return a + b;
}

int main(void) {
    int risultato = somma(3, 4);   // risultato = 7
    printf("%d\n", risultato);
    return 0;
}

In C, se una funzione viene chiamata prima di essere definita, il compilatore deve già conoscerne la "forma": tipo restituito, nome e tipi dei parametri. Per questo si usa un prototipo, cioè l'intestazione della funzione seguita da un punto e virgola, dichiarato prima di main:

int somma(int a, int b);   // prototipo

int main(void) {
    printf("%d\n", somma(3, 4));
    return 0;
}

int somma(int a, int b) {  // definizione
    return a + b;
}

Nei programmi divisi in più file, i prototipi si mettono di solito in un file header (.h), incluso da tutti i file che devono usare quella funzione.

Stile di programmazione#

Un programma corretto ma illeggibile è comunque un problema, perché prima o poi qualcuno (anche tu) dovrà modificarlo. Qualche buona abitudine, valida in C come in qualunque altro linguaggio:

• ›Nomi chiari — voti e media sono più leggibili di v e m, anche se richiedono qualche carattere in più.
• ›Indentazione coerente — ogni livello di parentesi graffe aggiunge un rientro; rende visibile a colpo d'occhio la struttura del programma.
• ›Funzioni piccole e coese — ognuna dovrebbe fare una cosa sola e farla bene, invece di occuparsi di dieci cose diverse.
• ›Evitare i "numeri magici" — un 7 senza spiegazione nel codice è un mistero; const int GIORNI_SETTIMANA = 7; si spiega da solo.
• ›Commenti utili — spiegano il perché di una scelta non ovvia, non ripetono ciò che il codice già dice chiaramente.

Correttezza del software: test e debug#

Un programma che compila non è detto che sia corretto: la compilazione controlla solo che la sintassi sia valida, non che il programma faccia quello che deve fare. Per questo servono metodi sistematici per verificarlo (test) e per correggerlo quando qualcosa non va (debug).

Tipi di errori#

• ›Errori di sintassi — violano le regole grammaticali del linguaggio (una parentesi mancante, un punto e virgola dimenticato); il compilatore si ferma e li segnala.
• ›Errori a runtime — il programma compila ma si blocca durante l'esecuzione, ad esempio dividendo per zero o accedendo a memoria non sua (segmentation fault).
• ›Errori di logica — il programma compila ed esegue senza bloccarsi, ma produce un risultato sbagliato: sono i più insidiosi, perché nulla segnala che qualcosa non va.

Metodi di test#

Il test black-box (a scatola nera) verifica il comportamento del programma solo confrontando input e output con la specifica, senza guardare il codice. Il test white-box (a scatola bianca), al contrario, guarda proprio il codice per assicurarsi che ogni istruzione e ogni ramo (ogni if, ogni case) venga effettivamente eseguito almeno una volta.

In entrambi i casi sono fondamentali i casi limite (edge case): array vuoti, numeri negativi, zero, il primo e l'ultimo elemento di una sequenza. La maggior parte dei bug si nasconde proprio ai confini, non nei casi "normali".

Il debug#

Quando un test fallisce, il debug è il processo con cui si individua la causa e si corregge. Le due tecniche più comuni sono le stampe di debug (printf sparsi nel codice per vedere il valore delle variabili in punti chiave) e il debugger (uno strumento, come gdb, che permette di eseguire il programma un'istruzione alla volta, fermarsi in punti precisi con dei breakpoint, e ispezionare il contenuto delle variabili).

Una tecnica semplice ma efficace è il divide et impera: isolare, o commentare, metà del codice sospetto per capire se il problema sta lì o nell'altra metà, restringendo il campo passo dopo passo invece di rileggere tutto il programma alla ricerca dell'errore.

Array e stringhe#

Array#

Un array è una sequenza di valori dello stesso tipo, memorizzati uno dopo l'altro in memoria e identificati da un indice che parte sempre da 0: in un array di 5 elementi, le posizioni valide vanno da 0 a 4.

int voti[5] = {7, 8, 6, 9, 10};

printf("%d\n", voti[0]);   // primo elemento: 7
printf("%d\n", voti[4]);   // ultimo elemento: 10

voti[2] = 5;                // modifica il terzo elemento

Gli array si usano quasi sempre insieme a un ciclo for, che scorre tutte le posizioni usando il contatore come indice:

int voti[5] = {7, 8, 6, 9, 10};
int somma = 0;

for (int i = 0; i < 5; i++) {
    somma += voti[i];       // somma = somma + voti[i]
}

double media = somma / 5.0;
printf("Media: %.2f\n", media);

Il C non controlla se l'indice usato è dentro i limiti dell'array: accedere a voti[5] o voti[-1] è un errore che spesso non blocca subito il programma, ma corrompe dati vicini in memoria, causando bug difficili da individuare anche molto lontano dal punto in cui si sono generati.

Array multidimensionali#

Un array a due dimensioni (una matrice) si può vedere come una tabella con righe e colonne; per accedere a un elemento servono due indici, e per scorrerla servono due cicli for annidati.

int tabella[2][3] = {
    {1, 2, 3},   // riga 0
    {4, 5, 6}    // riga 1
};

for (int r = 0; r < 2; r++) {
    for (int c = 0; c < 3; c++) {
        printf("%d ", tabella[r][c]);
    }
    printf("\n");   // a capo dopo ogni riga
}

Stringhe#

A differenza del C++, il C non ha un tipo string dedicato: una stringa è semplicemente un array di char che termina con il carattere speciale '\0' (carattere nullo), usato per segnalare dove finisce il testo.

char nome[20] = "Simone";   // il compilatore aggiunge automaticamente '\0' alla fine

printf("%s\n", nome);
printf("Lunghezza: %zu\n", strlen(nome));

L'header <string.h> mette a disposizione funzioni utili per lavorare con le stringhe: strlen calcola la lunghezza, senza contare il carattere nullo finale, strcpy copia una stringa in un'altra, strcat le concatena, strcmp le confronta restituendo 0 se sono uguali.

#include <string.h>

char saluto[30] = "Ciao, ";
char nome[] = "Marco";

strcat(saluto, nome);            // saluto diventa "Ciao, Marco"
printf("%s\n", saluto);

if (strcmp(nome, "Marco") == 0) {
    printf("Sei tu, Marco!\n");
}

Attenzione alle dimensioni: se copi o concateni una stringa più lunga dello spazio disponibile nell'array di destinazione, scrivi fuori dai suoi confini. È lo stesso problema di accedere a un array fuori indice, ma con le stringhe è particolarmente frequente, ed è una delle cause storiche di bug e vulnerabilità di sicurezza nei programmi C.

Puntatori e allocazione dinamica della memoria#

Cosa sono i puntatori#

Un puntatore è una variabile che, invece di contenere direttamente un valore, contiene l'indirizzo di memoria in cui quel valore si trova. Due operatori sono essenziali: & (indirizzo di), che restituisce l'indirizzo di una variabile, e * (dereferenziazione), che, applicato a un puntatore, accede al valore contenuto in quell'indirizzo.

int x = 10;
int *p = &x;      // p contiene l'indirizzo di x

printf("%d\n", *p);   // *p accede al valore puntato: 10

*p = 20;               // modifica x attraverso il puntatore
printf("%d\n", x);    // stampa 20

Il tipo di un puntatore (int *, char *...) indica il tipo di dato a cui punta, non il puntatore in sé: serve al compilatore per sapere quanti byte leggere e come interpretarli. Un puntatore che non punta a nulla di valido dovrebbe sempre essere inizializzato a NULL, e va controllato prima di essere usato.

Puntatori, array e funzioni#

In C il nome di un array, quasi ovunque venga usato, si comporta come un puntatore al suo primo elemento: arr[i] e *(arr + i) sono infatti equivalenti. È anche il motivo per cui gli array, passati a una funzione, non vengono mai copiati: la funzione riceve l'indirizzo dell'array originale, e può quindi modificarlo.

Le funzioni in C ricevono sempre una copia degli argomenti (passaggio per valore): modificare un parametro dentro la funzione non cambia la variabile originale del chiamante. Per modificare davvero una variabile esterna bisogna passarle esplicitamente il suo indirizzo con un puntatore:

void scambia(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(void) {
    int x = 5, y = 10;
    scambia(&x, &y);
    printf("%d %d\n", x, y);   // 10 5
    return 0;
}

È esattamente lo stesso meccanismo che usa scanf: scanf("%d", &eta) funziona perché riceve l'indirizzo di eta, e può quindi scrivere il valore letto direttamente nella variabile del chiamante.

Allocazione dinamica: malloc, realloc e free#

Le variabili viste finora vivono nello stack, una zona di memoria gestita automaticamente: nasce quando il programma entra in una funzione e viene liberata quando ne esce. A volte, però, non sappiamo in anticipo quanta memoria serve, ad esempio quanti elementi avrà un array perché dipende da un input dell'utente: in questi casi si usa lo heap, una zona di memoria che il programmatore gestisce esplicitamente con le funzioni della libreria <stdlib.h>.

#include <stdlib.h>

int n;
printf("Quanti voti? ");
scanf("%d", &n);

int *voti = malloc(n * sizeof(int));   // alloca spazio per n interi

if (voti == NULL) {
    printf("Memoria non disponibile\n");
    return 1;               // valore diverso da 0: il programma segnala un errore
}

for (int i = 0; i < n; i++) {
    voti[i] = i * 2;
}

free(voti);    // libera la memoria quando non serve più
voti = NULL;   // buona norma: evita di riusarla per errore

malloc restituisce l'indirizzo della memoria allocata, oppure NULL se l'allocazione fallisce: controllarlo è essenziale, perché usare un puntatore NULL come se fosse valido causa quasi sempre un crash. realloc permette di ridimensionare un blocco già allocato; conviene assegnarne il risultato a una variabile temporanea, perché se l'allocazione fallisce restituisce NULL, e si perderebbe altrimenti il riferimento al blocco originale.

La regola d'oro è che ogni malloc deve avere il suo free: dimenticarlo causa un memory leak, cioè memoria occupata che il programma non userà più, ma che il sistema operativo non può recuperare finché il programma resta in esecuzione.

Struct e file#

Raggruppare dati con le struct#

Una struct raggruppa più variabili, anche di tipi diversi, sotto un unico nome: utile per rappresentare un'entità con più proprietà, come uno studente con nome, età e media.

struct Studente {
    char nome[30];
    int eta;
    double media;
};

int main(void) {
    struct Studente s1 = {"Marco", 17, 7.5};
    printf("%s ha %d anni, media %.1f\n", s1.nome, s1.eta, s1.media);
    return 0;
}

Scrivere struct Studente ogni volta è scomodo: con typedef possiamo dare un nome più corto al tipo. Quando abbiamo un puntatore a una struct, si usa -> invece del punto per accedere ai suoi campi:

typedef struct {
    char nome[30];
    int eta;
} Persona;

int main(void) {
    Persona p1 = {"Anna", 16};
    Persona *ptr = &p1;

    printf("%s\n", ptr->nome);   // equivalente a (*ptr).nome
    return 0;
}

Leggere e scrivere file#

Per leggere o scrivere dati su disco si usa il tipo FILE, insieme a fopen per aprire un file specificando la modalità ("r" lettura, "w" scrittura che sovrascrive, "a" scrittura in coda), fprintf/fscanf per scrivere e leggere in modo formattato, e fclose per chiudere il file quando abbiamo finito.

#include <stdio.h>

int main(void) {
    FILE *f = fopen("voti.txt", "w");
    if (f == NULL) {
        return 1;
    }
    fprintf(f, "%d %d %d\n", 7, 8, 6);
    fclose(f);

    int a, b, c;
    f = fopen("voti.txt", "r");
    if (f == NULL) {
        return 1;
    }
    fscanf(f, "%d %d %d", &a, &b, &c);
    fclose(f);

    printf("%d %d %d\n", a, b, c);
    return 0;
}

Controllare sempre che fopen non restituisca NULL è essenziale: può fallire per tanti motivi (il file non esiste, mancano i permessi, il disco è pieno), ed è un caso concreto in cui un errore di runtime, se non gestito, provoca un crash invece di un messaggio chiaro.

Ricorsione#

Una funzione ricorsiva è una funzione che chiama se stessa per risolvere una versione più piccola dello stesso problema. Ogni funzione ricorsiva ha bisogno di un caso base, che si risolve senza ulteriori chiamate e ferma la ricorsione, e di un caso ricorsivo, che riduce il problema avvicinandolo al caso base.

int fattoriale(int n) {
    if (n <= 1) {          // caso base
        return 1;
    }
    return n * fattoriale(n - 1);   // caso ricorsivo
}

// fattoriale(4) restituisce 24

Per calcolare fattoriale(4), la funzione chiama fattoriale(3), che chiama fattoriale(2), che chiama fattoriale(1): qui si ferma, per il caso base, e restituisce 1; poi ogni chiamata sospesa riprende e moltiplica, "risalendo" fino al risultato finale. Ogni chiamata in sospeso occupa spazio nello stack: se il caso base non viene mai raggiunto, ad esempio passando un numero negativo, il programma esaurisce lo stack e termina con un errore (stack overflow).

La ricorsione non è sempre la scelta più efficiente — la somma di un array, ad esempio, si scrive più semplicemente con un ciclo — ma per problemi che si suddividono naturalmente in sotto-problemi identici, come vedremo tra poco con gli algoritmi di ordinamento più avanzati, rende il codice molto più chiaro di una versione iterativa equivalente.

Algoritmi di ordinamento e ricerca#

Ricerca sequenziale e ricerca binaria#

La ricerca sequenziale scorre l'array un elemento alla volta finché non trova quello cercato, o finché non arriva in fondo:

int ricercaSequenziale(int arr[], int n, int chiave) {
    for (int i = 0; i < n; i++) {
        if (arr[i] == chiave) {
            return i;      // trovato: restituisce la posizione
        }
    }
    return -1;             // non trovato
}

Se l'array è ordinato, la ricerca binaria è molto più efficiente: confronta la chiave con l'elemento centrale e, in base al risultato, scarta metà dell'array a ogni passo invece di scorrerlo tutto.

int ricercaBinaria(int arr[], int n, int chiave) {
    int inizio = 0, fine = n - 1;

    while (inizio <= fine) {
        int centro = (inizio + fine) / 2;

        if (arr[centro] == chiave) {
            return centro;
        } else if (arr[centro] < chiave) {
            inizio = centro + 1;   // scarta la metà sinistra
        } else {
            fine = centro - 1;     // scarta la metà destra
        }
    }
    return -1;   // non trovato
}

Bubble sort e selection sort#

Ordinare un array significa disporne gli elementi secondo un criterio, di solito crescente. Il bubble sort confronta ripetutamente coppie di elementi adiacenti e li scambia se sono nell'ordine sbagliato, facendo "risalire" gradualmente i valori più grandi verso la fine, come bolle:

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

Il selection sort segue un'idea diversa: a ogni passaggio cerca l'elemento più piccolo tra quelli non ancora ordinati, e lo scambia nella prima posizione utile.

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int indiceMin = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[indiceMin]) {
                indiceMin = j;
            }
        }

        int temp = arr[i];
        arr[i] = arr[indiceMin];
        arr[indiceMin] = temp;
    }
}

Entrambi sono semplici da capire ma poco efficienti su array grandi. Algoritmi più avanzati come merge sort e quicksort, basati sul paradigma divide et impera e quindi tipicamente implementati in modo ricorsivo, ottengono lo stesso risultato in modo molto più efficiente, come vedremo nel prossimo paragrafo parlando del costo degli algoritmi.

Il costo di un algoritmo: la notazione O grande#

Per confrontare due algoritmi che risolvono lo stesso problema non basta "provare a vedere quale è più veloce": il risultato dipenderebbe dal calcolatore usato, dal linguaggio, persino da cos'altro sta girando in quel momento. Serve una misura indipendente dall'hardware: si conta il numero di operazioni elementari eseguite in funzione della dimensione n dell'input.

Caso peggiore, migliore e medio#

Lo stesso algoritmo può comportarsi diversamente a seconda dei dati in ingresso. Nella ricerca sequenziale, ad esempio: nel caso migliore l'elemento cercato è il primo (1 confronto); nel caso peggiore non c'è, oppure è l'ultimo (n confronti); nel caso medio, su dati casuali, ci si aspettano circa n/2 confronti. In fase di progettazione si considera quasi sempre il caso peggiore, perché è quello che garantisce un limite superiore valido per qualunque input.

Le classi di complessità più comuni#

La notazione O grande descrive come cresce il numero di operazioni al crescere di n, ignorando costanti moltiplicative e termini di ordine inferiore: quello che conta è l'andamento per n grande, non i dettagli implementativi. Le classi più comuni, dalla più alla meno efficiente:

• ›O(1) — tempo costante: accedere a un elemento di un array tramite indice, indipendentemente da quanto è grande.
• ›O(log n) — tempo logaritmico: la ricerca binaria, perché a ogni passo dimezza lo spazio di ricerca.
• ›O(n) — tempo lineare: la ricerca sequenziale, perché nel caso peggiore serve scorrere tutti gli n elementi.
• ›O(n log n) — merge sort e quicksort: più lento di O(n) ma molto più veloce di O(n²) su array grandi.
• ›O(n²) — bubble sort e selection sort, che per ogni elemento ne confrontano molti altri: su un array 10 volte più grande, il tempo diventa circa 100 volte maggiore.

Questo spiega perché, con array grandi, la scelta dell'algoritmo giusto conta molto più della velocità del calcolatore su cui gira: un O(n²) su un array di un milione di elementi può metterci ore, mentre un O(n log n) equivalente impiega pochi secondi.

Liste concatenate#

Gli array hanno un limite intrinseco: la dimensione va decisa in anticipo, o gestita a mano con realloc, e inserire un elemento in mezzo richiede di spostare tutti quelli successivi. Una lista concatenata risolve questo problema rappresentando la sequenza come una catena di nodi allocati dinamicamente, ciascuno collegato al successivo tramite un puntatore.

Lista concatenata semplice#

Ogni nodo contiene un valore e un puntatore al nodo successivo, NULL se è l'ultimo. Con typedef e una struct che si riferisce a se stessa possiamo definirlo così:

typedef struct Nodo {
    int valore;
    struct Nodo *next;
} Nodo;

Nodo *creaNodo(int valore) {
    Nodo *n = malloc(sizeof(Nodo));
    n->valore = valore;
    n->next = NULL;
    return n;
}

Per inserire un nuovo nodo in testa alla lista serve modificare il puntatore alla testa stessa, non solo un nodo: per questo la funzione riceve un puntatore al puntatore (Nodo **testa), l'unico modo in C per modificare davvero una variabile passandone l'indirizzo, anche quando quella variabile è già essa stessa un puntatore.

void inserisciInTesta(Nodo **testa, int valore) {
    Nodo *nuovo = creaNodo(valore);
    nuovo->next = *testa;
    *testa = nuovo;
}

Per scorrere la lista si parte dalla testa e si segue next finché non si arriva a NULL:

Nodo *corrente = testa;

while (corrente != NULL) {
    printf("%d ", corrente->valore);
    corrente = corrente->next;
}

Lista doppiamente collegata#

Una lista doppiamente collegata aggiunge a ogni nodo un secondo puntatore, prev, verso il nodo precedente. Costa un po' di memoria in più per nodo, ma permette di scorrere la lista in entrambe le direzioni e di rimuovere un nodo di cui si ha già il riferimento senza dover ripartire dalla testa per trovarne il precedente.

typedef struct NodoD {
    int valore;
    struct NodoD *prev;
    struct NodoD *next;
} NodoD;

Come per ogni struttura allocata dinamicamente, ogni nodo creato con malloc va liberato con free quando non serve più: per le liste questo significa scorrerle e liberare i nodi uno a uno, non basta "perdere" il puntatore alla testa, altrimenti quella memoria resta occupata per tutta la durata del programma — il memory leak di cui parlavamo a proposito dell'allocazione dinamica.

In sintesi#

Abbiamo attraversato un percorso lungo: da come è fatto un calcolatore e come rappresenta l'informazione in bit, al sistema operativo che media tra hardware e programmi, dalla compilazione che trasforma il codice sorgente in eseguibile, fino alla progettazione di algoritmi corretti ed efficienti. Poi siamo entrati nel linguaggio C vero e proprio: variabili e tipi, istruzioni strutturate, funzioni, e infine le strutture dati che permettono di gestire quantità di dati più grandi e complesse — array, stringhe, puntatori, memoria dinamica, struct, file e liste concatenate.

Sono tantissimi concetti, ed è normale non fissarli tutti alla prima lettura. Il modo migliore per consolidarli resta lo stesso di sempre: scrivere codice. Prova a implementare gli algoritmi di ordinamento su array diversi, a costruire una lista concatenata da zero, a misurare quanto impiega un programma al crescere di n. E se poi passerai al C++, a Java o a Python, riconoscerai in ogni linguaggio gli stessi mattoni fondamentali che hai imparato qui, semplicemente vestiti in modo diverso.