Si vuole realizzare il tipo di dato Dizionario con un albero binario di ricerca. Si supponga
che non vengano ammesse chiavi duplicate. Dato il package Dizionario sviluppato durante il
corso e la seguente classe DizNode.java che memorizza un nodo dell' albero di ricerca,
package Dizionario;
class DizNode {
int key; // chiave associata al nodo
Object elem; // elemento associato alla chiave
DizNode parent; // padre del nodo
DizNode left; // figlio sinistro del nodo
DizNode right; // figlio destro del nodo
// post: ritorna un albero di un solo nodo, con chiave key, elemento ob,
// sottoalberi sinistro e destro vuoti e padre null
DizNode(int key, Object ob) {
this.key = key;
elem = ob;
parent = left = right = null;
}
}
si richiede di completare la seguente classe DizABR.java che implementa tutti i metodi
dell'interfaccia Dizionario.java
package Dizionario;
public class DizABR implements Dizionario {
private DizNode root; // radice dell'albero
private int count; // numero di nodi dell'albero
...
...
}
Consegnare:
- La classe DizABR.java completa
- La correttezza dei metodi iterativi di DizABR.java
- Una classe che permetta di testare tutti i metodi di DizABR.java
Si vuole realizzare il tipo di dato Dizionario con una tabella hash in cui le collisioni
vengono gestite con liste di collisione. Dato il package Dizionario sviluppato durante
il corso e data la seguente classe che memorizza una coppia (key,elem) nel nodo di una
lista doppiamente concatenata
package Dizionario;
class DizRecordLC {
int key; // chiave
Object elem; // elemento
DizRecordLC next; // riferimento all'elemento successivo
DizRecordLC prev; // riferimento all'elemento precedente
// post: costruisce un nuovo nodo con chiave key, elemento ob,
// elemento successivo nextel e precedente prevel
DizRecordLC(int key, Object ob, DizRecordLC nextel, DizRecordLC prevel) {
this.key = key;
elem = ob;
next= nextel;
if (next != null)
next.prev = this;
prev = prevel;
if (prev != null)
prev.next = this;
}
// post: costruisce un nuovo nodo con chiave key, elemento ob
// e next e prev nulli
DizRecordLC(int key, Object ob) {
this(key, ob, null, null);
}
}
si richiede di completare l'implementazione della seguente classe DizHashLC.java, utilizzando
liste di collisione doppiamente concatenate e un'opportuna funzione hash.
package Dizionario;
import java.math.BigInteger;
public class DizHashLC implements Dizionario, Hash {
private DizRecordLC[] S; // tabella hash
private int count; // num. coppie presenti nel dizionario
private int tot_accessi; // num. totale accessi alla tabella hash
...
...
}
Consegnare:
- La classe DizHashLC.java completa
- Una classe che permetta di testare tutti i metodi di DizHash.java
Dato il package BinTrees sviluppato durante il corso, si richiede di aggiungere alla classe
BinaryTree.java i seguenti metodi:
// post: ritorna una stringa contenente, per ciascun nodo n dell'albero, la coppia (key(n), altezza(n))
// dove key(n) e' il valore della chiave di n e altezza(n) e' l'altezza del sottoalbero radicato
// in n, compreso n stesso. Se l'albero e' vuoto ritorna null.
public String chiaveAltezza() {...}
// post: ritorna una stringa contenente le chiavi di tutti nodi
// dell'albero che hanno esattamente due nipoti
public String dueNipoti() {...}
// post: ritorna true se l'albero e' completo; ritorna false altrimenti
public boolean isComplete() {...}
Si richiede di utilizzare la ricorsione. Eventuali metodi di appoggio devono avere livello di
visibilità private. I metodi devono avere complessità lineare nel numero dei
nodi dell'albero.
Consegnare:
- la classe BinaryTree.java completa
- la prova di correttezza dei metodi sviluppati
- una classe che permetta di testare tutti i metodi di BinaryTree.java
Esercizio 1:
Completare l'implementazione della seguente classe DuePile.java che gestisce le operazioni
relative a due pile mediante un solo array. Si richiede di realizzare le operazioni in
modo efficiente.
public class DuePile {
private static final int MAX_SIZE = 100;
private Object[] PP; // array che rappresenta le due pile
private count1; // contatore elementi della pila 1
private count2; // contatore elementi della pila 2
private top1; // puntatore alla testa della pila 1
private top2; // puntatore alla testa della pila 2
// post: inizializza opportunamente le variabili di classe
public DuePile() {...}
// post: ritorna true sse la pila 1 e' vuota
public boolean isEmpty1() {...}
// post: ritorna true sse la pila 2 e' vuota
public booelan isEmpty2() {...}
// post: ritorna il numero di elementi della pila 1
public int size1() {...}
// post: ritorna il numero di elementi della pila 2
public int size2() {...}
// post: svuota la pila 1
public void clear1() {...}
// post: svuota la pila 2
public void clear2() {...}
// pre: ob non nullo
// post: inserisce ob nella pila 1; ritorna true se l'operazione
// e' andata a buon fine, false altrimenti
public boolean push1(Object ob) {...}
// pre: ob non nullo
// post: inserisce ob nella pila 2; ritorna true se l'operazione
// e' andata a buon fine, false altrimenti
public boolean push2(Object ob) {...}
// post: elimina e ritorna l'elemento in cima alla pila 1;
// se la pila e' vuota ritorna null
public Object pop1() {...}
// post: elimina e ritorna l'elemento in cima alla pila 2;
// se la pila e' vuota ritorna null
public Object pop2() {...}
// post: ritorna l'elemento in cima alla pila 1;
// se la pila e' vuota ritorna null
public Object top1() {...}
// post: ritorna l'elemento in cima alla pila 2;
// se la pila e' vuota ritorna null
public Object top2() {...}
}
Consegnare:
- La classe DuePile.java completa
- L'analisi della complessità dei metodi della classe DuePile.java
- Una classe che permetta di testare tuttti i metodi di DuePile.java
Esercizio 2:
Completare l'implementazione della seguente classe DueCode.java che gestisce le operazioni
relative a due code mediante un solo array. Si richiede di realizzare le operazioni in
modo efficiente.
public class DueCode {
private static final int MAX_SIZE = 100;
private Object[] QQ; // array che rappresenta le due code
private count1; // contatore elementi della coda 1
private count2; // contatore elementi della coda 2
private head1; // puntatore alla testa della coda 1
private head2; // puntatore alla testa della coda 2
private tail1; // puntatore alla coda della coda 1
private tail2; // puntatore alla coda della coda 2
// post: inizializza opportunamente le variabili di classe
public DueCode() {...}
// post: ritorna true sse la coda 1 e' vuota
public boolean isEmpty1() {...}
// post: ritorna true sse la coda 2 e' vuota
public booelan isEmpty2() {...}
// post: ritorna il numero di elementi della coda 1
public int size1() {...}
// post: ritorna il numero di elementi della coda 2
public int size2() {...}
// post: svuota la coda 1
public void clear1() {...}
// post: svuota la coda 2
public void clear2() {...}
// pre: ob non nullo
// post: inserisce ob nella coda 1; ritorna true se l'operazione
// e' andata a buon fine, false altrimenti
public boolean enqueue1(Object ob) {...}
// pre: ob non nullo
// post: inserisce ob nella coda 2; ritorna true se l'operazione
// e' andata a buon fine, false altrimenti
public boolean enqueue2(Object ob) {...}
// post: elimina e ritorna l'elemento in cima alla coda 1;
// se la coda e' vuota ritorna null
public Object dequeue1() {...}
// post: elimina e ritorna l'elemento in cima alla coda 2;
// se la coda e' vuota ritorna null
public Object dequeue2() {...}
// post: ritorna l'elemento in cima alla coda 1;
// se la coda e' vuota ritorna null
public Object front1() {...}
// post: ritorna l'elemento in cima alla coda 2;
// se la coda e' vuota ritorna null
public Object front2() {...}
}
Consegnare:
- La classe DueCode.java completa
- L'analisi della complessità dei metodi della classe DueCode.java
- Una classe che permetta di testare tuttti i metodi di DueCode.java
