• Laboratorio 7

    AVVISO
    Nei seguenti esercizi faremo uso dell'interfaccia Comparable, appartenente alla libreria standard di Java. Notate tuttavia che, dal momento che non abbiamo studiato i tipi parametrici e le classi generiche (cfr. cap. 16 del libro di testo), useremo l'interfaccia non parametrica Comparable invece della versione parametrica Comparable<T> disponibile a partire dalla JDK 5.0. Per questo motivo il compilatore potra` talvolta produrre dei messaggi di warning (avvisi) di questo tipo:
        Note: NomeClasse.java uses unchecked or unsafe operations.
        Note: Recompile with -Xlint:unchecked for details.
    
    Questi avvisi non segnalano errori del codice, ma si riferiscono semplicemente al fatto che stiamo usando Comparable invece di Comparable<T>. Possiamo tranquillamente ignorarli.

    Esercizio 0

    Questionario di autovalutazione: risposte e statistiche
    Attenzione: come osservato da uno studente, la domanda n. 2 conteneva un'errore, che e` stato corretto nel file delle risposte. In particolare le parole "un metodo non statico" che comparivano nella domanda sono ora sostituite dalle parole "un metodo statico".

    Esercizio 1

    Argomento (ripasso): interfacce e ereditarieta`, la classe Object e l'interfaccia Comparable, algoritmi di ordinamento e ricerca su array di oggetti ordinabili

    Ripassare la classe ArrayAlgs per oggetti di tipo Comparable vista a lezione. Studiare con attenzione gli algoritmi di ordinamento e ricerca. Prestare particolare attenzione all'uso di riferimenti di tipo Object e di tipo Comparable
    Collaudare gli algoritmi di ordinamento con questa semplice classe ArrayAlgsTester. Notare in particolare che

    Esercizio 2

    Argomento: interfacce, ordinamento di oggetti

    In questo esercizio si fa uso dell'interfaccia Container, che definisce un contenitore astratto di oggetti e il cui codice non va modificato.
    Scrivere la classe Text che realizza l'interfaccia Container e la cui interfaccia pubblica e` documentata qui. Tale classe e` in grado di memorizzare le parole di un testo (contenitore di testo). La classe realizzi il metodo void sort() per ordinare le parole in senso lessicografico crescente. Il metodo sia ottimizzato per l'ordinamento di un numero elevato di parole.
    Si scriva poi la classe TextTester che Per collaudare le classi si legga (ad esempio) dal file alberi.txt.
    Esempio di uso:
    $java TextTester nomeInputFile
    


    Soluzione7_2


    Esercizio 3

    Argomento: interfacce, ordinamento di oggetti

    In questo esercizio si fa uso Si scriva una classe SortedContainer, che realizza l'interfaccia Container e la cui interfaccia pubblica e` riportata qui. La classe rappresenta un contenitore in cui possono essere inseriti generici oggetti ordinabili, ovvero appartenenti a classi che implementano l'interfaccia Comparable. In particolare un oggetto di tipo SortedContainer puo` contenere oggetti appartenenti alla classe Student.
    Si scriva poi una classe di collaudo SortedContainerTester che Come file di input si puo` usare il file studenti.txt. Esempio di uso:
    $ java SortedContainerTester studenti.txt studentiordinati.txt
    Ecco qualche suggerimento, da leggere con attenzione.

    Soluzione7_3


    Esercizio 4

    Argomento: interfacce, ereditarieta` e uso di super, ordinamento di oggetti

    In questo esercizio si fa uso Si scriva una classe StudentContainer che estende la classe SortedContainer scritta nell'esercizio precedente, e la cui interfaccia pubblica e` riportata qui. La classe rappresenta un contenitore in cui possono essere inseriti solo oggetti di tipo Student (e non generici oggetti di tipo Comparable).
    Si scriva poi una classe di collaudo StudentContainerTester che Come file di input si puo` usare il file studenti.txt. Esempio di uso:
    $ java StudentContainerTester studenti.txt studentiordinati.txt
    Ecco qualche suggerimento, da leggere con attenzione.

    Soluzione7_4


    Esercizio 5

    Argomento: interfacce, ereditarieta` e uso di super, polimorfismo, ordinamento di oggetti

    In questo esercizio si fa uso dell'interfaccia Poligono, che estende Comparable e definisce un poligono nel piano, e il cui codice non va modificato Realizzare le seguenti classi: Tutte queste classi devono, oltre a realizzare i metodi delle interfacce Comparable e Poligono, sovrascrivere il metodo toString() in modo che le stringhe associate ad oggetti di queste classi siano nel formato Si scriva infine una classe di collaudo PoligonoTester che: Il programma puo` essere collaudato usando il file poligoni.txt. Esempio di uso:
    $ java PoligoniTester poligoni.txt
    Ecco qualche suggerimento, da leggere con attenzione.

    Soluzione7_5


    Esercizio 6 (approfondimento su algoritmi di ordinamento)

    Argomento: algoritmi di ordinamento, ordinamento di oggetti

    Realizzare un algoritmo di ordinamento per dati di un array che procede in questo modo: Questo algoritmo prende il nome di ordinamento a bolle (bubbleSort). Infatti, se si considera l'array come se fosse disposto verticalmente, con la cella di indice 0 in alto, lo spostamento di valori effettuato dall'algoritmo e` simile al movimento di bolle che gorgogliano verso l'alto.

    Dopo avere scritto un metodo statico che realizza l'algoritmo per ordinare array di stringhe, inserirlo in una classe eseguibile che ne verifichi il corretto funzionamento leggendo stringhe dall'ingresso standard.

    Soluzione7_6


    Esercizio 7 (Approfondimento su mergeSort, solo per i piu` interessati)

    Argomento: algoritmi di ordinamento

    Realizzare un algoritmo di ordinamento per fusione (mergeSort) che funzioni in modo iterativo anziche` ricorsivo.
    Suggerimenti:
    1. Realizzare una prima versione del programma che funzioni correttamente soltanto quando la dimensione dell'insieme dei dati (cioe` la lunghezza n dell'array) e` una potenza di 2.
      • Alla prima iterazione del ciclo principale, l'array da ordinare viene considerato (dal punto di vista logico) come costituito da n sotto-array di dimensione 1
      • Tali sotto-array elementari vengono fusi a coppie, ciascun array in posizione pari (a partire dalla posizione 0) fuso con l'array seguente in posizione dispari. L'algoritmo di fusione di due array ordinati e` identico a quello visto per la versione ricorsiva di MergeSort
      • Al termine di tale prima iterazione l'array originale e` costituito da n/2 sotto-array consecutivi, ciascuno dei quali contiene due elementi ordinati.
      • La successiva iterazione del ciclo principale fonde tali sotto-array a coppie, come nella prima iterazione, cosicche` al termine l'array originale e` costituito da n/4 sotto-array consecutivi, ciascuno dei quali contiene quattro elementi ordinati
      • L'algoritmo applica iterativamente questa procedura fino al completo ordinamento del vettore.
    2. Modificare la prima versione in modo da gestire insiemi di dati di lunghezza arbitraria, eliminando quindi il vincolo che tale lunghezza sia una potenza di 2, dopo aver individuato le necessarie modifiche da apportare all'algoritmo sopra delineato.
    Dopo avere scritto un metodo statico iterativeMergeSort, che realizza l'algoritmo sopra descritto, inserirlo in una classe eseguibile che

    Soluzione7_7