Algoritmi e strutture dati - uniroma1.it

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


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;

}


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


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());


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();

}


Iterator it = v.iterator();

while (it.hasNext())

System.out.println(it.next());


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


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…


Implementazione delle liste

Tramite array

Tramite strutture collegateogni elemento contiene un riferimento al successivo


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


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


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


Liste in Java

Interfaccia ListRappresenta una collezione ordinata di elementiAmmette duplicatiImplementazioni: classi LinkedList, ArrayList e Vector


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


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…


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…


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


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


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


Implementazione di stackArray: realizzazione tramite Vector

Liste: realizzazione tramite lista concatenata

A0

A1

Ai top = i

AN AN-1 Ai A0

top

Start


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();

}


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


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();

}


return list.isEmpty();

}

public Object topEl(){

return list.getLast();

}NB: le LinkedList sono doppiamente collegate


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


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


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


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


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


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);

}


return first == -1;

}



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;

}



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;

}



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));


}

}

} // fine classe ArrayQueue


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;

}


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;

}


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;

}


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

Algoritmi e strutture dati - uniroma1.it

Documents

Transcript of Algoritmi e strutture dati - uniroma1.it