Liste Concatenate
11 Aprile 2008
•E’ una delle strutture dati fondamentali in tutti i
linguaggi di programmazione di alto livello
•Una Lista Concatenata serve per rappresentare
sequenze di elementi (di dimensione variabile)
[ 19,
57,
3,
35, 11,
91,
5 ]
[]
•Tipo di dato basato su una definizione RICORSIVA
Definizione Ricorsiva
• Una lista concatenata e’
• vuota
• o e’ un nodo che contiene un valore e un
riferimento ad una lista (il resto della lista)
Esempio
val next
Lista non vuota:
Primo elemento
11
64
Lista vuota
IntList
• Vediamo per esempio una possibile
specifica nel caso di elementi di tipo Integer
• Definiamo un tipo di dato astratto
modificabile
• Operazioni per
--costruire la lista vuota
--costruire un nodo
--aggiungere un elemento all’inizio
--metodi per scorrere i nodi della lista
Specifica di IntList
public class IntList {
// OVERVIEW: un IntList è una lista modificabile
// di Integer.
// Elemento tipico [x1,...,xn]
public IntList () {
// EFFECTS: inizializza this alla lista vuota }
public IntList (Integer x) throws
NullPointerException {
// EFFECTS: se x e’ null solleva
//NullPointerException, inizializza this alla
//lista che contiene esattamente x }
Specifica di IntList
public
void addEl (Integer x)
throws NullPointerException
{//MODIFIES:this
// EFFECTS: se x e’ null solleva
//NullPointerException, altrimenti aggiunge x
//all’inizio di this }
public Integer first () throws EmptyException{
// EFFECTS: se this è vuoto solleva
//EmptyException, altrimenti
// ritorna il primo elemento di this}
public IntList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva
//EmptyException, altrimenti
// ritorna la lista ottenuta da this togliendo
//il primo elemento}
Specifica di IntList
public int size () {
// EFFECTS: ritorna il numero di elementi di
//this}
public String toString (){
//EFFECTS: restituisce una stringa che descrive
//la sequenza di elementi di this }
}
}
Esempio sull’uso delle Liste
IntList p = new IntList ();
\\[]
p.addEl(new Integer(3));
\\[3]
p.addEl(new Integer(4));
\\[4,3]
p.addEl(new Integer(7));
\\[7,4,3]
•Il metodo toString() permette al solito di
osservare lo stato interno
Esempio sull’uso delle Liste
IntList p = new IntList (new
Integer(3));
\\[3]
p.addEl(new Integer(4));
\\[4,3]
p.addEl(new Integer(7));
\\[7,4,3]
•Il secondo costruttore che costruisce la lista di un
elemento non e’ necessario
Nota
•Il metodo rest restituisce il resto della lista
(la lista ottenuta rimuovendo il primo elemento)
•Il metodo first restituisce il primo elemento
IntList p = new IntList (new Integer(3));
p.addEl(new Integer(4));
p.addEl(new Integer(7));
• first=====> 7
•rest ====> restituisce la lista [4,3]
Scorrere la lista
•Usando first e rest si puo’ scorrere la lista (metodo di ricerca)
•Realizzato in un modulo separato in base alla specifica di
IntList
public static boolean cerca (Intlist l,Integer x)
throws NullPointerException{
// EFFECTS: se l o x sono null solleva
//NullPointerException,
//altrimenti restituisce true se x occorre nella
//lista l, false se non occorre}
Utilizzando solo la specifica
public static boolean cerca (Intlist l,Integer x)
throws NullPointerException{
if (x==null|| l==null) throw new
NullPointerException(“Lista.cerca”);
//caso base
if (l.size()==0) {return false;}
//caso ricorsivo
{Integer el=l.first();
if (el.equals(x)) {return true;}
return cerca(l.rest(),x);}
}
Esempio 1
•
•
•
•
•
l=[1,6,3] x=6
Confronta x con l.first()=1
Chiama la procedura con l’=l.rest()= [6,3] ed x=6
Confronta x con l’.first()=6
La chiamata ricorsiva restituisce true (il metodo
chiamante restituisce true)
Esempio 2
•
•
•
•
•
•
•
•
l=[1,6,3] x=4
Confronta x con l.first()=1
Chiama la procedura con l’=l.rest()= [6,3] ed x=4
Confronta x con l’.first()=6
Chiama la procedura con l’’=l’.rest()= [3] ed x=4
Confronta x con l’’.first()=3
Chiama la procedura con l’’’=l’’.rest()= [] ed x=4
Caso Base: lista vuota termina restituendo false
(tutti i metodi annidati restituiscono false)
Come si implementa?
• Ci sono vari modi (a LSD altre soluzioni)
• Dobbiamo scegliere delle variabili d’istanza che
permettano di rappresentare sia la lista vuota che
quella non vuota
• Deve essere possibile distinguere i due casi in
modo chiaro
private boolean vuota;
private Integer val;
private IntList next;
//indica se e’ vuota
//contiene il valore
//puntatore al resto
Rappresentazione Lista
val
next
vuota
Lista vuota:
Lista non vuota:
any
any
154
24
any
any
true
false
false
true
Nota
• Il flag vuota serve per indicare la lista vuota
• Nell’implementazione che facciamo quando
vuota e’ falso garantiamo che il puntatore al
resto della lista non sia null
• Semplifica l’implementazione dei metodi
ricorsivi (non sono necessari test per vedere
che il puntatore sia definito)
Implementazione
public class IntList {
// OVERVIEW: un IntList è una lista non modifica
// Integers.Elemento tipico [x1,...,xn]
private boolean vuota;
private Integer val;
private IntList next;
Costruttori
public IntList () {
// EFFECTS: inizializza this alla lista vuota
vuota=true;}
public IntList (Integer x) {
// EFFECTS: inizializza this alla lista che
contiene esattamente x
if (x==null) throw new
NullPointerException(“IntList.IntList”);
vuota=false; val=x; next=new IntList();}
Notate che nel secondo costruttore next viene inizializzato alla lista
vuota (sta sempre alla fine, definizione ricorsiva) !
Costruttori
val
next
vuota
Lista vuota:
Lista con un elemento:
any
any
24
any
any
true
false
true
Inserimento
public void addEl (Integer x) {
//MODIFIES:this
// EFFECTS: aggiunge x all’inizio di this
if (x==null) throw new
NullPointerException(“IntList.IntList”);
{if (vuota) {val=x;next=new IntList();vuota=false;}
else
{IntList n = new IntList(val);
n.next = this.next; //copia di this
this.val =x;
this.vuota=false;
this.next=n;}
}}
Mettiamo l’elemento in testa,
creando un nuovo nodo che contiene x ed ha come resto della lista this
First e rest
public Integer first () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException
//altrimenti ritorna il primo elemento di this
if (vuota) throw new
EmptyException(“IntList.first”);
return val;}
public IntList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva EmptyException,
//altrimenti ritorna la lista ottenuta da this
//togliendo il primo elemento
if (vuota) throw new
EmptyException(“IntList.first”);
return next;}
Size
public int size () {
// EFFECTS: ritorna il numero di elementi di this
if (vuota) return 0;
return 1 + next.size();
}
Metodo
Ricorsivo!!!!!!!!!
ToString()
public String toString (){
String s=“”;
if (vuota) {return s;}
return val.intValue() + next.toString();
}
Metodo Ricorsivo !
Esercizio I
• Definire una variante StringList
• Contiene Stringhe
• Ha un metodo per aggiungere all’inizio ed alla
fine,e per rimuovere
• Ha un metodo per verificare l’uguaglianza di due
liste
Specifica di StringList
public class StringList {
// OVERVIEW: un StringList è una lista
//modificabile di stringhe.
// Elemento tipico [x1,...,xn]
public StringList () {
// EFFECTS: inizializza this alla lista vuota }
public StringList (String x) {
// EFFECTS: se x e’ null solleva
//NullPointerException, altrimenti inizializza
//this alla lista che contiene esattamente x }
Specifica di StringList
public void FaddEl (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva
//NullPointerexception, altrimenti aggiunge x
//all’inizio di this }
public void LaddEl (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva
//NullPointerexception, altrimenti aggiunge x
//alla fine di this }
public void remove (String x) {
//MODIFIES:this
// EFFECTS: se x e’ null solleva
//NullPointerexception, altrimenti rimuove da
//this una occorrenza di x }
Specifica di StringList
public String first () throws EmptyException{
// EFFECTS: se this è vuoto solleva
//EmptyException, altrimenti
// ritorna il primo elemento di this}
public StringList rest () throws EmptyException{
// EFFECTS: se this è vuoto solleva
//EmptyException, altrimenti
// ritorna la lista ottenuta da this togliendo
//il primo elemento}
Specifica di StringList
public int size () {
// EFFECTS: ritorna il numero di elementi di
//this}
public boolean equals(Object x) {
// EFFECTS: se x e’ null solleva
//NullpointerException, se this ed x sono uguali
//(sono liste che rappresentano la stessa
//sequenza di elementi) restituisce
//true, altrimenti false}
public String toString (){// EFFECTS: standard }
}
}
Esercizio II
• Implementare la seguente classe
• Classe che definisce alcune procedure
statiche per manipolare liste di stringhe
• Da realizzare in modulo separato (non
vedono la rappresentazione della lista)
• metodi ricorsivi
public class IntListProc {
// OVERVIEW: fornisce metodi statici per manipolare
//liste di stringhe
public static String min(StringList l) throws
EmptyException
{// REQUIRES: l non e’ null
//EFFECTS: se l e’ vuota solleva EmptyException,
altrimenti restituisce il minimo elemento di l}
public
static StringList
append (StringList l1, StringList l2)
{// REQUIRES: l1 ed l2 non null
//EFFECTS: restituisce una lista che e’ la
//concatenazione di l1 ed l2. Ex: l1=[8,0], l2=[9]
===> [8,0,9]
}
}
ATTENZIONE: le liste passate per parametro non devono
essere modificate
MAIN
• Test della definizione di StringList (usare
toString())
• Test dei metodi statici
Metodi Statici
• Devono operare su StringList tramite
l’interfaccia pubblica
• Non hanno visibilita’ delle variabili
d’istanza val e next