C ++ estoy atascado llenado este BST con sus valores propios
https://stackoverflow.com/questions/384587
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
He creado una BST lleno de objetos WordInfo que tienen un vector de señalar cuál de los otros objetos WordInfo es un sinónimo o antónimo. Cada palabra se identifica por un número entero en su archivo de origen, dictionary.txt. El BST ha recibido hasta el momento de su lista de palabras, pero tengo problemas para llenar los sinónimos. Para decirlo sin rodeos, estoy bastante confundido sobre cómo hacer que mis objetos interactúan como yo quiero que lo hagan.
Aquí es donde creo que es el núcleo de mi problema:
//--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;
}
archivo de cabecera:
#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
dictionary.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
Solución
Dejando a un lado los comentarios que otros han hecho - Confieso que hay más código de este ejemplo de lo que estoy dispuesto a mirar - Creo que el problema fundamental que tiene es que su función busca búsqueda existente por objeto, mientras se necesita uno que busca la ID. Crear una nueva función de búsqueda que toma el id como parámetro y recorrer el árbol de la comparación de la identificación de la corriente objeto WordInfo al ello se ha pasado. Cuando encuentre el que tiene la Identificación del juego, devolverlo (en lugar de devolver verdadero / falso en cuanto a si se ha encontrado). Si no encuentra un objeto con el identificador de juego, volver nula. Tendrá que una manera de comparar un identificador (int) a un objeto WordInfo. Mi C ++ es un poco oxidado por lo que la sintaxis puede ser un poco apagado.
//--- 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;
}
Nota: esto requiere que implemente operator>(const int id) y operator<(const int id)
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
