View Full Version : ordinamento di un alb_bin in C...
marcus81
14-06-2002, 08:27
Dunque ho un abero binario su cui inserisco delle strutture così composte in ogni nodo:
typedef struct squadre{
char nome_squadra[12];
int punti;
}SQUADRE;
nel primo inserimento l'ordinamento viene fatto in base al campo nome_squadra(ordinamento lessicografico), e i punti vengono inizializzati tutti a zero.
Una procedura mi aggiorna i punti a seconda di vittoria(+3), pareggio(+1),sconfitta(nulla).
l'obbiettivo è di mettere in ordine la classifica tramite un'altra funzione...e li vengono i miei problemi!
Come ordinare un albero binario già costruito in base al campo punti?
l'ordinamento lo vorrei fare in modo tale che posso leggere l'albero in ordine simmetrico...
Come fare?grazie x l'aiuto;)
marcus81
14-06-2002, 08:50
nessuno?
marcus81
14-06-2002, 08:52
:rolleyes:
marcus81
14-06-2002, 13:40
nessuno ha qualke soluzione?:(
nemmeno il "maestro" cionci?:)
Il metodo migliore per ordinare un albero binario dovrebbe essere lo heap sort...
L'unica cosa che mi lascia un po' perplesso è la visita simmetrica...
Se non sbaglio con lo heap sort standard si fa un ordinamento per la visita posticipata...
Cerco qualche algoritmo e te lo posto...
/\/\@®¢Ø
14-06-2002, 18:33
Originariamente inviato da marcus81
[B]
Come ordinare un albero binario già costruito in base al campo punti?
l'ordinamento lo vorrei fare in modo tale che posso leggere l'albero in ordine simmetrico...
Come fare?grazie x l'aiuto;)
Il modo piu' semplice e' quello di estrarre l'elemento da aggiornare, aggiornare il campo e reinserirlo. Con uno heap potresti invece evitare le eliminazioni e gli inserimenti (sempre che tu aggiorni solo "verso l'alto" i punteggi ), pero' in tal caso non riusciresti a fare ricercche, ma solo a prendere la squadra col valore piu' alto ( oppure a fare una scansione come in un normale array ).
Se i valori dei punteggi li cambi in blocco ( i punteggi di tutte le squadre dopo ogni giornata ad esempio ) un'altra alternativa e' quella di tenerti i valori in un semplice array e usare un algoritmo di ordinamento 'classico' , alcuni sono buoni se i valori sono "abbastanza ordinati". Per le ricerche potrai usare sempre una ricerca binaria sull'array e quindi non perdi in performance.
/\/\@®¢Ø
14-06-2002, 18:34
Non ho risposto a tutta la domanda... cosa intendi per "ordine simmetrico" ?
Originariamente inviato da /\/\@®¢Ø
[B]Non ho risposto a tutta la domanda... cosa intendi per "ordine simmetrico" ?
Forse intende "visita simmetrica"...cioè una cosa del genere :
visita(figlioSx);
visualizza valore del nodo;
visita(figlioDx);
In questo modo alla Sx del nodo ci dovranno essere tutti valori minori del nodo corrente...mentre alla destra tutti valori maggiori (solo per fare un esempio)...
/\/\@®¢Ø
14-06-2002, 18:46
Ah grazie ! Io la conosco come "ordine infisso".
In tal caso allora il primo metodo ( rimozione - aggiornamento - rimozione ) funziona senza problema ( basta appunto fare una "visita infissa" ), nel terzo caso ancora piu' semplice : scorri linearmente l'array. Nel caso dell'heap invece temo che la cosa non funzioni...
L'unico problema sarebbe costruirsi lo heap, ma non è poi così difficile...dopo applicare l'ordinamento standard porta a risultati sicuri...
Però lo heap sort crea un albero con un ordinamento valido solo per la visita anticipata e posticipata...ma non per quella simmetrica...
marcus81
14-06-2002, 23:09
dunque ragazzi:
per quanto riguarda lo heap nn ci ho mai messo mano,quindi nn saprei....
cmq ordinare l'albero a me serve soltanto per poi visualizzare una classifica in base al campo punti...nn per ricerca...e nn mi interesse se visito l'albero in ordine simmetrico,anticipato o posticipato: l'importante è che riesca poi a visualizzare sta classifica dalla squadra che ha + punti a scendere...
..inoltre ho già fatto tutte le funzioni con allocazione dinamica della memoria non con array quindi...
/\/\@®¢Ø
15-06-2002, 00:37
Beh, se fai un array di puntatori devi cambiare poco penso. Ovviamente le routine di inserimento/rimozioni andranno cambiate, ma quelle che operano sulla struct squadre non penso. E in piu' potresti usare le funzioni di ordinamento della libreria standard.
Comunque se vuoi tenerti l'albero basta appunto che fai la trafila rimozione-aggiornamento-inserimento, non sara' il massimo dell'eleganza ma funziona. Poi visitando l'albero in modalita' infissa ( figlio sinistro - padre - figlio destro ) ottieni i punteggi in ordine crescente ( o decrescente a seconda di come lo ordini ) come serve a te.
Se infine decidi di passare al C++, c'e' il 'set' che ti attende a braccia aperte :D:D;).
marcus81
15-06-2002, 09:12
potresti essere un pò + preciso su questo metodo di rimozione-inserimento-aggiornamento?nn l'ho mai fatto...
se nn sbaglio dovrei prelevare ogni nodo e reinserirlo nell'albero?cominciando da dove?
/\/\@®¢Ø
15-06-2002, 18:07
Come non detto, ho sbagliato... se usi come chiave i punteggi poi non puoi fare una ricerca per il nome della squadra ( a meno di passare al setaccio tutto l'albero ).
Comunque una domanda: ti e' proprio necessario l'albero binario ? Se non hai tanti valori ( e non penso tu abbia migliaia di squadre ) probabilmente il gioco non vale la candela...
Scusa, ma non ti basta fare un vettore con tutti i puntatori agli elementi dell'albero...poi ordini spostando questi puntatori all'interno del vettore (in base ad un membro della struttura del nodo)...e dopo, eventualmente, puoi ricostruirti l'albero binario...
/\/\@®¢Ø
15-06-2002, 18:24
Originariamente inviato da cionci
[B]Scusa, ma non ti basta fare un vettore con tutti i puntatori agli elementi dell'albero...poi ordini spostando questi puntatori all'interno del vettore (in base ad un membro della struttura del nodo)...e dopo, eventualmente, puoi ricostruirti l'albero binario...
Si, ma allora a questo punto visto che le squadre sono quelle, e' piu' pratico tenersi solo l'array e ordinarlo quando ce n'e' bisogno
Originariamente inviato da /\/\@®¢Ø
[B]
Si, ma allora a questo punto visto che le squadre sono quelle, e' piu' pratico tenersi solo l'array e ordinarlo quando ce n'e' bisogno
Certo...infatti non vedo il motivo per cui le ha tenute in un albero...
marcus81
16-06-2002, 08:34
il fatto è che in questo momento nn mi interessa tanto l'efficienza...
questo programma l'avevo prima fatto con le liste concatenate e mi è venuto un pò + semplice, adesso volevo convertire il tutto in alberi, solo al fine di avere + elasticità e familiarizzare meglio con gli alberi, visto ke a brevissimo avrò un compitino di C....
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.