|
|
|
|
Strumenti |
19-10-2001, 16:17 | #1 |
Senior Member
Iscritto dal: Feb 2001
Città: Altamura (BA)
Messaggi: 2100
|
Alberi n-ari
Salve a tutti,
non riesco ad implementare l'operatore insprimosottoalbero di una struttura dati albero realizzata tramite liste di figli. Qualcuno può darmi una mano? Il linguaggio usato è il C. Grazie a tutti, Domenico. |
19-10-2001, 19:09 | #2 |
Senior Member
Iscritto dal: Apr 2000
Città: Vicino a Montecatini(Pistoia) Moto:Kawasaki Ninja ZX-9R Scudetti: 29
Messaggi: 53970
|
Che intendi per insPrimoSottoalbero ? Spiegati meglio...comè la struttura dati ? Sono liste concatenate di nodi o liste di alberi ?
|
19-10-2001, 20:34 | #3 |
Senior Member
Iscritto dal: Feb 2001
Città: Altamura (BA)
Messaggi: 2100
|
in un array sono memorizzati tutti i nodi dell'albero ed ogni elemento dell'array è un puntatore ad una lista i cui elementi sono i figli di tale nodo .
Quindi ho un array di liste. Le informaioni relative ad ogni singolo nodo (etichetta) sono memorizzate in un altro array in corrispondenza dello stesso indice. Faccio un esempio dove l'etichetta del nodo è di tipo tipoelem (char, int, ecc ): struct tipocella { indice elemento; struct tipocella * successivo; }; typedef struct tipocella cella; typedef cella * lista ; // ho definito la lista struct tipoalbero { lista testa[max_num_nodi]; // array di liste tipoelem info[max_num_nodi]; // info associate ad ogni nodo }; typedef tipoalbero albero; la funzione : void insprimosottoalbero(albero, albero *, nodo); permette di fondere due alberi ed in particolare di inserire l'albero B (secondo parametro) come primo figlio del nodo (terzo parametro) dell'albero A (primo parametro). Se vuoi ti allego il sorgente . Ciao e grazie, Domenico. |
19-10-2001, 22:24 | #4 |
Bannato
Iscritto dal: Jul 2000
Città: Malo (VI)
Messaggi: 994
|
Spero di aver ben capito la struttura del tuo albero
allora la funzione che cerchi potrebbe essere la seguente Per comodita suppongo che i due albero abbiano un campo in cui memorizzano il numero di nodi void insprimosottoalbero(albero* A, albero * B, nodo) { // c'e' spazio ? if ( A->size + B->size > max_num_nodi ) return; // copiamo le liste del secondo albero nel primo for ( int i=0 ; i< B->size ; i++ ) { A->testa[i+A->size]=B->testa[i]; } // gli elementi di B, che avevano indice 0 a B->size , ora hanno indice da A->size ad A->size+B->size, devo aggiornare le liste for( int = 0 ;i< B->size ; i++ ) { lista* l = A->testa[i+A->size]; while( l != NULL ) { l->elemento+= A->size; l=l->next; } } // ora non ci resta che mettere la radice di B ( che ora ha indice A->size ) // come figlio del nodo indicato lista* n = new lista; n->elemento= A->size; n->next=A->testa[nodo]; A->testa[nodo]=n; // aggiorniamo la dimensione A->size += B->size; } NB- Come avrai notato questo è C++, quindi dovrai fare alcune modifiche (minime) |
19-10-2001, 22:29 | #5 |
Bannato
Iscritto dal: Jul 2000
Città: Malo (VI)
Messaggi: 994
|
Dimenticavo....
per pigrizia non mi sono preoccupato di copiare le liste. Quindi l'albero inserito non e' piu' utilizzabile da se'. Se vuoi poterlo utilizzare ancora devi crearti delle nuove liste invece che copiare e modificare le vecchie. L'idea di base comunque rimane quella ( copia i nodi, aggiorna gli indici, collega la radice al nodo desiderato ), e non dovrebbe esserti difficile effettuare i dovuti cambiamenti. ciao marco |
19-10-2001, 23:13 | #6 |
Bannato
Iscritto dal: Jul 2000
Città: Malo (VI)
Messaggi: 994
|
Post post scriptum
non ho provato a compilare il codice, puo' darsi ( anzi, probabile ) che contenga errori. Mi interessava piu' che altro spiegarti il procedimento. |
20-10-2001, 08:44 | #7 |
Senior Member
Iscritto dal: Feb 2001
Città: Altamura (BA)
Messaggi: 2100
|
Ok ci provo.
Grazie, Domenico. |
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 02:47.