AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.
-
Upload
fortunato-cossu -
Category
Documents
-
view
215 -
download
1
Transcript of AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.
![Page 1: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/1.jpg)
AlgoLab - Pile e Code
Pile e code
Laboratorio di Algoritmi 02/03
Prof. Ugo de’ Liguoro
![Page 2: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/2.jpg)
AlgoLab - Pile e Code
Pile: definizione informale
Una pila è una struttura dati lineare, cui gli elementi possono essere aggiunti o sottratti da un solo estremo (LIFO).
![Page 3: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/3.jpg)
AlgoLab - Pile e Code
Operazioni sulle pile
Una pila (stack) si definisce astrattamente come una struttura dati su cui siano definite alemeno quattro operazioni:
1. Push(e,s) : aggiunge e alla pila s
2. Pop(s) : elimina l’elemento emergente da s
3. Top(s) : ritorna il valore dell’emergente di s
4. IsEmpty(s): ritorna true se s non ha elementi.
Nota: se s è vuota, Pop(s) e Top(s) sono indefinite.
![Page 4: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/4.jpg)
AlgoLab - Pile e Code
L’interfaccia Stack
interface Stack {
void push(Object newitem);
// aggiunge newitem come emergente
void pop();
// rimuove l’emergente dalla pila
Object top();
// ritorna l’emergente senza rimuoverlo
boolean empty();
// true se la pila e’ vuota
}
![Page 5: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/5.jpg)
AlgoLab - Pile e Code
L’interfaccia List
interface List {
void cons (Object newitem);
// aggiunge newitem in testa alla lista
boolean insert(Object newitem, int index);
// inserisce newitem alla pos. index; false
// se index > length()
boolean delete(int index);
// rimuove l’elemento di pos. index; false se
// index not in 0..length()-1
Object retrieve(int index);
// pre: index in 0..length()-1
// post: ritorna l’elemento di indice index
public int length (); // ritorna la lunghezza
}
![Page 6: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/6.jpg)
AlgoLab - Pile e Code
Le pile implementate come liste
Supponendo di aver riscritto SList in modo tale che implementi l’interfaccia List, e quindi sia generica (elementi di tipo Object):
class StackByList extends SList implements Stack {
public void push(Object newitem) {cons(newitem);}
public void pop() {delete(0);}
public Object top() {return retrieve(0);}
public boolean empty() {return length() == 0;}
}
![Page 7: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/7.jpg)
AlgoLab - Pile e Code
La gerarchia dei tipi e delle classi
L’implementazione delle pile presentata si basa dunque sulla gerarchia (interfacce e relazioni di implementazione in rosso, classi e relazioni di ereditarietà in blu):
List Stack
SList
StackByList
![Page 8: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/8.jpg)
AlgoLab - Pile e Code
Notazione polacca postfissa
Nella notazione polacca postfissa per le espressioni aritmetiche un operatore segue i suoi operandi. E’ definita dalla grammatica:
<espressione> ::= <numerale> |
<espressione> <espressione> <operatore>
Esempi:
(7 + 3) £ 5 si traduce in 7 3 + 5 £7 + 3 £ 5 si traduce in 7 3 5 £ +
![Page 9: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/9.jpg)
AlgoLab - Pile e Code
Algoritmo di valutazione
Valuta (Stringa espr)
// espr è fatta di parole separate da spazi
s := pila vuota
while (scansione di espr non è finita)
e := prossima parola di espr;
if (e è un numerale) then Push(e,s)
else // e è un operatore
n := Top(s); Pop(s); // l’ordine di lettura ed eliminaz.
m := Top(s); Pop(s); // dalla coda è importante …
op := oppure a seconda di e;
Push(m op n, s) // … qui
return Top(s). // se espr è un’espr. in not. polacca, s ha un solo el.
![Page 10: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/10.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4top
![Page 11: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/11.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
8top
![Page 12: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/12.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
8
7top
![Page 13: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/13.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
8
7
3top
![Page 14: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/14.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
8
10top
![Page 15: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/15.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
80top
![Page 16: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/16.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
80
2top
![Page 17: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/17.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
4
40top
![Page 18: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/18.jpg)
AlgoLab - Pile e Code
Esecuzione dell’algoritmo
4 8 7 3 +
44top
![Page 19: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/19.jpg)
AlgoLab - Pile e Code
Code: definizione informale
Le code sono strutture lineari i cui elementi si inseriscono da un estremo e si estraggono dall’altro (FIFO)
![Page 20: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/20.jpg)
AlgoLab - Pile e Code
Operazioni sulle code
Una coda (queue) si definisce astrattamente come una struttura dati su cui siano definite alemeno le operazioni:
Enqueue(e,q) : aggiunge e come ultimo in q
Dequeue(q) : elimina il primo in q
Head(q) : ritorna il valore del primo in q
IsEmpty(q): ritorna true se q non ha elementi.
Nota: se q è vuota, Dequeue(q) e Head(q) sono indefinite.
![Page 21: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/21.jpg)
AlgoLab - Pile e Code
Code realizzate con vettori (1)
q
f rcoda vuota
7 1 5q
f r
1 5q
f rDequeue(q)
![Page 22: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/22.jpg)
AlgoLab - Pile e Code
Code realizzate con vettori (2)
5 2q
f r
Enqueue(9,q) 9 5 2q
fr
L’indice della locazione successiva (sia per f che per r) si calcola:
i + 1 mod n (n = lunghezza del vettore)
![Page 23: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/23.jpg)
AlgoLab - Pile e Code
Code realizzate con vettori (3)
9 3 5 2q
fr
Condizione necessaria perché una coda di lunghezza n sia piena è:
r + 1 mod n = f
Tale condizione tuttavia non è sufficiente, dato che si verifica anche in quello di coda vuota
coda piena
q
frcoda vuota
![Page 24: AlgoLab - Pile e Code Pile e code Laboratorio di Algoritmi 02/03 Prof. Ugo de’ Liguoro.](https://reader036.fdocumenti.com/reader036/viewer/2022062702/5542eb76497959361e8e009f/html5/thumbnails/24.jpg)
AlgoLab - Pile e Code
Code realizzate con liste
front
rear
…
Come si realizza tutto questo in Java, sfruttando il più possibile le interfacce e l’ereditarietà?