Algoritmi e Strutture Dati
Capitolo 4 - Strutture di dati elementari
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Liste
Liste (List, Linked List)
✦
Una sequenza di nodi, contenenti dati arbitrari e 1-2 puntatori all'elemento
successivo e/o precedente
✦
Contiguità nella lista ⇒ contiguità nella memoria
✦
Costo operazioni
✦
Tutte le operazioni hanno costo O(1)
✦
Realizzazione possibili
✦
Bidirezionale / monodirezionale
✦
Con sentinella / senza sentinella
✦
Circolare / non circolare
✦
© Alberto Montresor
2
Linked List - Altri esempi
© Alberto Montresor
3
List - circolare, bidirezionale, con sentinella
Nota:
List e Pos
sono tipi
equivalenti
© Alberto Montresor
4
List (Java) - bidirezionale senza sentinella
class Pos
{
Pos succ;
Pos pred;
Object v;
Pos(Object v) {
succ = pred = null;
this.v = v;
}
© Alberto Montresor
5
List (List (Java) - bidirezionale senza sentinella
) - senza sentinella
public class List {
/** First element of the list */
private Pos head;
/** Last element of the list */
private Pos tail;
public List() {
head = tail = null;
}
© Alberto Montresor
6
List (Java) - bidirezionale senza sentinella
sentinella
public Pos insert(Pos pos, Object v) {
Pos t = new Pos(v);
if (head == null) {
// Insert in a emtpy list
head = tail = t;
} else if (pos == null) {
// Insert at the end
t.pred = tail;
tail.succ = t;
tail = t;
} else {
// Insert in front of an existing position
© Alberto Montresor
7
List (Java) - bidirezionale senza sentinella
- senza sentinella
public void remove(Pos pos) {
if (pos.pred == null)
head = pos.succ;
else
pos.pred.succ = pos.succ;
if (pos.succ == null)
tail = pos.pred;
else
pos.succ.pred = pos.pred;
}
© Alberto Montresor
8
Liste - Realizzazione con vettori
E’ possibile realizzare una lista con vettori
✦
Posizione ≡ indice nel vettore
✦
Le operazioni insert() e remove() hanno costo O(n)
✦
Tutte le altre operazioni hanno costo O(1)
✦
Problema
✦
Spesso non si conosce a priori quanta memoria serve per memorizzare la lista
✦
Se ne alloca una certa quantità, per poi accorgersi che non è sufficiente.
✦
Soluzione
✦
Si alloca un vettore di dimensione maggiore, si ricopia il contenuto del vecchio
vettore nel nuovo e si rilascia il vecchio vettore
✦
Esempi: java.util.Vector (1.0), java.util.ArrayList (1.2)
✦
© Alberto Montresor
9
Vettori dinamici: espansione
private Object[] buffer = new Object[INITSIZE];
// Utilizzato in ArrayList()
private void doubleStorage() {
Object[] newb = new Object[2*buffer.length];
System.arraycopy(buffer,0, newb,0, buffer.length);
buffer = newb;
}
// Utilizzabile in Vector()
private Object[] buffer = new Object[INITSIZE];
private void incrementStorage() {
Object[] newb = new Object[buffer.length+INCREMENT];
System.arraycopy(buffer,0, newb,0, buffer.length);
buffer = newb;
}
© Alberto Montresor
10
Vettori dinamici: espansione
Domanda:
✦
Qual è il migliore fra i due?
✦
Dalla documentazione Java:
✦
“As elements are added to an ArrayList, its capacity grows automatically.
The details of the growth policy are not specified beyond the fact that adding
an element has constant amortized time cost.”
✦
Domanda:
✦
Cosa significa?
✦
© Alberto Montresor
11
Vettori dinamici: contrazione
Domande:
✦
Quanto costa rimuovere un elemento da una lista?
✦
Quanto costa rimuovere un elemento da un vettore
non ordinato, evitando di lasciare “buchi”?
✦
Contrazione
✦
Per ridurre lo spreco di memoria di memoria è opportuno contrarre il vettore
quando il fattore di carico α = size / capacity diventa troppo piccolo
✦size: numero di elementi attualmente presenti
✦
capacity: dimensione del vettore
✦
Contrazione → allocazione, copia, deallocazione
✦
Domanda:
✦
Come scegliere il fattore di carico?
✦
© Alberto Montresor
12
Vettori dinamici: contrazione
Prima strategia:
✦
Una strategia che sembra ovvia è dimezzare la memoria quando il fattore di carico
α diventa ½
✦
Questo ci assicura un fattore di carico α > ½ anche in presenza di cancellazioni
✦
Domanda:
✦
Dimostrare che questa strategia può portare ad un costo ammortizzato lineare
✦
© Alberto Montresor
13
Vettori dinamici: contrazione
Qual è il problema?
✦
Che non abbiamo un numero di inserimenti/rimozioni sufficienti
per ripagare le espansioni/contrazioni.
✦
Dobbiamo lasciar decrescere il sistema ad un fattore inferiore a α = ¼
✦
Dopo un'espansione, il fattore di carico diventa ½
✦
Dopo una contrazione, il fattore di carico diventa ½
✦
Analisi ammortizzata: usiamo una funzione di potenziale che
✦
vale 0 all’inizio e subito dopo una espansione o contrazione
✦
cresce fino a raggiungere il numero di elementi presenti nella tavola quando
α aumenta fino ad 1 o diminuisce fino ad ¼
✦
© Alberto Montresor
14
Vettori dinamici: contrazione
La funzione di potenziale:
✦
Alcuni casi esplicativi:
✦
α=½
(subito dopo espansione/contrazione), Φ = 0
α=1
(immediatamente prima di espansione), size=capacity
quindi Φ = size
α=¼
(immediatamente prima di contrazione), capacity=4⋅size
quindi Φ = size
✦
✦
✦
In altre parole: immediatamente prima di espansioni e contrazioni il potenziale è
sufficiente per “pagare” il loro costo
✦
© Alberto Montresor
15
size
capacity
32
16
8
4
2
1
12 4
© Alberto Montresor
8
16
32
48
i
16
Vettori dinamici: contrazione
Se α ≥ 1/2 il costo ammortizzato di un inserimento senza espansione è:
✦
mentre con espansione è:
✦
Altri casi per α e contrazione per esercizio
✦
© Alberto Montresor
17
Stack
Una pila (stack)
✦
è un insieme dinamico in cui l’elemento rimosso
dall’operazione di cancellazione è predeterminato:
“quello che per meno tempo è rimasto nell’insieme”
✦
politica “last in, first out” (LIFO)
✦
Operazioni previste (tutte realizzabili in O(1))
✦
© Alberto Montresor
18
Stack
Possibili utilizzi
✦
Nei linguaggi con procedure: gestione dei record di attivazione
✦
Nei linguaggi stack-oriented:
✦
Le operazioni elementari prendono uno-due operandi
dallo stack e inseriscono il risultato nello stack
✦
Es: Postscript, Java bytecode
✦
top
Possibili implementazioni
✦
Tramite liste bidirezionali
✦
puntatore all'elemento top
✦
Tramite vettore
✦
dimensione limitata, overhead più basso
✦
© Alberto Montresor
19
Stack
Reverse Polish Notation (PNG), o notazione postfissa
✦
Espressioni aritmetiche in cui gli operatori seguono gli operandi
✦
Definita dalla grammatica: <expr> ::= <numeral> | <expr> <expr> <operator>
✦
Esempi:
✦
(7 + 3) × 5
si traduce in
7 3+5×
7 + (3 × 5)
si traduce in
7 35×+
✦
✦
Valutazione PNG, stack based (esempio: Java bytecode)
✦
push 7
7
push 3
37
push 5
537
✦
✦
✦
op. ×: pop, pop, push
15 7
op. +: pop, pop, push
22
✦
✦
© Alberto Montresor
20
Stack - pseudocodice
© Alberto Montresor
21
Stack: implementazione tramite vettori (Java)
public class VectorStack implements Stack
{
/** Vector containing the elements */
private Object[] A;
/** Number of elements in the stack */
private int n;
public VectorStack(int dim) {
n = 0;
© Alberto Montresor
22
Stack: implementazione tramite vettori (Java)
public Object top() {
if (n == 0)
throw new IllegalStateException("Stack is empty");
return A[n-1];
}
public Object pop() {
if (n == 0)
throw new IllegalStateException("Stack is empty");
return A[--n];
}
public void push(Object o) {
if (n == A.length)
© Alberto Montresor
23
Queue
Una coda (queue)
✦
è un insieme dinamico in cui l’elemento rimosso
dall’operazione di cancellazione è predeterminato:
“quello che per più tempo è rimasto nell’insieme”
✦
politica “first in, first out” (FIFO)
✦
Operazioni previste (tutte realizzabili in O(1))
✦
© Alberto Montresor
24
Queue
Possibili utilizzi
✦
Nei sistemi operativi, i processi in attesa di utilizzare una risorsa vengono gestiti
tramite una coda
✦
La politica FIFO è fair
✦
Possibili implementazioni
✦
head
tail
Tramite liste monodirezionali
✦puntatore head (inizio della coda), per estrazione
✦
puntatore tail (fine della coda), per inserimento
✦
Tramite array circolari
✦
dimensione limitata, overhead più basso
✦
© Alberto Montresor
25
Coda: Realizzazione tramite vettore circolare

La “finestra” dell’array occupata dalla coda si sposta lungo l’array!

Dettagli implementativi


L'array circolare può
essere implementato
con un'operazione di
modulo
Bisogna prestare attenzione
ai problemi di overflow
(buffer pieno)
© Alberto Montresor
3
6
54
head+n
43
head
head
6
3
54
43
head+
n
26
Coda: Realizzazione tramite vettore circolare
head+n
3
6
54
head+n
head
3
43
6
54
43 12
head+n
head
6
54
6
54
dequeue() → 3
43 12
head+n head
33
enqueue(12)
enqueue (15, 17, 33)
43 12 15 17
head
© Alberto Montresor
27
Coda - pseudocodice
© Alberto Montresor
28
Queue: Implementazione tramite vettore circolare (Java)
public class VectorQueue implements Queue
{
/** Vector containing the elements */
private Object[] A;
/** Number of elements in the queue */
private int n;
/** Top element of the queue */
private int head;
public VectorQueue(int dim) {
© Alberto Montresor
29
Queue: Implementazione tramite vettore circolare (Java)
public Object top() {
if (n == 0)
throw new IllegalStateException("Queue is empty");
return A[head];
}
public Object dequeue()
{
if (n == 0)
throw new IllegalStateException("Queue is empty");
Object t = A[head];
head = (head+1) % A.length;
n = n-1;
© Alberto Montresor
30