Vorrei chiedere due cose, su un esercizio di questo tipo:
L'interfaccia è:codice:Si fornisca un'efficiente implementazione dell'interfaccia BSTSet<E>, come mostrata nella pagina successiva, rappresentante un albero binario di ricerca (BST) i cui nodi sono degli insiemi contenti elementi di tipo generico <E>. Gli insiemi contengono elementi ordinabili. Ciascun insieme è rappresentato dal suo elemento con valore minore. All'interno dell'albero gli insiemi sono inseriti in base al loro elemento rappresentante. Si assuma che ogni insieme non contenga più 20 elementi. L'implementazione dell'albero dovrà essere realizzata utilizzando la struttura [parent/left/right] all'interno della classe nodo, che dovrà essere denominata SetNode<E>. L'implementazione del metodo search() è facoltativa, così come la gestione delle eccezioni all'interno delle classi (Se il metodo search() non viene implementato il corpo dovrà essere lasciato vuoto). Realizzare in seguito, mediante il metodo main() della classe, un programma Java che prenda in input un file di testo contenente un elenco di insiemi di interi da inserire in un albero (costruisce un albero di insiemi di interi) e restituisca in output un file di testo contenente alcune informazioni relative all'albero. Il programma consegnato dovrà compilare correttamente e dovrà produrre il corretto output. In caso contrario la soluzione verrà considerata errata. Specifiche della classe Qualsiasi struttura dati ausiliaria dovrà essere implementata dallo studente. Il file Java (e quindi la classe Java) dovrà essere denominato con il proprio numero di Matricola con un underscore “_” al posto del simbolo “/” (“M01_123456.java”). Nel caso in cui la matricola inizi per 667 utilizzare il prefisso SS7 (“SS7_123456.java”). Il file di input dovrà essere denominato “input.txt” mentre il file di output dovrà essere denominato con la propria matricola (“M01_123456.txt”, oppure “SS7_123456.java”). File di input e output Il file di input contiene l'elenco degli insiemi, uno per riga, contenuti nei nodi dell'albero. Ogni insieme è descritto da una sequenza di valori interi separati da uno spazio e terminanti con un punto e virgola. La prima riga del file di output contiene tre numeri interi: il numero di nodi, il numero di elementi e il valore più piccolo dell'albero. Tali valori sono relativi all'albero iniziale dopo aver applicato 5 operazione extracMinimum(). Segue la visita inorder dello stesso albero con uni insieme per ogni riga
Io avrei pensato di creare la classe SetNode, e all'interno di memorizzare l'insieme, realizzato tramte coda, implementata magari come array. Può andare?codice:import java.util.*; public interface BSTSet<E extends Comparable> { public int nodes (); // ritorna il numero di nodi dell'albero public int elements (); // ritorna il numero complessivo di elementi di tipo E public E getMinimum (); // ritorna l'elemento più piccolo contenuto nei nodi dell'albero public SetNode<E> search (E e); // ritorna il nodo contenente l'elemento e public void insert (SetNode<E> node); // aggiunge all'albero un nuovo nodo public SetNode<E> getRoot (); // ritorna la radice dell'albero public SetNode<E>[] inorder(); // ritorna un array con gli insiemi dell'albero in ordine inorder public E extractMinimum (); // elimina e ritorna l'elemnto più piccolo dell'albero }
Siccome ogni elemento dell'insieme è rappresentato dal più piccolo suppongo si debba fare un inserimento ordinato....allora dovrei usare il compareTo.
Di conseguenza dovrebbe essere solo la classe coda ad estendere Comparable o sbaglio?
Cioè avrei:
codice:class SetNode<E> . . .Si potrebbe fare così o mi darà errori nel trovare il metodo comparTo()?codice:class Queue<E extends Comparable> . . . public void insert(E element){ . . .//uso del compareTo per inserire in coda gli elementi }
Rispondi quotando
