LSD
Esercizi di ripasso

Pile e Code

[AddSums] Si scriva una classe AddSumsStack contentente il metodo statico addSums:

import lab2.*;
import lab2.Exceptions.*;

class AddSumsStack {
    static int addSums ( Stack s ){
    // da completare
   }
}

Si assume che la pila s contenga solo istanze di Integer. Il metodo addSums inserisce prima di ogni elemento x della pila s ricevuta in input la somma di tutti gli elementi di s che sono stati inseriti dopo di x. Se la pila è vuota, il metodo aggiunge alla pila un solo elemento contenente 0. Il metodo restituisce la somma degli elementi della pila originale.
Per testare la classe AddSumsStack, si compili ed esegua la classe UseAddSumsStack. L'output deve essere ESATTAMENTE il seguente:

Stato della pila prima di 'addSums':
7 6 5 4 3 2 1
Totale elementi pila: 28
Stato della pila dopo di 'addSums':
7 7 6 13 5 18 4 22 3 25 2 27 1 28

Chiamo 'addSums' sulla pila vuota...
Totale elementi pila: 0
Pila risultante:0

[Complementari]
Due sequenze di interi K = (k[0], k[1], k[2], ..., k[n]) e J = (j[0], j[1], j[2], ..., j[n]) sono complementari se hanno la stessa lunghezza e per ogni i in {0, 1, 2, ..., n}, k[i] è pari se e solo se j[n-i] è dispari. Ad esempio,
K = (1, 2, 3, 4, 5) e J = ( 6, 5, 4, 3, 2)    sono complementari
K = (0, 24, 32) e J = ( 1, 3, 45)             sono complementari
K = (1, 23, 4, 52) e J = ( 65, 4, 32, 2)      non sono complementari
K = (1, 2, 3) e J = (5, 4)           non sono complementari (perché di lunghezza diversa)
Utilizzando le pile e le code, si scriva una classe Complementari contente il metodo:
static boolean complementari (Queue K, Queue J);
che restituisce true se le sequenze di elementi passate come argomenti sono complementari, false altrimenti.
Il metodo main dovrà creare due code ed inserirci alcuni interi, quindi dovrà chiamare il metodo complementari e stampare un opportuno messaggio in base al risultato.

Liste

[OrdinaList] Sia dato il seguente frammento di programma

import lab2.*;
public class OrdinaList extends LinkedList {
     public void ordina( int n ) {
     // da definire
     }
}

