PDA

Visualizza la versione completa : C++ albero n-ario con vettore, metodo insprimosottoalbero


pietrol83
27-03-2012, 11:27
ciao a tutti, sto implementando la struttura dati albero n-ario con vettore dei padri. nel metodo insprimo sottoalbero ho un problema: viene perso il valore dell'etichetta di un nodo. posto i codici.

alberonv.h


#ifndef alberonv_h
#define alberonv_h

#include<iostream>
#include<stdlib.h>
#include<assert.h>

using namespace std;

template<class tipoelem>
class alberonv
{
public:
typedef int nodo;
alberonv(int);

void creaalbero();
bool alberovuoto();
bool foglia(nodo);
bool ultimofratello(nodo);
nodo radice();
nodo padre(nodo);
nodo primofiglio(nodo);
nodo succfratello(nodo);
tipoelem legginodo(nodo);
void scrivinodo(nodo, tipoelem);
void insradice(nodo);
void insprimosottoalbero(alberonv, nodo);
void inssottoalbero(alberonv, nodo);
void cancsottoalbero(nodo);
private:
typedef struct Node
{
int padre;
tipoelem etichetta;
} node;
node *tree;
int dimtree;
int nodialbero;
};

#endif

template<class tipoelem>
alberonv<tipoelem>::alberonv(int dim)
{
dimtree = dim;
this->creaalbero();
}

template<class tipoelem>
void alberonv<tipoelem>::creaalbero()
{
tree = new struct Node[dimtree];
for(int i = 0; i < dimtree; i++)
tree[i].padre = -1;
nodialbero = 0;
}

template<class tipoelem>
bool alberonv<tipoelem>::alberovuoto()
{
return(nodialbero == 0);
}

template<class tipoelem>
bool alberonv<tipoelem>::foglia(typename alberonv<tipoelem>::nodo nod)
{
bool esito = true;
for(int i = nod + 1; (i < dimtree) && esito; i++)
{
if(tree[i].padre == nod)
esito = false;
}

return esito;
}

template<class tipoelem>
bool alberonv<tipoelem>::ultimofratello(typename alberonv<tipoelem>::nodo nod)
{
bool esito = true;
for(int i = nod + 1; (i < this->nodialbero) && esito; i++)
{
if(tree[i].padre == tree[nod].padre)
esito = false;
}

return esito;
}

template<class tipoelem>
typename alberonv<tipoelem>::nodo alberonv<tipoelem>::radice()
{
return 0;
}

template<class tipoelem>
typename alberonv<tipoelem>::nodo alberonv<tipoelem>::padre(typename alberonv<tipoelem>::nodo nod)
{
return(tree[nod].padre);
}

template<class tipoelem>
typename alberonv<tipoelem>::nodo alberonv<tipoelem>::primofiglio(typename alberonv<tipoelem>::nodo nod)
{
bool trovato = false;
nodo figlio;

for(int i = nod; (i < nodialbero) && !trovato; i++)
{
if(tree[i].padre == nod)
{
figlio = i;
trovato = true;
}
}

return figlio;
}

template<class tipoelem>
typename alberonv<tipoelem>::nodo alberonv<tipoelem>::succfratello(typename alberonv<tipoelem>::nodo nod)
{
bool trovato = false;
nodo fratello;

for(int i = nod + 1; (i < nodialbero) && !trovato; i++)
{
if(this->padre(i) == this->padre(nod))
{
trovato = true;
fratello = i;
}
}

return fratello;
}

template<class tipoelem>
tipoelem alberonv<tipoelem>::legginodo(typename alberonv<tipoelem>::nodo nod)
{
return(tree[nod].etichetta);
}

template<class tipoelem>
void alberonv<tipoelem>::scrivinodo(typename alberonv<tipoelem>::nodo nod, tipoelem elem)
{
tree[nod].etichetta = elem;
}

template<class tipoelem>
void alberonv<tipoelem>::insradice(typename alberonv<tipoelem>::nodo nod)
{
tree[0].padre = 0;
nodialbero++;
}

