C ++ Overloading Operator <с параметром int (по сравнению с типом, который не обязательно будет int) - PullRequest
Новая
       30

C ++ Overloading Operator <с параметром int (по сравнению с типом, который не обязательно будет int)

1 голос
/ 22 декабря 2008

Я хочу перегрузить операторы <и>, чтобы разрешить поиск значения int внутри BST (которое предназначено не для хранения целых чисел, а слов).

Для тех, кто интересуется, почему эта перегрузка выполняется в первую очередь, проверьте C ++. Я застрял, заполняя этот BST правильными значениями

Мне нужны две функции поиска, чтобы можно было правильно заполнить слова словаря и позже определить его синонимы / антонимы.

Это функция поиска: 

//--- Definition of findId()
template <typename DataType>
DataType& BST<DataType>::findId(const int id ) const
{
   typename BST<DataType>::BinNodePointer locptr = myRoot;

   typename BST<DataType>::BinNodePointer parent =0;

   bool found = false;
   while (!found && locptr != 0)
   {
      if (locptr->data > id)       // descend left
        locptr = locptr->left;

      else if (locptr->data < id)  // descend right       
        locptr = locptr->right;

      else                           // item found
        found = true;
   }
   return found ? locptr->data : NULL;
}

И моя попытка до сих пор .. 

template <typename DataType>
bool BST<DataType>::operator >(const int anotherId)const
{
     typename BST<DataType>::BinNodePointer locptr;
     //undefined pointer, what should I make it point at?         

     return (locptr->data > anotherId);

}

Весь шаблон: 

#include <iostream>
#include <iomanip>
#include <stdlib.h>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE




template <typename DataType>
class BST
{
 public:
  /***** Function Members *****/
  BST();

  bool empty() const;


  DataType& findId (const int id)const;

  bool operator >(const int anotherId)const;

  bool operator < (const int anotherId)const;


  bool search(const DataType & item) const;

  void insert(const DataType & item);

  void remove(const DataType & item);

  void inorder(std::ostream & out) const;

  void graph(std::ostream & out) const;



  private:
  /***** Node class *****/
  class BinNode 
  {
   public:
    DataType data;
    BinNode * left;
    BinNode * right;

    // BinNode constructors
    // Default -- data part is default DataType value; both links are null.
    BinNode()
    : left(0), right(0)
    {}

    // Explicit Value -- data part contains item; both links are null.
    BinNode(DataType item)
    : data(item), left(0), right(0)
    {}


}; //end inner class

typedef BinNode * BinNodePointer; 

  /***** Private Function Members *****/
  void search2(const DataType & item, bool & found,
               BinNodePointer & locptr, BinNodePointer & parent) const;
 /*------------------------------------------------------------------------
   Locate a node containing item and its parent.

   Precondition:  None.
   Postcondition: locptr points to node containing item or is null if 
       not found, and parent points to its parent.#include <iostream>
 ------------------------------------------------------------------------*/

  void inorderAux(std::ostream & out, 
                  BST<DataType>::BinNodePointer subtreePtr) const;
  /*------------------------------------------------------------------------
    Inorder traversal auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Subtree with root pointed to by subtreePtr has been
        output to out.
 ------------------------------------------------------------------------*/

  void graphAux(std::ostream & out, int indent,
                      BST<DataType>::BinNodePointer subtreeRoot) const;
  /*------------------------------------------------------------------------
    Graph auxiliary function.

    Precondition:  ostream out is open; subtreePtr points to a subtree 
        of this BST.
    Postcondition: Graphical representation of subtree with root pointed 
        to by subtreePtr has been output to out, indented indent spaces.
 ------------------------------------------------------------------------*/

 /***** Data Members *****/
  BinNodePointer myRoot; 

}; // end of class template declaration

//--- Definition of constructor
template <typename DataType>
inline BST<DataType>::BST()
: myRoot(0)
{}

//--- Definition of empty()
template <typename DataType>
inline bool BST<DataType>::empty() const
{ return myRoot == 0; }







//--- Definition of findId()
template <typename DataType>
DataType& BST<DataType>::findId(const int id ) const
{
   typename BST<DataType>::BinNodePointer locptr = myRoot;

   typename BST<DataType>::BinNodePointer parent =0;

   bool found = false;
   while (!found && locptr != 0)
   {
      if (locptr->data > id)       // descend left
        locptr = locptr->left;

      else if (locptr->data < id)  // descend right       
        locptr = locptr->right;

      else                           // item found
        found = true;
   }
   return found ? locptr->data : NULL;
}


template <typename DataType>
bool BST<DataType>::operator >(const int anotherId)const
{
     typename BST<DataType>::BinNodePointer locptr;

     return (locptr->data > anotherId);

} 

template <typename DataType>
bool BST<DataType>::operator < (const int anotherId)const
{
     typename BST<DataType>::BinNodePointer locptr;

     return (locptr->data < anotherId);

} 



//--- Definition of search()
template <typename DataType>
bool BST<DataType>::search(const DataType & item) const
{
   typename BST<DataType>::BinNodePointer locptr = myRoot;

   typename BST<DataType>::BinNodePointer parent =0;

/*   BST<DataType>::BinNodePointer locptr = myRoot;
   parent = 0; */ //falta el typename en la declaracion original

   bool found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
        locptr = locptr->left;
      else if (locptr->data < item)  // descend right
        locptr = locptr->right;
      else                           // item found
        found = true;
   }
   return found;
}

//--- Definition of insert()
template <typename DataType>
inline void BST<DataType>::insert(const DataType & item)
{
   typename BST<DataType>::BinNodePointer 
        locptr = myRoot,   // search pointer
        parent = 0;        // pointer to parent of current node
   bool found = false;     // indicates if item already in BST
   while (!found && locptr != 0)
   {
      parent = locptr;
      if (item < locptr->data)       // descend left
         locptr = locptr->left;
      else if (locptr->data < item)  // descend right
         locptr = locptr->right;
      else                           // item found
         found = true;
   }
   if (!found)
   {                                 // construct node containing item


      locptr = new typename BST<DataType>::BinNode(item);  
      if (parent == 0)               // empty tree
         myRoot = locptr;
      else if (item < parent->data )  // insert to left of parent
         parent->left = locptr;
      else                           // insert to right of parent
         parent->right = locptr;
   }
   else
      std::cout << "Item already in the tree\n";
}

//--- Definition of remove()
template <typename DataType>
void BST<DataType>::remove(const DataType & item)
{
   bool found;                      // signals if item is found
   typename BST<DataType>::BinNodePointer 
      x,                            // points to node to be deleted
      parent;                       //    "    " parent of x and xSucc
   search2(item, found, x, parent);

   if (!found)
   {
      std::cout << "Item not in the BST\n";
      return;
   }
   //else
   if (x->left != 0 && x->right != 0)
   {                                // node has 2 children
      // Find x's inorder successor and its parent
      typename BST<DataType>::BinNodePointer xSucc = x->right;
      parent = x;
      while (xSucc->left != 0)       // descend left
      {
         parent = xSucc;
         xSucc = xSucc->left;
      }

     // Move contents of xSucc to x and change x 
     // to point to successor, which will be removed.
     x->data = xSucc->data;
     x = xSucc;
   } // end if node has 2 children

   // Now proceed with case where node has 0 or 2 child
   typename BST<DataType>::BinNodePointer 
      subtree = x->left;             // pointer to a subtree of x
   if (subtree == 0)
      subtree = x->right;
   if (parent == 0)                  // root being removed
      myRoot = subtree;
   else if (parent->left == x)       // left child of parent
      parent->left = subtree; 
   else                              // right child of parent
      parent->right = subtree;
   delete x;
}

//--- Definition of inorder()
template <typename DataType>
inline void BST<DataType>::inorder(std::ostream & out) const
{ 
   inorderAux(out, myRoot); 
}

//--- Definition of graph()
template <typename DataType>
inline void BST<DataType>::graph(std::ostream & out) const
{ graphAux(out, 0, myRoot); }

//--- Definition of search2()
template <typename DataType>
void BST<DataType>::search2(const DataType & item, bool & found,
                            BST<DataType>::BinNodePointer & locptr, 
                            BST<DataType>::BinNodePointer & parent) const
{
   locptr = myRoot;
   parent = 0;
   found = false;
   while (!found && locptr != 0)
   {
      if (item < locptr->data)       // descend left
      {
         parent = locptr;
         locptr = locptr->left;
      }
      else if (locptr->data < item)  // descend right
      {
         parent = locptr;
         locptr = locptr->right;
      }
      else                           // item found
         found = true;
   }
}
//--- Definition of inorderAux()
template <typename DataType>
void BST<DataType>::inorderAux(std::ostream & out, 
                               BST<DataType>::BinNodePointer subtreeRoot) const
{
   if (subtreeRoot != 0)
   {
      inorderAux(out, subtreeRoot->left);    // L operation
      out << subtreeRoot->data << "  ";      // V operation
      inorderAux(out, subtreeRoot->right);   // R operation
   }
}


//--- Definition of graphAux()


template <typename DataType>
void BST<DataType>::graphAux(std::ostream & out, int indent, 
                             BST<DataType>::BinNodePointer subtreeRoot) const
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << std::setw(indent) << " " << subtreeRoot->data << std::endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}


#endif

Ответы [ 3 ]

1 голос
/ 22 декабря 2008

Я не совсем уверен, почему вы хотите перегрузить> и <в этом случае, но, возможно, я не совсем понимаю вопрос. Похоже, вы намереваетесь иметь несколько различных видов узлов дерева, каждый из которых наследуется от <code>DataType. Если это так, просто добавьте функцию-член const к базовому классу DataType: 

class DataType
{
    private:
        mutable int internalID;
        // ...
    public:
        const int id() const { return internalID; }
        // ...
        virtual ~DataType();
};

Теперь, в вашем цикле findID, вы можете просто использовать: 


while (!found && locptr != 0)
{
    if (locptr->data.id() > id)
    {
        locptr = locptr->left;
    }
    else if (locptr->data.id() < id)
    {
        locptr = locptr->right;
    }
    else
    {
        found = true;
    }
}

И вам не нужно проходить через все ненужные хлопоты, связанные с перегрузкой операторов.

1 голос
/ 22 декабря 2008

Перегрузка оператора здесь не имеет смысла.

Функция-член 

bool BST<DataType>::operator >(const int anotherId)const;

По сути, это означает сравнить целое дерево с целым числом, что, на мой взгляд, не является вашей целью. Возможно, вы захотите убедиться, что у вас <определено для типа данных, а затем также добавить в класс узла что-то вроде </p> 

template<typename type>
friend bool operator>(const BST<type>::node&, BST<type>::const node&);

Мои два цента как минимум.

0 голосов
/ 22 декабря 2008
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...