Appunti di Programmazione II

PROGRAMMAZIONE II

Dispensa ragionata di C, strutture dati e progettazione del software

Università degli Studi di Torino · a.a. 2025/2026

Programmazione II 1

Sommario

• 1. Il corso, il C e il modello di memoria

• 2. Moduli, compilazione separata e sviluppo guidato dai test

• 3. Tipi composti: struct, typedef, enum e union

• 4. Memoria statica, automatica e dinamica

• 5. ADT, modularità, puntatori a funzione e generici

• 6. Liste collegate: modello e algoritmi iterativi

• 7. Ricorsione e induzione strutturale

• 8. Correttezza dei programmi e invarianti di ciclo

• 9. Alberi binari e alberi di ricerca

• 10. File e persistenza dei dati

• 11. Complessità computazionale

• 12. Debugging con GDB

• Appendice. Checklist di studio e laboratorio

Filo conduttore

Progettare bene in C significa scegliere una rappresentazione adeguata, descrivere il contratto delle funzioni,

gestire esplicitamente la memoria e controllare correttezza ed efficienza. Liste, alberi, ADT, ricorsione, testing

e complessità sono quindi aspetti collegati dello stesso metodo.

Programmazione II 2

1. Il corso, il C e il modello di memoria

Programmazione II riprende la programmazione imperativa in C e la porta verso problemi di dimensione

maggiore: memoria dinamica, strutture dati ricorsive, modularità, testing, correttezza, file e analisi

dell’efficienza. Il linguaggio è lo strumento con cui rendere eseguibili gli algoritmi; l’obiettivo è imparare a

progettare e controllare il comportamento del programma.

Obiettivi e prerequisiti

Sono dati per acquisiti i fondamenti di matematica discreta, la programmazione imperativa in C e le nozioni

elementari di correttezza formale: precondizioni, postcondizioni, logica di Floyd e invarianti di ciclo. Il corso

approfondisce allocazione dinamica, liste e alberi, separazione in più file, funzioni di ordine superiore, strutture

generiche, file, ADT, TDD e complessità asintotica.

Perché C?

C è nato dall’evoluzione di BCPL e B: Dennis Ritchie lo sviluppò ai Bell Laboratories a partire dal 1972. Il

linguaggio si diffuse con UNIX e fu standardizzato per ridurre le incompatibilità tra piattaforme. La sua forza è il

controllo diretto delle risorse e l’efficienza; il prezzo è che molte garanzie vengono lasciate al programmatore. C

è portabile se si programma con attenzione, ma non protegge automaticamente da accessi fuori dai limiti, uso

di memoria liberata o conversioni pericolose.

Tipizzazione e sicurezza

Definizioni

Un linguaggio è staticamente tipizzato se, al tempo di compilazione, il tipo associato a ogni variabile ed

espressione è noto. È dinamicamente tipizzato se il tipo viene determinato durante l’esecuzione. C è

staticamente tipizzato. Un linguaggio è type-safe se ogni operazione eseguibile su un dato è ammessa dal suo

tipo e gli usi scorretti producono un errore. C non è completamente type-safe.

Variabili: nome, tipo, indirizzo e valore

Una variabile C può essere descritta attraverso quattro proprietà: il tipo, che stabilisce come interpretare i byte

e quanto spazio occupano; il nome, usato dal programmatore; l’indirizzo, cioè la posizione in memoria; il valore

contenuto in quella posizione. L’operatore & produce l’indirizzo di una variabile, mentre * dereferenzia un

puntatore.

int x = 0;

int *p = &x;

*p = *p + 1; /* x vale ora 1 */

printf("%d %p\n", x, (void *)p);

L-value, r-value e const

In un’assegnazione il lato sinistro deve identificare una posizione modificabile, un l-value; il lato destro viene

valutato come valore, un r-value. Le quattro forme fondamentali di const per un puntatore sono: char *p,

puntatore e dati modificabili; char *const p, puntatore fisso a dati modificabili; const char *p, puntatore

riassegnabile a dati non modificabili tramite p; const char *const p, nessuno dei due modificabile tramite p.

Programmazione II 3

OSSERVAZIONE

Il principio del privilegio minimo vale anche per i tipi: una funzione dovrebbe ricevere soltanto l’accesso

necessario. Aggiungere const chiarisce il contratto, impedisce modifiche accidentali e riduce gli stati possibili

durante il debugging.

Un monito sulla progettazione

Il fallimento del volo Ariane 5 del 1996 mostra che un valore non rappresentabile deve essere gestito

