C ++ أنا عالق ملء هذا BST مع قيمها المناسبة
https://stackoverflow.com/questions/384587
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
لقد قمت بإنشاء BST مليئة بالأشياء WordInfo التي تحتوي على متجه للإشارة إلى أي من كائنات WordInfo الأخرى هو مرادف أو متنقل. يتم تحديد كل كلمة عن طريق عدد صحيح في ملف المصدر الخاص به، قاموس. تلقت BST حتى الآن قائمة الكلمات الخاصة به، ولكن لدي مشكلة في ملء المرادفات. لوضعها بصراحة، أنا مرتبك للغاية حول كيفية جعل كائناتي تفاعل بالطريقة التي أريدها.
إليك أين أعتقد أنها جوهر مشكلتي:
//--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
المحلول
ترك تعليقات جانبا للتعليقات التي اتخذتها الآخرين - أعترف بأن هناك مزيد من التعليمات البرمجية في هذه العينة أكثر مما كنت على استعداد للنظر في - أعتقد أن المشكلة الأساسية التي تواجهها هي أن وظيفة البحث الحالية التي تبحث عنها عن طريق كائن، في حين تحتاج إلى واحد الذي يبحث عن طريق المعرف. قم بإنشاء وظيفة بحث جديدة تأخذ المعرف كمعلمة وتكرر من خلال أشجارك تقارن معرف كائن WordInfo الحالي إلى المعرف الذي تم تمريره. عند العثور على واحد مع معرف المطابقة، قم بإرجاعه (بدلا من إرجاع True / False وكما إذا تم العثور عليها). إذا لم تجد كائنا مع معرف المطابقة، فارجع NULL. ستحتاج إلى وسيلة لمقارنة معرف (INT) كائن WordInfo. بلدي C ++ هو صدئ قليلا لذلك قد يكون بناء الجملة قبالة قليلا.
//--- 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).
لا تنتمي إلى StackOverflow
