Appunti · InformaticaIT · Maturità

Strutture dati e loro implementazione

Una struttura dati e un modo organizzato di rappresentare e conservare un insieme di dati in memoria, insieme alle operazioni che li manipolano: la scelta della struttura giusta determina la chiarezza e soprattutto l'efficienza degli algoritmi che la usano. In questo appunto si parte dai tipi strutturati statici (array, matrici, stringhe), si passa ai record e ai tipi definiti dall'utente, si studiano le strutture dinamiche lineari (liste concatenate, pile e code), si accenna alle strutture non lineari (alberi e grafi) e si chiude con gli algoritmi fondamentali di ricerca e ordinamento, valutandone il costo con la notazione asintotica.

5sezionica. 19min di lettura3competenzeLivelloBase 2 · Standard 1 · Approfondimento 2Verificato · 06/2026

T·0333 / 14

Profilo d’esame

Scegliere e implementare la struttura dati adeguata al problema da risolvereCollegare la rappresentazione dei dati all'efficienza degli algoritmi che li elaboranoOrganizzare e manipolare insiemi di dati con strutture appropriate (lineari e non lineari)

Operatori:descrivispiegaimplementaconfrontaclassificaanalizzadeterminagiustifica

livello base

E richiesto saper riconoscere e usare gli array, le pile e le code, descrivendone le operazioni fondamentali e applicando la ricerca lineare/binaria e un ordinamento elementare.

livello avanzato

Nell'opzione Scienze Applicate si chiede di implementare le strutture in un linguaggio reale (anche le liste concatenate), di motivare la scelta della struttura sul problema e di giustificare l'efficienza degli algoritmi con la notazione asintotica O-grande.

Profondità

Schrift

Inhalt · 5 sezioni

Strutture dati e loro implementazione

Array, matrici e stringhe#

BasisOSA-informatica-fondamenti-strutture-datiTipi di dato strutturati: array (vettori e matrici) e stringhe

Array di interi con indici e accesso diretto

Un array (o vettore) e la struttura dati piu elementare: una sequenza di elementi tutti dello stesso tipo, collocati in celle di memoria contigue e individuati da un indice intero. La proprieta decisiva e l'accesso diretto (o casuale): dato l'indice i, l'elemento si raggiunge in un solo passo, perche l'indirizzo della cella si calcola con la formula indirizzo(i) = base + i x dimensione_elemento. Per questo l'accesso e l'aggiornamento di un elemento costano un tempo costante, indipendente dalla lunghezza dell'array.

L'array e una struttura statica e a dimensione fissa: la sua lunghezza n viene decisa al momento della creazione e non cambia. Gli indici, nella maggior parte dei linguaggi moderni (Python, C, Java), partono da 0 e arrivano a n-1: questo e il motivo per cui un array di n elementi ha come ultimo indice valido n-1, e accedere all'indice n e un errore (sconfinamento). La contiguita in memoria, che rende l'array velocissimo in lettura, e anche il suo limite: inserire o cancellare un elemento in mezzo costringe a spostare tutti gli elementi successivi.

Una matrice e un array bidimensionale: una tabella di righe e colonne, ottenuta concettualmente come array i cui elementi sono a loro volta array. L'elemento di riga i e colonna j si indica con M[i][j]; in memoria la matrice viene linearizzata, tipicamente per righe (row-major order), cosicche l'elemento M[i][j] di una matrice con C colonne occupa la posizione lineare i x C + j. Le matrici modellano griglie, immagini, tabelle e sistemi lineari, e si generalizzano in array a piu dimensioni.

Una stringa e, dal punto di vista della rappresentazione, un array di caratteri: ogni carattere e codificato (per esempio in Unicode/UTF-8) e occupa una posizione indicizzabile. Le operazioni tipiche sono la lettura del carattere i-esimo, il calcolo della lunghezza, la concatenazione e la ricerca di una sottostringa. Trattare la stringa come array spiega perche scorrere tutti i suoi caratteri costa un tempo proporzionale alla lunghezza, mentre leggere un singolo carattere noto e immediato.

\text{indirizzo}(i) = \text{base} + i \cdot d

Indirizzo di un elemento

In un array, l'indirizzo dell'elemento di indice i si ottiene dall'indirizzo base sommando i volte la dimensione d di un elemento: il calcolo e immediato, quindi l'accesso e a costo costante O(1).

\text{pos}(i,j) = i \cdot C + j

Linearizzazione per righe

In una matrice memorizzata per righe (row-major) con C colonne, l'elemento di riga i e colonna j occupa la posizione lineare i x C + j; gli indici partono da 0.

