Si consideri la classe astratta che specifica IL tipo di dato astratto Tabella



Scaricare 28.84 Kb.
17.11.2017
Dimensione del file28.84 Kb.

Programmazione II

3/11/2009


Si consideri la seguente classe che specifica il tipo di dato astratto “Albero binario etichettato”. Un albero binario è un albero in cui ogni nodo è etichettato con una stringa, ed ha esattamente due sottoalberi (sinistro e destro). Definizione ricorsiva:

--caso base: l’albero vuoto

--caso ricorsivo: un nodo con etichetta “n”, e col riferimento al sottoalbero sinistro sx e destro dx.


public class Balbero {

// OVERVIEW: Un Balbero è un albero binario i cui nodi

// sono etichettati con Stringhe. E’ non modificabile.
public Balbero(){//EFFECTS: inizializza this all’albero vuoto}
public boolean IsIn(String d) throws NullPointerException{

// EFFECTS: se d e’ null solleva NullPointerException,

//se d e’ l’etichetta di un nodo di this restituisce true,

//altrimenti restituisce false}




public Balbero nuovoalbero(String s, Balbero b)

throws NullPointerException{

// EFFECTS: se s o b e’ null solleva NullPointerException,

// altrimenti restituisce un nuovo Balbero, la cui radice ha

// etichetta s, ed i cui sottoalberi sinistro e destro sono

//this e b,rispettivamente}


public Iterator elements(){

// EFFECTS: restituisce un generatore che produce le etichette //dei nodi di this (una ed una sola volta), seguendo un ordine //di visita dei nodi di tipo posticipato (prima il sottoalbero //sx, poi il sottoalbero dx e poi la radice).

}



  1. Si fornisca la rappresentazione con relativi funzione di astrazione e invariante di rappresentazione


private Balbero sx;

private Balbero dx;

private String label;

private boolean vuota;
Invariante di rappresentazione:

I(c) = c.vuota oppure


(c.sx!= null e c.dx != null e

I(c.sx) e I(c.dx) e c.label !=null)

Funzione di astrazione:

(c) = l’albero vuoto se c.vuota

(c) = e’ l’albero che ha c.label come etichetta



della radice, e (c.sx) e (c.dx) come

alberi sinistro e destro



  1. Si implementino il costruttore ed i metodi


public class Balbero {

private Balbero sx;

private Balbero dx;

private String label;

private boolean vuota;

public Balbero(){

//EFFECTS: inizializza this all’albero vuoto

vuota=true;

}
public boolean IsIn(String d)

throws NullPointerException{

//EFFECTS: se d e’ null solleva NullPointerException,

//se d e’ l’etichetta di un nodo di this restituisce true, //altrimenti restituisce false
if (d==null) throw

new NullPointerException(“IsIn”);

if (vuota) return false;

if (d.equals(label)) return true;

boolean result= sx.IsIn(d);

if (! result) return dx.IsIn(d);

return true;

}
public Balbero nuovoalbero(String s, Balbero b)

throws NullPointerException{

//EFFECTS:se s o b e’ null solleva

//NullPointerException, altrimenti restituisce un

// nuovo Balbero, la cui radice ha etichetta s, ed

//i cui sottoalberi sinistro e destro sono

//this e b,rispettivamente



if (s==null || b==null) throw

new NullPointerException(“nuovoalbero”);

Balbero nuovo=new Balbero();

nuovo.label=s;

nuovo.sx=this; nuovo.dx=b; return nuovo;}
public Iterator elements(){

//EFFECTS: restituisce un generatore che produce le

//etichette dei nodi di this (una ed una sola volta), seguendo

// un ordine di visita dei nodi di tipo posticipato (prima il //sottoalbero sx, poi il sottoalbero dx e poi la radice).

return new Bgen(this, count());

}
private static class BGen implements Iterator {

private int cnt; // numero di elementi ancora da generare

private BGen figlio; // sottogeneratore corrente

private Balbero me;
public BGen (Balbero o, int n) {

// REQUIRES: o != null

cnt = n;

if (cnt > 0) { me = o;

figlio = new BGen(o.sx, o.sx.count()); }
public boolean hasNext () {

return cnt > 0; }

public Object next () throws NoSuchElementException {

if (cnt == 0) throw new

NoSuchElementException(“OrderedIntList.smallToBig”) ;

cnt --;

try { return figlio.next(); }

catch (NoSuchElementException e) {

if (cnt==0) return me.label;

figlio = new BGen(me.dx, dx.count());

return figlio.next();}

}

}


  1. Si discuta la validita’ dell’invariante di rappresentazione per quanto riguarda il costruttore ed il metodo nuovoalbero

Il costruttore costruisce un oggetto c che soddisfa l’invariante dato che vale c.vuota.


Nel caso di nuovoalbero assumiamo che this e b soddisfino l’invariante e mostriamo che l’oggetto restituito soddisfa l’invariante.

Notiamo che il Balbero associato a nuovo soddisfa l’invariante al momento dell’inizializzazione, perche’ il costruttore soddisfa l’invariante. Gli assegnamenti successive preservano l’invariante dato che s,b, this sono diversi da null. Inoltre nuovo.sx e nuovo.dx soddisfano l’invariante per ipotesi induttiva.


4) Si implementi la seguente classe


public class UsaBalbero {

public static String minimo(Balbero a)

throws NullPointerException,EmptyException{

//EFFECTS: se a e’ null solleva NullPointerException,

//se a e’ vuoto solleva EmptyException,

// altrimenti restituisce la minima stringa che compare come



// etichetta di a (in base all’ordinamento lessicografico)}
if (a==null) throw new NullPointerException(“Usaalbero”);

Iterator g=a.elements();

String min;

try{min= (String) g.next();}

catch (NoSuchElementException e)

{ throw new EmptyException(“Usaalbero”);}

while (g.hasnext)

{String prox= (String) g.next();

int i=min.compareTo(prox);

if (i>0) {min=prox;}

}

return min;

}



©astratto.info 2017
invia messaggio

    Pagina principale