Strutture Dati Statiche in C++ — Formazione Digitale

00 — Perché

Perché le strutture dati?

Immagina di dover gestire i voti di una classe di 30 studenti. Senza strutture dati servirebbe una variabile per ogni studente — int voto1, voto2, ..., voto30 — con 30 dichiarazioni separate, 30 istruzioni di input, 30 condizioni in ogni algoritmo. Il codice diventa ingestibile al primo problema reale.

Le strutture dati risolvono questo problema organizzando dati correlati in modo sistematico. Con un array bastano una dichiarazione e un ciclo for per operare su tutti i 30 voti. Tre vantaggi immediati: il codice è più leggibile, più breve e funziona allo stesso modo per 30 o per 3000 studenti.

📌 Due famiglie principali

🏗 Statiche — questa pagina

Dimensione fissata a compile time. Memoria nello stack. Più semplici da usare, meno flessibili.

🔗 Dinamiche — pagina successiva

Dimensione variabile a runtime. Memoria nell'heap con new / delete. Più flessibili, richiedono gestione esplicita della memoria.

Questa pagina copre: array monodimensionale, array bidimensionale (matrice), struct, array di struct, stack su array e coda su array.

01 — Struttura

Array monodimensionale

Un array è una sequenza di elementi dello stesso tipo, memorizzati in celle contigue in memoria. Ogni cella è identificata da un indice intero che parte da 0 e arriva a n-1. L'accesso a qualsiasi elemento è O(1): il programma calcola l'indirizzo direttamente dall'indice, senza scorrere nulla.

⚠ La dimensione è fissa e nota a compile time In C++ la dimensione di un array statico deve essere una costante intera — non una variabile. Il compilatore deve sapere quanto spazio riservare nello stack prima di eseguire il programma.

int n = 5; int arr[n]; // ❌ errore — n non è una costante
const int N = 5; int arr[N]; // ✔ corretto

Per array a dimensione variabile (stabilita a runtime) si usa l'allocazione dinamica con new — argomento della pagina sulle strutture dinamiche.

Dichiarazione e inizializzazione

C++ · dichiarazione

const int N = 5;
int voti[N];                        // non inizializzato (valori indeterminati)
int voti[N] = {7, 8, 6, 9, 5};   // con valori iniziali
int voti[]  = {7, 8, 6, 9, 5};   // dimensione dedotta: n=5
int voti[N] = {};                   // tutti gli elementi a zero

Accesso e iterazione

C++ · accesso per indice

voti[0] = 10;             // modifica il primo elemento
cout << voti[2];          // stampa il terzo elemento (indice 2)
for (int i = 0; i < N; i++) {
    cout << "voti[" << i << "] = " << voti[i] << endl;
}

⚠ Out of bounds — comportamento indefinito Accedere a un indice negativo o ≥ n non genera un errore in C++: il programma legge o scrive memoria arbitraria. Il risultato è imprevedibile. Il compilatore non controlla i limiti — è responsabilità del programmatore.

Array e funzioni

Passare un array a una funzione significa passare l'indirizzo del primo elemento, non una copia. Le modifiche apportate dentro la funzione si riflettono sull'array originale. Per questo non occorre restituire l'array con return: è già passato per riferimento implicitamente.

C++ · array_funzioni.cpp

#include <iostream>
using namespace std;

// modifica l'array originale — le modifiche restano dopo la chiamata
void raddoppia(int arr[], int n) {
    for (int i = 0; i < n; i++)
        arr[i] *= 2;
}

// const protegge da modifiche involontarie — lettura sola
float calcolaMedia(const int arr[], int n) {
    int somma = 0;
    for (int i = 0; i < n; i++) somma += arr[i];
    return (float)somma / n;
}

int main() {
    const int N = 5;
    int voti[N] = {7, 8, 6, 9, 5};
    cout << "Media: " << calcolaMedia(voti, N) << endl;  // 7.0
    raddoppia(voti, N);   // voti ora è {14, 16, 12, 18, 10}
    cout << "Media dopo raddoppio: " << calcolaMedia(voti, N) << endl; // 14.0
    return 0;
}

📌 Cosa succede davvero quando passi un array a una funzione Quando scrivi raddoppia(voti, N), il C++ non copia l'intero array: passa solo l'indirizzo del primo elemento. Dentro la funzione, arr[i] e voti[i] puntano alla stessa cella di memoria. Scrivere arr[i] *= 2 modifica direttamente l'elemento originale — la modifica è visibile nel chiamante anche dopo che la funzione è terminata. Non serve usare return per “restituire” l'array modificato: è già lì.

