Laboratorio 8

Interfacce e classi di utilita` generale
Nello svolgimento degli esercizi si potranno utilizzare alcune classi, interfacce ed eccezioni generiche che sono state presentate a lezione e che non fanno parte della libreria standard.
  • Interfacce ed eccezioni
    • Il file Container.java contiene il codice dell'interfaccia Container, la quale definisce un contenitore astratto di oggetti.
    • Il file Stack.java contiene il codice dell'interfaccia Stack, la quale estende Container e definisce il tipo di dato astratto Pila. Il file contiene inoltre il codice delle classi (eccezioni) EmptyStackException e FullStackException.
    • Il file Queue.java contiene il codice dell'interfaccia Queue, la quale estende Container e definisce il tipo di dato astratto Coda. Il file contiene inoltre il codice delle classi (eccezioni) EmptyQueueException e FullQueueException
    • Il file List.java contiene il codice dell'interfaccia List, la quale estende Container e definisce il tipo di dato astratto Lista. Il file contiene inoltre il codice dell'interfaccia ListIterator
  • Classi
    • Il file ArrayStack.java contiene il codice della classe ArrayStack, la quale implementa Stack usando un array riempito solo in parte e ridimensionabile
    • Il file ArrayQueue.java contiene il codice della classe ArrayQueue, la quale implementa Queue usando un array circolare riempito solo in parte e ridimensionabile
    • Il file LinkedList.java contiene il codice della classe LinkedList, la quale implementa List tramite una lista concatenata. La classe LinkedList definisce due classi interne: ListNode e LinkedListIterator (che implementa ListIterator)

Esercizio 0

Questionario di autovalutazione: risposte e statistiche

Esercizio 1

Argomento: uso di tipi di dati astratti

Scrivere il codice (o riutilizzare quello gia` esaminato a lezione) di due classi ArrayStack e ArrayQueue che realizzano rispettivamente l'interfaccia Stack e l'interfaccia Queue (le quali a loro volta estendono entrambe l'interfaccia Container).
Scrivere poi una classe StackQueueTester che Per il collaudo usare ad esempio il file di input dante.txt. Esempio di uso:
$ java StackQueueTester inputFile outputFile1 outputFile2


Soluzione8_1


Esercizio 2

Argomento: uso di tipi di dati astratti

Scrivere il codice (o riutilizzare quello gia` esaminato a lezione) di una classe LinkedList che realizzi l'interfaccia List tramite una catena dotata di iteratore. Notare in particolare che Si realizzi una classe di collaudo LinkedListTester che Si prepari un file di prova e si verifichi con questo il funzionamento delle classi (come file di prova si puo` usare ad esempio il file monti.txt, dove i vari token sono separati dal carattere ','). Esempio di uso:
$ java LinkedListTester inputFile


Soluzione8_2


Esercizio 3

Argomento: realizzazione di tipi di dati astratti, liste e iteratori

Scrivere il codice di una classe ArrayList che realizzi l'interfaccia List usando un array riempito solo in parte come contenitore degli elementi della lista. Si realizzi una classe di collaudo ArrayListTester che realizza lo stesso comportamento specificato nell'esercizio precendente per la classe LinkedListTester, con la sola differenza che almeno uno dei due oggetti creati all'interno del metodo main e` di tipo ArrayList invece che di tipo LinkedList (si noti che il codice del metodo statico ausiliario copyList non cambia, dal momento che questo metodo elabora generici riferimenti di tipo List).
Si prepari un file di prova e si verifichi con questo il funzionamento delle classi (come file di prova si puo` usare ad esempio il file monti.txt, dove i vari token sono separati dal carattere ','). Esempio di uso:
$ java ArrayListTester inputFile


Soluzione8_3


Esercizio 4

Argomento: realizzazione di tipi di dati astratti, code e pile

Progettare una classe StackByQueue che realizzi l'interfaccia Stack usando come unica variabile di esemplare una coda. La classe deve rispettare questo schema (che e` qualcosa di piu` di una interfaccia pubblica visto che abbiamo specificato anche tutti e soli i campi di esemplare della classe). Scrivere una classe di collaudo StackByQueueTester che
Soluzione8_4


Esercizio 5

Argomento: realizzazione di tipi di dati astratti, code e pile

Progettare una classe QueueByStack che realizzi l'interfaccia Queue usando come unica variabile di esemplare una coda. La classe deve rispettare questo schema (che e` qualcosa di piu` di una interfaccia pubblica visto che abbiamo specificato anche tutti e soli i campi di esemplare della classe). Scrivere una classe di collaudo QueueByStackTester che
Soluzione8_5


Esercizio 6

Argomento: algoritmi su tipi di dati astratti, pile

Realizzare un algoritmo per la rimozione di elementi (cioe` elementi dello stesso tipo e aventi le stesse informazioni di stato) da una pila di oggetti Dopo avere scritto un metodo statico removeDuplicates che realizza l'algoritmo sopra descritto, inserirlo in una classe eseguibile StackDuplicateRemover che: Fare l'analisi delle prestazioni asintotiche dell'algoritmo di rimozione dei duplicati.

Soluzione8_6


Esercizio 7 (impegnativo)

Argomento: algoritmi su tipi di dati astratti, pile

Realizzare un algoritmo che ordina gli elementi di una pila: dopo l'applicazione dell'algoritmo gli oggetti contenuti nella pila devono essere ordinati, con l'elemento minore in cima alla pila (si supponga, ovviamente, che tutti gli oggetti siano esemplari di una stessa classe che realizza l'interfaccia Comparable). Dopo avere scritto un metodo statico sortStack che realizza l'algoritmo sopra descritto, inserirlo in una classe eseguibile che:

Soluzione8_7


Esercizio 8 (approfondimento su classi interne, solo per i piu` interessati)

Si consideri il codice del file ClEsterna.java, che definisce una classe denominata ClEsterna e una sua classe interna denominata ClInterna. Si consideri inoltre la classe di collaudo ClInterneTester.java, il cui metodo main utilizza riferimenti ed oggetti di tipo ClEsterna e di tipo ClInterna.