ciao a tutti, ho creato anche un albero n-ario con cursori ma ci sono alcuni metodi che vanno in crash. ho provato a fare il debugging e mi viene segnalato che c'è un errore di segmentazione. non riesco a capire perchè. posto i codici.
alberonc.h
codice:
#ifndef alberonc_h
#define alberonc_h
#include<iostream>
#include<stdlib.h>
#include<assert.h>
#define MAXSPAZIO 100
using namespace std;
template<class tipoelem>
class alberonc
{
public:
typedef int nodo;
alberonc();
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(alberonc, nodo);
void inssottoalbero(alberonc, nodo);
void cancsottoalbero(nodo);
private:
typedef struct Cella
{
tipoelem etichetta;
nodo padr;
nodo pfiglio;
nodo sfratello;
} cella;
static bool inizializzato;
static int spaziolibero;
cella *spazio;
int numnodi;
static nodo libero;
nodo root;
};
#endif
template<class tipoelem>
bool alberonc<tipoelem>::inizializzato = false;
template<class tipoelem>
int alberonc<tipoelem>::spaziolibero = MAXSPAZIO;
template<class tipoelem>
typename alberonc<tipoelem>::nodo alberonc<tipoelem>::libero = 0;
template<class tipoelem>
alberonc<tipoelem>::alberonc()
{
this->creaalbero();
}
template<class tipoelem>
void alberonc<tipoelem>::creaalbero()
{
assert(spaziolibero <= MAXSPAZIO);
if(!inizializzato)
{
spazio = new struct Cella[MAXSPAZIO];
for(int i = 0; i < MAXSPAZIO - 1; i++)
{
spazio[i].padr = (i + 1) % MAXSPAZIO;
spazio[i].pfiglio = -1;
spazio[i].sfratello = -1;
}
spazio[MAXSPAZIO - 1].padr = -1;
spazio[MAXSPAZIO - 1].pfiglio = -1;
spazio[MAXSPAZIO - 1].sfratello = -1;
inizializzato = true;
}
numnodi = 0;
root = libero;
}
template<class tipoelem>
bool alberonc<tipoelem>::alberovuoto()
{
return(numnodi == 0);
}
template<class tipoelem>
bool alberonc<tipoelem>::foglia(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].pfiglio == -1);
}
template<class tipoelem>
bool alberonc<tipoelem>::ultimofratello(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].sfratello == -1);
}
template<class tipoelem>
typename alberonc<tipoelem>::nodo alberonc<tipoelem>::radice()
{
return root;
}
template<class tipoelem>
typename alberonc<tipoelem>::nodo alberonc<tipoelem>::padre(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].padr);
}
template<class tipoelem>
typename alberonc<tipoelem>::nodo alberonc<tipoelem>::primofiglio(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].pfiglio);
}
template<class tipoelem>
typename alberonc<tipoelem>::nodo alberonc<tipoelem>::succfratello(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].sfratello);
}
template<class tipoelem>
tipoelem alberonc<tipoelem>::legginodo(typename alberonc<tipoelem>::nodo node)
{
return(spazio[node].etichetta);
}
template<class tipoelem>
void alberonc<tipoelem>::scrivinodo(typename alberonc<tipoelem>::nodo node, tipoelem elem)
{
spazio[node].etichetta = elem;
}
template<class tipoelem>
void alberonc<tipoelem>::insradice(typename alberonc<tipoelem>::nodo node)
{
libero = spazio[libero].padr;
cout << "libero = " << libero << "\n\n";
spazio[root].padr = -1;
spazio[root].sfratello = -1;
spazio[root].pfiglio = -1;
numnodi++;
spaziolibero--;
}
template<class tipoelem>
void alberonc<tipoelem>::insprimosottoalbero(alberonc<tipoelem> T, typename alberonc<tipoelem>::nodo node)
{
nodo tmp = T.root;
T.root = libero;
spazio[tmp].padr = node;
spazio[tmp].sfratello = spazio[node].pfiglio;
spazio[node].pfiglio = tmp;
numnodi = numnodi + T.numnodi;
T.numnodi = 0;
}
template<class tipoelem>
void alberonc<tipoelem>::inssottoalbero(alberonc<tipoelem> T, typename alberonc<tipoelem>::nodo node)
{
nodo tmp = T.root;
T.root = libero;
spazio[tmp].sfratello = spazio[node].sfratello;
spazio[tmp].padr = spazio[node].padr;
spazio[node].sfratello = T.root;
numnodi = numnodi + T.numnodi;
T.numnodi = 0;
}
template<class tipoelem>
void alberonc<tipoelem>::cancsottoalbero(typename alberonc<tipoelem>::nodo node)
{
if(!this->alberovuoto())
{
if(!this->foglia(node))
{
nodo v = this->primofiglio(node);
while(!this->ultimofratello(v))
{
this->cancsottoalbero(v);
v = this->succfratello(v);
}
this->cancsottoalbero(v);
}
spazio[node].padr = libero;
libero = node;
spazio[node].pfiglio = -1;
numnodi--;
spaziolibero++;
}
}
testalberonc.cpp
codice:
#include "alberonc.h"
#include<iostream>
#include<stdlib.h>
using namespace std;
int main()
{
alberonc<int> T;
system("pause");
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";
alberonc<int>::nodo n = 0;
T.insradice(n);
T.scrivinodo(T.radice(), 0);
cout << " alberovuoto() = " << T.alberovuoto() << "\n\n\n\n";
system("pause");
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";
alberonc<int>::nodo m = 0;
alberonc<int> Taux;
Taux.insradice(m);
Taux.scrivinodo(Taux.radice(), 1);
T.insprimosottoalbero(Taux, T.radice());
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";
alberonc<int> Taux2;
alberonc<int>::nodo o = 0;
Taux2.insradice(o);
Taux2.scrivinodo(Taux2.radice(), 2);
T.inssottoalbero(Taux2, 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;
}
perchè va in crash???