|
-
December 8th, 2008, 07:16 PM
#1
Stuck with A Trie implementation
Hi guys,
Anyone can give me some help for this Trie application. I implemented an insert method and a find method in the Trie class, and in the Scrab application, I inserted 3 strings into the Trie, and then use find method to check whether the string is in the Trie. The insert method seems working fine, but the find method cannot find the string. Please give me some help guys, I haven't touched any C/C++ things for a long time(working on Java), but now I need to reactivate my C/C++ skills. So please help me with that, Guys.
The Trie class and Scrab applciation is as following:
Code:
#include "Trie.h"
Trie::Trie() {
valid = false;
}
//inserts a word into the trie,give the entry of the first char and last one
bool Trie::insert(string::const_iterator first, string::const_iterator last) {
Trie currentNode;
if(first != last) {
map<char,Trie>::iterator iter = children.find(*first);
if(iter != children.end()) {
currentNode = (iter->second);
return (currentNode.insert(++first, last));
}
else {
if((first == (last - 1)) && !valid) {
children.insert(map<char,Trie>::value_type(*first,currentNode));
cout << "last char of each word:" << *first << endl;
cout << "insert:childrensize after last char:" << children.size() << endl;
valid = true;
return 1;
}
else {
children.insert(map<char,Trie>::value_type(*first,currentNode));
cout << "insert:childrensize after every insert:" << children.size() << endl;
return currentNode.insert(++first,last);
}
}
}
return 1;
}
//checks if a word is in the trie, give the entry of the first char and last one
bool Trie::find(string::const_iterator first, string::const_iterator last) const {
if (first != last) {
//Checks whether it reaches the end of the
if(children.size() == 0 && valid){
return 1;
}
if (children.find(*first) != children.end()) {
Trie* currentNode = (children.find(*first))->second;
//cout << "find:child:" << *(first);
//cout << "find:children size:" << currentNode.children.size() << endl;
return currentNode.find(first+1,last);
}
else {
cout << "Something wrong~~" << endl;
return 0;
}
}
return 1;
}
class Scrab {
public:
Trie root;
Scrab();
~Scrab();
};
Scrab::Scrab(){
cout << "Initializing Scrab" << endl;
}
Scrab::~Scrab(){
cout << "Destructing Scrab" << endl;
}
int main( int argc, const char* argv[] )
{
int total_words = 0;
char* charSequence;
Scrab scrab;
cout << "***********************" << endl;
cout << "* Scrabbinator Helper *" << endl;
cout << "***********************" << endl;
if (argc != 2) {
cerr << "Please type in file path and name."<<endl;
}
if (argv[1] != NULL) {
cout<<argv[1]<<endl;
ifstream in;
in.open(argv[1]);
if(!in) { // file couldn't be opened
cerr << "Error: file could not be opened" << endl;
exit(1);
}
while(!in.eof()){
//cout << "children size:" << scrab.root.children.size() << endl;
//cout << "found or not:" << scrab.root.find(word.begin(),word.end()) << endl;
string word;
in>>word;
if(word.length() != 0) {
if(scrab.root.insert(word.begin(),word.end()))
total_words++;
cout<<"result:"<<scrab.root.find(word.begin(),word.end())<<endl;
}
}
cout<<"*******************************" <<endl;
cout<<"Read " <<total_words<<" distinct word(s) from the file \'"<<argv[1]<<"\'"<<endl;
cout<<"Please enter letter sequence and optional match pattern:"<<endl;
cin >> charSequence;
in.close();
}
Last edited by RICO_BEE; December 8th, 2008 at 11:13 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|