Create the dictionary class using c++ Prefix Data Structure To store the words i

Question

Create the dictionary class using c++

Prefix Data Structure To store the words in this assignment, you will be creating dictionary using a data structure called a prefix tree. This data structure allows for the quick lookup of whether or not a word is valid. It will also allow you to find all words with a specific prefix. Rather than store each word individually, we instead store the words using a tree: root Node Node Word flag false false false false Node Node Word flag true true false Node Node NULL false true false Word flag The example above shows two how the words "aa" (abbreviation for administrative assistant) and "axe" are represented using a tree. Each node holds 26 pointers to other nodes; each of these nodes corresponds to a specific letter. Each node also holds an array of 26 boolean flags. Essentially, each word is represented by a path down the tree. If the path ends with a "false", then the path does not represent a valid word. For example, the root node has a path from the first Node pointer (i e. the pointer representing 'a')to another Node. Notice that this second level node has a "true flag for the first index. This indicates that "aa" is a valid word. If we examine the pointer for the second level 'x' position, we find that a path exists fo "ax" to another node. When we examine this third level node, we find that the pointer for the 'a' position is NULL This indicates that "aaa" is not a valid word. If we examine the pointer for the 'e' position, we find that the flag for this position is true; this make sense since "axe" is a valid word. Prefixes A prefix is a valid path that may or may not be a valid word. For example, "a" and Max are valid prefixes since there are words starting with these letters. However, Naaa" s not a valid prefix.

Explanation / Answer

#include #include #include #include #include template struct StdMapCR { std::vector data; bool Get(KeyType key, ValueType & val) { /*...*/ } void Put(KeyType key, ValueType val) { /*...*/ } void Resize(unsigned long new_size) { /*...*/ } //... }; template struct StdListCR { std::vector data; bool Get(KeyType key, ValueType & val) { /*...*/ } void Put(KeyType key, ValueType val) { /*...*/ } void Resize(unsigned long new_size) { /*...*/ } //... }; template struct HashFunction; template struct HashFunction { struct Hash { unsigned long operator()(const std::string & key, unsigned long size) { /*...*/ } }; }; template struct SearchFunctions { struct Equal { bool operator()(KeyTypev1, KeyTypev2) { return v1==v2; } }; struct Less { bool operator()(KeyTypev1, KeyTypev2) { return v1

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.