1 algoritmi e strutture dati ii tipo di dato astratto e strutture dati elementari
TRANSCRIPT
![Page 1: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/1.jpg)
1
Algoritmi e Strutture Dati II
Tipo di dato astratto e Strutture dati elementari
![Page 2: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/2.jpg)
2
Argomenti della lezione
Tipi di dato astratto Strutture dati elementari
Listeo Implementazione di liste in Java
StackCode
Esempi di applicazione
![Page 3: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/3.jpg)
3
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:o Rappresentazione con interfacciao Implementazione con classe
![Page 4: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/4.jpg)
5
Tipo di dato Lista
Insieme di elementi tra i quali è definito un ordinamento totale.
Numerose varianti Ammette (almeno) le operazioni seguenti:
cons(elem): inserisce elem in testa alla lista cdr(): elimina l’ elemento in testa alla lista car(): restituisce l’ elemento in testa alla lista
senza eliminarlo
Nelle implementazioni (es. Java) sono spesso presenti altre operazioni cons(elem, i), remove(i), get(i)
![Page 5: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/5.jpg)
10
Liste in Java
Questi ADT sono rappresentati e implementati da interfacce e classi del package java.util (in realtà strutture dati più ricche)
L’interfaccia più generale è Collection
Rappresenta un insieme di elementi, eventualmente replicati (multinsieme)
Ammette operazioni di inserimento e cancellazione
![Page 6: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/6.jpg)
11
Liste in Java/2
Interfaccia List Rappresenta una collezione ordinata di
elementi Ammette duplicati Implementazioni: classi LinkedList, ArrayList e Vector
![Page 7: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/7.jpg)
12
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 8: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/8.jpg)
13
Classe LinkedList
LinkedList: realizza una lista come generica lista doppiamente concatenata.
Costruttore LinkedList LinkedList(): metodo 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 9: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/9.jpg)
14
Classe ArrayList
Corrisponde all’implementazione con array
CostruttoreArrayList ArrayList(): costruisce
lista vuota Metodi principali:
Simili a quelli di LinkedList Fornisce anche metodi per la modifica
delle dimensioni dell’array
![Page 10: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/10.jpg)
15
Iteratori
Sono oggetti che implementano l’interfaccia Iterator
Servono a scorrere sequenzialmente oggetti di tipo Collection (quindi anche liste)
Esempio:...
LinkedList myList = new LinkedList();
....
myIterator = myList.iterator();
![Page 11: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/11.jpg)
16
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 12: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/12.jpg)
17
Classe Vector
E’ simile ad ArrayListI metodi sono simili a quelli di ArrayList
E’ una classe sincronizzataE’ consigliabile usarla quando più
thread accedono alla stessa struttura dati
![Page 13: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/13.jpg)
18
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 14: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/14.jpg)
19
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 15: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/15.jpg)
20
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 16: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/16.jpg)
21
La classe java.lang.Object
Java definisce una classe speciale Object. Tutte le altre classi sono sottoclassi di
Object. Ed è quindi la radice della gerarchia di classi Java
E’ una classe abstract.
![Page 17: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/17.jpg)
22
Metodi della classe Object /1
La classe Object definisce alcuni metodi di utilità, fra cui: public boolean equals(Object obj) confronta
il contenuto di this ed obj, restituendo true se sono equivalenti false in caso contrario. Viene ridefinito per implementare un concetto di uguaglianza relativo alla classe in cui è ridefinito.
![Page 18: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/18.jpg)
23
Metodi della classe Object /2
public String toString() restituisce una rappresentazione standard dell’oggetto come stringa. Viene chiamato automaticamente quando si ottiene l’output di un oggetto con println(). Molte classi ridefiniscono questo metodo in modo da ottenere una descrizione opportuna dei tipi di oggetto creati.
![Page 19: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/19.jpg)
24
Metodi della classe Object /3
public Object clone() ritorna una copia dell’oggetto.
Deep cloning: copia in profondità i dati riferiti dai campi dell’oggetto. Difficile da realizzare se si desidera mantenera la generalità sui dati memorizzati
Shallow cloning: copia solo i riferimenti ai dati memorizzati nei campi, non gli oggetti stessi
![Page 20: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/20.jpg)
25
Wrapper di tipi di dato primitivi Trasformano un tipo di dato primitivo in
un oggetto.Object o = new Integer(5)Object p = new Character(c)Object q = new Double(5.0)
Metodo parse per ottenere il tipo di dato primitivo dall’oggettoint a = Integer.parseInt(o)double f = Double.parseDouble(q)
Le stringhe sono considerate oggetti
![Page 21: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/21.jpg)
26
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 22: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/22.jpg)
27
Implementazione del tipo Pila
Realizzazione tramite Array
Liste: realizzazione tramite lista
concatenata
A0
A1
Ai top = i
A0 A1 Ai AN
top
Start
![Page 23: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/23.jpg)
28
Implementazione asd_library
asd_library.stack.Stack
![Page 24: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/24.jpg)
29
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 25: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/25.jpg)
31
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 26: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/26.jpg)
32
Tipo astratto coda Lista nella quale gli inserimenti avvengono in
coda e le cancellazioni (estrazioni) in testa (disciplina FIFO)
Operazioni sempre presenti clear(): elimina tutti gli elementi dalla coda 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
![Page 27: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/27.jpg)
33
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 28: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/28.jpg)
34
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 29: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/29.jpg)
Algoritmi e strutture dati 35
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 30: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/30.jpg)
36
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 31: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/31.jpg)
37
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; }
![Page 32: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/32.jpg)
38
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 33: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/33.jpg)
39
Implementazione asd_library
asd_library.queue.Queue
![Page 34: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/34.jpg)
44
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 35: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/35.jpg)
45
Algoritmo (solo un tipo di parentesi)Algorithm stringAnalyzer
balanced = 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 36: 1 Algoritmi e Strutture Dati II Tipo di dato astratto e Strutture dati elementari](https://reader035.vdocumenti.com/reader035/viewer/2022062303/5542eb4b497959361e8b802b/html5/thumbnails/36.jpg)
46
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[])
( [
()
]