template<class tipoelem>
void alberonv<tipoelem>::insprimosottoalbero(alberonv<tipoelem> T, typename alberonv<tipoelem>::nodo nod)
{
cout << T.legginodo(T.radice()) << "\n\n";
int scostamento = nod + 1;
node *tmp = tree;
this->dimtree = this->nodialbero + T.nodialbero;
node *treeaux = new struct Node[dimtree];
for(int i = 0; i <= nod; i++)
treeaux[i] = tree[i];
for(int i = 0; i < T.nodialbero; i++)
{
treeaux[nod + 1 + i].etichetta = T.tree[i].etichetta;
if(i == T.radice())
treeaux[nod + 1 + i].padre = nod;
else
treeaux[nod + 1 + i].padre = T.tree[i].padre + scostamento;
}
for(int i = nod + 1; i < this->nodialbero; i++)
{
treeaux[i + T.nodialbero] = tree[i];
treeaux[i + T.nodialbero].padre = tree[i].padre + T.nodialbero;
}
this->nodialbero += T.nodialbero;
for(int i = nodialbero; i < dimtree; i++)
treeaux[i].padre = -1;
tree = treeaux;
delete tmp;
}

template<class tipoelem>
void alberonv<tipoelem>::inssottoalbero(alberonv<tipoelem> T, typename alberonv<tipoelem>::nodo nod)
{
node *treeaux = new struct Node[this->nodialbero + T.nodialbero];
node *tmp = tree;
this->dimtree += T.nodialbero;
for(int i = 0; i <= nod; i++)
treeaux[i] = tree[i];
for(int i = 0; i < T.nodialbero; i++)
{
treeaux[nod + i + 1].etichetta = T.tree[i].etichetta;
if(i == T.radice())
treeaux[nod + i + 1].padre = tree[nod].padre;
else
treeaux[nod + i + 1].padre = T.tree[i].padre + nod + 1;
}
for(int i = nod + 1; i < this->nodialbero; i++)
{
treeaux[i + T.nodialbero] = tree[i];
treeaux[i + T.nodialbero].padre = tree[i].padre + T.nodialbero;
}
tree = treeaux;
nodialbero += T.nodialbero;
for(int i = nodialbero; i < dimtree; i++)
treeaux[i].padre = -1;
delete tmp;
}

template<class tipoelem>
void alberonv<tipoelem>::cancsottoalbero(typename alberonv<tipoelem>::nodo nod)
{
if(!this->foglia(nod))
{
nodo v = this->primofiglio(nod);
while(!this->ultimofratello(v))
{
this->cancsottoalbero(v);
v = this->succfratello(v);
}
this->cancsottoalbero(v);
}
tree[nod].padre = -1;
nodialbero--;
}

testlaberonv.cpp


#include "alberonv.h"

#include<iostream>
#include<stdlib.h>

using namespace std;

