[C++]programma su albero ordinato

[InformaticoRC]

Salve forum.

Ho un piccolo problema con questo programma che consiste nel costruire un albero binario ordinato inserendo da tastiera una coppia di dati formata da numero e carattere. L'ordinamento va fatto in base al primo numero inserito.
Non ci sono errori sintattici e il programma va in esecuzione, ma si blocca dopo l'inserimento di numero e carattere. le ho provate di tutte ma niente.

#include <iostream>
using namespace std;

class nodo
{
private:
int numero;
char carattere;
nodo *sinistra;
nodo *destra;

public:
nodo();
void setInt(int num) {numero=num;};
int getInt(){return numero;};
void setCar(char car) {carattere=car;};
int getCar(){return carattere;};
void pointsx(nodo *point){sinistra=point;};
void pointdx(nodo *point){destra=point;};
nodo *getsx(){return sinistra;};
nodo *getdx(){return destra;};

};

nodo::nodo()
{
numero='1';
carattere='a';
sinistra=NULL;
destra=NULL;
}

class albero
{
private:
nodo *nuovo;

public:
albero();
void inserisci(int numero, char carattere, nodo *temp=NULL);
void visualizza(nodo *temp=NULL);
};

albero::albero()
{
nuovo=NULL;
}


nodo *nuovo, *temp=NULL;


void albero::inserisci(int numero, char carattere, nodo *temp)
{
nodo *newNode;
newNode=new nodo;
newNode->setInt(numero);
newNode->setCar(carattere);
if(temp==NULL)
{
temp=nuovo;
}
if(nuovo=NULL)
{nuovo=newNode;}
else
{
if(newNode->getInt() <= temp->getInt())
{
if(temp->getsx() == NULL)
{
temp->pointsx(newNode);
return;}
inserisci(numero, carattere, temp->getsx());
}
else if(newNode->getInt() > temp->getInt())
{
if(temp->getdx() == NULL)
{
temp->pointdx(newNode);
return;}
inserisci(numero, carattere, temp->getdx());
}
else
cout << "numero già inserito\n";
}
return ;
}

void albero::visualizza(nodo *temp)
{
if(temp != NULL)
{



visualizza(temp->getsx());
cout << temp->getInt() << " " << temp->getCar() << " ";
visualizza(temp->getdx());


}
}

int main()
{
albero *albero1;
albero1=new albero;

int scelta, num, car;
int numero, carattere;

do
{
cout<<"\n";
cout<<"######################################################################\n";
cout<<"# ALBERO BINARIO ORDINATO #\n";
cout<<"######################################################################\n";
cout<<"# Digita 1 per inserire un numero e carattere #\n";
cout<<"# Digita 2 per visualizzare l'albero ordinato #\n";
cout<<"# Digita 3 per uscire #\n";
cout<<"######################################################################\n";
cout<<"\nDigita la tua scelta-->";
cin >> scelta;

switch(scelta)
{
case 1:

cout << "\nInserisci un numero -> ";
cin >> numero;

cout << "\nInserisci un carattere -> ";
cin >> carattere;

albero1->inserisci(numero, carattere, temp);
system ("pause");
system ("cls");
break;

case 2:
if(temp==NULL)
{
cout << "\nNon ci sono elementi nell'albero";
system ("pause");
system ("cls");
break;
}
else
{
cout << "\nL'albero ordinato: \n";
albero1->visualizza(temp);
cout<< "\n";
system ("pause");
system ("cls");
break;
}

default:
cout << "\nINSERISCI UN VALORE CORRETTO\n\n";
break;
}
}while(scelta != 3);
return 0;
}




Come risolvete il problema?

[demos88]

Debuggando il codice ho notato che nel metodo nodo::inserisci hai una istruziona "sospetta": l'assegnazione temp=nuovo. L'oggetto nuovo non è istanziato ed è null, per cui anche temp sarà null (è curioso pure che tale assegnazione venga fatta se temp è già null). Poi richiami il metodo getInt() su temp, che come detto è null, per cui il programma si pianta per un tentato accesso a un oggetto null.


ps: scommetto che il programma è per un corso universitario di dati e algoritmi :asd:
prendi in considerazione l'idea di implementare un albero AVL, sarebbe carino

[InformaticoRC]

Debuggando il codice ho notato che nel metodo nodo::inserisci hai una istruziona "sospetta": l'assegnazione temp=nuovo. L'oggetto nuovo non è istanziato ed è null, per cui anche temp sarà null (è curioso pure che tale assegnazione venga fatta se temp è già null). Poi richiami il metodo getInt() su temp, che come detto è null, per cui il programma si pianta per un tentato accesso a un oggetto null.


ps: scommetto che il programma è per un corso universitario di dati e algoritmi :asd:
prendi in considerazione l'idea di implementare un albero AVL, sarebbe carino

Grazie per la risposta, ora lo andrò ad aggiustare.
Si, ci hai preso..è per il corso universitario di Algoritmi e strutture dati;) ;)

[InformaticoRC]

ho provato a seguire il tuo ragionamento e perciò ho cancellato l'assegnamento nuovo=null. mandandolo poi in esecuzione succede una cosa strana: se inserisco correttamente numero e carattere mi si blocca sempre, se invece inserisco la coppia numero numero l'inserimento avviene, ma se inserisco una seconda coppia mi si blocca nuovamente. mah :muro:

[demos88]

ho provato a seguire il tuo ragionamento e perciò ho cancellato l'assegnamento nuovo=null. mandandolo poi in esecuzione succede una cosa strana: se inserisco correttamente numero e carattere mi si blocca sempre, se invece inserisco la coppia numero numero l'inserimento avviene, ma se inserisco una seconda coppia mi si blocca nuovamente. mah :muro:
forse hai fatto qualche casino con i tipi di dati.
la variabile carattere l'hai dichiarata di tipo int, presumo non sia corretto