💡 Non si può restituire un array locale con return Scrivere int* f() { int arr[5]; return arr; } è un errore: l'array locale viene distrutto quando la funzione termina e il puntatore diventa invalido. La soluzione è modificare l'array passato come parametro — che vive nel chiamante e non viene distrutto.

🔧 Vettore Visivo

Imposta la dimensione (1–10) e genera un array con valori casuali. Clicca su una cella per modificarne il valore. Digita un indice per evidenziare la posizione corrispondente.

🔧 Vettore VisivoDimensione libera · Valori modificabili

Dimensione (1–10):

arr[ ]

Genera un array per iniziare

Indice fuori range — valori validi: 0 … n-1

💡 Clicca su una cella per modificare il valore · Usa ⏎ e Esc per confermare o annullare

Imposta la dimensione e premi Genera.

02 — Struttura

Array bidimensionale (matrice)

Un array bidimensionale è un array di array: ogni elemento è identificato da due indici, riga e colonna. Si dichiara con tipo nome[RIGHE][COLONNE]. In memoria gli elementi sono contigui, memorizzati riga per riga (row-major): prima tutti gli elementi della riga 0, poi della riga 1, e così via.

Dichiarazione e inizializzazione

C++ · dichiarazione matrice

const int RIGHE = 3, COLONNE = 4;
int m[RIGHE][COLONNE];   // matrice 3x4 non inizializzata
int m[3][4] = {
    { 1,  2,  3,  4},   // riga 0
    { 5,  6,  7,  8},   // riga 1
    { 9, 10, 11, 12}    // riga 2
};

Accesso e ciclo annidato

C++ · accesso e stampa

m[0][0] = 1;   // prima riga, prima colonna
m[2][3] = 12;  // terza riga, quarta colonna
for (int i = 0; i < RIGHE; i++) {
    for (int j = 0; j < COLONNE; j++)
        cout << m[i][j] << "\t";
    cout << endl;
}

Passare una matrice a una funzione

Per passare un array bidimensionale a una funzione, il numero di colonne è obbligatorio nella firma — il compilatore ne ha bisogno per calcolare l'indirizzo di ogni cella. Il numero di righe si passa come parametro separato.

C++ · matrice_funzione.cpp

#include <iostream>
using namespace std;
const int COLONNE = 4;

// le colonne DEVONO essere specificate nella firma
void stampaMatrice(const int m[][COLONNE], int righe) {
    for (int i = 0; i < righe; i++) {
        for (int j = 0; j < COLONNE; j++)
            cout << m[i][j] << "\t";
        cout << endl;
    }
}

int sommaMatrice(const int m[][COLONNE], int righe) {
    int tot = 0;
    for (int i = 0; i < righe; i++)
        for (int j = 0; j < COLONNE; j++)
            tot += m[i][j];
    return tot;
}

int main() {
    int m[3][COLONNE] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
    stampaMatrice(m, 3);
    cout << "Somma: " << sommaMatrice(m, 3) << endl;  // 78
    return 0;
}

🔧 Matrice Visiva

Scegli righe e colonne (max 6×6), genera con valori casuali, poi clicca su una cella per vedere i suoi indici.

🔧 Matrice VisivaDimensioni configurabili · Clicca per leggere m[i][j]

Righe (1–6): Colonne (1–6):

Premi “Genera casuale” per creare la matrice.

Imposta le dimensioni e premi Genera.

03 — Struttura

Struct (record)

In informatica, un record è una struttura dati che raccoglie informazioni di tipo diverso (eterogenee) relative a una singola entità. In C++ il record si chiama struct. Il concetto è identico a quello di record in un database: ogni campo ha un nome e un tipo, e insieme descrivono un oggetto del mondo reale.

Database (tabella Studenti)	C++ struct Studente
Campo `matricola INT`	`int matricola;`
Campo `nome VARCHAR(30)`	`char nome[30];`
Campo `media FLOAT`	`float media;`
Un record = una riga della tabella	Una variabile di tipo `Studente`

struct e typedef struct — differenza

In C++ esistono due modi per definire una struct. Il risultato è equivalente, ma la sintassi cambia.

C++ · struct vs typedef struct

// FORMA 1 — struct classica C++
struct Studente {
    int   matricola;
    char  nome[30];
    float media;
};
Studente s1;          // ✔ C++ standard (senza "struct" davanti)
struct Studente s1;   // ✔ stile C (più verboso)


// FORMA 2 — typedef struct (stile C, comune nei libri scolastici)
typedef struct {
    int   matricola;
    char  nome[30];
    float media;
} Studente;             // "Studente" è un alias del tipo anonimo
Studente s1;          // ✔ unico modo valido
struct Studente s1;   // ❌ errore — non esiste "struct Studente"


// In questo corso useremo typedef struct per coerenza con i testi adottati.

Dichiarazione, operatore punto e accesso ai campi

L'operatore punto (.) è il modo per accedere ai singoli campi di una variabile struct. Si legge come “della variabile, il campo”: s1.media è “di s1, la media”. È il collegamento diretto tra la variabile e il suo dato interno.

C++ · accesso ai campi

Studente s1;                     // dichiarazione — spazio nello stack
// operatore punto: variabile.campo
s1.matricola = 101;
s1.media     = 8.5f;
strcpy(s1.nome, "Anna Bianchi");  // per char[] si usa strcpy, non =

// inizializzazione diretta (stesso ordine dei campi)
Studente s2 = {102, "Mario Rossi", 7.8f};
cout << s2.matricola << " " << s2.nome << " " << s2.media << endl;

Così appare in memoria la variabile s1 dopo l'inizializzazione:

Studente s1 — una variabile, tre campi

intmatricola101

char[30]nome"Anna Bianchi"

floatmedia8.5

Esempio completo

C++ · struct_studente.cpp

#include <iostream>
#include <cstring>
using namespace std;
typedef struct { int matricola; char nome[30]; float media; } Studente;
void stampa(Studente s) {
    cout << s.matricola << " | " << s.nome << " | " << s.media << endl;
}
int main() {
    Studente s1 = {101, "Anna Bianchi", 8.5f};
    Studente s2 = {102, "Mario Rossi",  7.2f};
    stampa(s1); stampa(s2);
    return 0;
}

04 — Struttura

Array di struct

Combinando array e struct si ottiene una struttura dati potente: un array in cui ogni cella contiene un record completo. È l'equivalente diretto di una tabella di database in memoria — righe di dati strutturati, accessibili per indice in O(1).

Rappresentazione visiva

Ogni cella dell'array contiene un record completo. Le celle sono affiancate orizzontalmente con gli indici sopra — esattamente come un array semplice, ma ogni slot è una struct con tre campi.

[0]

[1]

[2]

[3]

[4]

matricola101

nomeAnna Bianchi

media8.5

matricola102

nomeMario Rossi

media7.2

matricola103

nomeLuca Verdi

media9.1

slot
libero

Ogni cella = una variabile Studente · Ogni campo visibile separatamente · classe[1].nome → "Mario Rossi"

Dichiarazione

C++ · array di struct

const int MAX = 30;
Studente classe[MAX];   // array di 30 record Studente
Studente classe[3] = {
    {101, "Anna Bianchi", 8.5f},
    {102, "Mario Rossi",  7.2f},
    {103, "Luca Verdi",   9.1f}
};
cout << classe[0].nome;      // "Anna Bianchi"
cout << classe[2].matricola;  // 103

Inserimento di un nuovo record

Con un array di struct si usa un contatore (n) che tiene traccia di quanti elementi sono stati effettivamente inseriti. Il contatore va passato per riferimento (&) affinché la funzione possa aggiornarlo.

C++ · inserisci record

void inserisci(Studente cl[], int& n, int mat, const char* nome, float media) {
    if (n >= MAX) { cout << "Array pieno!" << endl; return; }
    cl[n].matricola = mat;
    strcpy(cl[n].nome, nome);
    cl[n].media     = media;
    n++;   // il contatore aggiornato si riflette nel chiamante
}
// utilizzo:
int n = 0;
inserisci(classe, n, 101, "Anna Bianchi", 8.5f);
inserisci(classe, n, 102, "Mario Rossi",  7.2f);
cout << "Studenti inseriti: " << n << endl;  // 2

Iterazione e ricerca

C++ · array_struct_completo.cpp

#include <iostream>
#include <cstring>
using namespace std;
typedef struct { int matricola; char nome[30]; float media; } Studente;
const int MAX = 30;
int main() {
    Studente classe[MAX];
    int n = 0;
    classe[n++] = {101, "Anna Bianchi", 8.5f};
    classe[n++] = {102, "Mario Rossi",  7.2f};
    classe[n++] = {103, "Luca Verdi",   9.1f};
    for (int i = 0; i < n; i++)
        cout << classe[i].matricola << " | " << classe[i].nome << " | " << classe[i].media << endl;
    int cerca = 102;
    for (int i = 0; i < n; i++) {
        if (classe[i].matricola == cerca) { cout << "Trovato: " << classe[i].nome << endl; break; }
    }
    return 0;
}

💡 Passare array di struct a una funzione Come per gli array semplici, si passa il puntatore al primo elemento. Usare const Studente cl[] per le funzioni che non devono modificare i dati. Ricordare di passare sempre anche il contatore n degli elementi effettivi.

05 — Struttura

Stack (pila)

