1

Argomenti della lezione

Tipi di dato astratti Strutture dati elementari

Listeo Implementazione di liste in Java

StackCode

Esempi di applicazione

2

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:o Rappresentazione con interfacciao Implementazione con classe

10

Liste in Java/2

Interfaccia List Rappresenta una collezione ordinata di

elementi Ammette duplicati Implementazioni: classi LinkedList, ArrayList e Vector

11

Liste in Java/3

Classe LinkedList

Realizza una lista doppiamente concatenata

Puntatori a inizio e fine della lista

Classe ArrayList

Realizza lista mediante array

Dimensione puo’ essere variata dinamicamente.

12

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

13

Classe ArrayList

Corrisponde all’implementazione con array

CostruttoreArrayList ArrayList(): costruisce

lista vuota Metodi principali:

Simili a quelli di LinkedList Fornisce anche metodi per la modifica

delle dimensioni dell’array

14

Iteratori

Sono oggetti che implementano l’interfaccia Iterator

Servono a scorrere sequenzialmente oggetti di tipo Collection (quindi anche liste)

Esempio:...

LinkedList myList = new LinkedList();

....

myIterator = myList.iterator();

15

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

16

Classe Vector

E’ simile ad ArrayListI metodi sono simili a quelli di ArrayList

E’ una classe sincronizzataE’ consigliabile usarla quando più

thread che accedono alla stessa struttura dati

17

Classe Vector/2

Array:

Possono contenere tipi di dati primitivi

Dimensione fissa Pochi metodi ma

maggiore efficienza

Classe Vector Contiene Object. I tipi di

dati primitivi devono essere convertiti mediante gli opportuni wrapper.

Gestione flessibile dello spazio di memoria.

Gran numero di metodi a scapito dell'efficienza

18

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

19

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

20

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

21

Implementazione del tipo Pila

Realizzazione tramite Array

Liste: realizzazione tramite lista

concatenata

A0

A1

Ai top = i

A0 A1 Ai AN

top

Start

22

Implementazione Java con Vectorpublic 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(); }

public Object topEl(){ return

pool.lastElement(); } public Object pop(){

return pool.remove(pool.size()-1);

} public void push(Object el){ pool.addElement(el); }

}

23

Implementazione tramite LinkedListpublic 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.Stacknon realizza una vera pila (cisono operazioni in più)

25

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

26

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 pienaSe (coda == testa) coda vuota (un solo elemento presente)

27

Implementazione di coda con Array circolare first: indice del primo elemento - testa last: indice dell'ultimo - coda size: 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 28

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;

}

29

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 vuotafirst=0;

} else storage[++last] = el; }

30

Implementazione di coda con Array circolare/4

public Object dequeue(){ Object tmp = null;if(!isEmpty()) {tmp = storage[first];if (first == last) //caso unico elementolast = first = -1;

else if (first == size - 1) first = 0; else first++; }

return tmp; }

31

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

32

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

33

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

34

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

35

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

36

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

37

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

38

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[])

( [

()

]