[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
prendi in considerazione l'idea di implementare un albero AVL, sarebbe carino

[InformaticoRC]

Originariamente inviato da 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
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

[demos88]

Originariamente inviato da 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

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

[InformaticoRC]

Originariamente inviato da 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

ringrazio per i consigli