Strutture gerarchiche e ricorsive in JAVA

di il
3 risposte

Strutture gerarchiche e ricorsive in JAVA

Ciao a tutti!!!

Ho una classe java Dynamic che attraverso un parser legge dei dati da un file xml e poi istanzia il relativo oggetto rappresentato appunto in xml.

Per memorizzare questi dati utilizzo una HashMap (chiave,valore) dove alla chiave corrisponde il nome dell' attributo-tag mentre il valore è quello che sta dentro il tag xml.

Ogni volta che invoco la Dynamic svuoto l' HashMap ed inserisco le info relative al nuovo file xml (ne ho 5 intanto che rappresentano:Continent,Nation,City,Airport,Port) e poi posso istanziare il relativo oggetto.

Nel file xml ho anche dei tag che mi indicano l' oggetto padre e l' oggetto figlio relativi:in Nation il padre è Continent ed i figli City che a loro volta hanno come figli Airport e Port)

Come faccio a rappresentare al meglio in Java questa mia gerarchia?Che struttura dati posso utilizzare (la + semplice ma efficiente)?

Se io Dynamic la utilizzo di volta in volta solo per caricare un xml per volta e poi ne svuoto il relativo HashMap dove posso memorizzare tutte le info di tutti i file xml im modo che poi possa andare su e giù per la gerarchia estraendone le info?

Mi consigliate una struttura dati dove memorizzo l' oggetto e magari l' id del padre e del figlio (questo appunto per sapere chi è figlio e chi è padre) o avete altre idee?

Devo creare una struttura gerarchica dove ricorsivamente da Continent passa a tutte le Nation relative e ad ogni Nation mi sviluppa tutti i figli City e cosi via.

Tenete conto che questi miei oggetti dovranno rappresentare delle tabelle DB con tanto di record(dove i campi sono qui gli attributi degli oggetti).

Grazie.

3 Risposte

  • Re: Strutture gerarchiche e ricorsive in JAVA

    Ciao.. se ti serve un personale consiglio sull'implementazione da usare.. secondo me la realizzazione più efficace (anke in termini di complessità computazionele) è usare uno heap.. cioè un vettore che però di fatto si comporta come un albero addossato tutto a sinistra..
    se implementato bene.. i dati, strutture o classi che siano le inserisci nello heap.. e in fase di estrazione di un determinato dato cercato la complessità ammonta al massimo a O(log n).. dove n è i numero dei nodi dell'albero.. quindi la ricerca dei dati è molto veloce..

    Spero di esseri stato d'aiuto...

    Saluti...
  • Re: Strutture gerarchiche e ricorsive in JAVA

    Non so esattamente come implementare uno Heap ma penso che il padre abbia la chiave più grande e via via giù quelle con chiave più piccole.
    Io invece parto da Continent che ha come chiave associata 11 la più piccola e via via i figli (Nation 12,City 13 eccetera).
    Ma credo questo sia risolvibile.
    Può andar bene semplicemente una lista di nodi dove ho per ogni nodo l' oggetto corrispondente e poi 2 valori (uno per il padre e l' altro per i figli)?
    Come faccio cioè a rappresentare questa struttura:

    id_curr , OggettoCurr , id_padre , id_figli

    11 , Continent , 0 , 12
    12 , Nation , 11 , 13
    13 , City , 12 , 14
    14 , Port , 13 , 0
    15 , Airport , 13 , 0

    Dove quindi se mi trovo in Port vedo padre 13 (cioè City che a sua volta ha padre 12 cioè Nation)
    Grazie.
    [/img]
  • Re: Strutture gerarchiche e ricorsive in JAVA

    Ciao.. ok.. va bene anke se usi un albero.. la complessità sale un pochino.. ma alla fine il risultato è uguale..

    Siccome in Java non ci sono i puntatori.. per costruire un albero devi usare la classe Node che dispone dei metodi padre - nodo destro - nodo sinistro.. in questo modo puoi costruire facilmente un albero..

    l'unico problema forse che potresti avere è che la classe node permette di avere solo un figlio destro e uno sinistro.. sinceramente non so se c'è una classe simile a Node che permette di avere infiniti fratelli.. ma il problema lo puoi risolvere facendo corrispondere ad ogni nodo della classe Node un ArrayList che punta alla tua classe dove ci sono i dati...

    Attendo tue notizie (spero positive) sulla realizzazione del tuo albero...

    Saluti...
Devi accedere o registrarti per scrivere nel forum
3 risposte