Post on 06-Nov-2021
Algoritmi e strutture dati
ArgomentiStrutture dati elementari e loro implementazioni in Java:
VettoriListe Stack (Pile)Queue (Code)
Esempi di applicazione
Algoritmi e strutture dati 2
Tipo di dato astrattoTipo 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 elementocancellazione dell’i-esimo elementotest di lista vuota
Attenzione: l’ADT specifica cosa fa ogni operazione, non comeUn tipo di dato astratto è solitamente rappresentato in Java con un’interfaccia ed è implementato con una classe
Algoritmi e strutture dati 3
VettoriMemorizzazione di elementi omogenei in locazioni continue
Array unidimensionali:int[] num;
String[] str;
Creazione:num = new int[5];
str = new String[6];
Lunghezza:num.length
str.length
Accesso al singolo elemento:a[0] = 100;
str[1] = str[2];
Array bidimensionali:
int[][] mat = new int[4][3];
for(int i = 0; i<4; i++){
mat[i][0] = i;
mat[i][1] = i+1;
mat[i][2] = i+2;
}
Algoritmi e strutture dati 4
array e Vector
Classe Vector
Contiene Object. I tipi di dati primitivi devono essere convertiti mediante gli opportuni wrapperGestione flessibile dello spazio di memoriaGran numero di metodi a scapito dell'efficienza
array
Può contenere tipi di dati primitiviDimensione fissaPochi metodi ma maggiore efficienza
Algoritmi e strutture dati 5
Esempi di utilizzo della classe Vector e dell’interfaccia IteratorVector 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());
Algoritmi e strutture dati 6
Vector di tipi di dato primitiviVector 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());
Algoritmi e strutture dati 7
Liste, stack e code in JavaQuesti ADT sono rappresentati e implementati da interfacce e classi del package java.utilL’interfaccia più generale è Collection
Rappresenta un insieme di elementi, eventualmente replicati (multi-insieme)Ammette operazioni di inserimento e cancellazione
Algoritmi e strutture dati 8
Tipo di dato ListaInsieme di elementi tra i quali è definito un ordinamento totaleNumerose variantiEsempi di operazioni
insert(elem, i): inserisce elem in posizione i-esimaremove(i): elimina l’i-esimo elemento della listafindkth(i): restituisce l’i-esimo elementoisEmpty: restituisce vero se la lista è vuota…
Algoritmi e strutture dati 9
Implementazione delle liste
Tramite array
Tramite strutture collegateogni elemento contiene un riferimento al successivo
Algoritmi e strutture dati 10
Implementazione con arrayOccorre conoscere la dimensione max della lista Può portare a spreco dimemoria
Costo delle principali operazioni:
insert: O(n) (caso peggiore: elemento in prima posizione)remove: O(n), (caso peggiore: primo elemento) findkth: O(1)
A0 A1 A2 AN-3AN-2AN-1 Elemento non usato
Inserimento in pos. 2
Algoritmi e strutture dati 11
Implementazione con strutture collegate
Efficienzainsert, remove: O(i) (bisogna trovare la posizione dell’elemento da inserire/rimuovere). O(1) per inserimenti/cancellazioni in prima posizionefindkth: O(i) (posizione dell’elemento)
A0 A1 Ai AN
Inserimento in pos. 1
Algoritmi e strutture dati 12
Altri tipi di lista
Lista doppia: consente una scansione in entrambe le direzioni
A0 A1 Ai AN
Lista circolare: consente di rappresentare strutture in cui l’ordinamento è mod N
A0 A1 Ai AN
Algoritmi e strutture dati 13
Liste in Java
Interfaccia ListRappresenta una collezione ordinata di elementiAmmette duplicatiImplementazioni: classi LinkedList, ArrayList e Vector
Algoritmi e strutture dati 14
Liste in Java
classe ArrayList
realizza lista mediante arrayla dimensione può essere variata dinamicamente
classe LinkedList
lista doppiamente concatenata;riferimenti ai nodi di inizio e di fine
Algoritmi e strutture dati 15
Classe LinkedListLinkedList: realizza una lista come generica lista doppiamente concatenataMetodi principali:
LinkedList LinkedList(): metodo costruttorevoid add( Object o): inserisce alla fine della listavoid addLast(Object o): inserisce alla fine della listavoid addFirst(Object o): inserisce in testa alla listaObject removeFirst(): elimina all’inizio della listaObject removeLast(): elimina alla fine della listaboolean remove(Object obj): rimuove l’oggetto obj se esisteObject remove(int pos): rimuove l’oggetto in posizione posObject getFirst(): ritorna il primo oggettoObject getLast():ritorna l’ultimo oggettoObject get(int pos): ritorna l’oggetto in posizione pos…
Algoritmi e strutture dati 16
Classe ArrayListCorrisponde all’implementazione con array. Fornisce anche metodi per la modifica delle dimensioni dell’array.Metodi principali:
ArrayList ArrayList(): costruisce lista vuotaArrayList ArrayList(Collection col): costruisce lista da colvoid add(int pos, Object o): aggiunge in posizione posvoid addLast (Object o): aggiunge alla fine della listaboolean addAll(Collection col): aggiunge gli elementi di col alla fine della listaObject get(int pos): ritorno oggetto in posizione posObject getLast(): ritorna ultimo oggetto della listaObject remove(int pos): rimuove oggetto in posizione posvoid ensureCapacity(int min): aumenta la capacità dell’array fino a minint size(): ritorna la dimensione della lista…
Algoritmi e strutture dati 17
Classe Vector
Simile ad ArrayList
Consigliabile usarla quando più threadaccedono alla stessa struttura dati
Vector è sincronizzato (argomento avanzato trattato in corsi futuri)
Metodi simili a quelli di ArrayList
Algoritmi e strutture dati 18
riepilogo
O(1) + O(n)O(1) + O(1) (*)O(k) + O(1)ins kth
O(lg n) + O(n)O(n) + O(1)O(n) + O(1)del elem
O(1) + O(1) (*)
O(1)
O(n)
O(1) (*)
array
O(1) + O(n)O(k) + O(1)del kth
O(lg n) + O(n)O(1)ins elem
O(lg n)O(n)find elem
O(1)O(k)find kth
array ordinatolista coll.
(*) Poco significativa
Algoritmi e strutture dati 19
Tipo stack (o pila)
Lista nella quale inserimenti e cancellazioni avvengono solo in coda (disciplina LIFO)Operazioni
clear(): elimina tutti gli elementi dalla pilaisEmpty(): verifica se la pila è vuotaisFull(): verifica se la pila è pienapush(el): inserisce l'elemento specificato da elin cima alla pilapop(): elimina l'elemento in cima alla pilatopEl(): restituisce l'elemento in cima alla pila senza eliminarlo dalla pila
Algoritmi e strutture dati 20
Implementazione di stackArray: realizzazione tramite Vector
Liste: realizzazione tramite lista concatenata
A0
A1
Ai top = i
AN AN-1 Ai A0
top
Start
Algoritmi e strutture dati 21
Implementazione tramite Vectorpublic Object topEl(){
returnpool.lastElement();
}
public Object pop(){
returnpool.remove(pool.size()-1);
}
public void push(Object el){
pool.addElement(el);
}
public String toString(){
return pool.toString();
}
}
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();
}
Algoritmi e strutture dati 22
java.util.Stack (estende Vector)
Stack Stack(): Crea una pila vuota boolean empty(): restituisce true se la pila è vuotaObject peek(): realizza l'operazione topEl()Object pop(): rimuove e restituisce l'elemento affioranteObject push(el): inserisce l'elemento specificato in cima alla pilaint search(el): restituisce la posizione di elall'interno della pila
Algoritmi e strutture dati 23
Implementazione tramite LinkedList
public Object pop(){
return list.removeLast();
}
public void push(Object el){
list.add(el);
}
public String toString(){
return list.toString();
}
}
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();
}NB: le LinkedList sono doppiamente collegate
Algoritmi e strutture dati 24
Riconoscimento di stringhe parenteticamente corrette
La stringa vuota è parenteticamentecorrettaSe P1, P2 e P3 sono corrette, allora lo è anche P1(P2)P3Es.:
ab(ax)((b)du(mb)) è correttaa(ax)(c e a)b(e non sono corrette
Algoritmi e strutture dati 25
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 = falseelse pop()
} if (c == ‘(’)
push()c = <prossimo carattere di S>
}if ((<fine di S) && (! <stack vuoto))
balanced = falsereturn 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 26
Tipo astratto coda (queue)
Lista nella quale gli inserimenti avvengono in coda e le cancellazioni (estrazioni) in testa (disciplina FIFO)Operazioni:
clear() elimina tutti gli elementi dalla codaisEmpty() verifica se la coda è vuotaisFull() verifica se la coda è piena 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 dalla struttura
Algoritmi e strutture dati 27
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 (testa == (coda + 1) mod N) coda pienaSe (coda == testa) un solo elemento presente
Algoritmi e strutture dati 28
Implementazione di coda con Array circolare
first: indice del primo elementolast: indice dell'ultimosize: 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
Algoritmi e strutture dati 29
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 30
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;
}
Algoritmi e strutture dati 31
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;
}
Algoritmi e strutture dati 32
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
Algoritmi e strutture dati 33
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;
}
Algoritmi e strutture dati 34
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;
}
Algoritmi e strutture dati 35
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;
}
Algoritmi e strutture dati 36
Implementazione di una coda con lista concatenata/4public 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