esplicitamente. Un’accelerazione, maggiore rispetto a quella prevista per Ariane 4, fu convertita in un intero e

produsse un overflow nel sistema di navigazione. Il punto generale è che dominio dei dati, conversioni e limiti

numerici devono essere parte della specifica.

Programmazione II 4

2. Moduli, compilazione separata e sviluppo guidato

dai test

Un programma reale cresce più velocemente se il codice è diviso in moduli. La suddivisione migliora

organizzazione, manutenzione, testing e riuso. In C il modo naturale è separare la parte visibile, in un file

header .h, dall’implementazione, in uno o più file .c compilati separatamente.

Header, implementazione e applicazione

L’header contiene il contratto: prototipi e documentazione di ciò che il modulo offre. Il file .c contiene il codice

che realizza quel contratto. Il programma applicativo include l’header, ma non ha bisogno di conoscere

l’implementazione interna.

/* square.h */

/** Restituisce il quadrato di n. */

int square(int n);

/* square.c */

#include "square.h"

int square(int n) { return n * n; }

/* main.c */

#include <stdio.h>

#include "square.h"

int main(void) {

int n;

if (scanf("%d", &n) != 1) return 1;

printf("%d\n", square(n));

return 0;

}

Compilazione e linking

La compilazione separata produce un file oggetto per ogni sorgente. Il linker collega i file oggetto e le librerie,

risolvendo i riferimenti alle funzioni. Se si modifica soltanto square.c, non è necessario ricompilare main.c:

basta ricreare square.o e rilanciare il linking.

gcc -std=c18 -Wall -Wextra -pedantic -c square.c

gcc -std=c18 -Wall -Wextra -pedantic -c main.c

gcc -o square_app main.o square.o

Specificare prima di implementare

Una specifica descrive cosa deve fare una funzione, non come lo farà. Deve indicare precondizioni, risultato,

casi limite ed effetti sui parametri. Per esempio, stoi converte una stringa in un intero ignorando gli spazi iniziali,

riconoscendo un segno e fermandosi al primo carattere non numerico. L’overflow deve essere gestito oppure

dichiarato fuori specifica.

/* P-IN: s punta a una stringa terminata da '\0'.

P-OUT: converte le cifre iniziali dopo spazi e segno. */

int stoi(const char *s);

TDD: una specifica eseguibile

Nel Test-Driven Development si scrivono test significativi prima, o comunque contemporaneamente, al codice

di produzione. Una test suite è automatica, descrive esempi input-output, è necessariamente incompleta ma

deve evolvere insieme alla funzione. Il ciclo è: test che fallisce, minimo codice per superarlo, miglioramento

senza rompere i test esistenti.

static void check(const char *s, int expected) {

int result = stoi(s);

Programmazione II 5

if (result != expected)

printf("FAIL: '%s': atteso %d, ottenuto %d\n",

s, expected, result);

}

int main(void) {

check("", 0);

check("000420abc", 420);

check("-42", -42);

check(" +17x", 17);

check("abc12", 0);

}

Test di regressione

I test devono includere stringa vuota, zero, zeri iniziali, segno positivo e negativo, spazi, caratteri non numerici

all’inizio o dopo le cifre e casi limite. Quando la specifica cresce, si aggiungono test della nuova funzionalità e si

controlla che quelli precedenti continuino a passare: questo è il regression testing.

Programmazione II 6

3. Tipi composti: struct, typedef, enum e union

I tipi composti permettono di rappresentare concetti del problema invece di spargere variabili scollegate nel

programma. La scelta del tipo è già una parte della progettazione: rende visibili le relazioni tra dati e riduce gli

errori di interpretazione.

Struct: aggregare dati correlati

Una struct è un tipo derivato costituito da membri nominati, anche di tipo diverso. La definizione del tipo non

crea da sola una variabile né riserva lo spazio per un oggetto: è la dichiarazione della variabile a farlo. Si usa .

con una variabile struct e -> con un puntatore; p->m equivale a (*p).m.

struct card {

const char *face;

const char *suit;

};

struct card my_card = { "Three", "Hearts" };

struct card *card_ptr = &my_card;

printf("%s\n", card_ptr->suit);

Autoreferenzialità e assegnamento

Una struct non può contenere direttamente un membro del proprio tipo, perché ciò richiederebbe una

dimensione infinita; può però contenere un puntatore al proprio tipo, costruendo liste e alberi. L’assegnamento

tra struct copia tutti i membri: se un membro è un puntatore, viene copiato l’indirizzo, non l’oggetto puntato. C

