Implement a dictionary by using Trie . Requirement: a. Complete trie.h, trie.cpp, and client1.cpp.

client1

#include #include "trie.h"

using namespace std;

int main() { Trie vocabulary; cout << "Type '0'--quit; '1'--add a word; '2'--search a word; '3'--search prefix: "; int choice; cin >> choice; while(choice) { if(choice == 1) { cout << "Add to the vocabulary this word: "; string word; cin >> word; vocabulary.add(word); } else if(choice == 2) { cout << "Search this word: "; string key; cin >> key; if(vocabulary.contains(key)) cout << key << " exists!" << endl; else cout << key << " does not exists." << endl; } else if(choice == 3) { cout << "Search this prefix: "; string key; cin >> key; if(vocabulary.isPrefix(key)) cout << key << " is a prefix." << endl; else cout << key << " is not a prefix." << endl; } else { cout << "Input incorrect. Try again." << endl; } cout << "Type '0'--quit; '1'--add a word; '2'--search a word; '3'--search prefix: "; cin >> choice; } return 0; }

-------------------------------------------------------------------------------------------------------------------

trie.h

#ifndef TRIE_H #define TRIE_H

#define MAX_CHAR 256

class Node { private: Node *children[MAX_CHAR]; bool bisEnd; public: Node(); bool isEnd(); void insert(string suffix); Node* search(string pat); };

class Trie { private: Node root; public: void add(string word); bool contains(string pat); bool isPrefix(string pat); }; #endif

--------------------------------------------------------------------------------------------

trie.cpp

#include #include "trie.h"

using namespace std;

/* add your Trie implementation here */