C'č uno dei soliti esercizi contorti, che stavo provando a fare ma ho parecchie difficoltą:
Ecco le interfacce:codice:Si realizzi un'implementazione delle due interfacce TNode<E> e Tree<E> mostrate nella pagina seguente. Le implementazioni fornite, che dovranno essere denominate rispettivamente ArrayTNode<E> e ArrayTree<E>, dovranno utilizzare un array per la memorizzazione dei nodi dell'albero. I singoli nodi dovranno quindi risiedere all'interno di un array mentre i puntatori ai nodi firstSon, sibling e parent dovranno essere espressi attraverso indici dell'array. In seguito si realizzi un programma Java che preso in input un file contenente una lista di nomi (composti da nome e cognome) costruisca un albero completo (ArrayTree<String>) dove ogni nodo possiede esattamente 3 figli. Gli elementi verranno forniti in modo da costruire l'albero procedendo per livelli (dalla radice alle foglie), e costruendo ciascun livello da sinistra verso destra. Il programma dovrą stampare in un file di output la visita preorder dell'albero ottenuto, utilizzando il metodo toString() della classe ArrayTree. Input Il file di input contiene una lista di stringhe, una per riga, ciascuna contenente un nome seguito da un cognome e separati da uno spazio. Output Il file di output dovrą contenere una lista di stringhe, una per riga, risultanti dalla visita preorder dell'albero ottenuto.
Ora gią secondo me ci sono errori, intanto element č un metodo che non puņ prendere parametri. Poi non riesco a capire come implementare il metodo AddChild.codice:public interface TNode<E> { public E element(String nome); // ritorna il valore dell'elemento contenuto nel nodo public int sibling(); // ritorna l'indice nell'array del successivo fratello public int firstSon(); // ritorna l'indice nell'array del primo figlio public int addChild(); // inserisce un nuovo figlio in coda alla lista dei figli public int parent(); // ritorna l'indice nell'array del nodo padre public int degree(); // ritorna il numero di figli del nodo public void setElement(E element); // setta il valore dell'elemento contenuto nel nodo } public interface Tree<E> { public int size(); // ritorna il numero di nodi presenti nell'albero public TNode<E> root(); // ritorna il nodo radice dell'albero public String toString(); // stampa l'albero, un elemento per riga, utilizzando una visita poreorder public TNode<E> search(E val); // ritorna il nodo che contiene il valore val, null altrimenti public E minimum(); // ritorna il valore minore presente nell'albero }
Intanto cosa aggiunge se non prende parametri? Se l'array io lo credo nella classe che implementa Tree, come faccio in una classe che non č altro che la classe nodo, a fare un inserimento se ancora non ho alcun array su cui lavorare?
Ora siccome restituisce un intero io immagino che indichi qual' č la posizione dove inserire nell'array il nodo.
Il mio problema č, funziona davvero cosģ? Come faccio a mano a mano, dopo che inserisco i vari nodi a modificare i relativi indici a parent, sibling....eccetera?
Ho scritto qualcosa..
codice:public class ArrayTNode<E> implements TNode<E> { private E element; private int sibling; private int firstSon; private int parent; private int degree; private int position; private ArrayTNode<E> next; public ArrayTNode(E element){ this(element,0); } public ArrayTNode(E element, int position){ this(element,position,-1); } public ArrayTNode(E element, int position, int sibling){ this(element, position, sibling, -1); } public ArrayTNode(E element, int position, int sibling, int firstSon){ this(element, position, sibling, firstSon, -1); } public ArrayTNode(E element, int position, int sibling, int firstSon, int parent){ this(element, position, sibling, firstSon, parent, 0); } public ArrayTNode(E element, int position, int sibling, int firstSon, int parent, int degree){ this(element,position, sibling, firstSon, parent, degree, null); } public ArrayTNode(E element, int position, int sibling, int firstSon, int parent, int degree, ArrayTNode<E>next){ this.element=element; this.position=position; this.sibling=sibling; this.firstSon=firstSon; this.parent=parent; this.degree=degree; this.next=next; } public E element(){return element;} public int getPosition(){return position;} public ArrayTNode<E> getNext(){return next;} public ArrayTNode<E> getNode(){ return this;} public int sibling(){return sibling;} public int firstSon(){return firstSon;} public int addChild(){ int startposition=this.getPosition(); ArrayTNode<E> tmp=getNode(); int posbrother=tmp.sibling(); if(posbrother==-1) //se il nodo non ha figli inserisco nella posizione dopo return startposition+1; else{ while(posbrother!=-1){ tmp=tmp.getNext(); posbrother=tmp.sibling(); //sennņ arrivņ all'ultimo figlio e lo aggiungo dopo startposition=tmp.getPosition(); } } return startposition+1; } public int parent(){return parent;} public int degree(){return degree;} public void setElement(E element){this.element=element;} }
codice:public class ArrayTree<E extends Comparable<E>> implements Tree<E> { public static final int max=100; private int size; protected ArrayTNode<E>[] array; public ArrayTree() { array=(ArrayTNode<E>[]) new Object[max]; size=0; } public int size(){return size;} public TNode<E> root(){return array[0];} public String toString(){ } public TNode<E> search(E val){ for(int i=0; i<array.length; i++){ if(array[i].equals(val)) return array[i]; } return null; } public E minimum(){ E min=array[0].element(); for(int i=0; i<array.length; i++){ if(min.compareTo(array[i].element())>0) min=array[i].element(); } return min; } }
Rispondi quotando
