Strutture Dati - Prova del 19 Aprile

Ecco le mie soluzioni ai due esercizi della prova di Strutture Dati del 19 Aprile con il prof. Salvatore La Torre.


E Il primo esercizio consisteva nell'implementare il metodo int maxValFoglie(BinaryTree<Integer> t) che restituisce il massimo tra i valori contenuti nelle foglie dell'albero t:

public static int maxValFoglie(BinaryTree<Integer> T)

{

int max = 0;

Iterable<Position<Integer>> posizioni = T.positions();

Iterator<Position<Integer>> it = posizioni.iterator();

while(it.hasNext())

{

Position<Integer> curr = it.next();

if (T.isExternal(curr))

max = Math.max(max, curr.element());

}

return max;

}

//versione ricorsiva

public static int maxValFoglie(BinaryTree<Integer> T)

{

return maxValFoglie(T, T.root(), 0);

}

public static int maxValFoglie(BinaryTree<Integer> T, Position<Integer> p, int max)

{

if(T.isExternal(p))

max = Math.max(max, p.element());

else

{

if (T.hasLeft(p))

max = maxValFoglie(T, T.left(p), max);

if (T.hasRight(p))

max = maxValFoglie(T, T.right(p), max);

}

return max;

}

mentre il secondo consisteva nell'implementare il metodo void forzaInorder(BinaryTree<E> t, PositionList<E> l) che a) testa se l'albero t e la lista l hanno lo stesso numero di elementi; b) in caso affermativo, gli elementi di l sono copiati in t in modo che la visita inorder di t produca l'ordine della lista l; c) in caso negativo viene lanciata una IrregularArgumentException:

public static <E> void forzaInorder(BinaryTree<E> t, PositionList<E> l)

{

if (t.size() != l.size())

throw new IllegalArgumentException("Tree and Sequence are different");

 

f(t,l,t.root());

}

public static <E> void f (BinaryTree<E>t, PositionList<E>s, Position<E> p)

{

if (t.hasLeft(p))

f(t, s, t.left(p));

 

t.replace(p, s.remove(s.first()));

 

if (t.hasRight(p))

f(t, s, t.right(p));

}    

Continua...

Prova del 5 Aprile 2011

Questa è l'implementazione della mini-prova di Strutture Dati fatta dal prof La Torre il 5 Aprile 2011. Nella prima parte dell'esercizio veniva fornita un'interfaccia SequenzaIncompleta, e veniva chiesto di implementarne i metodi nella classe MiaSequenzaIncompleta usando a scelta una delle classi sviluppate durante il corso che implementano l'interfaccia Sequence (completa). Nella seconda parte veniva fornita una classe di Test per MiaSequenzaIncompleta dove veniva chiesto di scrivere una funzione che prende in input una Sequenza e la inverte.

public interface SequenzaIncompleta<E> 

{

public void addFirst(E e);

public E removeLast();

public E get(int i);

public Position<E> first();

public int size();

}

public class MiaSequenzaIncompleta<E> implements SequenzaIncompleta<E>

{

private ArrayIndexSequence<E> sequenza;

//private NodeSequence<E> sequenza;

public MiaSequenzaIncompleta()

{

sequenza = new ArrayIndexSequence<E>();

//sequenza = new NodeSequence<E>();

}

public void addFirst(E e) 

{

sequenza.addFirst(e);

}

public Position<E> first() 

{

return sequenza.first();

}

public E get(int i) 

{

return sequenza.get(i);

}

public E removeLast() {

return sequenza.removeLast();

}

public int size() {

return sequenza.size();

}

}

public class TestSequenzaIncompleta 

{

public static void main(String[] args) 

{

SequenzaIncompleta<Integer> s = new MiaSequenzaIncompleta<Integer>();

for (int i=10; i>0 ; i--)

s.addFirst(i);

System.out.println("Sequenza iniziale");

stampa(s);

System.out.println("Sequenza invertita");

inverti(s);

        stampa(s);

        

System.out.println("Rimuovi ultimo");

stampa(s);

System.out.println("Elemento rimosso ="+ s.removeLast());

System.out.println("Primo elemento ="+ s.first().element());

System.out.println("Inverti di nuovo");

inverti(s);

stampa(s);

}

private static <E> void stampa(SequenzaIncompleta<E> S){

for (int i=0; i<S.size() ; i++)

System.out.print(S.get(i)+ " ");

System.out.println("\n");

}

private static <E> void inverti(SequenzaIncompleta<E> S)

{

int n = S.size();

int count = 0;

for(int i=1; i<n; i++)

{

S.addFirst(S.get(i+count));

count++;

}

for(int i=1; i<n; i++)

S.removeLast();

}

//soluzione del prof.

/* private static <E> void inverti(SequenzaIncompleta<E> S)

    {

      int size = S.size();

      for(int i=1; i<size; i++) S.addFirst(S.get(2*i-1));

      for(int i=1; i<size; i++) S.removeLast();

    }

*/

}

Continua...