| Parte
II |
Linguaggio
Java: classi,
ordinamento, ricerca |
Una
soluzione possibile |
| Ordinare Stringhe |
L'interfaccia Container.java definisce un contenitore
astratto. Scrivere la classe Text che realizza l'interfaccia Container, la cui interfaccia pubblica è documentata in Text.html, 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 - legga parole da un file e le memorizzi in un contenitore di classe Text. Una parola sia una stringa delimitata da spazi e dai caratteri di interpunzione .,;:-!?(). Il nome del file sia passato come argomento nella riga di comando. - ordini le parole in senso lessicografico crescente - elimini le parole eventualmente ripetute. Si noti che nel contenitore ordinato le parole ripetute sono vicine. Per eliminare le ripetizioni, si crei un nuovo contenitore dove inserire solo le parole senza ripetizione (prima di inserire verificare che la parola non sia uguale all'ultima inserita). - stampi a standard output le parole del contenitore senza ripetizioni. Per la prova si legga dal file alberi.txt. Esempio di uso: $java TextTester nomeInputFile |
Text.java TextTester.java |
| Ordinare oggetti |
Si consideri la
classe Studente.java. Si scriva la classe ContenitoreOrdinatoStudenti che realizza l'interfaccia Container adatta a memorizzare oggetti di classe Studente. L'interfaccia pubblica della classe è specificata in ContenitoreOrdinatoStudenti.html. Il costruttore ContenitoreOrdinatoStudenti(String filename) legge i dati di un insieme di studenti dal file il cui nome e' passato come parametro esplicito. Il metodo inserisci() deve inserire ordinatamente usando il metodo compareTo() della classe Studente. Si renda eseguibile la classe, programmando il metodo main in modo che legge da file i dati di un insieme di studenti, uno per riga (formato "nome:matricola"), e inserisca gli studenti in un contenitore di classe ContenitoreOrdinatoStudenti. Il nome del file sia passato come argomento sulla riga di comandi. Si invii, successivamente, gli elementi dell'archivio ordinato in ordine decrescente a un file, il cui nome e' passato come argomento nella riga di comando. Si provi la classe Contenitore usando il file studenti.txt. Esempio di uso: $java ContenitoreOrdinatoStudenti nomeInputFile nomeOutputFile |
ContenitoreOrdinatoStudenti.java |
| Parte
III |
Linguaggio
Java: ordinamento di oggetti confrontabili |
Una
soluzione possibile |
| Ordinare oggetti
confrontabili |
Si scriva la classe ContenitoreOrdinato che
realizza l'interfaccia Container. La classe e' un contenitore generico in cui possono essere inseriti oggetti che implementano l'interfaccia Comparable (ad esempio gli oggetti di classe String o di classe Studente). L'interfaccia pubblica della classe e' riportata in ContenitoreOrdinato.html. Si scriva una classe di prova ProvaContenitoreOrdinato.java che - legge da file, il cui nome e' passato sulla riga di comando, i dati di un insieme di studenti (uno per riga nel formato "nome:matricola") - costruisce degli oggetti di classe Studente e li inserisce in un contenitire di classe ContenitoreOrdinato - invia successivamente in un file di uscita - il cui nome e' passato nella riga di comando - gli elementi contenuti nell'archivio in ordine decrescente. Per eseguire la funzione richiesta, si usi il metodo togliMax() che estrae dal contenitore l'elemento massimo (nel senso del metodo compareTo(). Attenzione: il metodo togliMax ritorna un generico oggetto di classe Object. Nota Bene: Per memorizzare il riferimento restituito dal metodo togliMax() si puo' usare un riferimento di classe Studente con un forzamento esplicito: Studente s = (Studente)archivio.togliMax(); Senza il forzamento esplicito, si deve usare un riferimento di classe Object: Object obj = archivio.togliMax(); Sul riferimento di classe s possiamo successivamente invocare i metodi della classe Studente, ad esempio: int matr = s.matricola(); mentre il compilatore segnala errore se lo facciamo sul riferimento di classe Object perche' nella classe Object non e' definito il metodo matricola():: int matr = obj.matricola(); // ERRORE Per il polimorfismo, funzionano correttamente invece i seguenti due enunciati: System.out.println(s); System.out.println(obj); Uso: $ java ProvaContenitoreOrdinato inputFile outputFile Come file di input si usi il file studenti.txt. |
ContenitoreOrdinato.java ProvaContenitoreOrdinato.java |
| Ordinare oggetti confrontabili | Si scriva la classe ContenitoreOrdinabile che
realizza l'interfaccia Container. Come la precedente, la classe e' un contenitore generico in cui possono essere inseriti oggetti che implementano l'interfaccia Comparable. L'interfaccia pubblica della classe e' riportata in ContenitoreOrdinabile.html. La classe realizza il metodo pubblico ordina() per ordinare gli elementi comparabili contenuti nel contenitore. Per ordinare si usi l'algoritmoper fusione, programmandolo nella classe ArrayAlgorithms. Si scriva la classe di prova ProvaContenitoreOrdinabile.java che - legge da file, il cui nome e' passato sulla riga di comando, i dati di un insieme di studenti (uno per riga nel formato "nome:matricola") - costruisce degli oggetti di classe Studente e li inserisce in un contenitire di classe ContenitoreOrdinato - invia successivamente in un file di uscita - il cui nome e' passato nella riga di comando - l'elenco degli elementi contenuti nell'archivio due volte, la prima volta senza ordinamento, la seconda volta dopo aver ordinato l'archivio. Esempio usando i dati contenutI nel file studenti.txt: *** STAMPA ARCHIVIO SENZA ORDINAMENTO *** 769374:Rinaldo Sette 698765:Franca Cinque Sei 897650:Giorgio Quattro 987456:Marco Tre 356789:Rita Due 456378:Antonio Uno *** STAMPA ARCHIVIO DOPO ORDINAMENTO *** 987456:Marco Tre 897650:Giorgio Quattro 769374:Rinaldo Sette 698765:Franca Cinque Sei 456378:Antonio Uno 356789:Rita Due Uso: $ java ProvaContenitoreOrdinabile inputFile outputFile Come file di input si usi il file studenti.txt. |
ContenitoreOrdinabile.java ProvaContenitoreOrdinabile.java |
| Ordinare oggetti confrontabili |
Ecco un'altra versione delle
classi dell'esercizio precedente: ContenitoreOrdinatoObj.java
e ContenitoreOrdinabileObj.java. Le classi, fornite dal docente, si differenziano da quelle dell'esercizio precedente perche' sono definite per memorizzare generici oggetti di classe java.lang.Object. Naturalmente, per poter essere ordinati, gli oggetti inseriti nel contenitore devono essere di una classe che realizza l'interfaccia java.lang.Comparable. 1. Provare a compilare ed eseguire le seguenti classi di prova, fornite dal docente, che memorizzano oggetti di classe Complex (che non realizza l'interfaccia java.lang.Comparable): - ProvaContenitoreOrdinato1.java: usa la classe ContenitoreOrdinato per memorizzare numeri complessi - ProvaContenitoreOrdinato2.java: usa la classe ContenitoreOrdinatoObj per memorizzare numeri complessi - ProvaContenitoreOrdinabile1.java: usa la classe ContenitoreOrdinabile per memorizzare numeri complessi - ProvaContenitoreOrdinabile2.java: usa la classe ContenitoreOrdinabileObj per memorizzare numeri complessi - ProvaContenitoreOrdinabile3.java: usa la classe ContenitoreOrdinabileObj per memorizzare e ordinare numeri complessi Uso: $ java ProvaContenitoreOrdinato1 complex.txt out.txt 2. Rispondere alle seguenti domande: 2.1/ perche' il compilatore segnala errore nelle classi ProvaContenitoreOrdinato1 e ProvaContenitoreOrdinabile1 e non nelle altre classi? 2.2/ perche' in esecuzione ProvaContenitoreOrdinato2 e ProvaContenitoreOrdinabile3 provocano l'eccezione java.lang.ClassCastException? Perche' la classe ProvaContenitoreOrdinabile2 viene eseguita senza lanciare l'eccezione java.lang.ClassCastException? |
| Parte
IV |
Linguaggio
Java, tipi di dati astratti, strutture dati |
Una
soluzione possibile |
| Semplici strutture
dati |
1. Realizzare le classi ArStack che
realizza le interfacce Stack e Container. La classe usa per la
memorizzazione di oggetti un array riempito
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 in un contenitore di classe ArStack. 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 del contenitore in un file, introducendo gli elementi estratti in un secondo contenitore di classe ArStack.. Il nome del file sia passato come argomento sulla riga di comando. - stampi il contenuto del secondo contenitore in un terzo file di output, il cui nome e' passata nella riga di comando Uso: $ java Main inputFile outputFile1 outputFile2 3. Eseguire l'analisi del testo contenuto nel file numeri.txt. |
EmptyStackException.java ArStack.java Main.java |
| Parte V |
Linguaggio
Java: ordinamento di oggetti confrontabili |
Una
soluzione possibile |
| Ordinare oggetti.
Criteri di
ordinamento multipli |
Realizzare la classe
StudenteEsteso che estende la funzionalita' della classe Studente del
laboratorio precedente in modo che sia possibile ordinare
gli oggetti della classe, per ordine di matricola o,
alternativamente, per ordine alfabetico. Scrivere poi una classe di prova ProvaArchivio.java che: - legga da file i dati di un insieme di studenti. A ciascun studente sia riservata nel file una riga con il seguente formato: matricola : cognome nome - imposti il criterio di ordinamento. Questo verra' passato come argomento sulla riga di comando: uso: $ java ProvaArchivio inputfile criterio dove criterio puo' essere la stringa "matricola" o la stringa "nome". - inserisca i dati in un archivio di classe ContenitoreOrdinatoStudenti - stampi i dati contenuti nell'archivio su standard output. Provare con il file di input studenti.txt. Leggere prima di iniziare comparazioneMultipla.html. |
StudenteEsteso.java ProvaArchivioEsteso.java |
| Creare delle classi che realizzano l'interfaccia
Comparable |
I
poligoni del piano sono caratterizzati dall'avere una misura del
perimetro e dell'area. Questa proprieta' astratta e' descritta nella seguente interfaccia poligono.java. Gli oggetti di interfaccia poligono sono comparabili fra loro (il criterio di comparazione sia la misura dell'area). Realizzare le seguenti classi: - Triangolo che realizza poligono; - Rettangolo che realizza poligono; - Quadrato che estende rettangolo; Si scriva poi una classe MainPoligoni che: - legga dal file poligoni.txt un insieme di poligoni. A ciascun poligono sia riservata una riga nel file con il formato: <T> a b c per il Triangolo, dove a, b c sono le lunghezze dei lati <R> a b per il Rettangolo, dove a, b sono le lunghezze dei lati <Q> a per il Quadrato, dove a e' la lunghezza del lato. - memorizzi i poligoni in ArchivioOrdinato del tipo realizzato nel primo esercizio - stampi alla fine a standard output l'elenco ordinato dei poligoni. A tal proposito si riscrivano nelle classi gli opportuni metodi toString(). Uso: $ java MainPoligoni inputfile |
Triangolo.java Rettangolo.java Quadrato.java MainPoligoni.java |
| Parte VI | Linguaggio
java e algoritmi di ordinamento |
Una soluzione possibile |
| Ordinamento |
Si scriva un programma che - legga da standard input una sequenza (di dimensione non predeterminata) di numeri interi, un numero per riga, senza alcun requisito di ordinamento (cioè, in generale, in ordine casuale); - visualizza i numeri sullo standard output dopo aver eliminato eventuali valori duplicati (o, in generale, replicati più volte), lasciando quindi un solo esemplare di ciascun numero presente nella sequenza originale; al termine, i numeri potranno trovarsi in un ordine diverso da quello iniziale (non è richiesto che siano ordinati). Risolvere il problema in due modi 1. effettuando prima un ordinamento dell'insieme dei dati con l'algoritmo mergesort (avente efficienza O(n lg n)), mettendo poi a punto e realizzando un algoritmo per l'eliminazione degli elementi replicati in un array ordinato con prestazioni asintotiche medie e di caso peggiore di tipo O(n)2. senza effettuare alcun ordinamento dell'insieme dei dati, mettendo a punto e realizzando un algoritmo con prestazioni asintotiche medie e di caso peggiore di tipo O(n2). Per la soluzione del problema dell'eliminazione dei duplicati, NON utilizzare array aggiuntivi oltre a quello in cui sono memorizzati i dati stessi (si possono usare altri array per la sola fase di ordinamento del punto 1. |
provate da soli |