[C] Esercizio d'esame

[Manugal]

Ciao a tutti.

Ho un problema con un esercizio d'esame....

Posto il testo:



Progettare un programma C che legge in preordine
da stdin un albero binario etichettato con interi sui nodi
e lo stampa su stdout in postordine.

Si veda il file "format-tree.txt" per i formati di lettura e stampa
degli alberi.


L'input \`e formattato come segue.

<format T in preordine>


L'output \`e formattato come segue.

Le prime 6 righe di stampa sono formattate come segue.
<nome>
<cognome>
<giorno di nascita (2 cifre)>
<mese di nascita (2 cifre)>
<anno di nascita (4 cifre)>
<indirizzo email>


Le rimanenti righe sono formattate come segue.

<format T in postordine>


Ecco alcuni esempi per il programma dello studente Mario Rossi della Spigola
nato il 17.05.1723 ed email mrds@nessun.posto.it.
Testate il vostro programma almeno sugli esempi proposti
controllando che, per il dato input, l'output (a parte le prime 6 righe) sia
ESATTAMENTE
quello riportato nell'esempio.


Esempio 1.

stdin:
1 1 123
1 0 1456
0 0 2940
1 1 7123
0 1 2456
0 0 2678
1 1 1990
0 0 4589
0 0 1717

stdout:
Mario
Rossi della Spigola
17
05
1723
mrds@nessun.posto.it
0 0 2940
1 0 1456
0 0 2678
0 1 2456
0 0 4589
0 0 1717
1 1 1990
1 1 7123
1 1 1123


Commento all'esempio 1.

L'albero usato nell'esempio 1 e':


123
/ \
1456 7123
/ / \
2940 2456 1990
\ / \
2678 4589 1717



Io stdin lo metto su un file txt e poi faccio la redirezione. A questo punto nel programma non so come fare a dire che se trova 1 nella prima colonna quel nodo ha figlio sinistro e se trova 0 no. Poi siccome i dati sono presi da stdin come faccio a metterli in postorder? E' un pò complicato... :what:

[Manugal]

Per favore è importante :(

[71104]

ma LOL :D ma che stai col Tronci e col Salvo??? :D asd

cmq mi pare semplice: ora non ricordo esattamente come fosse il preordine, mi pare fosse che prima leggi la radice, poi il figlio sinistro, e poi il destro;si risolve facilmente con una funzione ricorsiva, tipo questa qua:

typedef struct _NODE {
int nData;
struct _NODE *pLeft, *pRight;
} NODE, *TREE;

TREE ReadTree() {
TREE t = (TREE)malloc(sizeof(NODE));
int fHasLeft, fHasRight;
int nData;
scanf("%d %d %d", &fHasLeft, &fHasRight, &nData);
t->nData = nData;
if (fHasLeft) {
t->pLeft = ReadTree();
}
if (fHasRight) {
t->pRight = ReadTree();
}
return t;
}


bada che non l'ho testato, potrebbe contenere errori...

[Manugal]

Grazie.

Ebbene si sto con quei due psicopatici :D

Cmq sia non mi pare così semplice dato che l'input è di questo tipo:

1 1 123
1 0 1456
0 0 2940
1 1 7123
0 1 2456
0 0 2678
1 1 1990
0 0 4589
0 0 1717

(cioè nella prima colonna se c'è 1 vuol dire che ha un figlio sinistro altrimenti no, nella seconda colonna se c'è 1 vuol dire che ha un figlio destro altrimenti no e poi nella terza c'è proprio il valore di quel nodo)

E l'output è di questo tipo:

0 0 2940
1 0 1456
0 0 2678
0 1 2456
0 0 4589
0 0 1717
1 1 1990
1 1 7123
1 1 1123


Cioè io parto leggendo i valori dall'input e poi? Come lo costruisco l'albero? Spero che tu possa aiutarmi dato che sicuramente avrai già passato l'esame :)

[Manugal]

Ho capito la tua funzione ma per stampare come faccio?

[Manugal]

Ho provato a fare la funzione di stampa ma mi va in un loop infinito. Ma non dovrebbe terminare quando l'albero finisce? :confused:



void PrintTree(TREE p){

if(p!=NULL){
if(p->pLeft){
printf("1 0 %d\n", p->nData);
PrintTree(p->pLeft);
}
else if(p->pRight){
printf("0 1 %d\n", p->nData);
PrintTree(p->pRight);
}
else if(p->pLeft && p->pRight){
printf("1 1 %d\n", p->nData);
else
printf("0 0 %d\n", p->nData);
}
}
}

[71104]

già, dimenticavo il codice per stampare; dovrebbe essere così, è molto semplice, ma anche questo non l'ho testato quindi potrebbero esserci errori:

void WriteTree(TREE t) {
if (!t) {
return;
}
WriteTree(t->pLeft);
WriteTree(t->pRight);
printf("%d %d %d\n",
t->pLeft != NULL,
t->pRight != NULL,
t->nData);
}

in bocca al lupo :)

[Manugal]

Scusa ma come hai fatto tu come fa a sapere che deve stampare nelle prime due colonne 01 10 00 oppure 11?

[71104]

Scusa ma come hai fatto tu come fa a sapere che deve stampare nelle prime due colonne 01 10 00 oppure 11? espressioni nella forma "x != NULL" restituiscono valori booleani: l'operatore != restituisce un valore booleano.
in C i valori booleani si rappresentano con 0 per indicare false e 1 per indicare true e questa caratteristica cade a pennello nel tuo caso :)

[Manugal]

Ah ok ho capito, però non stampa niente :D

[Manugal]

Nessuno che mi aiuti? :( :(

[71104]

hai messo system("pause") alla fine? (è una dimenticanza molto comune alla Sapienza)

[Manugal]

Cioè a che servirebbe? E dove lo dovrei mettere? :)

[71104]

la devi usare solo su Windows per non far chiudere la console subito dopo la terminazione del programma; la devi mettere nella main come ultima istruzone.

int main() {
.
.
.
system("pause");
return 0;
}

[Manugal]

Ah ho capito a cosa serve, ma il problema non è che mi si chiude la console. Il problema è che non stampa proprio niente. Cmq ho provato a metterla alla fine del main ed è la stessa cosa. Io uso Dev-C++ e ogni volta che c'è qualcosa che non va non è che mi da messaggi strani, no semplicemente non stampa niente faccio partire il programma e mi ritorna al prompt. Quindi bisognerebbe capire cos'è che non va nel codice, ma non riesco a capire cosa.

[Manugal]

Possibile nessuno sa niente? :( :( :(

Ditemi anche se è colpa del compilatore... :(

[Manugal]

:winner: :winner: vittoriaaa!!!!!!!!!!!!!! :winner: :winner:

Ci sono riuscito finalmente. Praticamente la funzione ReadTree andava scritta così:



TREE ReadTree() {
TREE t = (TREE)malloc(sizeof(NODE));
int fHasLeft, fHasRight;
int nData;
scanf("%d %d %d", &fHasLeft, &fHasRight, &nData);
t->nData = nData;
t->pLeft = NULL; /* Mancavano queste due
t->pRight= NULL; righe */
if (fHasLeft) {
t->pLeft = ReadTree();
}
if (fHasRight) {
t->pRight = ReadTree();
}
return t;
}



Grazie cmq per l'interessamento :)