Esempio svolto

Indirizzo di un elemento di matrice

Una matrice M di interi ha 4 righe e 5 colonne ed e memorizzata per righe (row-major), a partire dall'indirizzo base 1000; ogni intero occupa 4 byte. Determina l'indirizzo in memoria dell'elemento M[2][3] (indici a partire da 0).

Posizione lineare
Con C = 5 colonne, la posizione lineare e pos = i x C + j = 2 x 5 + 3.
Indirizzo in byte
Si moltiplica la posizione per la dimensione d = 4 byte e si somma all'indirizzo base 1000.
Calcolo finale
13 x 4 = 52, quindi 1000 + 52 = 1052.

Risultato: L'elemento M[2][3] si trova all'indirizzo 1052; l'intera posizione si calcola con poche operazioni aritmetiche, quindi l'accesso e a costo costante O(1).

Errori frequenti

Confondere il numero di elementi (n) con l'ultimo indice (n-1) e scrivere cicli che accedono all'indice n, provocando un errore a tempo di esecuzione.
Credere che inserire un elemento in mezzo a un array sia istantaneo: in realta richiede di spostare tutti gli elementi seguenti, con costo O(n).

Ripasso attivo

Dato un array A di n numeri interi, scrivi (in pseudocodice o in un linguaggio a tua scelta) un algoritmo che calcoli la somma e il valore massimo degli elementi con una sola scansione, indicandone il costo asintotico in funzione di n.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Record e tipi di dato definiti dall'utente#

BasisOSA-informatica-fondamenti-strutture-datiRecord/strutture e tipi di dato definiti dall'utente

Record Studente: campi eterogenei sotto un unico nome

Un record (chiamato struct in C, e realizzato come classe/dataclass o namedtuple in Python e come record o classe in Java) e un tipo di dato strutturato che raggruppa sotto un unico nome piu valori, anche di tipo diverso, ciascuno identificato da un campo. Mentre l'array aggrega elementi omogenei accessibili per posizione, il record aggrega valori eterogenei accessibili per nome del campo: per esempio uno studente puo essere descritto dai campi cognome (stringa), matricola (intero) e media (reale).

Il record permette di costruire tipi di dato definiti dall'utente, cioe nuovi tipi modellati sulla realta del problema, andando oltre i tipi primitivi (intero, reale, carattere, booleano) offerti dal linguaggio. Questa astrazione e fondamentale: dare un nome unico a un'entita composta rende il programma piu leggibile, riduce gli errori e prepara il terreno alla programmazione a oggetti, dove al dato si aggiungono anche i metodi che lo manipolano (ripasso: incapsulamento).

Combinando record e array si ottengono le strutture dati che descrivono collezioni di entita: un array di record rappresenta, ad esempio, l'elenco degli studenti di una classe, dove ogni cella contiene un record con i suoi campi. L'accesso avviene in due passi: prima si seleziona l'elemento per indice (array), poi il campo per nome (record), come in elenco[i].media.

Il record e anche il mattone con cui si costruiscono le strutture dinamiche: un nodo di una lista o di un albero e tipicamente un record che contiene il valore (informazione) e uno o piu campi puntatore/riferimento ad altri nodi. La capacita di definire tipi composti e quindi il ponte tra i tipi primitivi e le strutture dati avanzate trattate nelle sezioni successive.

Esempio svolto

Media dei valori di un campo in un array di record

Dato un array elenco di N record Studente (con i campi cognome, matricola, media), scrivi un algoritmo che calcoli la media aritmetica del campo media su tutti gli studenti e indicane il costo.

Inizializzazione
Si pone un accumulatore somma a 0.
Scansione
Per i da 0 a N-1 si somma elenco[i].media all'accumulatore: si accede prima all'elemento per indice, poi al campo per nome.
Media
Al termine si divide la somma per N (con N > 0).

Risultato: L'algoritmo esegue una sola scansione dell'array, quindi ha costo lineare O(N); restituisce la media dei voti se N > 0, altrimenti il valore non e definito.

Errori frequenti

Usare array paralleli (un array per ogni attributo) al posto di un array di record, perdendo la coesione logica dell'entita e moltiplicando le occasioni di disallineamento tra gli array.
Confondere il tipo (la definizione del record, il modello) con la variabile (la singola istanza con valori concreti dei campi).

Ripasso attivo

