Strutture dati elementari

PileCodeListe concatenateAlberi medianti puntatori

Pile (Stacks)

•C’è una politica LIFO (last-in, first-out), ossia l’elemento rimosso dalla pila è quello che è stato più recentemente inserito•Operazioni:

– PUSH(S,x) (inserisci)

– POP(S) (elimina,rimuovi)

– STACK-EMPTY(S) (controlla se è vuota)

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.

123456 top[S]

S…

PilePUSH(S,x)1. if top[S]=N2. then “overflow”3. else top[S] ← top[S]

+14. S[top[S]] ← x

3 7 9

top[S]=3

1 2 3 4 5 6

3 7 9

top[S]=4

1 2 3 4 5 6

3 7 9

top[S]=4

1 2 3 4 5 6

8

PUSH(S,8)

La pila consiste di top[S] elementi, ossia di un vettore S[1,…, top[S] ].

N è il numero massimo di elementi che la pila può contenere.

S[1] rappresenta l’elemento alla base della pila, mentre S[top[S] ] è l’elemento alla cima.

PilePOP(S,x)1. if STACK-EMPTY(S)2. then “underflow”3. else top[S] ← top[S] -14. return S[top[S] + 1]

3 7 9

top[S]=3

1 2 3 4 5 6

3 7 9

top[S]=4

1 2 3 4 5 6

8

POP(S)

Se la pila è vuota viene generato un errore di “underflow”. Se top[S] supera N, la pila va in “overflow”.

Tutte e tre le operazioni richiedono tempo O(1).

8

return 8

STACK-EMPTY(S)1. if top[S] = 02. then return TRUE3. else return FALSE

Code (Queues)

•C’è una politica FIFO (first-in, first-out), ossia l’elemento rimosso dalla coda è quello che è stato inserito da più tempo•Operazioni:

– ENQUEUE(S,x) (inserisci)

– DEQUEUE(S) (elimina,rimuovi)

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.

head[Q]

Q

3 4 5 6

tail[Q]

…

Code (Queues)ENQUEUE(Q,x)1. Q[tail[Q]] ← x2. if tail[Q] = length[Q]3. then tail[Q] ← 14. else tail[Q] ← tail[Q] + 1

3 9 6

tail[Q]=7

1 2 3 4 5 6

8

ENQUEUE(Q,5)

Quando head[Q]=tail[Q]+1 la coda è piena. Un tentativo di inserire un elemento dalla coda genererà una situazione di “overflow”.

7 8 9 10

head[Q]=3

3 9 6

tail[Q]=8

1 2 3 4 5 6

8

7 8 9 10

head[Q]=3

5

Inizialmente si avrà head[Q]=tail[Q]=1.Quando head[Q]=tail[Q] la coda è vuota. Un tentativo di prendere un elemento dalla coda genererà una situazione di “underflow”.

Code (Queues)DEQUEUE(Q)1. x ← Q[head[Q]] 2. if head[Q] = length[Q]3. then head[Q] ← 14. else head[Q] ←

head[Q] + 15. return x

DEQUEUE(Q,5)

I casi di “underflow” e di “overflow” non sono trattati nel pseudo-codice.

Le operazioni ENQUEUE e DEQUEUE richiedono tempo O(1).

3 9 6

tail[Q]=8

1 2 3 4 5 6

8

7 8 9 10

head[Q]=3

5

3 9 6

tail[Q]=8

1 2 3 4 5 6

8

7 8 9 10

head[Q]=4

5

return 3

Liste concatenate

•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.

key

prev next

4 12 8 -9-head[L]

Doubly linked list

• 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.

key

prev next

4 12 8 -9-head[L]

NILNIL

Doubly linked list

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’elemento x con chiave key[x] e puntatori (prev[x], next[x]) nella lista L.

key

prev next

4 12 8 -9-head[L]

NILNIL

Doubly linked list

4 12 8 -9-head[L]

LIST-SEARCH(L,k)1. x ← head[L]2. while x ≠ NIL and key[x] ≠ k3. do x ← next[x]4. return x

LIST-SEARCH(L,12)

x key[x]=9

4 12 8 -9-head[L]

x key[x]=4

4 12 8 -9-head[L]

x key[x]=12 TROVATO!

Per una lista di n elementi richiede tempo Θ(n) nel caso peggiore, poiché si deve scorrere l’intera lista.

Doubly linked list

49-head[L]

LIST-INSERT(L,x)1. next[x] ← head[L]2. if head[L] ≠ NIL 3. then prev[head[L]] ← x 4. head[L] ← x5. prev[x] ← NIL

LIST-INSERT(L,x) key[x] = 5

5

Per una lista di n elementi richiede tempo O(1), poiché richiede un numero costante di passi.

x

49head[L] 5x

49head[L] 5x

-

8 -

8 -

8 -

Doubly linked listLIST-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.

49head[L] 5x

- 8 -

49head[L] 5x

- 8 -

4head[L] 5- 8 -

L’uso di una sentinella

• 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.

45 8

nil[L]

nil[L]

L’uso di una sentinella

Le operazioni con la presenza della sentinella:

LIST-INSERT’(L,x)1. next[x] ← next[nil[L]]2. prev[next[nil[L]]] ← x 3. next[nil[L]] ← x4. prev[x] ← nil[L]

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] ≠ k3. do x ← next[x]4. return x

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

•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.

key

next

4 12 8 -9head[L]

45 8head[L]

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

- - - -

- -

-

-

-

root[T]

Ecco un esempio.

Le foglie sono i nodi senza figli, ossia left[x]=right[x]=nil.

Rappresentazione di alberi

- -

- -

-

-

-

root[T]

Una possibile rappresentazione:

•left[x] punta al figlio più a sinistra

•right[x] punta al fratello alla sua destra, se esiste.

- -

- - -