ps: con gli alberi ci ho smanettato tanto in java, in c++ non sono molto pratico, ma così a occhio ti consiglio di fare un bel restyle del codice perchè ho come l'impressione che ci siano diverse istruzioni superflue e oggetti che non servono (quel temp non mi convince)

[clockover]

Scusami ma perchè passi anche temp alla funzione?? Che cos'è temp?

La struttura albero è giusta però la funzione inserisci è un po pastricciata..
inserisci(key, value){
se root == null
root = nuovo nodo(key, value)
return
child = nuovo nodo(key, value)
iteri tutti i nodi dell'albero secondo la tua relazione d'ordine e inserisci come nuova foglia child

compatto e molto più leggibile

[InformaticoRC]

c'era la variabile di carattere e il metodo GetCar() distrattamente dichiarate di tipo int.
forse sto risolvendo, poi vi faccio vedere il codice.

[InformaticoRC]

Fatto, ora funziona ;)

#include <iostream>

using namespace std;

class nodo
{
private:
int numero;
char carattere;
nodo *sinistra;
nodo *destra;

public:
nodo();
void setInt(int num) {numero=num;};
int getInt(){return numero;};
void setCar(char car) {carattere=car;};
char getCar(){return carattere;};
void pointsx(nodo *point){sinistra=point;};
void pointdx(nodo *point){destra=point;};
nodo *getsx(){return sinistra;};
nodo *getdx(){return destra;};
};

nodo::nodo()
{
destra = NULL;
sinistra = NULL;
numero = 1;
carattere = 'a';
}

class albero
{
nodo *nuovo;

public:
albero();
void insert(int numero, char carattere, nodo *temp = NULL);
void visualizza(nodo *temp = NULL);
};


albero::albero()
{
nuovo = NULL;
}

void albero::insert(int numero, char carattere, nodo *temp)
{
nodo *new_node;
new_node = new nodo;
new_node->setInt(numero);
new_node->setCar(carattere);

if(temp == NULL)
temp = nuovo;

if(nuovo == NULL)
nuovo = new_node;
else
{
if(new_node->getInt() < temp->getInt())
{
if(temp->getsx() == NULL)
{temp->pointsx(new_node);
return;}
insert(numero, carattere, temp->getsx());

}
else
{
if(temp->getdx() == NULL)
{temp->pointdx(new_node);
return;}
insert(numero, carattere, temp->getdx());
}

return;
}
}

void albero::visualizza(nodo *temp)
{

if(temp == NULL)
temp = nuovo;

if(temp->getsx() != NULL)
visualizza(temp->getsx());

cout << endl << temp->getInt() << " " << temp->getCar() << " ";

if(temp->getdx() != NULL)
visualizza(temp->getdx());
}

int main()
{
int scelta;
int numero;
char carattere;

albero *albero1;
albero1 = new albero;


do
{
cout<<"\n";
cout<<"######################################################################\n";
cout<<"# ALBERO BINARIO ORDINATO #\n";
cout<<"######################################################################\n";
cout<<"# Digita 1 per inserire un numero e carattere #\n";
cout<<"# Digita 2 per visualizzare l'albero ordinato #\n";
cout<<"# Digita 3 per uscire #\n";
cout<<"######################################################################\n";
cout<<"\nDigita la tua scelta-->";
cin >> scelta;

switch(scelta)
{
case 1:
cout << "Digita valore numerico -> ";
cin >> numero;
cout << "Digita carattere -> ";
cin >> carattere;
albero1->insert(numero, carattere);
system("pause");
system("cls");
break;

case 2:
albero1->visualizza();
cout << "\n\n";
system("pause");
system("cls");
break;

}


}
while(scelta != 3);

system("pause");
return 0;
}

[demos88]

Non ho controllato il codice, se funziona bene.
Tuttavia alcune cose che consiglierei per un codice leggibile e più pulito:
- Il nome delle classi andrebbe scritto con iniziale maiuscola
- Il costruttore della classe Nodo è concettualmente errato: in pratica il costruttore assegna dei valori arbitrari alle variabili e poi ti tocca fare dei set. Sarebbe meglio scrivere un costruttore che riceve come parametri i 2 valori da assegnare così la creazione dell'oggetto è più elegante e veloce e si riduce a una riga:

Nodo new_node (1,'a');

Basta che fai un overloading del metodo Nodo();
- Il metodo inserisci così a occhio mi sembra utilizzi un oggetto in più del necessario. Magari prova a pensare a un metodo di inserimento ricorsivo, di solito i professori vanno matti per queste cose :asd:

[InformaticoRC]

Non ho controllato il codice, se funziona bene.
Tuttavia alcune cose che consiglierei per un codice leggibile e più pulito:
- Il nome delle classi andrebbe scritto con iniziale maiuscola
- Il costruttore della classe Nodo è concettualmente errato: in pratica il costruttore assegna dei valori arbitrari alle variabili e poi ti tocca fare dei set. Sarebbe meglio scrivere un costruttore che riceve come parametri i 2 valori da assegnare così la creazione dell'oggetto è più elegante e veloce e si riduce a una riga:

Nodo new_node (1,'a');

Basta che fai un overloading del metodo Nodo();
- Il metodo inserisci così a occhio mi sembra utilizzi un oggetto in più del necessario. Magari prova a pensare a un metodo di inserimento ricorsivo, di solito i professori vanno matti per queste cose :asd:

ringrazio per i consigli :cool: ;)