Write a C++ program that will create a trie data structure which can handle the
ID: 3583151 • Letter: W
Question
Write a C++ program that will create a trie data structure which can handle the following text: "I like food". The user will enter the text. After you build the trie, allow the user to enter a single word and determine whether or not it was in the original text. You should provide 2 functions: (1) receive the text and build the trie; (2) receive a word and determine whether it exists within the text.
Please Do not use:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
Explanation / Answer
#include <iostream>
#include <vector>
using namespace std;
class Nodes {
public:
Nodes() { mContents = ' '; mMarkers = false; }
~Nodes() {}
char content() { return mContents; }
void setContent(char c) { mContents = c; }
bool wordMarkers() { return mMarker; }
void setWordMarkerss() { mMarkers = true; }
Nodes* findChild(char c);
void appendChild(Nodes* child) { mChildrens.push_back(child); }
vector<Nodes*> children() { return mChildrens; }
private:
char mContents;
bool mMarker;
vector<Nodes*> mChildrens;
};
class Trie program {
public:
Trie program();
~Trie program();
void addWords(string s);
bool searchWords(string s);
void deleteWords(string s);
private:
Nodes* root;
};
Nodes* Nodes::findChild(char c)
{
for ( int i = 0; i < mChildrens.size(); i++ )
{
Nodes* tmp = mChildrens.at(i);
if ( tmp->content() == c )
{
return tmp;
}
}
return NULL;
}
Trie program::Trie program()
{
root = new Nodes();
}
Trie program::~Trie program()
{
// Free memory
}
void Trie program::addWords(string s)
{
Nodes* current = root;
if ( s.length() == 0 )
{
current->setWordMarkerss(); // an empty word
return;
}
for ( int i = 0; i < s.length(); i++ )
{
Nodes* child = current->findChild(s[i]);
if ( child != NULL )
{
current = child;
}
else
{
Nodes* tmp = new Nodes();
tmp->setContent(s[i]);
current->appendChild(tmp);
current = tmp;
}
if ( i == s.length() - 1 )
current->setWordMarkerss();
}
}
bool Trie program::searchWords(string s)
{
Nodes* current = root;
while ( current != NULL )
{
for ( int i = 0; i < s.length(); i++ )
{
Nodes* tmp = current->findChild(s[i]);
if ( tmp == NULL )
return false;
current = tmp;
}
if ( current->wordMarkers() )
return true;
else
return false;
}
return false;
}
// Test program
int main()
{
string inputtext;
cout << "Enter your inputtext: " << flush;
cin >> inputtext;
getline (cin, inputtext);
addWords(string inputtext);
string inputword;
cout << "Enter your input word: " << flush;
cin >> inputword;
getline (cin, inputword);
if ( Trie program->searchWords(inputword)
cout << "Found" << endl;
else
cout << "not Found " << endl;
delete Trie program;
}
Output:
Enter your inputtext: I like food
Enter your inputword:like
Found
Enter your inputtext: I like food
Enter your inputword:the
not Found
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.