[RISOLTO] - [C++] Dato membro statico

[N1cuz]

In un classico esercizio di informatica devo implementare una classe "albero binario di ricerca" assegnando un nodo sentinella ai figli delle foglie dell'albero anzichè NULL, il problema è che il nodo sentinella dovrebbe essere condiviso da tutte le istanze della classe, dunque statico, ma non riesco ad inizializzarlo e non capisco dov'è che sbaglio:

Codice: Seleziona tutto

template <class T>
class Tree
{
 protected:
  typedef struct node
  {
    T item;
    long key;
    node* left;
    node* right;
    node* daddy;
  
    node()
    {
      key = 0;
      left = right = daddy = &NIL;
    }

    node(T i, long k)
    {
      key = k;
      item = i;
      left = right = daddy = &NIL;
    }
};

 private:
  node* root;
  static node NIL;

... ecc ...

};
template <class T>
Tree<T>::node Tree<T>::NIL; 

L'errore che ottengo è:

Codice: Seleziona tutto

nico@nicoLaptop:~$ make ./Documents/C++/Tree/main
g++     Documents/C++/Tree/main.cpp   -o Documents/C++/Tree/main
In file included from Documents/C++/Tree/main.cpp:1:
Documents/C++/Tree/BinaryTree.h:240: error: expected constructor, destructor, or type conversion before 'Tree'
make: *** [Documents/C++/Tree/main] Error 1

Qualcuno può aiutarmi? Grazie mille.
Nico

[Toni]

ciao
come suggerito da gcc l errore sta nella mancanza di un costruttore
dovresti aggiungere nel campo public di tree un membro tipo
tree(lista di argomenti per inizializzare le variabili)

[N1cuz]

ciao
come suggerito da gcc l errore sta nella mancanza di un costruttore
dovresti aggiungere nel campo public di tree un membro tipo
tree(lista di argomenti per inizializzare le variabili)

Il costruttore l'ho fatto, non l'ho scritto nel post perchè lo davo per scontato...

[mcosta]

Puoi postare il codice per intero?

[N1cuz]

Ti posto quello dell' albero binario, tanto anche sull'albero RB il problema è il solito, se non uso la sentinella viene compilato non sono riuscito a capire dov'è l'errore:

Codice: Seleziona tutto

#ifndef _BinaryTree_h
#define _BinaryTree_h 1

#include <iostream>

template <class T>
class Tree
{
 protected:
  typedef struct node
  {
    T item;
    long key;
    node* left;
    node* right;
    node* daddy;
  
    node()
    {
      key = 0;
      left = right = daddy = &NIL;
    }

    node(T i, long k)
    {
      key = k;
      item = i;
      left = right = daddy = &NIL;
    }

    node(const node& rhs)
    {
      key = 0;
      left = right = daddy = &NIL;

      key = rhs.key;
      left = rhs.left;
      right = rhs.right;
      daddy = rhs.daddy;
    }

    node& operator=(const node& n)
    {
      if (this == &n)
	return *this;
      
      key = n.key;
      left = n.left;
      right = n.right;
      daddy = n.daddy;

      return *this;
    }

      T& Get_key() 
    {
      return key;
    }
  };

 private:
  node* root;
  static node NIL;

 void Clean(node* r)
  {
    if(r != &NIL);
      {
	Clean(r->left);
	Clean(r->right);
	delete r;
      }
  }

 public:
 Tree()
    {
      root = new node;
      NIL.daddy = root;
      root = &NIL;
    }

   ~Tree()
   {
     Clean(root);
   }

   void insert(T obj, long k)
  {
    node* x = root;
    node* y = &NIL;
    node* z = new node(obj, k);
    //z->daddy = z->left = z->right = NIL;

    while(x != &NIL)
      {
	y = x;
	if(z->key <= x->key)
	  x = x->left;
	else
	  x = x->right;
      }

    z->daddy = y;
    if(y == &NIL)
      root = z; 
    else 
      if(z->key <= y->key)
	y->left = z;
      else
	y->right = z;
  }

  node* minimum(node* x)
    {
      while(x->left != &NIL)
	x = x->left;

      return x;
    }

  node* maximum(node* x)
    {
      while(x->right != &NIL)
	x = x->right;

      return x;
    }

  node* search(T k)
    {
      node* tmp = new node;
      tmp =  root;      

      while(tmp != &NIL && k != tmp->key)
	{
	  if(tmp->key > k)
	    tmp = tmp->left;
	  else
	    tmp = tmp->right;
	}
      
      return tmp;
    }


  node* successor(node* x)
    {
      if(x->right != &NIL)
	return minimum(x->right);

      node* y = x->daddy;

      while(y != &NIL && x == y->right)
	{
	  x = y;
	  y = y->daddy;
	}

      return y;
    }

  node* predecessor(node* x)
    {
      if(x->left != &NIL)
	return maximum(x->left);
     
      node* y = x->daddy;

      while(y != &NIL && x == y->left)
	{
	  x = y;
	  y = y->daddy;
	}

      return y;
    }
     
  node* remove(const T& k)
    {
      node* z = search(k);

      node* x = new node;
      node* y = new node;

      if(z->left == &NIL || z->right == &NIL)
	y = z;

      else
	y = successor(z);
	 
      if(y->left != &NIL) 
	x = y->left;

      else 
	x = y->right;
	
      x->daddy = y->daddy;

      if(y->daddy == &NIL)
	root = x;

      else
	{
	  if(y == y->daddy->left)
	    y->daddy->left = x;

	  else
	    y->daddy->right = x;
	}

      if(y != z)
	z->key = y->key;

      return y;
    }

  node* Get_pappy(const node& s)
    {
	return s.daddy;
    }

  node* Get_root() const
    {
      return root;
    }

  void print(const node* r)
  {
    if(r != &NIL)
      {
	print(r->left);
	std::cout << r->key << " ";
	print(r->right);
      }
  }
};

template <class T>
Tree<T>::node Tree<T>::NIL;

#endif

[414N]

Perchè incorpori la definizione della struttura nodo dentro l'albero?

[N1cuz]

Perchè incorpori la definizione della struttura nodo dentro l'albero?

... e perchè non dovrei?

[414N]

Perchè incorpori la definizione della struttura nodo dentro l'albero?

... e perchè non dovrei?

Per una questione di separazione del codice. Mantenendola all'interno di Tree risulta anche poco estensibile.
Ovviamente di questo ti importa poco se è un esercizio fine a sé stesso.

[N1cuz]

Ok, siamo d'accordo, avrei potuto fare una classe nodo base da cui derivare nodi specializzati per ogni utilizzo (con campi aggiuntivi come "color" per alberi rb, "rank" per alberi di selezione e così via...), ma non ti pare esargerato per fare un semplice esercizio? In questo modo faccio prima (ed è sufficiente per lo scopo) con una struttura ad hoc implementata nella classe.

P.S.
In generale la tua critica è più che corretta!