C++ 我坚持用它的正确值填充这个 BST [英] C++ I'm stuck filling this BST with its proper values
问题描述
我已经创建了一个充满 WordInfo 对象的 BST,它有一个向量来指出哪些其他 WordInfo 对象是同义词或反义词.每个单词在其源文件 dictionary.txt 中由一个整数标识.到目前为止,BST 已经收到了它的单词列表,但我在填写同义词时遇到了麻烦.坦率地说,我很困惑如何让我的对象按照我希望的方式进行交互.
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<<"\n";
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;
}
头文件:
#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\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
字典.txt
1 cute
2 hello
3 ugly
4 easy
5 difficult
6 tired
7 beautiful
synonyms
1 7
7 1
antonyms
1 3
3 1 7
4 5
5 4
7 3
推荐答案
先不说其他人的评论——我承认这个示例中的代码比我愿意看的要多——我认为是根本问题您遇到的是您现有的搜索功能按对象搜索,而您需要一个按 id 搜索的功能.创建一个新的搜索函数,将 id 作为参数并遍历树,将当前 WordInfo 对象的 id 与传入的 id 进行比较.当找到具有匹配 id 的那个时,返回它(而不是返回 true/false是否被发现).如果没有找到具有匹配 id 的对象,则返回 null.您需要一种将 id (int) 与 WordInfo 对象进行比较的方法.我的 C++ 有点生疏,所以语法可能有点不对.
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;
}
注意:这需要你实现 operator>(const int id)
和 operator<(const int id)
.
Note: this requires that you implement operator>(const int id)
and operator<(const int id)
.
这篇关于C++ 我坚持用它的正确值填充这个 BST的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!