Algoritmi e strutture dati
Argomenti
 Strutture dati elementari e loro
implementazioni in Java:
Vettori
Liste
Stack (Pile)
Queue (Code)
 Esempi di applicazione
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 ordinata di elementi con le seguenti
operazioni:
 inserimento di un nuovo elemento
 cancellazione dell’i-esimo elemento
 test di lista vuota
 Attenzione: l’ADT specifica cosa fa ogni operazione,
non come
 Un tipo di dato astratto è solitamente rappresentato in
Java con un’interfaccia ed è implementato con una
classe
30/04/2002
Algoritmi e strutture dati
2
Vettori
 Memorizzazione di elementi omogenei in locazioni
continue
Array unidimensionali:
Array bidimensionali:
int[] num;
String[] str;
int[][] mat = new int[4][3];
Creazione:
num = new int[5];
for(int i = 0; i<4; i++){
str = new String[6];
mat[i][0] = i;
Lunghezza:
mat[i][1] = i+1;
num.length
mat[i][2] = i+2;
str.length
}
Accesso al singolo elemento:
a[0] = 100;
str[1] = str[2];
30/04/2002
Algoritmi e strutture dati
3
array e Vector
array
Classe Vector
 Può contenere tipi di
 Contiene Object. I tipi di
dati primitivi
 Dimensione fissa
 Pochi metodi ma
maggiore efficienza
30/04/2002
dati primitivi devono
essere convertiti
mediante gli opportuni
wrapper
 Gestione flessibile dello
spazio di memoria
 Gran numero di metodi a
scapito dell'efficienza
Algoritmi e strutture dati
4
Esempi di utilizzo 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());
30/04/2002
Algoritmi e strutture dati
5
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());
30/04/2002
Algoritmi e strutture dati
6
Liste, stack e code in Java
 Questi ADT sono rappresentati e
implementati da interfacce e classi del
package java.util
 L’interfaccia più
generale è Collection


Rappresenta un insieme
di elementi,
eventualmente
replicati (multi-insieme)
Ammette operazioni
di inserimento e
cancellazione
Algoritmi e strutture dati
7
Tipo di dato Lista
 Insieme di elementi tra i quali è definito un
ordinamento totale
 Numerose varianti
 Esempi di operazioni





30/04/2002
insert(elem, i): inserisce elem in posizione
i-esima
remove(i): elimina l’i-esimo elemento della
lista
findkth(i): restituisce l’i-esimo elemento
isEmpty: restituisce vero se la lista è vuota
…
Algoritmi e strutture dati
8
Implementazione delle liste
 Tramite array
 Tramite strutture collegate
 ogni elemento contiene un riferimento
al successivo
30/04/2002
Algoritmi e strutture dati
9
Implementazione con array
 Occorre conoscere la
dimensione max della
lista
 Può portare a spreco di
memoria
 Costo delle principali
operazioni:



A0 A1 A2
AN-3AN-2AN-1
insert: O(n) (caso
peggiore: elemento in
prima posizione)
remove: O(n), (caso
peggiore: primo
elemento)
findkth: O(1)
Elemento non usato
Inserimento in pos. 2
30/04/2002
Algoritmi e strutture dati
10
Implementazione con strutture collegate
 Efficienza
 insert, remove: O(i) (bisogna trovare la posizione dell’elemento
da inserire/rimuovere). O(1) per inserimenti/cancellazioni in
prima posizione
 findkth: O(i) (posizione dell’elemento)
A0
A1
Ai
AN
Inserimento in pos. 1
30/04/2002
Algoritmi e strutture dati
11
Liste in Java
 Interfaccia List
 Rappresenta una collezione ordinata di
elementi
 Ammette duplicati
 Implementazioni: classi LinkedList,
ArrayList e Vector
30/04/2002
Algoritmi e strutture dati
13
Liste in Java
classe LinkedList
classe ArrayList
 lista doppiamente
 realizza lista
concatenata;
 riferimenti ai nodi
di inizio e di fine
30/04/2002
mediante array
 la dimensione può
essere variata
dinamicamente
Algoritmi e strutture dati
14
Classe LinkedList
 LinkedList: realizza una lista come generica lista
doppiamente concatenata
 Metodi principali:












