[C] Nuovo problema

[Manugal]

Ciao a tutti! Scusate se sto tempestando il forum, ma siccome domani ho l'esame sto cercando di fare il maggior numero di esercizi possibili :)

Allora adesso ho da fare questo....

Progettare un programma C che legge in preordine
da stdin un albero generico (cioe' non necessariamente binario)
etichettato con interi sui nodi e ritorna la somma dei valori
delle etichette x dell'albero che soddisfano
le seguenti condizioni:
1. x e' dispari;
2. il padre di x e' pari.

Il programma restituisce 0 se non ci sono nodi che soddisfano
le condizioni di cui sopra.

L'input da dare è di questo tipo:

(La prima colonna indica il numero di figli che ha il corrispondente nodo e la seconda colonna indica il nodo stesso)

3 122
1 457
0 698
0 23
2 724
1 456
0 678
2 346
0 777
0 998

Non capisco bene cosa vuol dire "il padre di x è pari". Ma x è un elemento non è un nodo :confused: .


Io cmq ho provato a fare un codice del genere:



#include <stdio.h>
#include <malloc.h>

struct nodo{
int val;
struct nodo *left;
struct nodo *right;
};

typedef struct nodo NODO;
typedef NODO *TREE;

TREE ReadTree(){

TREE t=(TREE)malloc(sizeof(TREE));
int nFigli, nVal, i;
scanf("%d %d", &nFigli, &nVal);
t->val=nVal;
t->left=NULL;
t->right=NULL;
for(i=0; i<nFigli; ++i){
t->left=ReadTree();
t->right=ReadTree();
}
return t;
}

int evaluateSum(TREE t){

int sum=0;

if(t==NULL)
return sum;
else
if((t->val)%2!=0)
sum+=t->val;
return sum+evaluateSum(t->left)+evaluateSum(t->right);

}

int main(void){
TREE albero=(TREE)malloc(sizeof(NODO));
albero=ReadTree();
printf("Sum: %d", evaluateSum(albero));
return 0;
}



Quando lo faccio partire però si blocca. Forse ho gestito male la parte relativa a quanti figli ha un nodo... boh. Voi che ne dite? Grazie.

[Manugal]

Ho modificato un po' il codice però la somma non mi viene esattamente come dovrebbe (dovrebbe venire 2157 invece viene 122). COsa posso fare?



#include <stdio.h>
#include <malloc.h>

struct nodo{
int val;
struct nodo *figlio;
};

typedef struct nodo NODO;
typedef NODO *TREE;

TREE ReadTree(){

TREE t=(TREE)malloc(sizeof(TREE));
int nFigli, nVal, i;
scanf("%d %d", &nFigli, &nVal);
t->val=nVal;
t->figlio=NULL;
if(nFigli-- >0)
t->figlio=ReadTree();

return t;
}

int evaluateSum(TREE t){

int sum=0;

if(t==NULL)
return sum;
else if((t->val)%2==0){
sum+=t->val;
return sum+evaluateSum(t->figlio);
}
else
return 0;
}

int main(void){
TREE albero=(TREE)malloc(sizeof(NODO));
albero=ReadTree();
printf("Sum: %d", evaluateSum(albero));
return 0;
}

[71104]

l'albero non deve essere binario, quindi la struct io la reimplementerei così:

typedef struct _NODE {
int nValue;
struct _NODE *pChild, *pNext;
} NODE, *TREE;

pChild è il puntatore al primo figlio, e pNext al "fratello", perciò ogni nodo è come se avesse in pChild la testa di una lista a puntatori semplici dei suoi figli.

poi la ReadTree se non erro dovrebbe diventare così:

TREE ReadTree() {
TREE t = (TREE)malloc(sizeof(NODE)),
**ppCur = &t->pChild;
int nChildren = 0;
scanf("%d %d", &nChildren, &t->nValue);
t->pChild = NULL;
t->pNext = NULL;
while (nChildren) {
*ppCur = ReadTree();
ppCur = &(*ppCur)->pNext;
nChildren--;
}
return t;
}

[Manugal]

Ciao e grazie della risposta. Non capisco bene quando dici:



perciò ogni nodo è come se avesse in pChild la testa di una lista a puntatori semplici dei suoi figli.



Che intendi dire?

Ho provato comunque il tuo codice ma non va lo stesso, cioè quando lo faccio partire si blocca.

[71104]

be', un albero n-ario ha n figli; come fai a rappresentarli? in ciascun nodo potresti o metterci un array, ma sarebbe difficile perché dovresti gestirlo dinamicamente, oppure, soluzione migliore, una lista (le avete fatte le liste?); io ci ho messo una lista: il puntatore pChild punta alla testa della lista e pNext punta all'elemento successivo. per esempio:

1
|
2-----3-----4
| |
5--6 7--8
|
9

il nodo 1 ha tre figli (2, 3 e 4), 2 ha due figli (5 e 6), 3 ne ha altri due (7 e 8) e il 6 ne ha uno (9).
ogni sbarretta verticale corrisponde concettualmente a un puntatore pChild, mentre le sbarrette orizzontali corrispondono a pNext.

[Manugal]

Si si le liste le abbiamo fatte, solamente non riesco a spiegarmi perché usare un puntatore a puntatore. Cioè pChild è già un puntatore di suo (un puntatore a struttura), quindi se io devo rappresentare ad esempio 3 filgi su un nodo, non potrei usare p->pChild normalmente dicendogli che finché il numero di figli è maggiore di zero deve richiamare ricorsivamente ReadTree() su p->pChild? E poi i fratelli come li gestisco? Al solito con la ricorsione?

[71104]

Si si le liste le abbiamo fatte, solamente non riesco a spiegarmi perché usare un puntatore a puntatore. Cioè pChild è già un puntatore di suo (un puntatore a struttura), quindi se io devo rappresentare ad esempio 3 filgi su un nodo, non potrei usare p->pChild normalmente dicendogli che finché il numero di figli è maggiore di zero deve richiamare ricorsivamente ReadTree() su p->pChild?
così memorizzi solo l'ultimo figlio in pChild: dopo che avrai fatto ReadTree avrai sovrascritto pChild e ti sarà rimasto memorizzato solo l'ultimo figlio che hai letto...

E poi i fratelli come li gestisco? Al solito con la ricorsione? be' si, alla fine quel coso se lo giri di 45 gradi in senso orario diventa un albero binario :D
per effettuare la ricorsione su un albero N-ario devi fare più o meno così:

void Ricorsione(TREE t) {
if (!t) {
return;
}
DoSomething(t->nValue);
Ricorsione(t->pChild);
Ricorsione(t->pNext);
}

è praticamente uguale a un albero binario :)

[Manugal]

Ok ho capito. Allora questa istruzione all'interno del while a cosa serve?



ppCur = &(*ppCur)->pNext;



Per gestire la parte next non posso fare semplicemente p->pNext=ReadTree()? Oppure anche qui andrei a sovrascrivere il vecchio valore? Perché se così fosse, allora anche con gli esercizi precedenti sugli alberi binari che avevo postato qui andavo a sovrascrivere il valore precedente (perché mettevo t->pLeft=ReadTree() e t->pRight=ReadTree() ). Perché in quel caso non la sovrascrive? Suppongo che sia per il fatto della ricorsione .... allora perché qua visto che uso la ricorsione lo dovrebbe sovrascrivere? :D Spero di essermi spiegato. Cmq grazie sei molto gentile a spiegarmi queste cose..... :) Sei del secondo anno tu?

[Qu@ker]

typedef struct nodo {
int dato;
struct nodo** next;
} Nodo;

Nodo *readTree(FILE *f)
{
int valore, figli;
Nodo *n = malloc(sizeof(Nodo));

fscanf(f, "%d %d", &figli, &valore);
n->dato = valore;
if (figli > 0) {
int i;
n->next = malloc((figli+1) * sizeof(Nodo *));
for (i = 0; i < figli; ++i){
n->next[i] = readTree(f);
}
n->next[i] = NULL;
} else
n->next = NULL;

return n;
}

int valutaSomma(Nodo *n)
{
int risultato = 0;

if (n == NULL)
return 0;
if (n->dato % 2 != 0)
risultato = n->dato;
else if (n->next != NULL) {
Nodo **p;
for (p = n->next; *p; ++p)
risultato += valutaSomma(*p);
}
return risultato;
}

Ho messo i dati in un file. A me il risultato viene 1257, comunque.

[Manugal]

Come mai hai usato un array di puntatori? E i figli come fai a gestirli se hai solamente next nella struct (anzi più che i figli i fratelli)? Potresti commentarmi il codice? Grazie. :)

[Qu@ker]

I 'fratelli' (o meglio, i loro puntatori) stanno tutti nello stesso array.

Il codice? Mah ...e' autoesplicativo! :Prrr:

[Manugal]

In effetti si riguardandolo bene. :Prrr: Quindi i figli sarebbero proprio l'array, giusto?

Ma come mai quando hai fatto if(Figli>0), hai allocato un nuovo nodo con figli+1?

Poi il testo dice anche di controllare che x sia dispari e che il padre di x sia pari. Ma non riesco a capire cosa intende dire... cioè x è un elemento da come si può dedurre dal testo, non un nodo.

[Qu@ker]

Perche' utilizzo un elemento dell'array per segnalare che non ci sono piu' figli, inserendoci NULL (alle volte questo elemento viene definito 'sentinella').
L'alternativa era di inserire nella struct un campo contenente il numero dei figli.

[Manugal]

Ok grazie credo di aver capito :)

[Manugal]

Scusa ancora.... sto provando il tuo programma però quando lo faccio partire non stampa niente (uso Dev-C++ e quando c'è qualche problema non mi da nessun messaggio quindi non so dirti da cosa dipenda). Ti posto il main:



int main(void){
Nodo *t=malloc(sizeof(Nodo));
FILE *ifp;
ifp=fopen("input3.txt", "r");
t=readTree(ifp);
valutaSomma(t);
fclose(ifp);
return 0;
}

[Qu@ker]

int main(void)
{
Nodo *radice;
FILE *in = fopen("dati.txt", "r");
if (in == NULL) {
perror("fopen()");
exit(1);
}
radice = readTree(in);
fclose(in);
printf("Il risultato e\': %d\n", valutaSomma(radice));
return 0;
}

[Manugal]

Hai ragione ho scordato la printf :doh: Graazie.