Definisci un tipo record Libro con i campi titolo (stringa), anno (intero) e prezzo (reale); dichiara poi un array di 100 libri e scrivi l'istruzione che assegna 19.90 al prezzo del terzo libro del catalogo.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Strutture dinamiche lineari: liste, pile e code#

StandardOSA-informatica-fondamenti-strutture-datiStrutture dati dinamiche e lineari: liste, pile (stack) e code (queue)

Pila (LIFO) e coda (FIFO) a confronto con le rispettive operazioni

Le strutture dinamiche superano il limite della dimensione fissa dell'array: crescono e si riducono durante l'esecuzione, allocando e liberando memoria secondo necessita. La struttura dinamica lineare fondamentale e la lista concatenata: una sequenza di nodi, dove ogni nodo e un record che contiene un'informazione e un puntatore (riferimento) al nodo successivo; l'ultimo nodo punta a nullo (NULL/None) e una variabile testa indica il primo nodo.

Nella lista concatenata i nodi non sono contigui in memoria, percio non c'e accesso diretto: per raggiungere l'i-esimo elemento occorre partire dalla testa e seguire i puntatori, con costo O(n). In compenso, inserire o cancellare un nodo del quale si conosce gia la posizione costa O(1), perche basta ridirigere uno o due puntatori senza spostare alcun dato. E qui il compromesso fondamentale: l'array privilegia l'accesso, la lista privilegia l'inserimento/cancellazione.

La pila (stack) e una struttura lineare con disciplina LIFO (Last In, First Out): l'ultimo elemento inserito e il primo a essere estratto, come in una pila di piatti. Espone solo due operazioni principali, entrambe sulla cima (top): push (inserisce un elemento in cima) e pop (rimuove e restituisce l'elemento in cima); spesso si aggiungono top/peek (leggi la cima senza rimuoverla) e isEmpty. La pila modella la valutazione delle espressioni, la gestione delle chiamate di funzione (record di attivazione) e l'annullamento delle operazioni (undo).

La coda (queue) e una struttura lineare con disciplina FIFO (First In, First Out): il primo elemento inserito e il primo a uscire, come in una fila allo sportello. Le operazioni avvengono ai due estremi: enqueue inserisce in fondo (coda), dequeue rimuove dalla testa. La coda modella tutte le situazioni di attesa ordinata: code di stampa, scheduling dei processi nel sistema operativo, buffer di comunicazione. Sia pila sia coda, se ben implementate, eseguono le loro operazioni in tempo costante O(1).

Lista concatenata: nodi (informazione + puntatore al successivo)

Esempio svolto

Sequenza di operazioni su una pila

Una pila e inizialmente vuota. Esegui nell'ordine: push(5), push(8), pop, push(3), pop, push(7). Indica l'elemento estratto da ciascun pop e il contenuto finale della pila dalla base alla cima.

