Algoritmi e Strutture Dati
II
Tipo di dato astratto e
Strutture dati elementari
1
Argomenti della lezione
 Tipi di dato astratto
 Strutture dati elementari
 Liste
o Implementazione di liste in Java
 Stack
 Code
 Esempi di applicazione
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:
o Rappresentazione con interfaccia
o Implementazione con classe
3
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)
5
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
10
Liste in Java/2
 Interfaccia List
 Rappresenta una collezione ordinata di
elementi
 Ammette duplicati
 Implementazioni: classi LinkedList,
ArrayList e Vector
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.
12
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
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
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();
....
myIterator = myList.iterator();
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
16
Classe Vector
 E’ simile ad ArrayList
 I metodi sono simili a quelli di
ArrayList
 E’ una classe sincronizzata
 E’
consigliabile usarla quando più thread
accedono alla stessa struttura dati
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
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());
......
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());
........
20
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.
21
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.
22
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.
23
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

24
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’oggetto
int a = Integer.parseInt(o)
double f = Double.parseDouble(q)
 Le stringhe sono considerate oggetti
25
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
26
Implementazione del tipo Pila
 Realizzazione tramite Array
Ai
top = i
A1
A0
 Liste: realizzazione tramite lista concatenata
top
Start
A0
A1
Ai
AN
27
Implementazione asd_library
asd_library.stack.Stack
28
Implementazione tramite LinkedList
public 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.Stack
non realizza una vera pila (ci
sono operazioni in più)
29
Implementazione Java con Vector
public Object topEl(){
return
pool.lastElement();
}
public Object pop(){
return
pool.remove(pool.size()-1);
}
public void push(Object el){
pool.addElement(el);
}
public 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();
}
}
31
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
32
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 piena
Se (coda == testa) coda vuota (un solo elemento
presente)
33
Implementazione di coda con
Array circolare
 first:
 last:
 size:
indice del primo elemento - testa
indice dell'ultimo - coda
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
34
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;
}
Algoritmi e strutture dati
35
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 vuota
first=0;
} else storage[++last] = el;
}
36
Implementazione di coda con
Array circolare/4
public Object dequeue(){
Object tmp = null;
if(!isEmpty()) {
tmp = storage[first];
if (first == last) //caso unico elemento
last = first = -1;
else if (first == size - 1)
first = 0;
else first++;
}
return tmp;
}
37
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
38
Implementazione asd_library
asd_library.queue.Queue
39
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

44
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
45
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[])
46