10.
Lezione/esercitazione del 25/10/04 [2 ore, in AULA C] per tutti i turni
di:
Algoritmi & Laboratorio
(
Modulo 2
)
"Riassunto" della lezione:
Vettori e array (in Java):
-
La tecnica dell'"array dinamico (o del raddoppio e dimezzamento)".
-
Realizzazione di una pila (mutabile) con un array dinamico
e costo ammortizzato delle operazioni di push e pop.
-
La classe (di libreria) Java ArrayList:
come si usa e come e' realizzata.
-
Le classi wrapper in Java.
Introduzione alle strutture dati (disponibili nella libreria Java):
-
La classe (di libreria) Java LinkedList:
come si usa e come e' realizzata.
-
Realizzazione di una pila (mutabile) con una LinkedList.
-
Realizzazione di una coda (mutabile) con una LinkedList.
-
Perche' l'interfaccia (di libreria) Java
List
e' progettata male.
Criterio per stabilire se una "interface" in Java (o un ADT)
e' progettata male:
una interface
I
e' progettata male se,
la conoscenza della particolare classe C che implementa l'interfaccia,
puo' influenzare il progetto di un algoritmo che realizza un certo compito
usando oggetti di tipo
I.
Ad esempio:
l'interfaccia
List e' progettata male, perche' un frammento di
codice
che deve cercare un elemento e in una
List
ordinata di elementi, dovrebbe usare la ricerca binaria
(facendo uso dell'operazione get) se la
List
fosse realizzata con una ArrayList e la ricerca sequenziale
(facendo uso dell'operazione iterator) se la
List
fosse realizzata con una LinkedList.
Riferimenti (LETTURE OBBLIGATORIE):
Studiare:
-
Vettori e array
([Hor] capitolo 12),
-
Introduzione alle strutture dati
([Hor] capitolo 17).
Esercizi assegnati:
-
Esercizio E3.
Realizzare, in Java, un ADT
BigIntegerMatrix
che rappresenti una
matrice quadrata di
BigInteger
di dimensione n*n.
Realizzare una classe di prova
TestBigIntegerMatrix.
-
Esercizio E4.
Realizzare una classe Java che contenga dei metodi static che implementano
gli algoritmi
fibonacci1,
fibonacci2,
fibonacci3,
fibonacci4,
fibonacci5,
fibonacci6,
fibonacci7
(illustati durante le lezioni del modulo 1)
utilizzando, quando opportuno, la classe BigInteger
e
l'ADT BigIntegerMatrix
sviluppato nell'esercizo E3.
Realizzare un modulo di test.
-
Esercizio E5.
Modificare (sia la versione in Java che quella in C de) gli ADT
PilaM
e
PilaI
realizzati nell'esercizio E2, in modo che gli elementi memorizzati
nella pila siano "oggetti generici" (ovvero, di tipo
Object
in Java, e di tipo
void * in C).
Realizzare i moduli di test.
-
Esercizio E6.
Modificare (sia la versione in Java che quella in C de) l'ADT
PilaM
realizzato nell'esercizio E5, in modo da utilizzare la
tecnica dell'array dinamico (raddoppio capacita' quando l'array e' pieno
e dimezzamento quando solo 1/4 della capacita' dell'array e' utilizzata).
Realizzare i moduli di test.
-
Esercizio E7.
Modificare la versione in Java dell'ADT
PilaM
realizzato nell'esercizio E6, in modo da utilizzare
una ArrayList.
Realizzare il modulo di test.
-
Esercizio E8.
Realizzare, in Java, l'ADT
CodaM,
che rappresenta una coda mutabile di "oggetti generici",
e due sue diverse implementazioni:
-
una basata su "array circolare" dinamico, e
-
una basata sulla classe
LinkedList.
Realizzare i moduli di test.
-
Esercizio E9 (TESTO AGGIORNATO IL 4/11/2004).
Scrivere, in Java, un'interfaccia
Heap,
che specifichi le operazioni di una struttura
dati heap (mutabile) di "oggetti generici".
Realizzare una classe ArrayBinaryHeap che implementi
l'interfaccia
Heap.
Prevedere due tipi diversi di costruttore: uno
che generi un heap atto a
memorizzare oggetti che implementano l'interfaccia
Comparable,
l'altro che
che generi un heap atto a
memorizzare oggetti che sono confrontati attraverso un
oggetto comparatore.
Realizzare i moduli di test.
|