Ultima Lezione del
Corso di
Fondamenti di Informatica 1
a.a. 2005 – 06
Ma 29-Nov-2005
1
2
ADT
CONTENITORE
public interface Container
{ boolean isEmpty()
void makeEmpty();
/*
spesso si definisce anche size()
che restituisce il numero di elementi
nel contenitore
*/
// int size();
}
3
ADT
PILA (STACK)
LIFO
public interface Stack extends Container
{ void push(Object obj);
Object top() throws EmptyStackException;
Object pop() throws EmptyStackException;
}
Strutture Dati
Array (operazioni in coda)
Lista concatenata
Complessita' Temporale
push()
top()
pop()
O(1)
O(1)
O(1)
java.util.Stack (con qualche differenza)
4
ADT
CODA (QUEUE)
FIFO
public interface Queue extends Container
{ void enqueue(Object obj);
Object getFront() throws EmptyQueueException;
Object dequeue() throws EmptyQueueException;
}
Strutture Dati
Array circolare
Lista concatenata
Complessita' Temporale
enqueue()
getFront()
dequeue()
O(1)
O(1)
O(1)
Non c’e’ implementazione nella libreria standard
5
interfaccia java.util.Queue (con qualche differenza)
LISTA
ADT
public interface List extends Container
{ ListIterator getIterator();
}
public interface ListIterator
{
boolean hasNext();
void add(Object obj);
Object next() throws NoSuchElementException;
void remove() throws IllegalStateException;
}
Strutture Dati
Array
Lista concatenata
Complessita' Temporale
hasNext()
next()
add()
remove()
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
O(1)
O(1)
java.util.ArrayList, Vector, LinkedList (con qualche differenza)
6
ADT
DIZIONARIO
public interface Dictionary extends Container
{ void insert(Comparable key, Object value);
Object find(Comparable key);
void remove(Comparable key);
}
Strutture Dati
Array non ordinato
Array ordinato
Lista Concatenata
Complessita' Temporale
insert() O(n)* O(n)
O(1)
find()
O(n) O(lgn) O(n)
remove() O(n) O(n)
O(n)
* O(1) senza verifica di univocità della chiave
java.util.HashMap, interfaccia java.util.Map
7
ADT
TABELLA
public interface Table extends Container
{ void insert(int key, Object value);
Object find(int key);
void remove(int key);
}
Strutture Dati
Array
Complessita' Temporale
insert() O(1)
find()
O(1)
remove() O(1)
Uso non ottimale della memoria
fattore di riempimento (dati contenuti/dimensione tabella)
8
ADT
HASH TABLE
interface HashTable extends Container
{ void insert(Object key, Object value);
Object find(Object key);
void remove(Object key);
}
Strutture Dati
Array e Lista
Concatenata
(bucket)
Complessita' Temporale
insert() O(n/M)*
find()
O(n/M)
remove() O(n/M)
* M dimensione della tabella
Nell’ipotesi che la funzione
di hash sia uniforme
java.util.Hashtable, java.util.HashMap
9
SET
ADT
interface HashTable extends Container
{ void add(Object obj);
boolean contains(Object obj);
Object[] toArray();
}
Strutture Dati
Array non ordinato
Array Ordinato
Complessita' Temporale
add()
contains()
toArray()
Union
Intersect
subtract
O(n2)
O(n2)
O(n2)
O(n2)
O(n2)
O(n2)
interfacce java.util.Set, SortedSet
classi: HashSet
O(n)
O(lgn)
O(n)
O(nlgn)
O(nlgn)
O(nlgn)
10
Esercitazione
11