Uno stack è una struttura dati LIFO (Last In, First Out): l'ultimo elemento inserito è il primo ad essere estratto, come una pila di piatti. Applicazioni: cronologia “Annulla”, gestione delle chiamate a funzione, parsing di espressioni matematiche.

Operazioni ADT

Operazione	Descrizione	Precondizione
push(x)	Inserisce x in cima alla pila	Pila non piena
pop()	Rimuove e restituisce l'elemento in cima	Pila non vuota
top()	Restituisce l'elemento in cima senza rimuoverlo	Pila non vuota
isEmpty()	Vero se la pila non contiene elementi	—
isFull()	Vero se la pila ha raggiunto la capacità massima	—

📌 Convenzione: top = -1 L'indice top viene inizializzato a -1 per indicare la pila vuota. Prima di ogni push si incrementa top, poi si inserisce: arr[++top] = val. Prima di ogni pop si legge il valore, poi si decrementa: return arr[top--].

Implementazione in C++

C++ · stack_array.cpp

#include <iostream>
using namespace std;
const int MAX = 5;
typedef struct { int arr[MAX]; int top; } Stack;
void init(Stack &s)         { s.top = -1; }
bool isEmpty(Stack &s)     { return s.top == -1; }
bool isFull(Stack &s)      { return s.top == MAX - 1; }
void push(Stack &s, int v) { if (!isFull(s))  s.arr[++s.top] = v; }
int  pop(Stack &s)          { if (!isEmpty(s)) return s.arr[s.top--]; return -1; }
int  top(Stack &s)          { if (!isEmpty(s)) return s.arr[s.top];   return -1; }
int main() {
    Stack s; init(s);
    push(s, 10); push(s, 25); push(s, 7);
    cout << top(s) << endl;  // 7
    cout << pop(s) << endl;  // 7
    cout << top(s) << endl;  // 25
    return 0;
}

🔧 Prova le operazioni (max 5 elementi)

🔧 Stack InterattivoLIFO — Last In, First Out

▼ cima (push/pop)

[4]← top

[3]← top

[2]← top

[1]← top

[0]← top

↑ base

top = —
isEmpty() = vero
isFull() = falso

Pila inizializzata — top = -1.

06 — Struttura

Coda (queue)

Una coda è una struttura dati FIFO (First In, First Out): il primo elemento inserito è il primo ad essere estratto, come la coda allo sportello. Applicazioni: code di stampa, buffer di rete, scheduling dei processi.

Operazioni ADT

Operazione	Descrizione	Precondizione
enqueue(x)	Inserisce x in fondo alla coda	Coda non piena
dequeue()	Rimuove e restituisce l'elemento in testa	Coda non vuota
front()	Restituisce l'elemento in testa senza rimuoverlo	Coda non vuota
isEmpty()	Vero se la coda non contiene elementi	—
isFull()	Vero se la coda ha raggiunto la capacità massima	—

📌 Convenzione: testa e coda testa indica l'indice del primo elemento da estrarre. coda indica l'indice dell'ultimo elemento inserito (inizializzato a -1 per coda vuota). Ogni enqueue incrementa coda; ogni dequeue incrementa testa. In questa implementazione lineare la coda non è riutilizzabile — per questo esiste la coda circolare.

Implementazione in C++

C++ · coda_array.cpp

#include <iostream>
using namespace std;
const int MAX = 10;
typedef struct { int arr[MAX]; int testa; int coda; int count; } Coda;
void init(Coda &q)    { q.testa=0; q.coda=-1; q.count=0; }
bool isEmpty(Coda &q) { return q.count==0; }
bool isFull(Coda &q)  { return q.count==MAX; }
void enqueue(Coda &q, int v) {
    if (isFull(q)) { cout << "Coda piena!" << endl; return; }
    q.arr[++q.coda] = v; q.count++;
}
int dequeue(Coda &q) {
    if (isEmpty(q)) { cout << "Coda vuota!" << endl; return -1; }
    int v = q.arr[q.testa++]; q.count--;
    return v;
}
int main() {
    Coda q; init(q);
    enqueue(q, 5); enqueue(q, 3); enqueue(q, 8);
    cout << dequeue(q) << endl;  // 5
    cout << dequeue(q) << endl;  // 3
    return 0;
}

🔧 Prova le operazioni (10 slot)

🔧 Coda Interattiva (10 slot)FIFO — First In, First Out

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

testa = 0 | coda = -1 | count = 0

Il visualizzatore scorre gli elementi a sinistra dopo ogni Dequeue per chiarezza grafica. Nel codice C++ con array lineare, è l'indice testa a scorrere verso destra.

Coda inizializzata — testa = 0, coda = -1.