1 argomenti della lezione tipi di dato astratti strutture dati elementari liste implementazione di...
TRANSCRIPT
![Page 1: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/1.jpg)
1
Argomenti della lezione
Tipi di dato astratti Strutture dati elementari
• Liste—Implementazione di liste in Java
• Stack• Code
Esempi di applicazione
![Page 2: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/2.jpg)
2
Tipo di dato astratto
Tipo di dato astratto o ADT (Abstract Data Type): insieme di oggetti e insieme di operazioni definite su di esso
Es.: lista con operazioni di inserimento e cancellazione
Attenzione: l’ADT specifica cosa fa ogni operazione, non come
In Java: Rappresentazione con interfaccia Implementazione con classe
![Page 3: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/3.jpg)
10
Liste in Java/2
Interfaccia List Rappresenta una collezione ordinata di
elementi Ammette duplicati Implementazioni: classi LinkedList, ArrayList e Vector
![Page 4: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/4.jpg)
11
Liste in Java/3
Classe LinkedList
Realizza una lista doppiamente concatenata
Puntatori a inizio e fine della lista
Classe ArrayList
Realizza lista mediante array
Dimensione puo’ essere variata dinamicamente.
![Page 5: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/5.jpg)
12
Classe LinkedList
LinkedList: realizza una lista come generica lista doppiamente concatenata.
Costruttore• LinkedList LinkedList(): costruttore
Metodi principali: • void add(Object o): inserisce alla fine della lista• void addFirst(Object o): inserisce in testa alla lista• Object removeFirst(): elimina all’inizio della lista• Object removeLast(): elimina alla fine della lista• Object remove(int pos): rimuove l’oggetto in posizione
pos• Object getFirst(): restituisce il primo oggetto• Object getLast(): restituisce l’ultimo oggetto• Object get(int pos): restituisce l’oggetto in posizione
pos• Iterator iterator(): restituisce un Iterator sulla lista
![Page 6: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/6.jpg)
13
Classe ArrayList
Corrisponde all’implementazione con array
Costruttore• ArrayList ArrayList() :
costruisce lista vuota Metodi principali:
• Simili a quelli di LinkedList • Fornisce anche metodi per la modifica
delle dimensioni dell’array
![Page 7: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/7.jpg)
14
Iteratori
Sono oggetti che implementano l’interfaccia Iterator
Servono a scorrere sequenzialmente oggetti di tipo Collection (quindi anche liste)
Esempio:...
LinkedList myList = new LinkedList();
....
Iterator myIterator = myList.iterator();
![Page 8: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/8.jpg)
15
Iteratori/2
myIterator permette di scorrere gli elementi di myList
Metodi:• Object next(): restituisce l’elemento successivo
della lista• boolean hasNext(): vero se la lista contiene altri
elementi• void remove(): elimina dalla lista l’elemento
corrente E’ solamente un oggetto di ausilio per scorrere
la lista Si può ovviamente scorrere la lista
direttamente usando gli indici
![Page 9: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/9.jpg)
16
Classe Vector
E’ simile ad ArrayListI metodi sono simili a quelli di ArrayList
E’ una classe sincronizzata• E’ consigliabile usarla quando più
thread che accedono alla stessa struttura dati
![Page 10: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/10.jpg)
17
Classe Vector/2
Array:
Possono contenere tipi di dati primitivi
Dimensione fissa Pochi metodi ma
maggiore efficienza
Classe Vector
Contiene Object. I tipi di dati primitivi devono essere convertiti mediante gli opportuni wrapper.
Gestione flessibile dello spazio di memoria.
Gran numero di metodi a scapito dell'efficienza
![Page 11: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/11.jpg)
18
Esempi di uso della classe Vector e dell’interfaccia Iterator
......Vector v = new Vector();
String st = br.readLine(); // br BufferedReader
while (st != null) {v.addElement(st); st = br.readLine();
} System.out.println();
Iterator it = v.iterator(); while (it.hasNext())
System.out.println(it.next());......
![Page 12: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/12.jpg)
19
Vector di tipi di dato primitivi.......
Vector v = new Vector();
String st = br.readLine(); // br BufferedReader
while (st != null) {int num = Integer.parseInt(st); v.addElement(new Integer(num)); st = br.readLine();
} System.out.println();
Iterator it = v.iterator(); while (it.hasNext())
System.out.println(it.next());........
![Page 13: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/13.jpg)
20
Tipo astratto Pila Lista nella quale inserimenti e cancellazioni avvengono solo
in testa (disciplina LIFO).
Operazioni sempre presenti
• push(el): inserisce l'elemento specificato da el in cima alla
pila
• pop(): elimina l'elemento in cima alla pila
• top(): restituisce l'elemento in cima alla pila senza
cancellarlo dalla lista
• isEmpty(): verifica se la pila è vuota
Altre operazioni
• clear(): elimina tutti gli elementi dalla pila
![Page 14: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/14.jpg)
21
Implementazione del tipo Pila
Realizzazione tramite Array
Liste: realizzazione tramite lista
concatenata
A0
A1
Ai top = i
A0 A1 Ai AN
top
Start
![Page 15: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/15.jpg)
22
Implementazione Java con Vectorpublic class Stack {
private java.util.Vector pool= new java.util.Vector();
public Stack(){ } public Stack(int n){ pool.ensureCapacity(n) } public void clear(){ pool.clear(); } public boolean isEmpty(){ return pool.isEmpty(); }
public Object topEl(){ return
pool.lastElement(); } public Object pop(){
return pool.remove(pool.size()-1);
} public void push(Object el){
pool.addElement(el); }
}
![Page 16: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/16.jpg)
23
Implementazione tramite LinkedListpublic class LLStack { private list= new
java.util.LinkedList();
public LLStack(){ } public void clear(){ list.clear(); } public boolean isEmpty(){ return
list.isEmpty(); } public Object topEl(){ return
list.getLast(); }
public Object pop(){ return list.removeLast(); } public void push(Object el){ list.add(el); } public String toString(){ return list.toString(); } }
Attenzione: java.util.Stacknon realizza una vera pila (cisono operazioni in più)
![Page 17: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/17.jpg)
25
Tipo astratto coda Lista nella quale gli inserimenti avvengono in
coda e le cancellazioni (estrazioni) in testa (disciplina FIFO)
Operazioni sempre presenti• isEmpty(): verifica se la coda è vuota• enqueue(el): inserisce l'elemento
specificato da el alla fine della coda• dequeue(): elimina il primo elemento della
coda• firstEl(): restituisce il primo elemento
della coda senza eliminarlo Altre operazioni
• clear(): elimina tutti gli elementi dalla coda
![Page 18: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/18.jpg)
26
Implementazione di code con array
A0 A1 A2 AN-3 AN-2 AN-1
testa coda
Elemento non usato
enqueue -> coda = coda + 1 (mod N)dequeue -> testa = testa + 1 (mod N)
Se (coda == testa – 1 mod N) coda pienaSe (coda == testa) coda vuota (un solo elemento presente)
![Page 19: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/19.jpg)
27
Implementazione di coda con Array circolare first: indice del primo elemento - testa last: indice dell'ultimo - coda size: numero di elementi dell'array
public class ArrayQueue {private int first, last, size; private Object[] storage; private static final int DEFAULTSIZE = 100;
// metodi nella prossima slide
![Page 20: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/20.jpg)
Algoritmi e strutture dati 28
Implementazione di coda con Array circolare/2
public ArrayQueue(){this(DEFAULTSIZE);
}public ArrayQueue(int n){ size = n;storage = new Object[size];first = last = -1;
} public boolean isFull(){ return ((first == 0) && (last == size - 1)) ||
(first == last + 1); } public boolean isEmpty(){ return first == -1;
}
![Page 21: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/21.jpg)
29
Implementazione di coda con Array circolare/3
public void enqueue(Object el){if(!isFull())if ((last == size - 1) || (last == -1)) { storage[0] = el; last = 0; if (first == -1) //caso coda vuotafirst=0;
} else storage[++last] = el; }
![Page 22: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/22.jpg)
30
Implementazione di coda con Array circolare/4
public Object dequeue(){ Object tmp = null; if(!isEmpty()) {tmp = storage[first];if (first == last) // caso unico elementolast = first = -1;
else if (first == size - 1) first = 0; else first++; }
return tmp; // Restituisce null se coda vuota}
![Page 23: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/23.jpg)
31
Implementazione di coda con Array circolare/5
public void printAll(){ if(isEmtpy())
System.out.println("Coda vuota."); else {int i = first;do {
System.out.print(storage[i] + " "); i = (i + 1) % size; } while(i != ((last + 1) % size)); System.out.println(); }}
} // fine classe ArrayQueue
![Page 24: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/24.jpg)
32
Implementazione di una coda con lista concatenata
public class QueueNode { protected Object info; protected QueueNode next = null; public QueueNode(Object el) { info = el; }}
public class Queue {private QueueNode head, tail;public Queue() {
head = tail = null; }
![Page 25: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/25.jpg)
33
Implementazione di una coda con lista concatenata/2
public boolean isEmpty() { return head == null; }public void clear() {
head = tail = null; }public Object firstEl() {
return head.info; }
![Page 26: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/26.jpg)
34
Implementazione di una coda con lista concatenata/3
public void enqueue(Object el) { QueueNode q = new QueueNode(el);if (!isEmpty()) {
tail.next = q; tail = tail.next; } else head = tail = q;
![Page 27: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/27.jpg)
35
Implementazione di una coda con lista concatenata/4public Object dequeue() {// cancella il nodo in
// testa e restituisce il campo info if (!isEmpty()) { Object el = head.info; if (head == tail) // un solo nodo?head = tail = null;
else head = head.next; return el;
} else return null; } // fine metodo dequeue
} // fine classe Queue
![Page 28: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/28.jpg)
36
Riconoscimento di stringhe parenteticamente corrette La stringa vuota è parenteticamente
corretta Se P1, P2 e P3 sono corrette, allora lo è
anche P1(P2)P3, P1[P2]P3 o P1{P2}P3
Es.:• ab(ax)[(b)du{(mb)}] è corretta• a(ax)[c e a){b(e} non sono corrette
![Page 29: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/29.jpg)
37
Algoritmo (solo un tipo di parentesi)
Algorithm stringAnalyzerbalanced = true;S = <Leggi la stringa>c = <primo carattere di S>count = 0;while ((! <fine di S>) && (count >= 0)) {
if (c == ‘(’) count++;
else if (c == ‘)’) count--;
c = <prossimo carattere di S>}if ((fine di S) && (count != 0))
balanced = false;
Provare a implementare il riconoscimento con parentesi di qualunque tipo.
Es.:- fg{([{ab(vc)g}kj])
} è corretta- gh{(df[ghj]}gh)hj
non è corretta
![Page 30: 1 Argomenti della lezione Tipi di dato astratti Strutture dati elementari Liste Implementazione di liste in Java Stack Code Esempi di applicazione](https://reader036.vdocumenti.com/reader036/viewer/2022070312/5542eb57497959361e8c1974/html5/thumbnails/30.jpg)
38
Algoritmo (caso generale)
Usa uno stack Se arriva ‘(‘, ‘[‘ o ‘{‘
inseriscila nello stack Se arriva ‘)‘, ‘]‘ o ‘}‘
confrontala con l’elemento affiorante
• Se non corrispondono allora la stringa non è bilanciata
Se si esamina la stringa fino alla fine e lo stack non è vuoto la stringa non è bilanciata. Es.: (((er[])
( [
()
]