Strutture dati elementari
Pile
Code
Liste concatenate
Alberi medianti puntatori
Pile (Stacks)
•C’è una politica LIFO (last-in, first-out), ossia l’elemento
rimosso dalla pila è quello che è stato più recentemente
inserito
S
•Operazioni:
– PUSH(S,x) (inserisci)
– POP(S) (elimina,rimuovi)
– STACK-EMPTY(S) (controlla
se è vuota)
…
6
5
4
3
2
1
top[S]
Una pila con al più n elementi può essere rappresentata da
un vettore S[1,…, n]. La variabile top[S] punto all’ultimo
elemento inserito.
Pile
PUSH(S,8)
PUSH(S,x)
1.
top[S] ← top[S]+1
2.
S[top[S]] ← x
1
2
3
3
7
9
4
5
6
5
6
5
6
top[S]=3
La pila consiste di top[S]
elementi, ossia di un vettore
S[1,…, top[S] ].
S[1] rappresenta l’elemento
alla base della pila, mentre
S[top[S] ] è l’elemento alla
cima.
1
2
3
3
7
9
4
top[S]=4
1
2
3
4
3
7
9 8
top[S]=4
Pile
POP(S,x)
1.
if STACK-EMPTY(S)
2.
then “underflow”
3.
else top[S] ← top[S] -1
4.
return S[top[S] + 1]
POP(S)
1
2
3
4
3
7
9 8
5
6
top[S]=4
STACK-EMPTY(S)
1.
if top[S] = 0
2.
then return TRUE
3.
else return FALSE
1
2
3
4
3
7
9 8
5
6
return 8
top[S]=3
Se la pila è vuota viene generato un errore di “underflow”.
Se top[S] supera n, la pila va in “overflow” (caso non
trattato nel pseudo-codice).
Tutte e tre le operazioni richiedono tempo O(1).
Code (Queues)
•C’è una politica FIFO (first-in, first-out), ossia l’elemento
rimosso dalla coda è quello che è stato inserito da più
tempo
Q
•Operazioni:
– ENQUEUE(S,x) (inserisci)
– DEQUEUE(S) (elimina,rimuovi)
3
head[Q]
4
5
…
6
tail[Q]
Una coda con al più n elementi può essere rappresentata
da un vettore Q[1,…, n]. Le variabili head[Q] e tail[Q]
puntano rispettivamente alla testa della coda e alla
posizione dove il nuovo elemento sarà inserito.
Code (Queues)
ENQUEUE(Q,x)
1.
Q[tail[Q]] ← x
2.
if tail[Q] = length[Q]
3.
then tail[Q] ← 1
4.
else tail[Q] ← tail[Q] + 1
ENQUEUE(Q,5)
1
2
3
4
5
3
9
6 8
head[Q]=3
6
7
8
tail[Q]=7
9
10
Inizialmente si avrà
1
2
3
4
5
6
7
8
9
10
head[Q]=tail[Q]=1.
3 9 6 8 5
Quando head[Q]=tail[Q] la
coda è vuota. Un tentativo di
head[Q]=3
tail[Q]=8
prendere un elemento dalla
coda genererà una situazione
di “underflow”.
Quando head[Q]=tail[Q]+1 la coda è piena. Un tentativo di
inserire un elemento dalla coda genererà una situazione di
“overflow”.
Code (Queues)
DEQUEUE(Q)
1.
x ← Q[head[Q]]
2.
if head[Q] = length[Q]
3.
then head[Q] ← 1
4.
else head[Q] ← head[Q] + 1
5.
return x
DEQUEUE(Q,5)
1
2
3
4
5
6
3
9
6 8 5
head[Q]=3
1
2
7
8
9
10
tail[Q]=8
3
4
5
6
7
3
9
6 8 5
8
9
10
return 3
head[Q]=4
tail[Q]=8
I casi di “underflow” e di “overflow” non sono trattati nel
pseudo-codice.
Le operazioni ENQUEUE e DEQUEUE richiedono tempo
O(1).
Liste concatenate
key
head[L]
-
9
4
prev
12
8
-
next
•Le liste concatenate consistono in un insieme di elementi
disposti l’uno di seguito all’altro.
•Diversamente dai vettori (anche detti array) gli elementi
non sono indicizzati, ma legati tra loro linearmente
attraverso dei puntatori.
•I puntatori all’interno di un elemento x possono puntare
all’elemento successivo (next[x]) o a quello successivo
(prev[x]).
•Le liste concatenate sono una struttura di dati semplice
e flessibile, soprattutto se si devono rappresentare un
insieme di elementi dinamicamente variabile.
Doubly linked list
NIL
head[L]
-
NIL
key
9
4
prev
12
8
-
next
• Un Doubly linked list è anche detto lista concatenata
bidirezionale.
•Ogni elemento x ha una chiave (key[x]), un puntatore
all’elemento successivo (next[x]) e un puntatore
all’elemento precedente (prev[x]).
•head[L] punta al primo elemento della lista L. Questo
primo elemento ha prev[x]=NIL, quindi non ha un
elemento che lo precede.
•L’ultimo elemento ha next[x]=NIL, quindi non ha un
successore.
•Quando head[L]=NIL si è in presenza di una lista vuota.
Doubly linked list
NIL
head[L]
-
NIL
key
9
4
prev
12
8
-
next
Operazioni:
oLIST-SEARCH(L,k)
Cerca il primo elemento con chiave k nella lista L.
oLIST-INSERT(L,x)
Inserisci un elemento x con chiave key[x] nella lista L.
oLIST-DELETE(L,x)
Elimina l’elemeno x con chiave key[x] e puntatori (prev[x],
next[x]) nella lista L.
Doubly linked list
LIST-SEARCH(L,k)
1.
x ← head[L]
2.
while x ≠ NIL and key[x] ≠ k
3.
do x ← next[x]
4.
return x
Per una lista di n elementi
richiede tempo Θ(n) nel
caso peggiore, poiché si
deve scorrere l’intera lista.
LIST-SEARCH(L,12)
head[L]
-
9
4
12
8
-
4
12
8
-
12
8
-
x key[x]=9
head[L]
-
9
x key[x]=4
head[L]
-
9
4
x key[x]=12 TROVATO!
Doubly linked list
LIST-INSERT(L,x)
1.
next[x] ← head[L]
2.
if head[L] ≠ NIL
3.
then prev[head[L]] ← x
4.
head[L] ← x
5.
prev[x] ← NIL
Per una lista di n elementi
richiede tempo O(1),
poiché richiede un
numero costante di passi.
LIST-INSERT(L,x)
key[x] = 5
head[L]
x
-
9
4
8
-
5
x
9
4
8
-
5
x
9
4
8
-
5
head[L]
head[L]
-
Doubly linked list
LIST-DELETE(L,x)
1.
if prev[x] ≠ NIL
2.
then next[prev[x]] ← next[x]
3.
else head[L] ← next[x]
4.
if next[x] ≠ NIL
5.
then prev[next[x]] ← prev[x]
LIST-DELETE(L,x)
key[x] = 9
Per una lista di n elementi
richiede tempo O(1),
poiché richiede un
numero costante di passi.
Non comprende la ricerca
dell’elemento da
rimuovere.
head[L]
-
5
9
x
4
8
-
head[L]
-
5
9
x
4
8
-
head[L]
-
5
4
8
-
L’uso di una sentinella
nil[L]
nil[L]
5
4
8
• La sentinella è un oggetto che aiuta a semplificare le
condizioni di confine della lista.
• Consiste di un oggetto nullo (nil[L]) che punta all’inizio e
alla fine della lista e viene puntato a sua volta dal primo
e dall’ultimo elemento della lista.
• Quando nil[L] punta e viene punato solo da se stesso la
lista L è vuota.
L’uso di una sentinella
Le operazioni con la presenza della sentinella:
LIST-DELETE’(L,x)
1.
next[prev[x]] ← next[x]
2.
prev[next[x]] ← prev[x]
LIST-SEARCH’(L,k)
1.
x ← next[nil[L]]
2.
while x ≠ nil[L] and key[x] ≠ k
3.
do x ← next[x]
4.
return x
LIST-INSERT’(L,x)
1.
next[x] ← next[nil[L]]
2.
prev[next[nil[L]]] ← x
3.
next[nil[L]] ← x
4.
prev[x] ← nil[L]
Il codice risulta più
compatto.
next[nil[L]] prende il posto
di head[L].
L’uso di una sentinella
• L’uso della sentinella rende il codice più compatto e
semplice.
• Non rende il codice più efficiente, anche se può ridurre il
tempo di esecuzione di qualche costante.
• L’uso della sentinella può dare un significativo
incremento dell’uso della memoria, soprattutto se si
usano molte liste. Questo è dovuto all’uso di elemento in
più per ogni lista.
Liste concatenate
key
head[L]
9
4
12
8
-
next
•Ci possono essere anche liste unidirezionali che usano un
solo link (o puntatore). Si chiamano Singly Linked Lists.
•Le Singly Link Lists rendono la procedura di rimozione di
un elemento pari a Θ(n) nel caso peggiore, perché deve
essere individuato l’elemento precedente.
•Si possono costruire anche liste circolari da una Doubly
Linked Lists, quando il primo elemento della testa punta
all’ultimo e viceversa.
head[L]
5
4
8
Rappresentazione di alberi binari
Un albero binario è un albero dove
ogni nodo può avere al massimo due
figli.
Si usano i campi p[x], left[x] e right[x]
per puntare rispettivamente al padre e
ai due figli del nodo x. Se un figlio non
esiste, allora il valore del puntatore è
nil.
root[T] punta alla radice dell’albero,
che ha p[x]=nil. Se root[T]=nil, allora
l’albero è vuoto.
p[x]
left[x] right[x]
Rappresentazione di alberi binari
Ecco un esempio.
Le foglie sono i nodi senza figli, ossia
left[x]=right[x]=nil.
root[T]
- -
- -
- -
Rappresentazione di alberi
Una possibile rappresentazione:
•left[x] punta al figlio più a sinistra
•right[x] punta al fratello alla sua destra, se esiste.
root[T]
-
-
-
- -
-
-
- -