Si completi la classe precedente in maniera che il metodo ordina ordini gli elementi della lista (che si assume siano istanze dell'interfaccia Comparable) in modo crescente. Si scriva un semplice progamma per testare il metodo.
[RichLinkedList] Definire l'interfaccia RichList che estende List con i metodi seguenti.

boolean removeAll( Object x )
che cancella tutte le occorrenze di x nella lista. Restituisce false nel caso l'oggetto non compaia nella lista, true altrimenti.

int occur( Object x )
che conta le occorrenze di un oggetto x nella lista. Restituisce 0 nel caso l'oggetto non compaia nella lista.
Definire la classe RichLinkedList che realizza RichList estendendo LinkedList. Scrivere una classe TestRichList che utilizza i nuovi metodi.
[MixedIntersection] Si scriva la classe MixedIntersection, contenente il metodo statico intersect:

import lab2.*;
public class MixedIntersection {
    public static Queue intersect ( Stack s, List l ) {
     // da completare
   }
}

Il metodo intersect, senza modificare né la pila s né la lista l passate per argomento, deve restituire una coda che contenga tutti gli oggetti comuni (cioè gli elementi equals) alla pila s e alla lista l. Il metodo deve lanciare una IllegalArgumentException se uno dei due parametri è null.
Per testare il metodo, si scarichi e si esegua la classe (già compilata) TestMixedIntersection.class.
[CreaStampa] Si scriva la classe CreaStampa che contene metodi statici per creare e stampare (senza distruggerle!) le seguenti strutture dati: Stack, Queue, List, Set. Ciascuna struttura deve essere riempita con istanze della classe Integer generate casualmente.
Testare la classe con un semplice programma di verifica.
Soluzione: CreaStampa.java

Alberi e alberi binari di ricerca

[TreeSetToArray] Estendere la classe TreeSet con il metodo toArray( ) che restituisce un array contenente tutti gli oggetti contenuti nell'albero ordinati in ordine crescente.
Testare il metodo con un semplice programma di verifica.
Soluzione: TreeSet2.java

[Bilanciato]Un albero è k-bilanciato (per un numero naturale k) se è vuoto, oppure se non è vuoto e

sia il sottoalbero sinistro che quello destro sono k-bilanciati
la differenza tra la profondità del sottoalbero sinistro e la profondità del sottoalbero destro è al più k, in valore assoluto.

Si scriva la classe Bilanciato che estende TreeSet e fornisce i seguenti metodi:

public static int profondita(BinNode n);
/* restituisce la profondita' dell'albero binario che ha come radice n */
public int profondita();
/* restituisce la profondita' dell'albero binario di ricerca su cui viene invocato */

public static boolean bilanciato (int k, BinNode n);
/* restituisce true se e solo se l'albero binario con radice n e' k-bilanciato
*/ public boolean bilanciato (int k);
/* restituisce true se e solo se l'albero binario di ricerca su cui viene invocato e' k-bilanciato */

Per testare i metodi, si compili e si esegua la classe TestBilanciato.java. Se i metodi sono corretti, l'output sarà ESATTAMENTE il seguente:

Primo albero:
L'albero, che ha profondità 3,
è 0-bilanciato, cioè è perfettamente bilanciato
Secondo albero:
L'albero, che ha profondità 3,
NON è 0-bilanciato
NON è 1-bilanciato
è 2-bilanciato

Soluzione: Bilanciato.java

[Mezzefoglie]Una "mezzafoglia" di un albero binario è un nodo che ha esattamente un figlio. Si scriva la classe MezzeFoglie che contiene il metodo

/* restituisce il numero di "mezzefoglie" contenute nell'albero la cui radice e' il nodo n */
public static int mezzeFoglie ( BinNode n){
// da completare }

Si consiglia di scrivere con precisione una definizione ricorsiva della funzione mezzeFoglie (ad esempio in un commento) prima di scrivere il codice. Indicare esplicitamente che tipo di visita dell'albero si usa.
Per testare il metodo, si compili e si esegua la classe TestMezzeFoglie.java. Se il metodo è corretto, l'output sarà ESATTAMENTE il seguente:

Le mezze foglie del primo albero sono 5
Le mezze foglie dell'albero vuoto sono 0

Soluzione: MezzeFoglie.java

[Mediano] L'elemento ai è il mediano della sequenza crescente di valori se i = n/2 quando n è pari e se i = (n+1)/2 quando n è dispari. Ad esempio 5 è il valore mediano della sequenza <1,3,5,7,8,9> ed anche della sequenza <1,3,5,7,8>. Estendere la classe TreeSet aggiungendo il metodo
public Object mediano ( )
che restituisce il nodo contenente il valore mediano dell'insieme se l'insieme non è vuoto, restituisce null altrimenti.
Testare il metodo con un semplice programma di verifica.
Soluzione: TreeSet3.java

[Potenti] Dato un albero binario (non necessariamente di ricerca) i cui nodi contengono interi, un nodo viene definito potente se l'intero in esso contenuto e' strettamente maggiore della somma dei valori contenuti nei nodi del sottoalbero destro e sinistro.

Sia dato il seguente frammento di programma

import lab2.*;

public class ContaPotente {

    public static int contaPotenti ( BinNode r ) {
    // da definire
    }
}

Si completi la classe precedente, in maniera che il metodo contaPotenti restituisca il numero di nodi potenti che sono contenuti nell'albero di radice r.
Per testare la classe ContaPotente, si compili ed esegua la classe TestContaPotente.java. L'output deve essere ESATTAMENTE il seguente:

Provo il metodo ContaPotente.contaPotenti()...
Albero vuoto: [valore atteso] 0 [valore ottenuto] 0
Albero con un nodo: [valore atteso] 1 [valore ottenuto] 1
Albero con un nodo: [valore atteso] 5 [valore ottenuto] 5

[LevelsToList]
Si scriva la classe LevelsToList che contiente il metodo

    public static List levelsToList (BinNode r) ;
    // da completare
    }

Il metodo levelsToList deve restituire una lista contente tutti gli oggetti dell'albero binario avente come radice r, ordinati secondo il seguente criterio
Ad esempio, se applicato al seguente albero,

il metodo restituisce la lista [50, 20, 70, 10, 40, 90, 30, 80, 100, 35].
Scrivere un metodo main che costruisce un albero binario, ci applica il metodo levelsToList e stampa il risultato.

Soluzione: LevelsToList [Le classi ListUtils e TreeUtils forniscono alcuni utili metodi per manipolare liste e alberi binari].