Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
221 views
in Technique[技术] by (71.8m points)

token - C++ I'm stuck filling this BST with its proper values

I have created a BST full of WordInfo objects that have a vector to point out which of the other WordInfo objects is a synonym or antonym. Each word is identified by an integer on its source file, dictionary.txt. The BST has received so far its list of words, but I have trouble filling in the synonyms. To put it bluntly, I'm pretty confused on how to make my objects interact the way I want them to.

Here's where I think is the core of my problem:

 //--function for getting synonyms in a vector
    void pushSynonyms(string synline, BST <WordInfo> wordTree)
      {
           int lineSize = synline.size();

             const char *aux;

             aux=synline.data();

             int index=0;

             int searchedOne= aux[0]; 
             //wanting to find an element in the tree with this ID


             //lacking:  search function

             while (index<=lineSize){
             mySynonyms.push_back (aux[index]); 

             index++;
             }    

      }



#include <iostream>
#include <fstream>
#include <string>

#include <sstream>
#include <stdlib.h>
#include <vector>

#include "MiBST.h"

using namespace std;

class WordInfo {

      public: 

      WordInfo() {
          // nothing to define?       
                 }

      ~WordInfo() {
           //nothing to define?       
                 }

      //--id accesor
      int id () const {return myId;}


      //--input function for filling Words
      void readWords (istream &in)
      {
         in>>myId>>word;     
      }



      //--function for getting synonyms in a vector
    void pushSynonyms(string synline, BST <WordInfo> wordTree)
      {
           int lineSize = synline.size();

             const char *aux;

             aux=synline.data();

             int index=0;

             int searchedOne= aux[0];


             //lacking: define search function

             while (index<=lineSize){
             mySynonyms.push_back (aux[index]); 

             index++;
             }    

      }



      //--function for getting antonyms in a vector
      void pushAntonyms(string synline, BST <WordInfo> wordTree )
      {
           int lineSize = synline.size();

             const char *aux;

             aux=synline.data();



             int index=0;

             // now I need fo find the right words to pair up


             while (index<=lineSize){
             myAntonyms.push_back (aux[index]); 

             index++;
             }    

      }

      //--output function
      void printWords (ostream &out)
      {
         out<<myId<<" "<<word;     
      }

      //--equals operator
      bool operator == (const WordInfo &otherWordInfo) const
      { return myId == otherWordInfo.myId;}

      //--equals operator for String
      bool operator == (const string & aString) const
      {return word ==aString;}

      //--less than operator
      bool operator < (const WordInfo & otherWordInfo)const
      {return myId<otherWordInfo.myId;}

      //--more than operator
      bool operator > (const WordInfo &otherWordInfo) const
      { return myId > otherWordInfo.myId;}



      private:
              vector<int> mySynonyms;
              vector <int> myAntonyms;
              string word;
              int myId;

      };


      //--- Definition of input operator
      istream & operator>>(istream & in, WordInfo & word)
      {


           word.readWords(in);

           //I want to call word.readSyns(in) too, how?
      }





      //---Definition of output operator

      ostream & operator <<(ostream &out, WordInfo &word)
      {
            word.printWords(out);       
      }

      int main() {

          //search each word by id and 
          // define its synonyms

          string wordFile;

          cout<< "enter name of dictionary file: ";
          getline (cin,wordFile);

          ifstream inStream(wordFile.data());

          if(!inStream.is_open())
          {
           cerr<<"cannot open "<<wordFile<<"
";
           exit(1);                       
          }

          //build the bst of word records
          BST <WordInfo> wordTree; //BST of word records

          WordInfo aword; // a word record

          //--loop that fills tree with words
          while((inStream>> aword && (!(aword=="synonyms"))))
          {
             wordTree.insert(aword);                  
          }

          string line;

          //--loop that takes synonyms
          while((inStream>>line)&& (line!="antonyms")){

                 aword.pushSynonyms(line, wordTree);                    
          }

          //--loop that takes antonyms           
           while(inStream >> line) {

               if (inStream.eof())break; 
           }

           wordTree.graph(cout);

          system("PAUSE");

          return 0;
          }

header file:

#include <iostream>
#include <iomanip>

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE




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

  bool empty() 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 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
";
}

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Leaving aside the comments others have made -- I confess that there is more code in this sample than I am willing to look at -- I think the fundamental problem you are having is that your existing search function searches by object, whereas you need one that searches by the id. Create a new search function that takes the id as a parameter and iterate through your tree comparing the id of the current WordInfo object to the id passed in. When you find the one with the matching id, return it (instead of returning true/false as to whether it was found). If you don't find an object with the matching id, return null. You'll need to a way to compare an id (int) to a WordInfo object. My C++ is a little rusty so the syntax may be a little off.

//--- Definition of find()
template <typename DataType>
DataType& BST<DataType>::find(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;
}

Note: this requires that you implement operator>(const int id) and operator<(const int id).


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

2.1m questions

2.1m answers

60 comments

57.0k users

...