[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...

[Manugal]

Per favore è importante

[71104]

ma LOL ma che stai col Tronci e col Salvo??? 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

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?

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]

Originariamente inviato da Manugal

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

[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]

vittoriaaa!!!!!!!!!!!!!!

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