| Parte
I |
Linguaggio
Java, tipi di dati astratti, strutture dati |
Una
soluzione possibile |
| Semplici strutture
dati |
1. Scrivere il
codice delle classi ArStack e
ArQueue
che realizzano, rispettivamente, l'interfaccia Stack e l'interfaccia Queue
(entrambe estendono l'interfaccia Container)
e che usano per la memorizzazione di oggetti array riempiti
parzialmente.
I metodi delle classi abbiano andamento asintottico O(1) (medio
se si ridimensiona l'array). 2. Scrivere una classe Main che - legga un testo da file, separi le righe in parole e memorizzi le parole sia in un oggetto di classe ArStack sia in un oggetto di classe ArQueue. Il nome del file sia passato come argomento nella riga di comando. Si consideri una parola come una stringa delimitata da spazi o caratteri di nuova riga. - stampi il contenuto dell'oggetto di classe ArStack in un file. Il nome del file sia passato come argomento sulla riga di comando. - stampi il contenuto dell'oggetto di classe ArQueue in un file. Il nome del file sia passato come argomento sulla riga di comando. uso: $ java Main inputFile outputFile1 outputFile2 3. Eseguire l'analisi del testo contenuto nel file dante.txt. |
EmptyStackException.java EmptyQueueException.java ArStack.java ArQueue.java Main.java |
| Coda realizzate tramite pile |
Scrivere la classe QueueByStacks che realizza
l'interfaccia Queue. La classe QueueByStacks usi al suo interno
esclusivamente strutture dati di tipo pila (nella classe non si possono
usare array). Provare la classe QueueByStacks con il file di testo dante.txt. Per fare questo si modifichi la classe Main dell'esercizio precedente. Suggerimento (da leggere se non riuscite a trovare una soluzione da soli). Qual e' l'andamento asintottico della complessita' temporale dei metodi della classe QueueByStacks? uso: $ java QueueByStacksMain inputFile outputFile1 outputFile2 |
QueueByStacks.java QueueByStacksMain.java |
| Parte
II |
Strutture dati: Liste in Java |
Una soluzione possibile |
| Lista
con catena |
Si
consideri il tipo di dati astratto Lista definito dalle interfacce List.java e ListIterator.java. Si realizzi una lista usando una catena. Si lanci l'eccezione EmptyListException nel caso si cerchi di accedere o rimuovere elementi in una lista vuota. Si realizzi una classe di prova MainListaSuCatena che legga da un file un insieme di parole e le memorizzi in una lista. Il nome del file sia passato come argomento sulla riga di comandi. Si copi successivamente la lista in una nuova lista e si stampi il contenuto delle due liste. Si prepari un file di prova e si verifichi con questo il funzionamento delle classi. Come file di prova potete usare il file monti.txt, dove i vari token sono separati dal carattere ','. uso: $ java MainListaSuCatena inputFile |
EmptyListException.java ListaSuCatena.java MainListaSuCatena.java |
| Lista con array |
Si esegua l'esercizio
precedente realizzando la lista in un array riempito parzialmente. uso: $ java MainListaSuArray inputFile |
ListaSuArray.java MainListaSuArray.java |
| Parte
III |
Strutture dati: Dizionari in
Java |
Una soluzione possibile |
| Tabella | Si vuole memorizzare
un testo di parole (ogni parola caratterizzata da una sequenza di
caratteri
alfanumerici separati fra loro da uno o piu' spazi) assieme a
un'informazione accessoria definita
dalla parola chiave CAPITOLO racchiusa tra parentesi angolari
(<>). Si assume che le
parentesi angolari siano presenti solo nella parola chiave. La parola chiave <CAPITOLO> suddivide il testo in ingresso in capitoli la cui numerazione parte da 1. Per tale gestione si definisca la classe Testo la cui interfaccia pubblica e' riportata in Testo.html. Per verificare il funzionamento del programma si utilizzi il seguente metodo main(): public static void main(String args[]) { String libro = "<CAPITOLO> testo del primo capitolo " + "<CAPITOLO> testo del secondo capitolo " + "<CAPITOLO> testo del terzo capitolo"; Testo mioTesto = new Testo(); mioTesto.inserisciTesto(libro); for (int i = 0; i < mioTesto.capitoli(); i++) { System.out.println("Capitolo " + (i + 1)); System.out.println(mioTesto.leggiCapitolo(i + 1)); } } uso: $ java Testo Leggere prima di iniziare la realizzazione. |
Testo.java |
| Dizionario |
Si vuole gestire un
database di studenti. Internamente uno studente e' definito da un'
istanza di classe Studente contenente le seguenti informazioni: - nome dello Studente - lista di esami sostenuti (ogni esame identificato da un nome) e corrispondente voto. L'interfaccia pubblica della classe Studente è definita nel file Studente.html. Piu' istanze di classe studente saranno contenute nella classe Scuola la cui interfaccia pubblica è definita nel file Scuola.html. Viene richiesto di realizzare le classi Studente e Scuola come descritto. Il seguente metodo main puo' essere usato come test finale: public class Prova { public static void main(String args[]) { Scuola scuola = new Scuola(); scuola.aggiungiStudente("Rossi"); scuola.aggiungiStudente("Bianchi"); scuola.aggiungiStudente("Verdi"); scuola.aggiornaCurriculum("Rossi", "Fondamenti di Informatica 1", 22); scuola.aggiornaCurriculum("Rossi", "Matematica A", 19); scuola.aggiornaCurriculum("Rossi", "Fisica 1", 24); scuola.aggiornaCurriculum("Bianchi", "Fondamenti di Informatica 1", 18); scuola.aggiornaCurriculum("Bianchi", "Matematica A", 19); scuola.aggiornaCurriculum("Bianchi", "Fisica 1", 20); scuola.aggiornaCurriculum("Verdi", "Fondamenti di Informatica 1", 30); scuola.aggiornaCurriculum("Verdi", "Matematica A", 30); scuola.aggiornaCurriculum("Verdi", "Fisica 1", 27); scuola.stampa(); } } Versione originale del testo del compito. Si realizzi il dizionario in tre modi diversi: - con array non ordinato - con array ordinato - con tabella hash Per ciascuno dei metodi si indichi la complessita' temporale. Programmare l'ordinamento nella classe Scuola usando, in alternativa, i tre algoritmi di ordinamento studiati: - ordinamento per selezione - ordinamento per inserimento - ordinamento per fusione Leggere prima di iniziare la realizzazione. |
Studente.java ScuolaArrayNonOrdinato.java ScuolaArrayOrdinato.java ScuolaHashTable.java OrdinatorePerFusione OrdinatorePerSelezione OrdinatorePerInserimento |