View Full Version : [C] Come ri riempie un albero di questo tipo?
leadergl
18-01-2006, 09:32
Raga come si riempie una struttura di questo tipo?
struct TipoAlbero
{
char elemento;
struct TipoAlbero *figlio;
struct TipoAlbero *fratello;
};
Questa è la relativa immagine:
http://www.leadergl.net/immagini/AlberiRadicati.jpg
Sei ancora impegnato con la Tassonomia?
leadergl
18-01-2006, 10:31
no, il "progetto" l'ho consegnato...ma mi sono accorto che dopo aver fatto, con mille fatiche, funzionare tutto ho sbagliato a far costruire l'albero......
e quindi mo so diventato curioso e vorrei sapere come si riempie normalmente un albero di questo tipo...
chi mi aiuta?
leadergl
18-01-2006, 13:51
...up...
e' un albero n-rio; qual è il tuo problema di preciso?
leadergl
18-01-2006, 15:08
riempirlo secondo uno schema...nel senso prima il nodo poi gli eventuali figli per poi passare pian piano ai vari eventuali fratelli....
quindi, prendendo ad esempio il disegno che ho postato, seguendo questo ordine:
http://www.leadergl.net/immagini/AlberiRadicati_Ordine.jpg
non ho capito bene cosa vuoi dire.... Lo riempi come vuoi basta che in fase di lettura segui lo stesso schema altrimenti sballi l'ordine :)
comunque non mi sembra una struttura molto astuta... Il nodo radice ha 1 solo figlio e nessun fratello?
comunque non mi sembra una struttura molto astuta... Il nodo radice ha 1 solo figlio e nessun fratello?
proprio perchè è laradice non ha fratelli...è una rapprsentazione abbastanza standard per gli alberi n-ari
leadergl
18-01-2006, 21:23
proprio perchè è laradice non ha fratelli...è una rapprsentazione abbastanza standard per gli alberi n-ari
si infatti...credo sia la rappresentazione più normale possibile di un albero di questo tipo...
cmq il mio quesito era un altro...qualcuno può aiutarmi?
leadergl
21-01-2006, 09:26
dai raga....help...
crick_pitomba
21-01-2006, 12:04
ciao,
non ho capito la domanda. cioè
da come hai rappresentato la figura sembra un albero strano
ma in effetti è un semplice albero binario in cui ogni nodo ha due rami.
per riempire questa struttura devi definire tu un algoritmo sulla base del quale decidi quando prendere il ramo a sinistra e quando prendere il ramo a destra
se vuoi riempire l'albero ricreando proprio quella figura, puoi utilizzare un algoritmo di riempimento basato sui confronti in cui se ad esempio il valore da inserire è minore del valore del nodo vai a sinistra (figlio), se il valore del nodo è maggiore della radice, vai a destra(fratello).
una possibile soluzione ad esempio è (ho messo dei numeri, per comodità)
immetti per primo il valore in cella 1, poi quello in cella 2 ecc
leadergl
21-01-2006, 12:11
si però io non ho mai detto che il mio è un albero ordinato...
il mio problema è diverso, devo costruire un Albero di Tassonomie, il tutto è spiegato in un altro thread, questo: http://www.hwupgrade.it/forum/showpost.php?p=10893286&postcount=17
cmq in generale se io volessi riempire l'albero così:
radice
figlio_1
figlio_2
figlio_1 (di figlio_2)
figlio_2 (di figlio_2)
figlio_1 (di figlio_2 di figlio_2)
figlio_3 (di figlio_2)
figlio_3
figlio_4
figlio_5
figlio_1 (di figlio_5)
figlio_2 (di figlio_5)
come si farebbe?
crick_pitomba
21-01-2006, 13:00
ho letto un po' l'altro thread e ho cercato di capire cosa ti potesse servire ma mi manca un piccolo dettaglio: non hai mai specificato come i figli sono legati ai genitori.Questo è alla base dell'algoritmo di costruzione dell'albero.
Comunque, se non ho capito male, tu hai la struttura dell'albero stampata sul file e leggendo una riga alla volta voui ricostruire l'albero?
sei già in grado di capire leggendo il file a che livello dell'albero sei?
cioà leggendo la sesta riga di
radice
figlio_1
figlio_2
figlio_1 (di figlio_2)
figlio_2 (di figlio_2)
figlio_1 (di figlio_2 di figlio_2)
figlio_3 (di figlio_2)
figlio_3
figlio_4
figlio_5
figlio_1 (di figlio_5)
figlio_2 (di figlio_5)
sai che sei al terzo livello di figli?
e leggendo poi la settima riga sai che sei risalito di un livello?
P.S. ho provato a contattarti via msn
beppegrillo
21-01-2006, 14:11
La struttura del file è questa, il file devi scorrerlo dall'alto verso il basso, in base al valore (n_filgli) sai se ti trovi su un livello oppure sei sceso a livello+1.
La struttura dati che puoi usare è quella del figlio_sx, fratello_dx, ma non è detto che tu debba distinguerli, visto che non ha nessuna importanta, quindi un nodo avrà una lista concatenata di n figli.
Struct nodo {
char* name;
struct nodo* figli
struct nodo* next
char** proprieta (tassonomia)
}
n_figli radice
n_figli figlio_1
" figlio_2
" figlio_1 (di figlio_2)
" figlio_2 (di figlio_2)
figlio_1 (di figlio_2 di figlio_2)
figlio_3 (di figlio_2)
figlio_3
figlio_4
figlio_5
figlio_1 (di figlio_5)
figlio_2 (di figlio_5)
Non mi e' ancora chiaro com'e' il file dei dati.
Perche' non ne posti un pezzetto, giusto per capire cosa si deve leggere?
Il resto non mi pare difficile, per esempio:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct albero {
char nome[5];
struct albero *fratello;
struct albero *figlio;
} alberoStrano;
typedef struct famiglia {
char *nome;
int figli;
} famiglia;
famiglia dati[] = {
{"1", 5}, {"11",0}, {"12",3}, {"121",0}, {"122",1},
{"1221",0}, {"123",0}, {"13",0}, {"14",0},{"15",2},
{"151",0},{"152",0},{NULL,0}
};
int indice;
void leggiNodo(famiglia *dati, alberoStrano **nodo, int fratelli)
{
int figli;
if (dati[indice].nome == NULL)
return;
*nodo = malloc(sizeof(alberoStrano));
strcpy((*nodo)->nome, dati[indice].nome);
figli = dati[indice++].figli;
if (figli > 0) {
leggiNodo(dati, &((*nodo)->figlio), figli-1);
} else
(*nodo)->figlio = NULL;
if (fratelli > 0)
leggiNodo(dati, &((*nodo)->fratello), fratelli-1);
else
(*nodo)->fratello = NULL;
}
void stampaNodo(alberoStrano *nodo)
{
printf("%s", nodo->nome);
if (nodo->figlio) {
printf(" (");
stampaNodo(nodo->figlio);
putchar(')');
}
if (nodo->fratello) {
putchar(' ');
stampaNodo(nodo->fratello);
}
}
int main()
{
alberoStrano *radice;
indice = 0;
leggiNodo(dati, &radice, 0);
stampaNodo(radice);
putchar('\n');
/* qui si dovrebbero liberare le risorse allocate,
ma lo lascio come esercizio ;) */
return 0;
}
beppegrillo
21-01-2006, 15:43
Non mi e' ancora chiaro com'e' il file dei dati.
Perche' non ne posti un pezzetto, giusto per capire cosa si deve leggere?
Il resto non mi pare difficile, per esempio:
In allegato c'è il testo.
P.s Ma perchè un albero n-ario è strano? :D
In allegato c'è il testo.
E' un file di Word. Ho provato ad aprirlo con OpenOffice, ma dove dice
"ad esempio:", ci sono solo alcune righe vuote. :D
P.s Ma perchè un albero n-ario è strano? :D
Be' quello non e' un albero n-ario, che sarebbe un albero dove ogni nodo
ha esattamente n figli.
E' un albero ordinato, che puo' essere visto come un albero binario organizzato
in modo particolare (da qui lo strano). :cool:
beppegrillo
21-01-2006, 17:12
Be' quello non e' un albero n-ario, che sarebbe un albero dove ogni nodo
ha esattamente n figli.
E' un albero ordinato, che puo' essere visto come un albero binario organizzato
in modo particolare (da qui lo strano). :cool:
Non è un albero ordinato, ol nemmeno n-ario, poichè i figli sono variabili.
Comunque era un rtf, l'ho rinominato.
Non è un albero ordinato, ol nemmeno n-ario, poichè i figli sono variabili.
Secondo Sedgewick, quello e' un albero ordinato.
Comunque ...basta capirsi. :cool:
Comunque era un rtf, l'ho rinominato.
Ok, l'ho rinominato, ma continuo a non vedere l'esempio... :mbe:
Pero', da quello che leggo, il secondo quesito richiede la costruzione del
TFILE, quindi sei TU che mi devi dire come e' fatto... :D
leadergl
21-01-2006, 17:38
Ti ringrazio, hai centrato il problema...grazie mille ;)
Mi sarà utile, il progetto l'ho già consegnato anche se per mia sfortuna la creazione dell'albero non avviene correttamente però almeno adesso so come andava fatto ;)
Questo è un esempio del file da cui leggo i dati:
Veicoli da trasporto|3|proprieta1|prop2|
Per Mare|0|proprieta1|prop2|
Da Terra|2|proprieta1|prop2|
Su Rotaia|0|proprieta1|
Su Ruote|0|proprieta1|
Per Aria|0|proprieta1|
La struttura è:
Nome_Nodo | Numero_Figli | Proprietà1 | ProprietàN
Nome_Nodo | Numero_Figli | Proprietà1 | ProprietàN
Nome_Nodo | Numero_Figli | Proprietà1 | ProprietàN
Non mi e' ancora chiaro com'e' il file dei dati.
Perche' non ne posti un pezzetto, giusto per capire cosa si deve leggere?
Il resto non mi pare difficile, per esempio:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct albero {
char nome[5];
struct albero *fratello;
struct albero *figlio;
} alberoStrano;
typedef struct famiglia {
char *nome;
int figli;
} famiglia;
famiglia dati[] = {
{"1", 5}, {"11",0}, {"12",3}, {"121",0}, {"122",1},
{"1221",0}, {"123",0}, {"13",0}, {"14",0},{"15",2},
{"151",0},{"152",0},{NULL,0}
};
int indice;
void leggiNodo(famiglia *dati, alberoStrano **nodo, int fratelli)
{
int figli;
if (dati[indice].nome == NULL)
return;
*nodo = malloc(sizeof(alberoStrano));
strcpy((*nodo)->nome, dati[indice].nome);
figli = dati[indice++].figli;
if (figli > 0) {
leggiNodo(dati, &((*nodo)->figlio), figli-1);
} else
(*nodo)->figlio = NULL;
if (fratelli > 0)
leggiNodo(dati, &((*nodo)->fratello), fratelli-1);
else
(*nodo)->fratello = NULL;
}
void stampaNodo(alberoStrano *nodo)
{
printf("%s", nodo->nome);
if (nodo->figlio) {
printf(" (");
stampaNodo(nodo->figlio);
putchar(')');
}
if (nodo->fratello) {
putchar(' ');
stampaNodo(nodo->fratello);
}
}
int main()
{
alberoStrano *radice;
indice = 0;
leggiNodo(dati, &radice, 0);
stampaNodo(radice);
putchar('\n');
/* qui si dovrebbero liberare le risorse allocate,
ma lo lascio come esercizio ;) */
return 0;
}
beppegrillo
21-01-2006, 17:42
Ok, l'ho rinominato, ma continuo a non vedere l'esempio... :mbe:
Pero', da quello che leggo, il secondo quesito richiede la costruzione del
TFILE, quindi sei TU che mi devi dire come e' fatto... :D
L'esempio è un immagine, forse openoffice non la interpreta bene :|
Comunque tfile puoi costruirtelo come ti pare, a patto di rispettare alcuni vincoli di "spazio", se leggi l'ultima domanda c'è scritto.
rdefalco
21-01-2006, 17:48
Ti ringrazio, hai centrato il problema...grazie mille ;)
Mi sarà utile, il progetto l'ho già consegnato anche se per mia sfortuna la creazione dell'albero non avviene correttamente però almeno adesso so come andava fatto ;)
Questo è un esempio del file da cui leggo i dati:
Io ho l'impressione che la struttura del testo che hai postato non sia corretta né interpretabile univocamente.
beppegrillo
21-01-2006, 18:06
Io ho l'impressione che la struttura del testo che hai postato non sia corretta né interpretabile univocamente.
esattamente in cosa?
rdefalco
21-01-2006, 18:13
EDIT probabilmente mi sbagliavo ma non dovrebbe essere così difficile da realizzare praticamente
Veicoli da trasporto|3|proprieta1|prop2|
Per Mare|0|proprieta1|prop2|
Da Terra|2|proprieta1|prop2|
Su Rotaia|0|proprieta1|
Su Ruote|0|proprieta1|
Per Aria|0|proprieta1|
Posso interpretarlo
Veicoli da trasporto
Per Mare Da Terra Su rotaia
Su ruote Per Aria
O in altri 10 modi diversi
beppegrillo
21-01-2006, 20:11
Ripeto, la struttura del file ognuno può crearsela come gli pare, l'importante è che si rispetti alcuni vincoli di spazio e che si costruisca correttamente poi l'albero da essa :D
Quindi, ipotizzando un file di nome 'prova.txt' cosi' formato:
Veicoli da trasporto|3|
Per Mare|0|
Da Terra|2|
Su Rotaia|0|
Su Ruote|0|
Per Aria|0|
il codice potrebbe diventare qualcosa del genere:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct alberOrdinato {
char *nome;
struct alberOrdinato *fratello;
struct alberOrdinato *figlio;
} albero;
void leggiNodo(FILE *in, albero **nodo, int fratelli)
{
char nome[256];
int figli;
if (fscanf(in, "%[^|]|%d| ", nome, &figli) != 2)
return;
*nodo = malloc(sizeof(albero));
(*nodo)->nome = malloc(strlen(nome)+1);
strcpy((*nodo)->nome, nome);
if (figli > 0) {
leggiNodo(in, &((*nodo)->figlio), figli-1);
} else
(*nodo)->figlio = NULL;
if (fratelli > 0)
leggiNodo(in, &((*nodo)->fratello), fratelli-1);
else
(*nodo)->fratello = NULL;
}
void stampaNodo(albero *nodo)
{
printf("\'%s\'", nodo->nome);
if (nodo->figlio) {
printf(" (");
stampaNodo(nodo->figlio);
putchar(')');
}
if (nodo->fratello) {
putchar(' ');
stampaNodo(nodo->fratello);
}
}
void freeAll(albero *nodo)
{
if (nodo->figlio)
freeAll(nodo->figlio);
if (nodo->fratello)
freeAll(nodo->fratello);
free(nodo->nome);
free(nodo);
}
int main()
{
albero *radice;
FILE *in = fopen("prova.txt", "r");
leggiNodo(in, &radice, 0);
fclose(in);
stampaNodo(radice);
putchar('\n');
freeAll(radice);
return 0;
}
P.S. non e' molto ben scritto, ma e' solo per rendere l'idea.
leadergl
22-01-2006, 11:04
Posso interpretarlo
C'eri quasi arrivato....la struttura è questa:
Veicoli da trasporto
Per Mare Da Terra Per Aria
Su ruote Su Rotaia
io l'avevo scritto per bene qui:
radice VEICOLI DA TRASPORTO
figlio_1 PER MARE
figlio_2 PER TERRA
figlio_1 (di figlio_2) SU RUOTE
figlio_2 (di figlio_2) SU ROTAIA
figlio_1 (di figlio_2 di figlio_2)
figlio_3 (di figlio_2)
figlio_3 PER ARIA
figlio_4
figlio_5
figlio_1 (di figlio_5)
figlio_2 (di figlio_5)
e qui:
Nome_Nodo_1 | NumeroFigli | Proprieta_1 | ... | Proprieta_N
Nome_Nodo_Figlio_1 | NumeroFigli | Proprieta_1 | ... | Proprieta_N
...
Nome_Nodo_Figlio_M | NumeroFigli | Proprieta_1 | ... | Proprieta_N
Nome_Nodo_2 | NumeroFigli | Proprieta_1 | ... | Proprieta_N
...
Nome_Nodo_N | NumeroFigli | Proprieta_1 | ... | Proprieta_N
rdefalco
22-01-2006, 11:38
C'eri quasi arrivato
No no avevo capito bene come era fatta la struttura finale a cui tu volevi arrivare. Solamente per 5 minuti mi era sembrato che una procedura ricorsiva non avrebbe potuto interpretare correttamente il file di testo per arrivare al tuo risultato. Poi invece ci ho ripensato e mi sono corretto. Non posto codice perché in questo periodo mi sto occupando solo di java e non voglio incasinarmi...
leadergl
22-01-2006, 11:53
;)
Comunque raga vi ringrazio tutto per l'aiuto...mi spiace solo che nel progetto mi sono incasinato su una cretinata...mannaggia a me e a sto C, vabbè pazienza ;)
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.