non fornisce un confronto == tra struct.

typedef struct employee Employee;

struct employee {

char name[40];

unsigned int age;

Employee *manager;

};

Employee a = { "Ada", 30, NULL };

Employee b = a; /* copia anche l'indirizzo manager */

Struct come parametri

Una struct passata come argomento viene copiata per valore. Se è grande conviene passare un puntatore;

quando la funzione non deve modificarla, il puntatore va qualificato const. Un array di struct segue invece le

regole degli array e viene passato come indirizzo del primo elemento.

typedef struct { int values[3]; } ArrayBox;

void changes_copy(ArrayBox x) { x.values[0] = 7; }

void changes_original(int *x) { x[0] = 7; }

void reads_only(const ArrayBox *x) {

printf("%d\n", x->values[0]);

}

typedef ed enum

typedef introduce un sinonimo, non un nuovo tipo. È utile per rendere leggibili struct, puntatori a nodo e firme.

Una enum definisce costanti intere con nomi significativi; di default partono da zero e crescono di uno, ma è

possibile indicare valori iniziali. Gli identificatori devono essere distinti nello stesso ambito.

typedef struct card Card;

Card deck[52];

typedef enum {

OUTOFMEMORY = -1,

Programmazione II 7

ALREADYPRESENT,

INSERTED

} Outcome;

enum month { JAN = 1, FEB, MAR, APR, MAY, JUN,

JUL, AUG, SEP, OCT, NOV, DEC };

Union e tagged union

Una union ha la sintassi di una struct, ma tutti i membri condividono la stessa area di memoria: in un dato

istante è significativo un solo membro. Il programmatore deve ricordare quale membro è attivo; l’approccio

comune è associare una enum, ottenendo una tagged union.

enum ValueTag { IS_INT, IS_CHAR };

typedef struct {

enum ValueTag tag;

union { int i; char c; } data;

} TaggedValue;

TaggedValue x = { .tag = IS_INT, .data.i = 42 };

Funzioni variadiche

Una funzione variadica accetta un numero variabile di argomenti. Deve avere almeno un parametro fisso,

seguito da ..., e un modo per sapere quanti argomenti e di quali tipi leggere. <stdarg.h> fornisce va_list,

va_start, va_arg e va_end; il tipo richiesto a va_arg deve rispettare i tipi effettivi e le promozioni del C.

#include <stdarg.h>

double average(int count, ...) {

va_list ap;

double sum = 0.0;

va_start(ap, count);

for (int i = 0; i < count; i++)

sum += va_arg(ap, double);

va_end(ap);

return sum / count;

}

Programmazione II 8

4. Memoria statica, automatica e dinamica

La memoria non è un dettaglio invisibile in C. Capire durata, visibilità e responsabilità di ogni oggetto è

necessario per usare correttamente puntatori e strutture ricorsive.

Durata e visibilità

Una variabile locale automatica vive durante l’attivazione della funzione. Una locale static mantiene il proprio

valore tra chiamate successive, pur restando visibile soltanto nel blocco. Variabili globali e locali static

appartengono alla memoria statica e vivono per tutta l’esecuzione. A livello di file static limita il collegamento al

file corrente; extern dichiara una definizione fornita altrove.

int next_number(void) {

static int counter = 1;

return counter++;

}

/* restituisce 1, poi 2, poi 3, ... */

Le tre aree di memoria

• Memoria statica: programma compilato, globali e locali static.

• Memoria automatica, o stack: record di attivazione, parametri e locali non static delle funzioni attive.

• Memoria dinamica, o heap: blocchi richiesti durante l’esecuzione con malloc e restituiti con free.

malloc e free

malloc riceve il numero di byte e restituisce un void * al primo byte del blocco oppure NULL. In C non serve un

cast esplicito: il tipo del puntatore a sinistra rende l’assegnamento controllabile. free rende il blocco disponibile,

ma non cambia il valore del puntatore: dopo free il puntatore è dangling e non deve essere dereferenziato.

int *p = malloc(sizeof *p);

if (p == NULL) return 1;

*p = 42;

free(p);

p = NULL; /* non più utilizzabile */

OSSERVAZIONE

La coppia free(p); p = NULL; mantiene coerente lo stato del programma. Controllare p != NULL dopo una free

senza averlo azzerato non protegge: un indirizzo non nullo può riferirsi a un oggetto ormai inesistente.

Array dinamici e aritmetica dei puntatori