LinkedList LinkedList(): metodo costruttore
void add( Object o): inserisce alla fine della lista
void addLast(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
boolean remove(Object obj): rimuove l’oggetto obj se
esiste
Object remove(int pos): rimuove l’oggetto in posizione pos
Object getFirst(): ritorna il primo oggetto
Object getLast():ritorna l’ultimo oggetto
Object get(int pos): ritorna l’oggetto in posizione pos
…
Algoritmi e strutture dati
15
Classe ArrayList
 Corrisponde all’implementazione con array. Fornisce anche
metodi per la modifica delle dimensioni dell’array.
 Metodi principali:










ArrayList ArrayList(): costruisce lista vuota
ArrayList ArrayList(Collection col): costruisce lista da col
void add(int pos, Object o): aggiunge in posizione pos
void addLast (Object o): aggiunge alla fine della lista
boolean addAll(Collection col): aggiunge gli elementi di col alla
fine della lista
Object get(int pos): ritorno oggetto in posizione pos
Object getLast(): ritorna ultimo oggetto della lista
Object remove(int pos): rimuove oggetto in posizione pos
void ensureCapacity(int min): aumenta la capacità dell’array fino
a min
int size(): ritorna la dimensione della lista
…

30/04/2002
Algoritmi e strutture dati
16
Classe Vector
 Simile ad ArrayList
 Consigliabile usarla quando più thread
accedono alla stessa struttura dati

Vector è sincronizzato (argomento avanzato
trattato in corsi futuri)
 Metodi simili a quelli di ArrayList
30/04/2002
Algoritmi e strutture dati
17
Tipo stack (o pila)
 Lista nella quale inserimenti e cancellazioni
avvengono solo in coda (disciplina LIFO)
 Operazioni






clear(): elimina tutti gli elementi dalla pila
isEmpty(): verifica se la pila è vuota
isFull(): verifica se la pila è piena
push(el): inserisce l'elemento specificato da el
in cima alla pila
pop(): elimina l'elemento in cima alla pila
topEl(): restituisce l'elemento in cima alla pila
senza eliminarlo dalla pila
30/04/2002
Algoritmi e strutture dati
18
Implementazione di stack
 Array: realizzazione tramite Vector
Ai
top = i
A1
A0
 Liste: realizzazione tramite lista concatenata
top
Start
AN
30/04/2002
AN-1
Ai
A0
Algoritmi e strutture dati
19
Implementazione tramite Vector
public class Stack {
private Vector pool =
new Vector();
public Stack(){
}
public Stack(int n){
pool.ensureCapacity(n);
}
public void clear(){
pool.clear();
}
public boolean isEmpty(){
return pool.isEmpty();
}
30/04/2002
public Object topEl(){
return
pool.lastElement();
}
public Object pop(){
return
pool.remove(pool.size()-1);
}
public void push
(Object el){
pool.addElement(el);
}
public String toString(){
return pool.toString();
}
}
Algoritmi e strutture dati
20
java.util.Stack (estende Vector)
 Stack Stack(): Crea una pila vuota
 boolean empty(): restituisce true se la pila
è vuota
 Object peek(): realizza l'operazione topEl()
 Object pop(): rimuove e restituisce
l'elemento affiorante
 Object push(el): inserisce l'elemento
specificato in cima alla pila
 int search(el): restituisce la posizione di el
all'interno della pila
30/04/2002
Algoritmi e strutture dati
21
Implementazione tramite LinkedList
public class LLStack {
private LinkedList list =
new LinkedList();
public LLStack(){
}
public void clear(){
list.clear();
}
public boolean isEmpty(){
return list.isEmpty();
}
public Object topEl(){
return list.getLast();
}
30/04/2002
public Object pop(){
return
list.removeLast();
}
public void
push(Object el){
list.add(el);
}
public String toString(){
return
list.toString();
}
}
NB: le LinkedList sono
doppiamente collegate
Algoritmi e strutture dati
22
Riconoscimento di stringhe
parenteticamente corrette
 La stringa vuota è parenteticamente
corretta
 Se P1, P2 e P3 sono corrette, allora lo è
anche P1(P2)P3
 Es.:


ab(ax)((b)du(mb)) è corretta
a(ax)(c e a)b(e non sono corrette
30/04/2002
Algoritmi e strutture dati
23
Algoritmo (usa uno stack)
Algorithm stringAnalyzer
balanced = true;
S = <Leggi la stringa>
c = <primo carattere di S>
while ((! <fine di S>) && (balanced)) {
if (c == ‘)’) {
if (<stack vuoto>)
balanced = false
else pop()
}
if (c == ‘(’)
push()
c = <prossimo carattere di S>
}
if ((<fine di S) && (! <stack vuoto))
balanced = false
return balanced
)
(
(
(
Provare a implementare il
riconoscimento con
parentesi di qualunque tipo.
Es.:
- fg{([{ab(vc)g}kj])} è
corretta
- gh{(df[ghj]}gh)hj non è
corretta
Algoritmi e strutture dati
24
Tipo astratto coda (queue)
 Lista nella quale gli inserimenti avvengono in coda e
le cancellazioni (estrazioni) in testa (disciplina
FIFO)
 Operazioni:






clear()
isEmpty()
isFull()
enqueue(el)
dequeue()
firstEl()
30/04/2002
elimina tutti gli elementi dalla coda
verifica se la coda è vuota
verifica se la coda è piena
inserisce l'elemento specificato da el
alla fine della coda
elimina il primo elemento della coda
restituisce il primo elemento della coda
senza eliminarlo dalla struttura
Algoritmi e strutture dati
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)
30/04/2002
Algoritmi e strutture dati
26
Implementazione di coda con
Array circolare
 first:
 last:
 size:
indice del primo elemento
indice dell'ultimo
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
30/04/2002
Algoritmi e strutture dati
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;
}
30/04/2002
Algoritmi e strutture dati
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;
}
30/04/2002
Algoritmi e strutture dati
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
30/04/2002
Algoritmi e strutture dati
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;
}
30/04/2002
Algoritmi e strutture dati
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;
}
30/04/2002
Algoritmi e strutture dati
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;
}
30/04/2002
Algoritmi e strutture dati
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
30/04/2002
Algoritmi e strutture dati
35