Pages: [1] 2   Go Down
Print
Author Topic: alberi nari  (Read 4086 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« on: 22-05-2009, 10:25:07 »

ma possono essere solo di stringhe o caratteri?cioè non capisco in base a quali criteri si dovrebbe fare l'inserimento...in tutti gli esempi di codice non c'è un inserimento generico per tipi comparable o object ad esempio...
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #1 on: 22-05-2009, 10:42:58 »


Può essere di qualsiasi tipo ma SOLITAMENTE ( quindi non è legge ) vista la complessità degli alberi n-ari il professore li mette sempre di stringhe.
Mentre, quasi sempre i grafi e gli alberi binari sono di object e quindi richidono la comparable.
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #2 on: 22-05-2009, 10:47:32 »

ok..ma potresti spiegarmi in base a che cosa vengono inseriti gli oggetti, che siano stringhe o altro, in questi alberi?non ho capito il criterio...
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #3 on: 22-05-2009, 10:55:47 »


quando sei in presenza di alberi n-ari solitamente avrai in ingresso due stringhe ( l'esempio classico è il file di testo con due stringhe in ogni riga ). La prima rappresenta il padre, la seconda rappresenta il figlio.
Al momento dell'inserimento dovrai controllare se il padre esiste all'interno dellalbero nel caso in cui quest'ultimo non sia vuoto, in caso positivo dovrai associare al padre il nuovo figlio.
Nel caso in cui non esista dovrai associare il padre alla radice e il figlio al padre.
Se tu guardi nell'implementazione che ho fatto qualche post fa, vedrai proprio che il ragionamento utilizzato è questo.
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #4 on: 22-05-2009, 11:00:42 »

si l'avevo guardata ma solo con il codice non riuscivo a capire bene!ma scaninsert che cosa fa?
« Last Edit: 22-05-2009, 11:03:32 by Vivynz » Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
thomas89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 341



« Reply #5 on: 22-05-2009, 11:27:37 »

Ma invece io ho un problema cn l'inserimento.. ho ricopiato per filo e per segno la slide del prof.. ma mi dice sempre Missing return statement.. non capisco xkè al prof nn la dice qst cosa ahah pray
Logged

Solo due cose sono infinite: l'universo e la stupidità umana, ma riguardo l'universo ho ancora dei dubbi.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #6 on: 22-05-2009, 11:30:32 »

ho provato a implementare inserimento e ricerca così...tentando di ragionare da sola senza vedere gli altri codici!può funzionare?
Code:
public void insert(Comparable p,Comparable f)
{
NodoNT t=search(p);
if(t!=null)
{
t.figliosx=new NodoNT(f,null,t.figliosx);
}
else
{
root.figliosx=new NodoNT(p,new NodoNT(f),root.figliosx);
}
}
public NodoNT search(Comparable c)
{
return search(c,root);
}
private NodoNT search(Comparable c,NodoNT p)
{
if(p!=null)
{
if(c.compareTo(p.info)==0)
return p;
else
{
NodoNT t=search(c,p.figliosx);
if(t!=null)
return t;
else
return search(c,p.fratellodx);
}
}
return null;
}
per la cancellazione invece non so da dove cominciare..
« Last Edit: 22-05-2009, 11:33:42 by Vivynz » Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #7 on: 22-05-2009, 13:41:55 »

ragazzi, io non ho capito invece come mai, non usate i metodi appositi, per fare uso delle variabili di istanza.
Per esempio quando fate "n.firstson=..." dove firstson è una variabile di istanza della classe NTNode.
Non si sarebbe potuto usare un metodo tipo setFirstSon(NTNode n):void dichiarato nella classe NTNode?
Grazie per le eventuali risposte.
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #8 on: 22-05-2009, 13:48:33 »

si quello che dici è giusto ed è anche una soluzione più elegante e magari anche un pò più corretta da un punto di vista formale ma ciò non vieta di utilizzare in questo modo le variabili il risultato è cmq lo stesso!
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #9 on: 22-05-2009, 14:10:28 »

Grazie per avermi risposto.
Ora ti vorrei chiedere se negli alberi n-ari la radice rimane sempre a null (radice fittizia) , cioè sono solo i nodi sottostanti ad avere un valore interno.
Grazie
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #10 on: 22-05-2009, 14:14:57 »

in teoria dovrebbe essere fittizia ma ciò mi crea dei problemi...
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #11 on: 22-05-2009, 14:52:12 »

In pratica ogni nodo sottostante alla radice ha come valore un carattere. Immettendo nuove stringhe l'algoritmo di inserimento verifica se ci sono caratteri in comune alle stringhe inserite in precedenza e fa gli opportuni settaggi ai fratelli, in modo tale da non avere dei duplicati di stringhe
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #12 on: 23-05-2009, 18:14:37 »

Ragazzi, ho un dubbio sull'implementazione che da il prof. sull'albero n-ario che si trova sulle slide.
In particolare volevo chiedervi se in questo caso l'Object che viene preso come parametro dal Nodo dell'albero, deve necessariamente essere un carattere.

Mi spiego meglio. Nel codice dell'inserimento che da il prof. c'è la seguente cosa:
Code:
if(p.info == x.charAt(0))...
in questa condizione se l'info del nodo "p" fosse una Stringa, il compilatore darebbe errore (in pratica l'info dovrebbe restituire un carattere in questo caso, visto il confronto che viene fatto... ) . Quindi per questo volevo capire se, l'inserimento e in generale il codice di questo albero è relativo ad un Trie anzichè ad un albero n-ario generico.
Grazie.
 ciao
« Last Edit: 23-05-2009, 18:16:29 by gam » Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #13 on: 25-05-2009, 10:41:03 »

@ gam: non ti rispondo perchè non vorrei dire qualche cavolata 

per quanto riguarda l'implementazione di un albero nario con la lista dei figli...ma come si fa???non capisco...perchè la lista avrebbe dei nodi con puntatore al nodo successivo..invece dovrebbero essere ognuno un nodo con puntatore alla lista dei figli..ma mi sto incasinando..dovrei poi usare un iteratore per scorrere la lista??e come si usa?
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #14 on: 29-05-2009, 09:51:37 »

ho implementato così l'albero nario con lista dei figli..
Code:
public class NTL
{
protected NodoNTL root;
public NTL(NodoNTL r)
{
root=r;
}
public NTL()
{
this(null);
}
public NodoNTL getRoot()
{
return root;
}
public boolean isEmpty()
{
return (root==null);
}
public void preorder()
{
preorder(root);
}
private void preorder(NodoNTL p)
{
if(p!=null)
{
p.visit();
Nodo n=p.figli.getHead();
for(;n!=null;n=n.getNext())
preorder((NodoNTL)(n.getInfo()));
}
}
public void postorder()
{
postorder(root);
}
private void postorder(NodoNTL p)
{
if(p!=null)
{
Nodo n=p.figli.getHead();
for(;n!=null;n=n.getNext())
postorder((NodoNTL)(n.getInfo()));
p.visit();
}
}
public void insert(Comparable p, Comparable f)
{
NodoNTL t=search(p);
if(t!=null)
{
t.figli.insertHead(new NodoNTL(f));
}
else
{
LinkedList l=new LinkedList();
l.insertHead(new NodoNTL(f));
root.figli.insertHead(new NodoNTL(p,l));
}
}
public NodoNTL search(Comparable c)
{
return search(c,root);
}
private NodoNTL search(Comparable c,NodoNTL p)
{
if(p!=null)
{
if(c.compareTo(p.info)==0)
return p;
else
{

Nodo n=p.figli.getHead();
NodoNTL t=null;
if(n!=null)
{
t=search(c,((NodoNTL)n.getInfo()));
if(t!=null)
return t;
else
{
NodoNTL temp=null;
for(;temp==null&&n.getNext()!=null;n=n.getNext())
temp=search(c,((NodoNTL)n.getNext().getInfo()));
return temp;
}
}
}
}
return null;
}

}
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Pages: [1] 2   Go Up
Print
Jump to: