PDA

View Full Version : [C] Visita per livelli


Manugal
11-06-2006, 21:26
Ciao a tutti!

Non ho capito bene a che serve usare una coda per effettuare la visita di un albero generale per livelli. Ad esempio in questo piccolo pezzo di codice è implementata la visita per livelli (non so se è esatta):


void visita (gtree t){
coda q;
gtree aux,tmp;

init(q);
if (!t) enqueue(q,t);
while(!empty(q)){
aux = dequeue(q);
printf("%d",aux->dato);
tmp = aux->lista_fratelli
while(!aux){
enqueue(q,aux);
aux = aux->lista_fratelli;
}
if (!(aux->primo_figlio))
enqueue(q,aux->primo_figlio);
}
}


Non riesco a capire bene cosa accade nella coda ad ogni iterazione. Grazie.

Manugal
12-06-2006, 12:30
up :rolleyes:

Black imp
12-06-2006, 13:43
senti abbi pazienza ma se non scrivi il testo di tutte quelle funzioni come si fa a immaginarsi che cosa fanno? :rolleyes:

se sono troppo lunghe metti un allegato scaricabile con tutto. se no scrivi direttamente la definizione delle strutture dati E delle funzioni .


dopo ripasso.

sottovento
12-06-2006, 16:08
Beh, in effetti il codice non e' per niente chiaro:
- viene valorizzata una variabile tmp che non viene usata e non si sa a cosa serva;

- L'istruzione
if (!t) enqueue(q,t);
mette un NULL nella cosa, salvo poi, con l'istruzione
aux = dequeue(q);
printf("%d",aux->dato);
estrarlo subito e dereferenziarlo. Questo dovrebbe provocare un crash, a meno che ci siano delle parti di programma non specificate che aggiustino le cose...

prova a pubblicare qualcosa di piu' e magari qualche info di cui sei a conoscenza.

High Flying
Sottovento

Manugal
15-06-2006, 11:47
C'era solo scritto questo: "Si trattava di usare una coda per mantenere traccia del livello dei nodi. La coda poteva essere definita con un dato di tipo gtree. Assumiamo quindi un tipo coda e assumiamo date tutte le routine standard su coda." La struttura dell'albero era una cosa del genere, credo almeno. Non ricordo bene perché quel codice l'ho copiato dalle soluzioni di un esame e il testo del problema non era scritto.


struct gtree{
int dato;
struct gtree *primofiglio;
struct node *listafratelli;
}


Effettivamente alcune parti del programma non sono molto chiare (forse avrà sbagliato a trascriverle). Ad esempio come if (!t) enqueue(q,t); oppure come if (!(aux->primo_figlio)).