Per un array dinamico di n elementi di tipo T si alloca n * sizeof *ptr byte. ptr + 1 avanza di sizeof(T) byte, non di

un byte. Il puntatore iniziale va conservato fino alla free; se lo si incrementa, si perde l’indirizzo da restituire

all’allocatore.

size_t n = 10;

double *values = malloc(n * sizeof *values);

if (values == NULL) return 1;

for (size_t i = 0; i < n; i++) values[i] = 0.0;

free(values);

values = NULL;

Struct dinamiche

Una struct allocata dinamicamente si usa con ->. La dimensione va richiesta con sizeof *ptr, evitando

duplicazioni che diventano errate quando cambia il tipo.

typedef struct { char title[80]; int pages; } Book;

Programmazione II 9

Book *book = malloc(sizeof *book);

if (book == NULL) return 1;

book->pages = 200;

free(book);

book = NULL;

Array e parametri

Il nome di un array statico, quando viene passato a una funzione, si converte normalmente in un puntatore al

primo elemento. La dimensione non viaggia con il puntatore: va passata separatamente. Un array dinamico

aggiunge la responsabilità di liberare il blocco, ma occupa soltanto lo spazio richiesto.

Programmazione II 10

5. ADT, modularità, puntatori a funzione e generici

Un tipo di dato astratto descrive un insieme di valori e operazioni senza imporre al codice cliente una

rappresentazione concreta. La separazione tra ciò che un modulo offre e come lo realizza è il passaggio dalla

programmazione di piccoli esercizi alla progettazione del software.

Modulo, signature, accoppiamento e coesione

Definizioni di progettazione

Un modulo è un’unità di codice compilabile separatamente; in C è tipicamente un file .c. La signature è la parte

visibile, normalmente un file .h. L’accoppiamento misura quanto moduli diversi dipendono l’uno dall’altro; la

coesione misura quanto le funzioni di un modulo appartengono a un concetto unificante. Una buona

progettazione cerca basso accoppiamento e alta coesione.

Tipo opaco

Si può dichiarare un puntatore a struct senza rendere visibile la definizione della struct. L’header espone il

nome del tipo e le operazioni; l’implementazione definisce i campi. Il client può conservare e passare il

puntatore, ma non può accedere alla rappresentazione.

/* ADTcomplex.h */

typedef struct dcomplex *ADTcomplex;

ADTcomplex mkADTcomplex(double re, double im);

void dsADTcomplex(ADTcomplex *pc);

ADTcomplex sum(ADTcomplex a, ADTcomplex b);

double modulus(ADTcomplex z);

_Bool equal(ADTcomplex a, ADTcomplex b, double epsilon);

/* ADTcomplex.c */

struct dcomplex { double re; double im; };

Perché nascondere la rappresentazione

Se app.c può scrivere c.re e c.im, la rappresentazione cartesiana è parte del suo codice. Sostituirla con una

rappresentazione polare obbliga a modificare tutti i client. Un tipo opaco consente di sostituire

l’implementazione senza cambiare l’uso pubblico, riducendo l’accoppiamento al prezzo di indirezione e

gestione dinamica.

Puntatori a funzione

Il nome di una funzione rappresenta l’indirizzo del suo codice. Un puntatore a funzione può essere

memorizzato, passato e restituito. È il meccanismo con cui rendere un algoritmo parametrico rispetto a un

comportamento, per esempio una relazione d’ordine.

int less_equal(int x, int y) { return x <= y; }

size_t find_last_max(const int a[], size_t n,

int (*compare)(int, int)) {

size_t max_index = 0;

for (size_t i = 1; i < n; i++)

if (compare(a[max_index], a[i])) max_index = i;

return max_index;

}

/* find_last_max(a, n, less_equal) */

Programmazione II 11

void * e polimorfismo universale

Un void * contiene un indirizzo verso un oggetto di tipo non noto. La dimensione del puntatore è nota, quella

dell’oggetto puntato no: non si può dereferenziare direttamente un void *. Prima bisogna riconvertirlo al tipo

corretto. Il client è responsabile della validità dei puntatori e della scelta coerente del comparatore.

int int_compare(const void *x, const void *y) {

int a = *(const int *)x;

int b = *(const int *)y;

return (a > b) - (a < b);

}

void *maximum(void *a[], size_t n,

int (*compare)(const void *, const void *)) {

void *max = a[0];

for (size_t i = 1; i < n; i++)

if (compare(max, a[i]) < 0) max = a[i];

return max;

}

ADT Set e SortedSet

Un Set è una collezione non ordinata senza dup