push(5), push(8)
La pila diventa, dalla base alla cima: 5, 8. La cima e 8.
pop
Si rimuove la cima: viene estratto 8 (l'ultimo inserito, LIFO). Resta: 5.
push(3)
Si inserisce 3 in cima. La pila diventa: 5, 3.
pop
Si rimuove la cima: viene estratto 3. Resta: 5.
push(7)
Si inserisce 7 in cima. La pila diventa: 5, 7.

Risultato: I pop estraggono nell'ordine 8 e poi 3; il contenuto finale della pila, dalla base alla cima, e 5, 7.

Errori frequenti

Scambiare le discipline LIFO e FIFO: estrarre dalla pila il primo elemento inserito (errato) invece dell'ultimo, o estrarre dalla coda l'ultimo invece del primo.
Perdere il riferimento alla testa o a un nodo intermedio durante un inserimento/cancellazione nella lista (ridirigere i puntatori nell'ordine sbagliato e cosi smarrire una parte della catena).

Ripasso attivo

Simula su carta una pila inizialmente vuota eseguendo, nell'ordine: push(5), push(8), pop, push(3), pop, push(7); indica per ogni pop l'elemento estratto e mostra il contenuto finale della pila dalla base alla cima.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Cenni alle strutture non lineari: alberi e grafi#

VertiefungOSA-informatica-fondamenti-strutture-datiCenni alle strutture non lineari: alberi e grafi

Albero binario: radice, nodi interni e foglie

Nelle strutture lineari ogni elemento ha al piu un predecessore e un successore; nelle strutture non lineari un elemento puo essere collegato a piu elementi, formando gerarchie o reti. Le due strutture non lineari fondamentali sono l'albero (gerarchia) e il grafo (rete di collegamenti generici); a livello liceale se ne studiano i concetti di base e le terminologie, senza richiedere implementazioni complesse.

Un albero e una struttura gerarchica composta da nodi collegati da archi, con un unico nodo speciale detto radice (root) da cui parte la gerarchia. Ogni nodo (tranne la radice) ha esattamente un genitore; i nodi collegati direttamente a un nodo, immediatamente sotto di esso, sono i suoi figli (i nodi raggiungibili in generale sono i suoi discendenti); i nodi senza figli sono le foglie. La profondita di un nodo e la sua distanza dalla radice, l'altezza dell'albero e la profondita massima. L'albero binario, in cui ogni nodo ha al piu due figli (sinistro e destro), e il caso piu studiato: modella espressioni, alberi di decisione e l'organizzazione gerarchica dei dati (file system, DOM di una pagina HTML).

Un grafo e un insieme di nodi (vertici) collegati da archi che rappresentano relazioni qualsiasi; a differenza dell'albero, puo contenere cicli e non ha una radice. I grafi possono essere non orientati (l'arco collega i due vertici simmetricamente) oppure orientati (l'arco ha un verso); gli archi possono inoltre essere pesati con un valore (distanza, costo, tempo). I grafi modellano reti stradali e di computer, mappe, relazioni sociali e dipendenze tra attivita.

L'albero e in realta un caso particolare di grafo: un grafo connesso e privo di cicli. Per rappresentare un grafo in memoria si usano due tecniche tipiche, la matrice di adiacenza (una tabella n x n in cui la cella indica se due vertici sono collegati) e le liste di adiacenza (per ogni vertice, la lista dei vertici a esso adiacenti): la scelta tra le due dipende dalla densita del grafo e dalle operazioni piu frequenti, ribadendo che la rappresentazione dei dati e sempre legata all'efficienza.

Esempio svolto

Lettura di un albero binario

Considera l'albero binario di radice 8 con figli 3 (sinistro) e 10 (destro), dove 3 ha i figli 1 e 6 e 10 ha il solo figlio destro 14. Individua la radice, elenca le foglie e determina l'altezza dell'albero.

Radice
La radice e il nodo da cui parte la gerarchia e che non ha genitore: e il nodo 8.
Foglie
Le foglie sono i nodi senza figli: 1, 6 e 14.
Altezza
L'altezza e la profondita massima, cioe il numero massimo di archi da radice a foglia: dal nodo 8 al nodo 6 si percorrono 2 archi (8 -> 3 -> 6).

Risultato: La radice e 8, le foglie sono 1, 6 e 14 e l'altezza dell'albero e 2.

Errori frequenti

Chiamare albero un grafo che contiene un ciclo o che ha piu di una radice: l'albero e per definizione connesso e aciclico, con un'unica radice.
Confondere la profondita di un nodo (distanza dalla radice) con l'altezza dell'albero (profondita massima), oppure scambiare nodi e foglie.

Ripasso attivo

Disegna un albero binario di radice 8 con i figli 3 (sinistro) e 10 (destro), dove 3 ha come figli 1 e 6 e 10 ha il solo figlio destro 14; individua la radice, le foglie e l'altezza dell'albero.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM))

Ricerca e ordinamento su strutture dati#

VertiefungOSA-informatica-fondamenti-strutture-datiAlgoritmi fondamentali su strutture dati: ricerca (lineare, binaria) e ordinamentoCenni alla notazione asintotica per il costo degli algoritmi

Ricerca binaria di 23 su un array ordinato di 10 elementi

Le strutture dati hanno senso pieno solo insieme agli algoritmi che le elaborano: i due problemi fondamentali sono la ricerca di un elemento e l'ordinamento di una collezione. Per confrontare gli algoritmi indipendentemente dalla macchina si usa la notazione asintotica O-grande, che descrive come cresce il numero di operazioni al crescere della dimensione n dell'input, trascurando costanti e termini di ordine inferiore. Cosi O(1) e costo costante, O(log n) logaritmico, O(n) lineare, O(n log n) quasi-lineare, O(n^2) quadratico.

La ricerca lineare (sequenziale) scorre la collezione dall'inizio confrontando ogni elemento con il valore cercato finche non lo trova o non esaurisce la struttura. Funziona su qualsiasi collezione, anche non ordinata, ma nel caso peggiore esamina tutti gli n elementi: il suo costo e O(n). E l'unica ricerca possibile su una lista concatenata o su un array non ordinato.

