Pages: [1]   Go Down
Print
Author Topic: Un'altro compito su alberi n-ari?  (Read 1493 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« on: 05-03-2010, 13:43:19 »

Salve ragazzi,
volevo chiedervi se secondo voi il seguente compito è corretto:

Code:
COMPITO A:

Dato un albero n-ario descritto attraverso una stringa con la seguente struttura:

    * Un insieme di nodi fratelli viene rappresentato come una lista di nodi separati da "," contenuti tra "[","]".
    * Ciascun nodo è immediatamente seguito dalla lista dei suoi figli (se esiste).


La stringa è: [a[b[c,d[e,f,z],t[h,l]],q,p[r,k]]]

a ha figlio b,q,p
b ha figlio c,d,t
c ha fratello d,t
...

1. Implementare un metodo bulkload, ricorsivo, che prenda in input la stringa e crei l'alberi n-ario che faccia uso della rappresentazione primofiglio, fratello.

2. Dato in input k, implementare un metodo searchk, ricorsivo, che restituisca, in una lista linkata, tutti i nodi che hanno esattamente k foglie.

il codice è il seguente (ho svolto solo il primo punto in maniera iterativa, per capirlo meglio) :
Code:
//METODO BULKLOAD AVENDO UNA STRINGA MI COSTRUISCE L'ALBERO CON IL  PRINCIPIO PRIMO FIGLIO FRATELLO
    public static  Albero bulkload(String a)
    {
        //devo scorrermi la stringa e vedere che se incontro successivamente un parentesi del tipo "[" vuol dire che devo far in modo di farmi restituire //i figli di quel nodo
        // i nodi fratelli sono separati da una semplice virgola
        Albero alb =new Albero();
        //all'inizio inserisco la radice perchè mi serve poi per il metodo insert  che deve andare a cercare il padre
        alb.insert(alb, a.charAt(0));
        for(int i=0; i<=a.length()-1; ++i)
        {
            if(a.charAt(i)!=','&&a.charAt(i)!=']')
            {
                if(a.charAt(i+1)=='[')//mi devo estarre tutti i figli di quel nodo e poi inserirli in un albero n-ario
                {
                    lista aux=new lista();
                    int o=0; //variabile che serve per tenere traccia della variabile y
                    for(int y=i+1; a.charAt(y)!=']'; ++y)// quando incontra la parentesi chiusa vuol dire che bisogna uscire perchè ho estratto tutti i figli di //quel determinato nodo
                    {
                        if(a.charAt(y)!=',')
                            aux.insertTail(a.charAt(y));
                        o=y;
                    }
                   
                    //ORA DEVO ESTRARRE DALLA LISTA I FIGLI E METTERLI NELL'ALBERO
                    Nodo aux1=aux.getHead();
                    for(int k=0; aux1!=null; aux1=aux1.getNext())
                        alb.insert(alb, aux1.getInfo());
                    //devo aggiornare l'indice i alla posizione successiva alla parentesi quadra chiusa
                    i=++o;
                }
            }
        }
        return alb;
    }
   
   
    //INSERIMENTO RICORSIVO
    public void insert(Albero a, Object x)
    {
        if(IsEmpty())
        {
            root=new NodoAlb(x);
        }
        else
        {
            NodoAlb n=new NodoAlb(x);
            NodoAlb aux=search1(x, root);//MI RESTITUISCE IL POSSIBILE PADRE
            if(aux.getSon()==null)
                aux.setSon(n);
            else
            {
                NodoAlb t=aux.getSon();
                while(t.getBrother()!=null)
                {
                    t=t.getBrother();
                }

                t.setBrother(n);
            }
        }
    }
   
    //METODO CHE RESTITUISCE IL PADRE DEL NODO CHE DOBBIAMO INSERIRE
    public NodoAlb search1(Object q, NodoAlb i)
    {
        if(i!=null)
        {
            if(((Character)q).charValue()==((Character)(i.getInfo())).charValue())//possibile padre
            {
                return i;
            }
            else//continuo la ricerca
            {
                NodoAlb w=search(q, i.getSon());
                if(w!=null)
                    return w;
                else
                {
                    return search(q, i.getBrother());
                }
            }
        }
        return null;
    }

Potete per piacere rispondermi perchè concettualmente penso di esserci pero poi in fase di verifica cadono le mie speranze!! pray
Logged
fedyfausto
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 130


Gandalfr


WWW
« Reply #1 on: 06-03-2010, 17:53:37 »

  //INSERIMENTO RICORSIVO

non vedo ricorsioni dello stesso metodo o_o

P.S. niente ho confuso
« Last Edit: 06-03-2010, 17:57:00 by fedyfausto » Logged

GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #2 on: 09-03-2010, 11:51:19 »

prova cosi...


//METODO BULKLOAD

    public void bulkload(String x){
        root=bulkload(x,0,root);
    }
   
    public NTnode bulkload(String x, int n, NTnode p){
        if(n < x.length()){
            if(x.charAt(n)=='['){
                n++;
                p.primofiglio=new NTnode(x.charAt(n),null,null,p);
            }
            else if(x.charAt(n)==','){
                n++;
                p.fratello=new NTnode(x.charAt(n),null,null,p.padre);
            }
            n++;
            if(x.charAt(n)=='[')
                p.primofiglio=bulkload(x,n,p.primofiglio);
            else if(x.charAt(n)==',')
                p.fratello=bulkload(x,n,p.fratello);
            else if(x.charAt(n)==']'){
                n++;
                p.padre=bulkload(x,n,p.padre);
            }
        }
        return p;
    }
Logged
InfoArtist
Matricola
*
Offline Offline

Gender: Male
Posts: 34



« Reply #3 on: 09-03-2010, 11:53:33 »

Volevo chiedere una cosa sugli alberi n-ari.....per caricare oggetti come si fa? non riesco a gestire l'inserimento nell'albero.... qualcuno mi può dare qualche idea?
Logged
GenteGuasta
Matricola
*
Offline Offline

Posts: 28


« Reply #4 on: 09-03-2010, 12:24:48 »

vuoi un idea o una certezza???

se vuoi la certezza eccola:

importi la libreria java.io.*;

crei l'albero nel main;

crei un bel metodo acquisisciOggetti() nel main come segue...


public class main{

BSTree t = new BSTree();      //creo l'albero

import java.io.*;                   //libreria necessaria x lo stream

public void acquisisciOggetti(){
     ObjectInputStream in = new ObjectInputStream(FileInputStream("Oggetti.dat");     //crei lo stream
     try{
          while(true){
                  t.insert(in.readObject());         //inserisci l'oggetto letto
          }   
     }catch(EOFException){
        in.close();
        break;
     }
}

ecco fatto!!!
     
                   


Logged
InfoArtist
Matricola
*
Offline Offline

Gender: Male
Posts: 34



« Reply #5 on: 09-03-2010, 22:52:00 »

Grazie...ma questo lo sapevo...forse mi sn espresso male... Il mio problema è la gestione degli inserimenti negli alberi nari....ho dei problemi per implementare un metodo ricorsivo di inserimento degli oggetti....i file li so caricare....grazie comunque...
Logged
Pages: [1]   Go Up
Print
Jump to: