Algoritmi e Strutture Dati
Capitolo 3
Strutture dati elementari
Camil Demetrescu, Irene Finocchi,
Giuseppe F. Italiano
Algoritmi e strutture dati
Ordinamento
n numeri
Insertion Sort
A[1,...,n] = vettore
i,j,key = variabili
2
Numeri
ordinati
Algoritmi e strutture dati
Problema
Input
Algoritmo
Strutture
Dati
3
Output
Algoritmi e strutture dati
Strutture Dati Astratte
• DATI
+
• OPERAZIONI
“Che cosa”
DATI
OP1
4
OP2
……………
OPn
Algoritmi e strutture dati
Insertion Sort
Insertion-sort(A)
1. for j=2 to size(A)
2.
do key = read(j)
3.
{insert A[j] in A[1,...,j-1]}
4.
i = j-1
5.
while i>0 and read(i)>key
6.
do modify(i+1,read(i))
7.
i=i-1
8.
modify(i+1,key)
5
Algoritmi e strutture dati
Esempio di ADS
Dati = insieme S di numeri
OP1 = estrai il minimo
OP2 = estrai il massimo
OP3 = restituisci la dimensione di S
OP4 = inserisci un nuovo numero in S
6
Algoritmi e strutture dati
Insertion sort
7
ADS =
Insieme S di numeri
+
Read, Size, Modify
DS =
S=“A[1,…,n]” (vettore)
Read(i)=“A[i]”
Size(A)=“n”
Modify(i,x)=“A[i]=x”
Algoritmi e strutture dati
ADS = che cosa vogliamo ?
DS = come lo implementiamo ?
8
Algoritmi e strutture dati
Quando una struttura dati
è “buona” ?
Una DS è buona quando non usa troppe
risorse.
Risorse
9
Tempo
Spazio di memoria
Numero di procesori
...
...
Algoritmi e strutture dati
Dato
Dato è tutto ciò su cui agisce un calcolatore
A livello hardware tutti i dati sono
rappresentati come sequenza di cifre binarie
Linguaggi ad alto livello ci permettono di
usare astrazioni tramite il concetto di
tipo di dato
10
Algoritmi e strutture dati
Tipo di Dato
Nei linguaggi di programmazione
1.
2.
il tipo di dato determina l’insieme dei valori (oggetti) che
una variabile può rappresentare
il tipo di dato, specifica le operazioni di interesse su un
insieme di valori (o collezione di oggetti (es. inserisci,
cancella, cerca, etc.))
ogni operatore accetta argomenti di uno o più tipi di dato
fissato e produce risultati di un tipo di dato fissato
11
Algoritmi e strutture dati
Gestione di collezioni di oggetti
Struttura dati:
– Organizzazione dei dati che permette di
supportare le operazioni di un tipo di dato
in modo efficiente
12
Algoritmi e strutture dati
Il tipo di dato Dizionario
13
Algoritmi e strutture dati
Il tipo di dato Pila
14
Algoritmi e strutture dati
Il tipo di dato Coda
15
Algoritmi e strutture dati
Tecniche di rappresentazione dei dati
Rappresentazioni indicizzate:
– I dati sono contenuti in array
Rappresentazioni collegate:
– I dati sono contenuti in record collegati
fra loro mediante puntatori
16
Algoritmi e strutture dati
Pro e contro
Rappresentazioni indicizzate:
– Pro: accesso diretto ai dati mediante indici
– Contro: dimensione fissa (riallocazione
array richiede tempo lineare)
Rappresentazioni collegate:
– Pro: dimensione variabile (aggiunta e
rimozione record in tempo costante)
– Contro: accesso sequenziale ai dati
17
Algoritmi e strutture dati
Esempi di strutture collegate
Lista semplice
Lista doppiamente
collegata
Lista circolare
doppiamente
collegata
18
Algoritmi e strutture dati
Alberi
Organizzazione gerarchica dei dati
Dati contenuti nei nodi, relazioni gerarchiche
definite dagli archi che li collegano
19
Algoritmi e strutture dati
Rappresentazioni collegate di alberi
Rappresentazione
con puntatori ai figli
(nodi con numero
limitato di figli)
Rappresentazione
con liste di puntatori ai
figli (nodi con numero
arbitrario di figli)
20
Algoritmi e strutture dati
Rappresentazioni collegate di alberi
cont.
Rappresentazione
con primo figliofratello successivo
(nodi con numero
arbitrario di figli)
21
Algoritmi e strutture dati
Visite di alberi
Algoritmi che consentono l’accesso
sistematico ai nodi e agli archi di un albero
Gli algoritmi di visita si distinguono in
base al particolare ordine di accesso ai nodi
22
Algoritmi e strutture dati
Algoritmo di visita generica
visitaGenerica visita il nodo r e
tutti i suoi discendenti in un albero
Richiede tempo O(n) per visitare un
albero con n nodi a partire dalla radice
23
Algoritmi e strutture dati
Algoritmo di visita in profondità
L’algoritmo di visita in profondità (DFS)
parte da r e procede visitando nodi di
figlio in figlio fino a raggiungere una
foglia. Retrocede poi al primo antenato
che ha ancora figli non visitati (se esiste)
e ripete il procedimento a partire da uno
di quei figli.
24
Algoritmi e strutture dati
Algoritmo di visita in profondità
Versione iterativa (per alberi binari):
25
Algoritmi e strutture dati
Algoritmo di visita in profondità
Versione ricorsiva (per alberi binari):
26
Algoritmi e strutture dati
Algoritmo di visita in ampiezza
L’algoritmo di visita in ampiezza (BFS)
parte da r e procede visitando nodi per
livelli successivi. Un nodo sul livello i
può essere visitato solo se tutti i nodi sul
livello i-1 sono stati visitati.
27
Algoritmi e strutture dati
Algoritmo di visita in ampiezza
Versione iterativa (per alberi binari):
28
Algoritmi e strutture dati
Riepilogo
• Nozione di tipo di dato come specifica delle
operazioni su una collezione di oggetti
• Rappresentazioni indicizzate e collegate di
collezioni di dati: pro e contro
• Organizzazione gerarchica dei dati mediante
alberi
• Rappresentazioni collegate classiche di alberi
• Algoritmi di esplorazione sistematica dei nodi di
un albero (algoritmi di visita)
29