La ricerca binaria (dicotomica) e molto piu veloce, ma richiede che l'array sia gia ordinato: confronta il valore cercato con l'elemento centrale e, sfruttando l'ordinamento, scarta ogni volta meta degli elementi rimanenti, ripetendo il procedimento sulla meta utile. Dimezzando l'intervallo a ogni passo, il costo e O(log n): su un milione di elementi bastano circa 20 confronti invece del milione della ricerca lineare. Il prezzo da pagare e mantenere l'array ordinato.

Gli algoritmi di ordinamento elementari riarrangiano gli elementi in ordine (per esempio crescente). Il selection sort cerca a ogni passo il minimo della parte non ordinata e lo porta in posizione; l'insertion sort inserisce ogni elemento nella sua posizione corretta nella parte gia ordinata; il bubble sort scambia ripetutamente coppie adiacenti fuori ordine facendo emergere il massimo a ogni passata. Tutti e tre hanno costo O(n^2) nel caso peggiore: sono semplici da capire ma poco efficienti su grandi quantita di dati, dove si ricorre ad algoritmi O(n log n) (come merge sort e quick sort). Questo legame tra struttura, ordinamento e ricerca chiarisce la competenza centrale: la rappresentazione dei dati determina l'efficienza.

T_{\text{lineare}}(n) = O(n)

Costo ricerca lineare

La ricerca sequenziale nel caso peggiore confronta tutti gli n elementi: il costo cresce linearmente con n.

T_{\text{binaria}}(n) = O(\log_2 n)

Costo ricerca binaria

Dimezzando a ogni passo l'intervallo di ricerca, il numero di confronti e dell'ordine del logaritmo in base 2 di n; richiede pero un array ordinato.

T_{\text{sort}}(n) = O(n^2)

Costo ordinamenti elementari

Selection, insertion e bubble sort confrontano nel caso peggiore un numero di coppie proporzionale a n^2: il costo cresce con il quadrato della dimensione.

Crescita del costo: confronto tra O(log n), O(n) e O(n²)

Esempio svolto

Ricerca binaria passo passo

Sull'array ordinato [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indici da 0 a 9) applica la ricerca binaria per cercare il valore 23; indica a ogni passo l'elemento centrale confrontato e conta i confronti.

Passo 1
Intervallo [0, 9]: centro all'indice (0+9)/2 = 4, valore 16. Poiche 23 > 16, si scarta la meta sinistra e si prosegue su [5, 9].
Passo 2
Intervallo [5, 9]: centro all'indice (5+9)/2 = 7, valore 56. Poiche 23 < 56, si scarta la meta destra e si prosegue su [5, 6].
Passo 3
Intervallo [5, 6]: centro all'indice (5+6)/2 = 5, valore 23. Coincide con il valore cercato: trovato all'indice 5.

Risultato: Il valore 23 viene trovato all'indice 5 in 3 confronti; coerentemente con il costo O(log n), poiche log2(10) e circa 3.32, sono sufficienti pochi confronti contro i fino a 10 della ricerca lineare.

Errori frequenti

Applicare la ricerca binaria a un array NON ordinato: il metodo presuppone l'ordinamento e su dati non ordinati puo dare risultati errati.
Confondere il caso migliore con il caso peggiore o trattare la notazione O come un tempo esatto: O descrive l'ordine di crescita, non i secondi impiegati.

Ripasso attivo

Sull'array ordinato [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] applica la ricerca binaria per cercare il valore 23: indica a ogni passo l'elemento centrale confrontato, il numero totale di confronti e l'esito.

Richiamo attivo

Ricorda i punti chiave — poi rivela.

Fonti: Indicazioni Nazionali per i Licei (DPR 89/2010, DM 211/2010) - Obiettivi Specifici di Apprendimento (Ministero dell'Istruzione e del Merito (MIM)) · Esame di Stato del secondo ciclo - quadri di riferimento e griglie di valutazione (Ministero dell'Istruzione e del Merito (MIM))

Riferimenti e fonti

Fonti

Ministero dell'Istruzione e del Merito (MIM)

Strutture dati e loro implementazione

Punti chiave

Indirizzo di un elemento di matrice

Punti chiave

Media dei valori di un campo in un array di record

Punti chiave

Sequenza di operazioni su una pila

Punti chiave

Lettura di un albero binario

Punti chiave

Ricerca binaria passo passo

Fonti

Strutture dati e loro implementazione

Punti chiave

Indirizzo di un elemento di matrice

Punti chiave

Media dei valori di un campo in un array di record

Punti chiave

Sequenza di operazioni su una pila

Punti chiave

Lettura di un albero binario

Punti chiave

Ricerca binaria passo passo

Fonti