Argomenti della lezione
 Tipi di dato astratti
 Strutture dati elementari
• Liste
—Implementazione di liste in Java
• Stack
• Code
 Esempi di applicazione
1
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
2
Liste in Java/2
 Interfaccia List
 Rappresenta una collezione ordinata di
elementi
 Ammette duplicati
 Implementazioni: classi LinkedList,
ArrayList e Vector
10
Liste in Java/3
Classe LinkedList
Classe ArrayList
 Realizza una lista
 Realizza lista mediante
doppiamente
concatenata
 Puntatori a inizio e fine
della lista
array
 Dimensione puo’ essere
variata dinamicamente.
11
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
12
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
13
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();
14
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
15
Classe Vector
 E’ simile ad ArrayList
 I metodi sono simili a quelli di
ArrayList
 E’ una classe sincronizzata
• E’ consigliabile usarla quando più thread
che accedono alla stessa struttura dati
16
Classe Vector/2
Array:
Classe Vector
 Possono contenere tipi
 Contiene Object. I tipi di dati
di dati primitivi
 Dimensione fissa
 Pochi metodi ma
maggiore efficienza
primitivi devono essere
convertiti mediante gli
opportuni wrapper.
 Gestione flessibile dello
spazio di memoria.
 Gran numero di metodi a
scapito dell'efficienza
17
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());
......
18
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());
........
19
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
20
Implementazione del tipo Pila
 Realizzazione tramite Array
Ai
top = i
A1
A0
 Liste: realizzazione tramite lista concatenata
top
Start
A0
A1
Ai
AN
21
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();
}
}
22
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ù)
23
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
25
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)
26
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
27
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
28
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;
}
29
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; // Restituisce null se coda vuota
}
30
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
31
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;
}
32
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;
}
33
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;
34
Implementazione di una coda
con lista concatenata/4
public 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
35
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
36
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
37
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[])
38