Unità C1
Estendere i linguaggi:
i tipi di dato astratti
Obiettivi
• Conoscere le principali strutture dati
esistenti
• Conoscere ed essere in grado di
implementare le operazioni definite sulle
strutture dati
• Saper scegliere la struttura dati più
adatta alla soluzione di un problema
Insiemi dinamici
• Caratteristica di un insieme dinamico: il numero e la
disposizione degli elementi che lo compongono può
variare nel corso della sua esistenza
• Elementi dell’insieme: alcuni tipi di insiemi dinamici
sono composti da elementi formati da informazioni
che li identificano chiave e da dati satellite.
• La chiave è un campo (o un insieme di campi) che
consente di identificare in modo univoco un
elemento.
• I dati satellite sono le informazioni memorizzate
nell’elemento.
Chiavi e dati satelliti
• Un esempio: gestione degli studenti della scuola.
• Ogni singolo elemento rappresenta uno studente.
• La chiave può essere per esempio il numero del
libretto scolastico (o il codice fiscale)
• I dati satellite sono tutti i dati che vengono
memorizzati per ogni studente:
–
–
–
–
–
Cognome
Nome
Indirizzo
Classe frequentata
…
Chiavi e chiavi artificiali
• Non sempre è possibile individuare una chiave di
identificazione degli elementi
• In molti casi si definisce una “chiave artificiale” (es il
codice fiscale, il numero di libretto o in alcuni casi un
ID (numero intero progressivo assegnato nel
momento in cui un elemento viene inserito
nell’insieme).
• La chiave può essere utilizzata per ordinare gli
elementi in modo crescente o decrescente.
Puntatori
• I puntatori nei linguaggi di programmazione
consentono di recuperare un dato
conoscendo l’indirizzo di memoria in cui è
memorizzato.
• Un puntatore è una variabile contenente un
indirizzo di una cella di memoria.
• Un puntatore, quindi, è una variabile che,
anziché contenere un valore numerico o una
stringa di testo, mantiene l’indirizzo di
memoria in cui è memorizzata l’informazione.
Operazioni sugli insiemi
• Le operazioni che si possono effettuare
sugli insiemi dinamici si suddividono in:
– operazioni di interrogazione
operazioni di sola lettura per recuperare
informazioni dall’insieme
– operazioni di modifica
consentono di inserire, cancellare e
riordinare gli elementi dell’insieme
cambiandone il numero e/o la disposizione
Le principali operazioni
Strutture dati
• Per gestire un insieme dinamico di elementi occorre
implementarlo mediante una struttura dati.
• Una struttura dati è composta da nodi, ciascuno dei
quali contiene un elemento dell’insieme ed eventuali
altre informazioni (puntatori) che servono per la
gestione della struttura.
Tipi di strutture dati
• Le strutture dati possono essere
suddivise in due grandi famiglie:
– lineari
l’insieme degli elementi è organizzato in
modo sequenziale.
– non lineari
non prevedono che un elemento sia
seguito esclusivamente da un altro
elemento (Esempio la struttura ad albero
del filesystem )
Le strutture fisiche dei dati
• Per implementare le strutture dati, si devono
utilizzare le strutture fisiche fornite dai
linguaggi che possono avere dimensione
statica o dinamica.
• Un array, per esempio, è una struttura di
memorizzazione dalla dimensione statica.
• Strutture fisiche dalla dimensione dinamica si
possono implementare grazie all’uso dei
puntatori.
Strutture dati lineari
• Una struttura dati si dice lineare se i
suoi elementi sono organizzati in modo
sequenziale, ovvero se logicamente gli
stessi sono posizionati uno dopo l’altro.
– Pila
– Coda
– Lista
Pila (stack)
• La pila è una struttura dati di tipo LIFO
che garantisce che l’ultimo elemento
depositato nella pila sia il primo a
essere servito.
• LIFO (Last-In First-Out, “l’ultimo arrivato
è il primo ad essere servito”)
• Esempio pila di piatti, pila di libri, di
monete
Operazioni sulla pila
• push
– consente di inserire un nuovo elemento in testa
alla pila
• pop
– permette di estrarre il primo elemento in cima alla
pila
• top
– consente di leggere il primo elemento in cima alla
pila senza estrarlo da essa
• vuota
– restituisce true se la pila è vuota, false in caso
contrario
Coda
• La coda è una struttura dati
di tipo FIFO che garantisce
che il primo elemento
inserito sia il primo a essere
servito.
• FIFO (First-In First-Out), il
primo elemento a entrare è
anche il primo a uscire
Operazioni sulla coda
• Le tipiche operazioni che si possono
effettuare su una coda sono le seguenti:
– enqueue (accodare)
consente di accodare un elemento alla
coda
– dequeue (togliere dalla coda)
consente invece di eliminare l’elemento
che da più tempo è presente nella coda
Lista concatenata
• La lista concatenata è una collezione ordinata di elementi,
ciascuno dei quali è concatenato al successivo mediante un
riferimento che indica dove andare a prendere il successivo
elemento.
• In una lista concatenata non è possibile accedere in modo diretto
a un elemento, bensì è necessario scorrere tutti gli elementi fino
a raggiungere quello cercato.
• Ogni elemento della lista è contenuto in un nodo, in cui è
presente anche un puntatore all’elemento successivo.
• L’ultimo elemento della lista avrà il puntatore nullo, mentre il
puntatore al primo nodo si conserva in una variabile opportuna.
Operazioni sulla lista
• Le operazioni principali che si possono effettuare su
una lista sono:
– inserimento
– ricerca
– cancellazione
• Esempio di cancellazione:
Strutture dati non lineari
• Una struttura dati non lineare è composta da nodi
posti in base a uno schema non sequenziale.
• Nelle strutture dati lineari, se ci troviamo posizionati
su un nodo, possiamo decidere al più di andare sul
nodo successivo come nelle liste concatenate, o sul
nodo precedente come nelle liste concatenate
bidirezionali.
• Nelle strutture dati non lineari, invece, partendo da un
nodo abbiamo la possibilità di spostarci in più
direzioni.
• Una struttura dati di questo genere assomiglia
maggiormente a una rete di nodi anziché a una
sequenza.
Un esempio: albero genealogico
Strutture non lineari: grafo
• Un grafo è una
struttura dati non
lineare composta da
nodi e archi che li
connettono.
• Esistono due
principali categorie di
grafi:
– grafi orientati;
– grafi non orientati.
Grafo orientato
•
•
•
•
•
•
•
•
In un grafo orientato i nodi sono detti
vertici e gli archi spigoli.
Gli spigoli che connettono i vertici tra
loro hanno una direzione e per
definirla si utilizza una freccia.
In un grafo orientato è possibile
avere cappi.
Un cappio è uno spigolo che inizia e
termina sullo stesso vertice.
Uno spigolo che esce da un vertice A
o che entra in un vertice B si dice,
rispettivamente, incidente da A o
incidente a B.
Il numero di spigoli uscenti da un
vertice si chiama grado uscente.
Il numero di spigoli entranti in un
vertice si chiama invece grado
entrante.
Il grado di un vertice è il suo grado
entrante più il suo grado uscente.
Grado, cammino
•
•
•
•
•
•
•
In un grafo (orientato e non) il percorso per andare da un nodo a un
altro è chiamato cammino e la sua lunghezza è pari al numero di archi
attraversati.
Un cammino si dice semplice se tutti i nodi della sequenza sono
distinti tra loro.
In un grafo orientato non è detto che esista un cammino per andare da
un nodo a un altro, in quanto il percorso è condizionato dalla direzione
degli spigoli.
Se da un nodo A è possibile andare a un nodo B, si dice anche che B è
raggiungibile da A tramite un determinato cammino c.
Il grado di un vertice di un grafo non orientato è semplicemente il
numero di archi incidenti su di esso.
Un grafo non orientato si dice connesso se ogni coppia di nodi è
collegata con un cammino.
Un grafo non orientato, connesso e aciclico è detto albero libero, o più
semplicemente un albero.
Albero
•
•
•
•
•
•
•
•
•
Un albero è un grafo non orientato, connesso
e aciclico.
La rappresentazione grafica è simile a un
albero con la radice in alto e le foglie in basso
Un albero è una struttura dati gerarchica
composta da nodi padri e nodi figli collegati da
archi (rami).
Un nodo figlio è correlato a uno e un solo
nodo padre.
Il nodo radice è il nodo da cui parte la struttura
ad albero e che non possiede un nodo padre.
Un nodo foglia non possiede nodi figli.
La profondità di un nodo è la distanza tra esso
ed il nodo radice.
La profondità maggiore tra tutti i nodi
dell’albero è l’altezza dell’albero.
Il grado di un nodo è il numero di figli che esso
possiede.
Albero (altre caratteristiche)
• Un antenato di un nodo x di
un albero è qualunque nodo
y che si trovi sull’unico
cammino che porta dalla
radice a x
• x è un discendente di y
• Se i nodi di un albero
possono avere al massimo n
figli, si parla di alberi n-ari
• Un albero si dice completo
se i nodi foglia hanno tutti la
stessa altezza e ogni altro
nodo ha il grado pari al grado
massimo.
Albero binario
•
•
Un albero binario è un albero i cui nodi possono avere
al più due nodi figli, denominati figlio destro e figlio
sinistro.
Un albero binario può essere definito anche in modo
ricorsivo:
– non contiene alcun nodo;
– oppure contiene un nodo radice, un albero binario
detto sottoalbero sinistro (eventualmente vuoto) e un
albero binario chiamato sottoalbero destro
(eventualmente vuoto).
•
Negli alberi binari esistono 3 tipi di ricerca:
– PreOrdine
visita prima il nodo padre, poi il sottoalbero sinistro e
infine quello destro
– PostOrdine
visita prima il sottoalbero sinistro, poi quello destro e
infine il nodo padre
– InOrdine visita prima il sottoalbero sinistro, poi il nodo
padre e infine il sottoalbero destro.