int main()
{
alberonv<int> T(3);
cout << " ***test metodo CREAALBERO***\n\n";
cout << "il metodo CREAALBERO crea un albero privo di nodi (vuoto). Per verificare\n";
cout << "la correttezza del metodo basta applicare il metodo ALBEROVUOTO.\n\n";
cout << " alberovuoto() = " << T.alberovuoto() << "\n\n\n\n";
system("pause");
cout << " ***test metodo ALBEROVUOTO***\n\n";
cout << "il metodo ALBEROVUOTO testa se l'albero ha o meno nodi, ritornando un\n";
cout << "valore booleano.\n\n";
cout << " test con esito positivo:\n";
cout << " alberovuoto() = " << T.alberovuoto() << "\n\n";
cout << " test con esito negativo:\n";
cout << " inserimento del nodo radice con valore:\n";
alberonv<int>::nodo n = 0;
T.insradice(n);
T.scrivinodo(T.radice(), 0);
cout << " alberovuoto() = " << T.alberovuoto() << "\n\n\n\n";

cout << " ***test metodo FOGLIA***\n\n";
cout << "il metodo FIGLIA controlla se il nodo passato come argomento e' o meno\n";
cout << "un nodo foglia restituendo un valore booleano.\n\n";
cout << " test con esito positivo:\n";
cout << " foglia(radice()) = " << T.foglia(T.radice()) << "\n\n";
cout << " test con esito negativo:\n";
cout << " inserimento di un sottoalbero, costituito dalla sola radice, come\n";
cout << " primofiglio della radice dell'albero T.\n";
alberonv<int>::nodo m = 0;
alberonv<int> Taux(1);
Taux.insradice(m);
Taux.scrivinodo(Taux.radice(), 1);
T.insprimosottoalbero(Taux, T.radice());
cout << T.legginodo(T.radice()) << " " << T.legginodo(T.primofiglio(T.radice())) << "\n\n";
cout << " foglia(radice()) = " << T.foglia(T.radice()) << "\n\n\n\n";
system("pause");
cout << " ***test metodo ULTIMOFRATELLO***\n\n";
cout << "il metodo ULTIMOFRATELLO testa se il nodo passato come argomento e' o meno\n";
cout << "l'ultimo nodo in relazione d'ordine tra i figli di un dato nodo.\n\n";
cout << " test con esito positivo:\n";
cout << " ultimofratello(primofiglio(radice())) = " << T.ultimofratello(T.primofiglio(T.radice())) << "\n\n";
cout << " test con esito negativo:\n";
cout << " inserimento di un nodo come fratello successivo del primo figlio della radice:\n";
Taux.scrivinodo(Taux.radice(), 2);
T.inssottoalbero(Taux, T.primofiglio(T.radice()));
cout << " ultimofratello(primofiglio(radice())) = " << T.ultimofratello(T.primofiglio(T.radice())) << "\n\n";
cout << "\n\n";
system("pause");
cout << " ***test metodo RADICE***\n\n";
cout << "il metodo RADICE fornisce l'indice del vettore relativo alla cella occupata\n";
cout << "dalla radice dell'albero.\n\n";
cout << " radice() = " << T.radice() << "\n\n\n\n";

cout << " ***test metodo PADRE***\n\n";
cout << "il metodo PADRE fornisce il nodo padre del nodo fornito come argomento.\n\n";
cout << " padre(primofiglio(radice())) = " << T.padre(T.primofiglio(T.radice())) << "\n\n\n\n";

cout << " ***test metodo PRIMOFIGLIO***\n\n";
cout << "il metodo PRIMOFIGLIO fornisce il nodo del primo figlio del nodo passato\n";
cout << "come argomento.\n\n";
cout << " primofiglio(radice()) = " << T.primofiglio(T.radice()) << "\n\n\n\n";

cout << " ***test metodo SUCCFRATELLO***\n\n";
cout << "il metodo SUCCFRATELLO fornisce il nodo fratello successivo al nodo passato\n";
cout << "come argomento.\n\n";
cout << " succfratello(primofiglio(radice())) = " << T.succfratello(T.primofiglio(T.radice())) << "\n\n\n\n";

cout << " ***test metodo LEGGINODO***\n\n";
cout << "il metodo LEGGINODO fornisce il valore dell'etichetta del nodo passato come argomento.\n\n";
cout << " legginodo(radice()) = " << T.legginodo(T.radice()) << "\n\n\n\n";

cout << "i metodi SCRIVINODO, INSRADICE, INSPRIMOSOTTOALBERO e INSSOTTOALBERO SONO stati utilizzati\n";
cout << "nei test precedenti.\n\n\n\n";

cout << " ***test metodo CANCSOTTOALBERO***\n\n";
cout << "il metodo CANCSOTTOALBERO elimina tutti i nodi del sottoalbeto avente radice il nodo passato\n";
cout << "come argomento.\n\n";
cout << " cancellazione dell'intero albero:\n";
T.cancsottoalbero(T.radice());
cout << " alberovuoto() = " << T.alberovuoto() << "\n\n\n\n";
system("pause");
return 0;
}

in pratica il metodo insprimosottoalbero prende in input un secondo albero, e il nodo dell'albero oggetto che diventerÓ il padre del sottoalbero passato come argomento. in pratica nel metodo viene creato un vettore di dimensione pari alla somma dei numeri di nodi che compongono i due alberi, poi vengono copiati i nodi dell'albero oggetto fino al nodo nod, poi si copia tutto l'albero passato come argomento e poi si copiano i restanti nodi dell'albero in oggetto in modo da mantenere le proprietÓ dell'albero n-ario.
ho fatto il debug e nel metodo tutto va bene ma appena fuori dal metodo perdo il valore dell'etichetta del primofiglio della radice. perchŔ? non Ŕ che perdo il nuovo vettore all'uscita dal metodo?

pietrol83
27-03-2012, 11:37
problema risolto!!! l'errore era nel metodo primofiglio.

Loading