23.10.20021 Strutture di dati F. Bombi 23 ottobre 2002.
-
Upload
vincenza-sole -
Category
Documents
-
view
218 -
download
0
Transcript of 23.10.20021 Strutture di dati F. Bombi 23 ottobre 2002.
23.10.2002 1
Strutture di datiStrutture di dati
F. Bombi
23 ottobre 2002
23.10.2002
2
Strutture di dati e tipi di dati Strutture di dati e tipi di dati astrattiastratti
Considereremo un piccolo numero di strutture di dati e di algoritmi che risolvono problemi di interesse generale che le utilizzano
Le strutture di dati saranno in genere prima descritte come tipi di dati astratti prescindendo dalla loro realizzazione mediante interfacce Java
Per ogni tipo di dato astratto verranno poi discusse una o più classi che lo realizzano (passando dall’astrazione alla concretezza)
23.10.2002
3
Tipi di dati astrattiTipi di dati astratti
Liste– Stack– Code
Alberi (solo definizioni generali)– Alberi binari– Alberi binari di ricerca
Tabelle hashDizionari
23.10.2002
4
ListeListe
Le liste possono essere considerate come contenitore di tipo dinamico
Consideriamo solo liste semplici composte da elementi atomici tutti dello stesso tipo
In modo formale una lista è definita ricorsivamente come:– Lista vuota se non contiene nessun elemento– Composta da una testa (che contiene il primo elemento)
e da un resto (la lista privata del primo elemento, lista che può essere vuota)
23.10.2002
5
Operazioni elementari sulle listeOperazioni elementari sulle liste
Qualsiasi operazione su di una lista può essere definite in funzione di 4 operazioni primitive. Indicando con ll una lista e con aa un elemento atomico abbiamo:– vuota(l): restituisce un booleano vero se la lista è vuota, falso in caso contrario
– testa(l): restituisce il valore del primo elemento della lista (che non deve essere vuota)
– resto(l): restituisce il valore della lista (che non deve essere vuota) privata del primo elemento
– crea(a, l): restituisce una lista composta dalla lista l alla quale è stato aggiunto in testa l’atomo a
È un errore cercare di applicare le primitive testo() o resto() ad una lista vuota
23.10.2002
6
Proprietà delle listeProprietà delle liste
Due liste sono uguali se:– Sono ambedue vuote– Oppure hanno testa uguale e (ricorsivamente)
resto ugualeIndicando con a un elemento atomico e con l una lista (anche vuota) è sempre vero che:– testa(crea(a,l)) è uguale ad a– resto(crea(a,l)) è la lista l
23.10.2002
7
Altre operazioni su listeAltre operazioni su listetesta - restotesta - resto
Utilizzando le quattro primitive e le definizioni date è facile definire altre operazioni sulle liste, ad esempio:
La lunghezza di una lista è definita in forma ricorsiva come:– Zero se la lista è vuota– Altrimenti la lunghezza è 1 + la lunghezza del resto
Ultimo elemento di una lista (non vuota):– Testa se il resto della lista è vuoto– Altrimenti è l’ultimo elemento del resto della lista
Crea costruisce la lista aggiungendo nuovi elementi in testa, per aggiungere elementi in coda possiamo definire accoda (che aggiunge in coda alla lista l l’atomo a) come:
– Se la lista l è vuota accoda è crea di a e l– Altrimenti accoda è crea della testa di l e di accoda di a al resto di l
23.10.2002
8
Liste con accesso limitatoListe con accesso limitato
Prima di studiare in maggior dettaglio come si possano definire e realizzare liste di tipo generale (nelle quali è possibile accedere a qualsiasi elemento, togliere e inserire in un punto qualsiasi della lista), analizziamo due tipi di liste nelle quali l’accesso è limitato agli estremi.– Stack: con accesso ad un solo estremo della lista– Coda: con inserzione da un lato ed estrazione dell’altro
23.10.2002
9
Stack (pila o catasta)Stack (pila o catasta)
Uno stack è una lista nella quale si ha accesso solo all’elemento che si trova ad un estremo della lista (detta la testa dello stack)
Le due operazioni fondamentali possibili in uno stack sono– Push: inserisci un nuovo elemento in testa allo stack– Pop: estrai l’ultimo elemento inserito nello stack (che ovviamente non
può essere vuoto) Lo stack realizza una disciplina di inserzione e di estrazione degli
elementi di tipo LIFO (Last In First Out): esce per primo l’ultimo elemento inserito nello stack
Un disciplina LIFO è richiesta per la gestione di tutte le operazioni che possono essere nidificate e nella ricorsione per cui la gestione di stack è la base della soluzione di moltissimi problemi
23.10.2002
10
L’interfaccia:L’interfaccia: Stack Stack
Uno stack conterrà dati di un certo tipo, per cui dovremmo parlare di stack di interi, di stringhe, …. In Java converrà pensare sempre a stack di oggetti sfruttando poi le capacità del linguaggio per gestire oggetti di un prefissato tipo
Uno stack può essere definito in modo astratto dalla seguente interfaccia Java:
public interface Stack{ void push (Object x);
Object pop () throws Underflow;Object testa () throws Underflow;boolean vuoto ();
}
23.10.2002
11
Realizzazione di uno stackRealizzazione di uno stack
La tecnica usata più di frequente per realizzare uno stack è quella di utilizzare un array di oggetti ed un cursore (detto stack pointer) per memorizzare la posizione della testa dello stack nell’array
Se supponiamo che lo stack pointer indichi il primo elemento libero dell’array oltre la testa, il valore dello stack pointer coincide con il numero di elementi presenti nello stack
23.10.2002
12
Inserimento di un elemento in uno Inserimento di un elemento in uno stackstack
2primo
secondo
libero
pointerprimo
secondo
terzo
2 + 1
Inserzione di“terzo”
liberolibero
libero libero
terzo
array
01
2
3
4
5
pointer01
2
3
4
5
23.10.2002
13
Estrazione di due elementi dallo Estrazione di due elementi dallo stackstack
primo
libero3 – 2 = 1
estrazione didue oggetti
escono:“terzo” e
“secondo”
3primo
secondo
terzo
pointer
libero
libero
libero
liberolibero
terzosecondo
pointer 01
2
3
4
5
01
2
3
4
5
23.10.2002
14
public class StackAr implements Stack{ private Object[] v; private int sp; private static final int MAX = 10; public StackAr (){ sp = 0; v = new Object[MAX]; } public StackAr (int max) { sp = 0; v = new Object[max]; } public void push (Object x) { v[sp++] = x; } public Object pop () throws Underflow { if (sp == 0) throw new Underflow("Pop di stack vuoto"); else return v[--sp]; } public Object testa () throws Underflow { if (sp == 0) throw new Underflow("Testa di stack vuoto"); else return v[sp-1]; } public boolean vuoto () { return sp == 0; }}
NB: la realizzazionenon gestisce l’overflowdel vettore v
Importante:Tutti i metodi hannocomplessità temporaleO(1), in altri termini leoperazioni su di uno stack richiedono untempo indipendentedalle dimensioni dellostack
23.10.2002
15
Attenzione al package Attenzione al package java.utiljava.util
Nel package java.util di Java esiste la classe Stack simile alla classe StackAr dotata dei seguenti metodi:– boolean empty ()– Object peek ()– Object pop ()– Object push (Object item)– int search (Object o)
23.10.2002
16
Programma di provaProgramma di prova Per provare la classe scriviamo un piccolo
programma che legga un testo una riga alla volta, inserisca ciascuna riga in uno stack e poi vuoti lo stack trasferendo le riga in un secondo stack. Lo stack sarà poi vuotato trasferendo le righe in uscita nello stesso ordine nel quale sono state lette
Il programma di prova verifica anche che testa() e pop() da uno stack vuoto producono un eccezione
Esercizio: un numero eccessivo di push() produce un overflow dello stack, modificare il codice in modo da gestire questa evenienza allungando l’array quando necessario (e accorciandolo…)
23.10.2002
17
public class ProvaSA{ public static void main (String[] arg) throws IOException { StackAr s1 = new StackAr(); StackAr s2 = new StackAr(); BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String str = in.readLine(); while (str != null) { s1.push(str); str = in.readLine(); } while (!s1.vuoto()) { System.out.println(s1.testa()); s2.push(s1.pop()); } while (!s2.vuoto()) System.out.println(s2.pop()); try { s2.testa(); } catch (Underflow e) { System.out.println("Underflow di testa"); } s2.pop(); }}
23.10.2002
18
Cosa occorre per la provaCosa occorre per la prova
Abbiamo bisogno di mettere nel directory di lavoro i file– Underflow.java Underflow.class– Stack.java Stack.class– StackAr.java StackAr.class– ProvaSA.java
public class Underflow extends RuntimeException{ public Underflow (String messaggio) {super(messaggio);}}
Exception
23.10.2002
19
Esercizio: Esercizio: ParentesiParentesi In un programma scritto in Java compaiono tre tipi
di parentesi– Tonde ()– Quadre []– Graffe {}
Ciascun tipo di parentesi racchiude costrutti che possono essere nidificati, ad ogni parentesi aperta deve corrispondere una parentesi chiusa dello stesso tipo, vogliamo scrivere un programma che verifichi che le parentesi siano disposte in modo corretto (per semplicità supponiamo che il testo non contenga stringhe di caratteri e commenti)
23.10.2002
20
Soluzione 1Soluzione 1
Una soluzione minimale potrebbe essere quella di gestire tre contatori, inizializzati a zero, che vengono incrementati ad ogni parentesi aperta e decrementati ad ogni chiusa. I contatori non devono mai assumere valori negativi. Al termine del testo si controlla che i contatori siano tornati a zero
Anche se un testo corretto supera il test è facile verificare che anche un testo del tipo:
[(])supererebbe il test pur essendo scorretto
23.10.2002
21
Soluzione 2Soluzione 2
Una soluzione adeguata si realizza nel modo seguente (utilizzando uno stack):– scandire il testo un carattere alla volta– quando si incontra una parentesi aperta
inserirne il valore nello stack– quando si incontra una parentesi chiusa estrarre
un elemento dallo stack e verificare che faccia il paio con la parentesi chiusa
– al temine del testo lo stack deve essere vuoto
23.10.2002
22
public class Parentesi{ public static void main (String[] arg) throws IOException { FileInputStream in = new FileInputStream(arg[0]); StackAr st = new StackAr(); int c = 0; int riga = 1; final String APRE = "([{"; final String CHIUDE = ")]}"; while ((c = in.read()) != -1) { if (c == '\n') riga++; else if (APRE.indexOf(c) != -1) st.push(new Integer(c)); else if (CHIUDE.indexOf(c) != -1) { if (st.vuoto()) System.out.println("Alla riga " + riga + " " + (char)c + " non bilanciata"); else { int x = ((Integer)st.pop()).intValue(); if (CHIUDE.indexOf(c) != APRE.indexOf(x)) System.out.println("Alla riga " + riga + " " + (char)c + " non bilancia " + (char)x); } } } Segue…
23.10.2002
23
if (!st.vuoto()) { System.out.print("Parentesi non chiuse: "); while (!st.vuoto()) System.out. print((char)((Integer)st.pop()).intValue() + " "); System.out.println(); } }}
Segue…
Il programma non gestisce correttamente stringhe e commenti.Esercizio: modificare il programma in modo da escludere dal controlloi commenti e le stringhe. Suggerimento: mantenere una variabile di stato che vale • zero: quando si legge il testo• 1 (uno): quando si entra in un commento di tipo “//” torna a zero quando la riga finisce• 2 (due): quando si entra in un commento di tipo “/*” e torna a zero quandosi incontra il token “*/”• 3 (tre): quando si entra in una stringa (si incontra il carattere “) e torna a zero quando si incontra il carattere “
23.10.2002
24
Coda (queue)Coda (queue) Un coda è una lista nelle quale si possono inserire
elementi solo alla fine ed estrarre elementi solo dalla testa (o viceversa)
Le due operazioni sono indicate come – accoda (enqueue) – togli dalla coda (dequeue) possibile solo se la coda non è
vuota La coda realizza uno disciplina di inserzione ed
estrazione di tipo FIFO (First In First Out) Code sono generalmente utilizzate per contenere
dati in attesa per essere elaborati, oppure eventi in attesa di essere serviti
23.10.2002
25
Interface CodaInterface Coda
public interface Coda
{void accoda (Object x);
Object togli () throws Underflow;
Object testa () throws Underflow;
boolean vuota ();
}
23.10.2002
26
Realizzazione di una codaRealizzazione di una coda
Come per uno stack la soluzione più semplice ed efficiente (overflow a parte) per realizzare una coda è quella di utilizzare un vettore e alcune variabili ausiliare per tenere conto della posizione occupata dalla testa e dalla coda della coda. In questo modo si evita di dover spostare gli elementi presenti nella coda all’estrazione
23.10.2002
27
Coda in un vettoreCoda in un vettore
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
MAX = 15
A B C D
testa
coda
Convenzioni:• testa e coda inizializzati a 0• coda indica la prima cella libera• testa indica il primo elemento in coda
Si potrebbe dire ancheche testa==coda indicache la coda è vuota mac’è un problema …
23.10.2002
28
Vettore chiuso ad anelloVettore chiuso ad anello
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Per chiudere il vettore ad anello bastapensare che l’elemento di indice 0segua l’elemento di indice n-1
Per distinguere la coda vuotadall’overflow è necessariousare un variabile ausiliaria(o rinunciare ad una cella)
23.10.2002
29
public class CodaAr implements Coda{ private Object[] v; private int testa; private int coda; private int taglia; private static final int MAX = 10; public CodaAr () { testa = coda = taglia = 0; v = new Object[MAX]; } public CodaAr (int max) { testa = coda = taglia = 0; v = new Object[max]; } public void accoda (Object x) { if (taglia == v.length) throw new Overflow("Accoda in coda piena"); v[coda++] = x; if (coda == v.length) coda = 0; taglia++; }
segue…
Nota: a differenza diquanto fatto per glistack in questo casoè necessario gestireesplicitamente l’overflow
23.10.2002
30
public Object togli () throws Underflow { if (taglia == 0) throw new Underflow("Togli da coda vuota"); Object tmp = v[testa]; testa = (++testa)%v.length; taglia--; return tmp; } public Object testa () throws Underflow { if (taglia == 0) throw new Underflow("Testa da coda vuota"); return v[testa]; } public boolean vuota () { return taglia == 0; }}
segue…
NB: tutte le primitive richiedonoun tempo costante indipendentedalla lunghezza della coda
Esercizio: modificare il codice in modo che non si verifichi mail’overflow, aumentano in modeautomatico la dimensione dell’array.Domanda: cosa succede del tempo?
23.10.2002
31
ListeListe
Stack e code sono liste nelle quali l’accesso è limitato ad una o ambedue le estremità. In una lista in generale vogliamo poter accedere a qualsiasi elemento in funzione della sua posizione nella lista, nota la posizione di un elemento della lista vogliamo poter passare alla posizione dell’elemento successivo ( o dell’elemento precedente), vogliamo infine poter togliere e inserire un elemento in una posizione qualsiasi
23.10.2002
32
Lista in un vettoreLista in un vettore
È certamente possibile rappresentare una lista mediante un vettore di oggetti come abbiamo fatto per stack e code
Una prima difficoltà nasce per rappresentare la posizioneposizione nella lista. Possiamo usare un interointero ma in questo modo dobbiamo esporre all’utente i dettagli realizzativi della nostra classe e questo viola i paradigmi della programmazione ad oggetti
La difficoltà principale deriva però dal fatto le operazioni di inserzione o eliminazione richiedono un tempo proporzionale alla lunghezzatempo proporzionale alla lunghezza della lista
23.10.2002
33
Lista in un vettoreLista in un vettoreeliminazione di un oggettoeliminazione di un oggetto
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
primo ultimo
Per rappresentare una lista in un vettore possiamo utilizzare due cursori che indicano l’inizio e lafine della parte in uso per la lista
23.10.2002
34
Inserzione di un oggettoInserzione di un oggetto
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
primo ultimo
X
X
23.10.2002
35
Quanto tempo occorre?Quanto tempo occorre?
Come al solito siamo interessati a stimare quanto tempo occorre per inserire o togliere un elemento da una lista di nn elementi rappresentata su di un vettore. Il tempo è proporzionale al numero di mosse
Risposta:– Se siamo ottimisti: un tempo costante proporzionale a 11– Se siamo pessimisti: un tempo proporzionale a nn– Se siamo degli statistici: un tempo proporzionale alla
media di tutti i casi possibiliT(n)=1/nT(n)=1/ni=n(n+1)/(2n)=(n+1)/2 i=n(n+1)/(2n)=(n+1)/2 n/2 n/2
23.10.2002
36
Uso di una Uso di una catenacatena L’uso di un vettore quale supporto di una struttura di dati
dinamica soffre del possibile overflow condizione alla quale si può porre rimedio solo attraverso l’allocazione di un nuovo vettore e la copiatura dei dati presenti nella struttura e rende onerose le operazioni di inserzione e di eliminazione di un elemento in posizione qualsiasi
Questi limiti possono essere superati utilizzando, quale supporto, una struttura dinamica detta linked listlinked list (letteralmente lista concatenatalista concatenata) che noi però chiameremo catenacatena per non generare confusione con il concetto di lista che è un’astrazione realizzabile con una catena ma anche con un array
23.10.2002
37
Come realizzare una catenaCome realizzare una catena Una catena può essere realizzata utilizzando
oggetti composti ciascuno da due campi, il primo sarà utilizzato per contenere il riferimento all’elemento e il secondo sarà un riferimento alla prossima cella della catenaclass Cella{ Object atomo; Cella prossima; Cella (Object x, Cella p) { atomo = x; prossima = p; } Cella () { atomo = prossima = null; }}
Possiamo assumere che l’ultima cella contenga un riferimento nullnull per indicare che non esiste una cella successiva
23.10.2002
38
Lista in una catenaLista in una catena
a p
Una cella di una catena
Una lista: (A, B, C, D)
a p a p a p a p
null
A B C D
INIZIO FINE
23.10.2002
39
Realizzazione di uno stackRealizzazione di uno stackpublic class StackLc implements Stack{ private class Cella { Object atomo; Cella prossima; Cella (Object x, Cella p) { atomo = x; prossima = p; } } private Cella testa; public void push (Object x) {testa = new Cella(x, testa);} public Object pop () throws Underflow { if (testa == null) throw new Underflow("Pop di stack vuoto"); else { Object tmp = testa.atomo; testa = testa.prossima; return tmp; } }
Non occorre il costruttorequello di dafault va bene
23.10.2002
40
public Object testa () throws Underflow { if (testa == null) throw new Underflow("Testa di stack vuoto"); else return testa.atomo; } public boolean vuoto () { return testa == null; }}
segue..
ConvenzioniConvenzioni:• lo stack vuoto è rappresentato da un riferimento a Cella nullCella null• la catena di celle va dalla testa verso l’elemento più vecchio• l’ultima cella è completata con un puntatore null
La cella con cui viene costruita la catena è privata, è definita all’interno della classe StackLc per cui l’utente della classe non conosce i dettagli realizzativi
23.10.2002
41
Stack vuoto
public void push (Object x) { testa = new Cella(x, testa); }
null
a p
A
null
testa
a p
B
testa
a p
C
testa
public Object pop () { Object tmp = testa.atomo; testa = testa.prossima; return tmp; }
tmp
testa
23.10.2002
42
Operazioni in posizione qualsiasiOperazioni in posizione qualsiasi
Inserire e togliere in testa ad una catena è facile, la flessibilità della struttura di dati si vede però quando si vogliano eseguire operazioni di inserzione o eliminazione di elementi in un punto qualsiasi della lista
23.10.2002
43
Inserzione di un elementoInserzione di un elementoUna lista: (A, B, C, D)
a p a p a p a p
null
A B C D
INIZIO FINE
Nuova lista: (A, B, X, C, D)
p
a p
X
tmp
tmp = new Cella(X, p.prossima);
p.prossima = tmp;
Per inserire unelemento è necessarioconoscere la posizionedell’elemento precedente
23.10.2002
44
Eliminazione di un elementoEliminazione di un elementoUna lista: (A, B, C, D) Nuova lista: (A, B, D)
a p a p a p a p
null
A B C D
INIZIO FINEp
p.prossima = p.prossima.prossima; a p
C
Per eliminare unelemento è necessarioconoscere la posizionedell’elemento precedente
23.10.2002
45
Liste e iteratoriListe e iteratori L’utilizzo di liste dotate delle sole primitive crea, testa,
resto sarebbe inaccettabile dal punto di vista dell’efficienza per cui di solito si definiscono listeliste dotate di un repertorio di primitive molto più ricco
Sino ad ora abbiamo lasciato nel vago come rappresentare la posizioneposizione di un elemento di una lista
Per rispettare i principi della programmazione ad oggetti una lista viene definita in un pacchetto mediante classi amiche una per costruire la lista l’altra (detta iteratore) per muoversi nella lista senza dover conoscere i dettagli realizzativi e per compiere operazioni ad una determinata posizioneposizione
Un iteratoreiteratore è un’astrazioneastrazione del concetto di posizione che nasconde i dettagli della sua realizzazione all’utente
23.10.2002
46
public class Lista{ public Lista () { … }
public int size () { … }
public void addFirst (Object x) { … }
public void addLast (Object x) { … }
public Object getFirst () { … }
public Object getLast () { … }
public Object removeFirst () { … }
public Object[] toArray () { … }
public String toString () { … }}
23.10.2002
47
public class Iteratore{ public Iteratore (Lista x) { … }
public Iteratore (Iteratore x) { … }
public void add (Object x) { … }
public boolean hasNext () { … }
public void next () { … }
public Object get () { … }
public void remove () { … }
public void set (Object x) { …}}
23.10.2002
48
Realizzazione in un vettoreRealizzazione in un vettore Per realizzare una lista possiamo utilizzare come
contenitore degli elementi un vettore Potremmo pensare di riempire solo in parte il
vettore (come abbiamo fatto per stack e code) Se pensiamo che le operazioni principali siano
quelle di inserzione o eliminazione di un elemento qualsiasi, dato che questo richiede di spostare, in media, la metà degli elementi della lista si è ritenuto accettabile copiare ogni volta l’intero array
Si è quindi fatta la convenzione di utilizzare sempre un vettore di dimensioni pari alla taglia della lista
23.10.2002
49
package vettore;import java.util.NoSuchElementException;public class Lista{ Object[] atomo; public Lista () { atomo = new Object[0]; } public int size () { return atomo.length; } public void addFirst (Object x) { Object[] tmp = new Object[atomo.length+1]; tmp[0] = x; for (int i = 0; i < atomo.length; i++) tmp[i+1] = atomo[i]; atomo = tmp; } ….}
package vettore;import java.util.NoSuchElementException;public class Iteratore{ private int posizione; private Lista l; public Iteratore (Lista x) { l = x; posizione = 0; } public boolean hasNext () { if (posizione == l.atomo.length) return false; else return true; } public void next () { if (!hasNext()) throw new NoSuchElementException ("non c'e'"); posizione++; } … }
segue
La lista è conservatain un array di dimensioniesatte. L’array vienecopiato ad ogni operazionein modo da poter aggiustarele dimensioni
L’iteratore conoscela lista e conservala posizione correntecon un cursore.
Lista e itaratore devonocondividere un campo (ilvettore) che quindi nonpuò essere né pubbliconé privato (default =amico nell’ambito del pacchetto)
23.10.2002
50
Elementi ripetutiElementi ripetuti
Data una lista di oggetti, vogliamo eliminare dalla lista eventuali elementi ripetuti in modo che, per ogni valore, ci sia al più un elemento presente
Usiamo il seguente algoritmo
sia p la posizione del primo elemento della listamentre p non è alla fine della lista
sia q la posizione dell’elemento che segue pmentre q non è alla fine della lista
se l’elemento p è uguale all’elemento q eliminare q
altrimenti avanzare q al prossimo elementoavanzare p al prossimo elemento
23.10.2002
51
import vettore.*;import java.io.*;
public class EliminaDoppi{ public static void main (String[] arg) throws IOException { BufferedReader in = new BufferedReader(new FileReader(arg[0])); String str; Lista l = new Lista(); Iteratore p = new Iteratore(l); while ((str = in.readLine()) != null) l.addLast(str); System.out.println("Dati di ingresso, taglia " + l.size()); while (p.hasNext()) { System.out.println(p.get()); p.next(); } System.out.println("Elimina doppi");
Lettura dei dati da un file eStampa dei dati per verifica
segue
23.10.2002
52
p = new Iteratore(l); while (p.hasNext()) { Comparable tmp = (Comparable)p.get(); p.next(); Iteratore q = new Iteratore(p); while (q.hasNext()) { if (tmp.compareTo(q.get()) == 0) q.remove(); else q.next(); } } for (p = new Iteratore(l); p.hasNext(); p.next()) System.out.println(p.get()); }}
L’algoritmo in pseudocodice:
sia p la posizione del primo elemento della listamentre p non è alla fine della lista
sia q la posizione dell’elemento che segue pmentre q non è alla fine della lista se l’elemento p = q eliminare q
altrimenti avanzare q al prossimo elementoavanzare p al prossimo elemento
Domanda: quale è lacomplessità temporaledell’algoritmo?È possibile fare meglio?
23.10.2002
53
Come costruire un Come costruire un packagepackage
• Per costruire un package cioè un insieme di classi correlate che forniscano un determinato servizio utilizziamo il seguente procedimento (semplificato) che assume che il package sia un sottopaccheto di quello di dafault (senza nome) composto dalle classi inserite della cartella (directory) di lavoro
• Nella cartella di lavoro creiamo una cartella con il nome del pacchetto, nel nostro caso vettorevettore oppure catenacatena
• Inseriamo nella cartella i file che contengono i componenti del pacchetto, nel nostro caso• Lista.javaLista.java• Iteratore.javaIteratore.java
• Inseriamo nella cartella di lavoro la classe o le classi che importano il pacchetto, nel nostro caso• EliminaDoppi.java EliminaDoppi.java
23.10.2002
54
Il Il packagepackage listalista
Directory di lavoro
vettorevettore EliminaDoppi.javaEliminaDoppi.java
Lista.javaLista.java Itearatore.javaItearatore.java
I file componenti il pacchettovettore vettore devono contenere come prima riga la dichiarazione
package vettore;package vettore;I file che utilizzano il pacchettodevono importarlo con
import vettore.*;import vettore.*;
Se vogliamo semplificare lecose rinunciando all’incapsulamentofornito dal pacchetto basta inseriretutti i file nel directory di lavoro edeliminare le dichiarazioni package lista;package lista;e l’istruzione import lista.*;import lista.*;
23.10.2002
55
ListaLista e e IteratoreIteratore in una catena in una catena
La realizzazione delle classi Lista e Iteratore mediante un array sono perfettamente funzionanti secondo le specifiche ma alcuni metodi hanno una complessità temporale O(n)O(n)
Utilizzando una catenacatena di celle è possibile realizzare le due classi in modo che tutti i metodi abbiano complessità O(1)O(1)
Abbiamo visto che per inserire o togliere un elemento da una catena è necessario disporre di un riferimento alla cella che precede l’elemento da eliminare o da inserire. Questo imporrebbe di trattare in modo diverso l’inserimento o la cancellazione del primo elemento
Per rendere più lineare la realizzazione conviene rappresentare una lista vuota mediante una cella vuota invece che un riferimento nullnull come fatto per un array
23.10.2002
56
Lista in una catenaLista in una catena
a p a p a p
nullnull
A B D
a p
nullnull
Testa
a p
nullnull
Testa
nullnull
Rappresentazione di una lista vuota
La posizione di un elemento è individuatada un riferimento alla cella che precedel’elemento. Un riferimento all’ultima cellasi riferisce alla finefine della lista cioè allaposizione che segue l’ultimo elementopresente nella lista
Fine
Fine
23.10.2002
57
package catena;import java.util.NoSuchElementException;public class Lista{ Cella testa; Cella fine; int taglia; public Lista () { testa = fine = new Cella(null, null); taglia = 0; }
public int size () { return taglia; }
La classe lista comprende tre campi:• testa• fine• taglia
(due riferimenti a Cella e un int)che devono essere visibili anche allaclasse IteraCatena
package catena;class Cella{ Cella prossima; Object atomo; Cella (Object x, Cella p) { atomo = x; prossima = p; }}
La classe Cella.javaCella.java ha visibilità di classe comepure i suoi campi in modoche questi sono visibili neimetodi del pacchetto “catena”
segue
23.10.2002
58
public void addFirst (Object x) { taglia++; testa.prossima = new Cella(x, testa.prossima); if (testa == fine) { fine = testa.prossima; } }
public void addLast (Object x) { taglia++; fine.prossima = new Cella(x, fine.prossima); fine = fine.prossima; }
public Object getFirst () { if (taglia == 0) throw new NoSuchElementException ("Lista vuota"); return testa.prossima.atomo; }
public Object getLast () { if (taglia == 0) throw new NoSuchElementException ("Lista vuota"); return fine.atomo; }
segue
segue
23.10.2002
59
public Object removeFirst () { if (taglia == 0) throw new NoSuchElementException ("Lista vuota"); taglia--; Object tmp = testa.prossima.atomo; testa.prossima = testa.prossima.prossima; if (testa.prossima == null) fine = testa; return tmp; }
public Object[] toArray () { Object[] tmp = new Object[taglia]; Cella p = testa.prossima; for (int i = 0; i < taglia; i++) { tmp[i] = p.atomo; p = p.prossima; } return tmp; }
segue
segue
23.10.2002
60
public String toString () { String tmp = ""; if (taglia == 0) return tmp; tmp += testa.prossima.atomo; Cella p = testa.prossima.prossima; for (int i = 1; i < taglia; i++) { tmp += "," + p.atomo; p = p.prossima; } return tmp; }}
segue
23.10.2002
61
package catena;import java.util.NoSuchElementException;
public class Iteratore{ Cella posizione; Lista l;
public Iteratore (Lista x) { l = x; posizione = l.testa; }
public Iteratore (Iteratore x) { l = x.l; posizione = x.posizione; }
public void add (Object x) { l.taglia++; posizione.prossima = new Cella(x, posizione.prossima); if (l.fine == posizione) l.fine = posizione.prossima; }
segue
23.10.2002
62
public boolean hasNext () { if (posizione == l.fine) return false; else return true; }
public void next () { if (!hasNext()) throw new NoSuchElementException ("L'elemento non c'e'"); posizione = posizione.prossima; }
public Object get () { if (!hasNext()) throw new NoSuchElementException ("L'elemento non c'e'"); return posizione.prossima.atomo; }
segue
segue
23.10.2002
63
public void remove () { if (!hasNext()) throw new NoSuchElementException ("Prima di rimuovere devi guardare"); if (posizione.prossima == l.fine) { l.fine = posizione; posizione.prossima = null; } else posizione.prossima = posizione.prossima.prossima; l.taglia--; }
public void set (Object x) { if (!hasNext()) throw new NoSuchElementException ("Prima di rimuovere devi guardare"); posizione.prossima.atomo = x; }}
I metodi che tolgono o inseriscono elemento devono gestire oltre ai riferimenti,per mantenere l’integrità della catena, anche il campotagliataglia (che memorizza il numero di elementi presenti) e ilriferimento alla finefine della catena quando si inserisce appunto allafine o quando si elimina l’ultima cella
segue
23.10.2002
64
public Object togli () throws NonTrovato { if (posizione.prossima == null) throw new NonTrovato("togli non presente"); Object tmp = posizione.prossima.atomo; if (posizione.prossima == l.fine) l.fine = posizione; posizione.prossima = posizione.prossima.prossima; l.taglia--; return tmp; }
public void inserisci (Object x) { posizione.prossima = new Cella(x, posizione.prossima); l.taglia++; if (posizione == l.fine) l.fine = posizione.prossima; }}
23.10.2002
65
Provare Provare CatenaCatena
Per provare la nuova realizzazione di ListaLista e Iteratore Iteratore possiamo utilizzare di nuovo la classe EliminaDoppiEliminaDoppi. Per fare questo è sufficiente modificare l’importazione del pacchetto da:
import vettore.*;import vettore.*;
a:import catena.*;import catena.*;