Comments and corrections are welcome.
Enjoy
// dictionary.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
#include
using namespace std;
//TRIE data structure implementation
//every valid node contains a character and a pointer to other nodes
// e.g. root->a->p->p->l->e
class Edge;
class Word
{
public:
Word()
{
for(int i=0;i<26;i++) edge[i] = NULL;
}
~Word()
{
for(int i=0;i<26;i++)
{
if(edge[i])
delete edge[i];
}
}
string word;
string desc; //description
Edge* edge[26]; //the index corresponds to the character in alphabetic order
};
class Edge
{
public:
Edge() {word=NULL;}
~Edge() {if(word) delete word;}
Word* word;
};
class Dictionary
{
public:
Dictionary();
~Dictionary();
void AddWord(char* w, char* des);
void RemWord(char* w);
int Search(char* w);
void SearchWild(char* w);
private:
int TryRemWord(Word* wrd, char* w);
void TraverseAllEdges(Word* wrd);
Word* Root; //stores the pointer to Root Word
};
Dictionary::Dictionary()
{
Root = new Word();
}
Dictionary::~Dictionary()
{
delete Root;
}
/* adds a word w to the dicitionary with description des*/
void Dictionary::AddWord(char* w, char* des)
{
Word* node = Root;
for(int i=0; w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
//cout << "edge for " << w[i] << " found\n";
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '\0')
{
//add the word dscription here given that the tree node already exists for this word
node->word = w;
node->desc = des;
}
}
else
{
//cout << "edge for " << w[i] << " created\n";
node->edge[w[i]-'a'] = new Edge();
node = node->edge[w[i]-'a']->word = new Word();
node->word.assign(w, i+1);
//cout << "word " << node->word.c_str() << " stored\n";
if(w[i+1] == '\0')
{
node->desc = des;
//cout << "description for word " << w << " stored\n";
}
}
}
}
/* removed a word w from the dictionary*/
void Dictionary::RemWord(char* w)
{
TryRemWord(Root, w);
}
int Dictionary::TryRemWord(Word* wrd, char* w)
{
int ret = -1;
int istargetword = 0;
//Traverse to reach the word
if(*w != '\0')
{
if(wrd->edge[*w-'a'])
{
if(*(w+1) != '\0')
{
//word found, now try removing the word and its predecessors
ret = TryRemWord(wrd->edge[*w-'a']->word, w+1);
}
else
{
ret = 0;
istargetword = 1;
}
}
else
ret = -1;
}
if(ret == 0)
{
//check if the current node has edges
int i;
for(i=0;i<26;i++)
{
if(wrd->edge[*w-'a']->word->edge[i])
{
ret = -1;
break;
}
}
if(i==26)
{
//there is no edge to it, check if it is the target word to be deleted
if(istargetword)
{
cout << "removing " << wrd->edge[*w-'a']->word->word.c_str() << endl;
delete (wrd->edge[*w-'a']);
wrd->edge[*w-'a'] = NULL;
ret = 0;
}
else
{
//there is no edge to it, now check for any valid word description
if(wrd->edge[*w-'a']->word->desc.empty())
{
cout << "removing " << wrd->edge[*w-'a']->word->word.c_str() << endl;
delete (wrd->edge[*w-'a']);
wrd->edge[*w-'a'] = NULL;
ret = 0;
}
else
ret = -1; //can't delete it because it is a valid word
}
}
else
{
if(istargetword)
wrd->edge[*w-'a']->word->desc.clear(); //can't delete it because it is not leaf node, so just remove the description
}
}
return ret;
}
/* searches a word w from the dictionary and prints the description*/
int Dictionary::Search(char* w)
{
//traverse the tree and find the match
Word* node = Root;
for(int i=0; w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '\0' && !node->desc.empty())
{
cout << w << ": " << node->desc.c_str() << endl;
return 0;
}
}
else
break;
}
cout << "meaning of " << w << " not found!\n";
return -1;
}
/* searches all the words with starting string as "w" and prints them */
void Dictionary::SearchWild(char* w)
{
Word* node = Root;
for(int i=0; w[i] != '*' && w[i] != '\0'; i++)
{
if(node->edge[w[i]-'a'])
{
node = node->edge[w[i]-'a']->word;
if(w[i+1] == '*')
{
TraverseAllEdges(node);
return;
}
}
}
}
/* traverses all the edges of a word recursively */
void Dictionary::TraverseAllEdges(Word* wrd)
{
if(!wrd->desc.empty())
cout << wrd->word.c_str() << endl;
for(int i=0;i<26;i++)
{
if(wrd->edge[i])
{
TraverseAllEdges(wrd->edge[i]->word);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Dictionary MDict;
MDict.AddWord("apple","it is a fruit");
MDict.AddWord("table","it is a furniture");
MDict.AddWord("earth","it is a planet");
MDict.AddWord("car","it is a vehicle");
MDict.AddWord("computer","it is an electronic device");
MDict.AddWord("ape","it is an animal");
MDict.AddWord("apex","the highest");
MDict.Search("apple");
MDict.SearchWild("c*");
MDict.RemWord("ape");
MDict.Search("apex");
MDict.AddWord("ape", "it is an animal");
MDict.Search("ape");
return 0;
}
