Pages: [1]   Go Down
Print
Author Topic: Domanda su realizzazione esercizio  (Read 788 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 18-10-2010, 15:53:31 »

Nella sezione alberi binari di ricerca c'è questo esercizio:

Code:
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.


Avrei pensato di considerare l'albero, implementandolo come array,i suoi nodi contengono elementi di tipo linkedList dove sono memorizzati i vari elementi, effettuando un inserimento ordinato in lista che mi consente di avere l'elemento minimo dell'insieme in testa.
Ora mi chiedevo, dato che dovrò fare questo inserimento devo confrontare gli elementi della linkedlist, quindi usare l'interfaccia Comparable. La mia domanda è come si possa fare:
Cioè, per potere usare il compareTo() posso fare estendere alla classe nodo l'interfaccia Comparable?

Code:
class SetNode<E extends Comparable>

Così facendo posso ad esempio scrivere qualcosa come:

Code:
if(nodo1.getElement().compareTo(nodo2.getElement())

Oppure il metodo non verrà trovato?

Forse devo specificare il tipo nel comparable...

Code:
class SetNode<E extends Comparable<E>>
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #1 on: 19-10-2010, 13:51:34 »

Ho provato a fare l'esercizio, ma ci saranno molte cose sbagliate, non mi compila nemmeno....mi potreste dare una dritta?

Non gli va bene come creo, nel main, gli oggetti albero, insieme e linkedlist, problemi di generics....ma non capisco perchè non va:

Code:
import java.util.*;
import java.io.*;

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'elemento più piccolo dell'albero
}


//CLASSE NODO
class Node<E>
{
private E element;
private Node<E> next;

public Node(E element)
{
this.element=element;
next=null;
}

public void setElement(E element){this.element=element;}

public E getElement(){return element;}

public void setNext(Node<E> next){this.next=next;}

public Node<E> getNext(){return next;}

}


//CLASSE LISTA
class LinkedList<E extends Comparable>
{
private Node<E> head, tail;
private final int CAPACITY;
private int elementi;

public LinkedList()
{
head=tail=null;
CAPACITY=20;
elementi=0;
}

public Node<E> getHead(){return head;}

public Node<E> getTail(){return tail;}

public int getElementi(){return elementi;}

public void addNode(Node<E> node){
assert elementi<CAPACITY;

if(elementi==0){
head=node;
tail=node;
}

else if(tail.getElement().compareTo(node.getElement())<0){
tail.setNext(node);
tail=node;
}

else if(head.getElement().compareTo(node.getElement())>0){
node.setNext(head);
head=node;
}

else{
boolean inserito=false;

Node<E> current;
Node<E> prev=head;

for(current=head; current!=null && !inserito; current=current.getNext())
{
if(current.getElement().compareTo(node.getElement())>0){
prev.setNext(node);
node.setNext(current);
inserito=true;
}

else prev=current;
}
}

   elementi++;
}

public E removeHead(){

if(elementi==0) return null;
Node<E> tmp=head;
head=head.getNext();
tmp.setNext(null);
elementi--;
return (E)tmp;
}

public String toString(){
String s="";
if(elementi==0)return s;
Node<E> tmp=getHead();

while(tmp!=null){
s+=tmp.getElement()+" ";
tmp=tmp.getNext();
}

return s;
}
}

//CLASSE SETNODE
class SetNode<E extends Comparable>
{
private E element;
private SetNode<E> left;
private SetNode<E> right;
private SetNode<E> parent;
private int position;

public SetNode(E element)
{
this.element=element;
left=null;
right=null;
parent=null;
position=0;
}

public int getPosition(){return position;}

public void setPosition(int p){position=p;}

public void setParent(SetNode<E> parent){this.parent=parent;}

public SetNode<E> getParent(){return parent;}

public E getElement(){return element;}

public boolean hasLeft(){return left!=null;}

public boolean hasRight(){return right!=null;}

public SetNode<E> getLeft(){
if(hasLeft()) return left;
return null;
}

public SetNode<E> getRight(){
if(hasRight()) return right;
return null;
}

public void setLeft(SetNode<E> left){this.left=left;}

public void setRight(SetNode<E> right){this.right=right;}
}

class Albero<E extends Comparable> implements BSTSet<E>
{
private SetNode<E> root;
private int nodes;
private int elements;
private E[] albero;

public Albero(int nodes)
{
root=null;
this.nodes=nodes;
elements=0;
albero=(E[]) new Object[nodes];

}

public int nodes(){return nodes;}

public int elements(){return elements;}

public E getMinimum (){
if(nodes==0) return null;

E element;
SetNode<E> tmp=root;

while(tmp.hasLeft())
tmp=tmp.getLeft();

return (E)((LinkedList<E>)tmp.getElement()).getHead();
}

public SetNode<E> search (E e){return null;}

public void insert (SetNode<E> node){
if(nodes==0){
root=node;
root.setPosition(0);
}


else{
SetNode<E> current=root;
boolean inserito=false;

while(!inserito){
if(((LinkedList<E>)current.getElement()).getHead().getElement().compareTo(((LinkedList<E>)node.getElement()).getHead().getElement())<0)
{
if(!(current.hasRight())){
current.setRight(node);
albero[current.getPosition()+1]=(E)node;
inserito=true;
}

else current=current.getRight();
}

else if(((LinkedList<E>)current.getElement()).getHead().getElement().compareTo(((LinkedList<E>)node.getElement()).getHead().getElement())>0)
{
if(!(current.hasLeft())){
current.setLeft(node);
albero[current.getPosition()+1]=(E)node;
inserito=true;
}
else current=current.getLeft();
}
}
}

    nodes++;
    elements+=((LinkedList<E>)node.getElement()).getElementi();
}


public SetNode<E> getRoot(){return root;}

public SetNode<E> getNodeMin(){
if(nodes==0) return null;

else{
SetNode<E> tmp=root;
while(tmp.hasLeft())
tmp=tmp.getLeft();
return tmp;
}
}

public SetNode<E> getNodeMax(){
if(nodes==0) return null;

else{
SetNode<E> tmp=root;
while(tmp.hasRight())
tmp=tmp.getRight();
return tmp;
}
}

public SetNode<E>[] inorder(){
SetNode[] array=(SetNode<E>[]) new SetNode[nodes];

int i=0;

SetNode<E> current=getNodeMin();
SetNode<E> dad=current;

while(current!=getNodeMax()){

if(array[0]==null)
array[i++]=current;

if(current.getParent()!=null){

current=current.getParent();
dad=current;
while(current.hasRight()){

current=current.getRight();
array[i++]=current;
}

current=dad;
}

else array[i]=current.getRight();
}

return array;
}

public String toString()
{
String s="";
SetNode<E>[] array=inorder();

for(int i=0; i<array.length; i++)
s+=((LinkedList<E>)array[i].getElement()).toString();

return s;
}

public E extractMinimum(){
if(nodes==0) return null;

SetNode<E> tmp=root;
E minimum=null;

while(tmp.hasLeft())
tmp=tmp.getLeft();

minimum=((LinkedList<E>)tmp.getElement()).removeHead();

elements--;
return minimum;
}
}

public class Programma
{
FileReader reader=null;
BufferedReader buff=null;
PrintWriter out=null;
StringTokenizer str;

public void costruiscialbero(String input, String output)
{
try{
reader=new FileReader(input);
buff=new BufferedReader(reader);
out=new PrintWriter(output);

int nodi=0;

while(buff.ready()){
nodi++;
buff.readLine();
}

System.out.println("Il numero di nodi è "+nodi);

Albero<SetNode> albero=new Albero<SetNode>(nodi);

LinkedList lista=new LinkedList();

SetNode<LinkedList> insieme=new SetNode<LinkedList>(lista);

reader=new FileReader(input);
buff=new BufferedReader(reader);

while(buff.ready())
{
str=new StringTokenizer(buff.readLine(), " ");
while(!(str.nextToken().equals(";"))){
Node nodo=new Node(str.nextToken());
insieme.getElement().addNode(nodo);
}

albero.insert((SetNode)insieme);
}


int a=0;

while(a<5){
albero.extractMinimum();
a++;}

out.print(albero.nodes()+" "+albero.elements()+" "+albero.getMinimum()+'\r'+'\n');

}

catch(FileNotFoundException e1)
{
System.out.println("Error...file not found");
}

catch(IOException e2)
{
System.out.println("Error...input/output");
}
}

public static void main(String [] args)
{
Programma main =new Programma();
long start=System.currentTimeMillis();
main.costruiscialbero("input.txt", "SS7_003292.txt");
long end=System.currentTimeMillis();
System.out.println("Il tempo d'esecuzione è "+(end-start)+" ns");
}
}

Gli errori sono...
Code:
Programma.java:357: type parameter SetNode is not within its bound
Albero<SetNode> albero=new Albero<SetNode>(nodi);
       ^]Programma.java:357: type parameter SetNode is not within its bound
Albero<SetNode> albero=new Albero<SetNode>(nodi);
                                  ^]Programma.java:361: type parameter LinkedList is not within its bound
SetNode<LinkedList> insieme=new SetNode<LinkedList>(lista);
        ^]Programma.java:361: type parameter LinkedList is not within its bound
SetNode<LinkedList> insieme=new SetNode<LinkedList>(lista);
                                        ^
« Last Edit: 19-10-2010, 22:05:08 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: