PDA

Visualizza la versione completa : C++ albero n-ario con cursori


pietrol83
28-03-2012, 21:15
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


#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


#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???

oregon
28-03-2012, 21:25
Ma scusa, dici di avere fatto debugging e non hai individuato in quale riga del main *esattamente* scatta il seg fault?

pietrol83
28-03-2012, 21:26
si è nel metodo insradice che viene invocato nel test del metodo ultimofratello, però non riesco a capire cosa ho fatto di sbagliato. secondo me è fatto correttamente.

oregon
28-03-2012, 21:31
Originariamente inviato da pietrol83
si è nel metodo insradice che viene invocato ...

Ovvero ? Quale riga *esattamente* ?

pietrol83
28-03-2012, 21:33
la riga 53 del main. quello che mi chiedo io: perchè va in crash in quella riga quando in una riga precedente c'è un'altra chiamata (funzionante) del metodo insradice???

oregon
28-03-2012, 21:37
Originariamente inviato da pietrol83
la riga 53 del main. quello che mi chiedo io: perchè va in crash in quella riga quando in una riga precedente c'è un'altra chiamata (funzionante) del metodo insradice???

Mamma mia ... che fatica ...

E secondo te mi devo contare le righe per capire di quale riga parliamo???

Non puoi indicarla ? ... Passa la voglia di rispondere ...

Scusa ... ma è la

Taux.insradice(m);

???

pietrol83
28-03-2012, 21:41
Originariamente inviato da pietrol83

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");


è QUESTA LA PORZIONE DI CODICE DOVE C'è LA CHIAMATA AL METODO INSRADICE.

oregon
28-03-2012, 21:45
Originariamente inviato da pietrol83
è QUESTA LA PORZIONE DI CODICE DOVE C'è LA CHIAMATA AL METODO INSRADICE.

Non c'è bisogno di gridare ma semplicemente di essere precisi.

Se fai il debugging invece, l'errore avviene in

Taux.insradice(m);

e se esegui passo passo entrando nella insradice, ti accorgi che

spazio

non è stato mai allocato.

pietrol83
28-03-2012, 21:48
non mi sn alterato. l'hai capito dal fatto dei caratteri in maiuscolo??? se è così è stato semplicemente perchè erroneamente si è attivato il block caps. asp, controllo meglio il codice.

pietrol83
28-03-2012, 21:57
Originariamente inviato da oregon
e se esegui passo passo entrando nella insradice, ti accorgi che

spazio

non è stato mai allocato.

mi sono accorto che spazio non l'ho dichiarato static quindi ad ogni istanza di alberonc viene creato un nuovo spazio quando questo dovrebbe essere ad ambiente condiviso. posso usare la new in questo modo?

template<class tipoelem>
typename alberonc<tipoelem>::cella *alberonc<tipoelem>::spazio = new struct Cella[MAXSPAZIO]

Loading