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

Lista non vuota:

val next

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 baseif (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; //indica se e’ vuotaprivate Integer val; //contiene il valoreprivate IntList next; //puntatore al resto

Rappresentazione Lista

val

next

vuota

Lista vuota:

any

any

true

Lista non vuota:

any

any

true

154

false

24

false

Nota

• Il flag vuota serve per indicare la lista vuota• Nell’implementazione che facciamo quandovuota 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 modificabile di// Integers.Elemento tipico [x1,...,xn]

private boolean vuota;private Integer val;private IntList next;

Costruttoripublic 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) !

Costruttorival

next

vuota

Lista vuota:

any

any

true

Lista con un elemento:

any

any

true

24

false

Inserimentopublic 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 restpublic 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) throwsEmptyException {// 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