Answer Happy

Description
Input.txt
Boilerplate.cpp code
Output.txt
Objective: The main objective of this project is to learn to construct a Trie (pronounced "try") like data structure. Description: Ever wonder how auto fil works? When you start typing a word or a sentence on Google, and it starts giving you the suggested completed sentences? Or how we start thinking when we get the first couple of letters correct in daily Wordle? Often when we are given a word that has a prefix of a couple of letters, we immediately start to narrow down the search space amongst all the words we know of. A Trie data structure (pronounced as "try") is an efficient structure to retrieve data. Following is an explanation of the data structure with an example. Recall the simple bucket sort program described in your textbook. The trie data structure is similar in nature, but it is used for inserting, searching, and removal of a set of words. We can assume that we are dealing with all upper case letters. We further assume that letters 'A'-'Z' are assigned numbers 0-25. That is 'A' is given the number 0 and 'Z' is given the number 25. We will now create an array of size 26. Let us say that we have two words "APPLE” and “APRIL”. In the one level trie data structure, at index position 0, we will have a linked list containing the words "APPLE" and "APRIL" in order. In a two level trie data structure, at index position 0, we will have a pointer to another array of size 26. At index position 15 (corresponding to letter P) this array there will be a linked list containing the words "APPLE" and "APRIL". If we have one more level, then that array will have pointers at locations 15 (corresponding to P) and 17 (corresponding to R). These are shown in the figures below. 0 0 1 2 2 Leaf Node 15 CAPPLE H 0 APRIL Linked List A trie data structure with depth 2 25 25 0 012 012 2 15 15/16 17 -0 ▼ ▼ APPLE APRIL A trie data structure with depth 3 25 25 25 Root Node
As part of this project, you need to implement the two classes given to you - TrieNode class and TrieDS class. Make sure all the standard methods for classes are specified and implemented. You are not allowed to use the string class that is part of the STL. You can simply use an array of characters. Please note that every string is terminated by a single character '\0'. You can use the STL list class to store the character arrays at the leaf nodes of the trie data structure. The list of words is to be stored in a sorted order in any linked list. There are multiple operations that can be performed on the data structure. The following are the various options and their explanation. I WORD- o Option A followed by a UPPER CASE WORD will insert the word in the appropriate list. R WORD - o Option R followed by a UPPER CASE WORD will remove the word from the appropriate list if present. F WORD o Option F followed by a UPPER CASE WORD will search for the word from the list and return true or false. D o Option D will display the entire data structure. The format will be defined and given as a sample output. Redirected Input explanation: You are not going to be using redirected input instead of fstream. Redirected input is a way to simulate/mimic a user typing the input prompted/expected by the program. Redirected input provides you a way to send a file to the standard input of a program without typing it using the keyboard. To use redirected input in Visual Studio environment, follow these steps: After you have opened or created a new project, on the menu go to project, project properties, expand configuration properties until you see Debugging, on the right you will see a set of options, and in the command arguments type using namespace std; int main() { int mainDepth; cin >> mainDepth; cout << mainDepth;
3 I APPLE I BASE I ZEBRA I TRANSPORT I RESPECTABLE D F APPLE I SURGEON I MUTTER I FANTASY I BRAINSTORM I HEADLINE F FANTASY I BEAUTIFUL I PROFOUND I TRANSLATE I LOUNGE I MAINSTREAM I DESIGNER I ASTONISHING I CONNECTION R MUTTER I MARRIAGE I INVISIBLE I JUNGLE I LABORATORY I RETORT I HEALTHY I MAPPING F MUTTER R SURGEON I INVADE I SURPLUS I CONCERT I COOPERATIVE R SURPLUS R CONNECTION R BASE F APPLE F BRAINSTORM F LOUNGE D
#include #include #include // for displaying list using namespace std; void emptyString (char* myString, int length) { for (int i = 0; i < length; i++) myString = '\0'; } // class prototype - since it is a recursive class template class TrieDS; template class TrieNode { public: }; // default constructor template TrieNode:: TrieNode() { } TrieDS* _next; // pointing to the next address list* _data; // store the data as a list TrieNode(); }; _next = NULL; _data = NULL; // template class TrieDS { public: TrieNode* myNodes; // array of length 26 to store the TrieNodes int depth; // given in the input TrieDS(); // default constructor int getCharPosition (DT str, int loc); // returns the index position // for the loc-th position character in str void insert (DT str); // insert str to the structure depending on the depth void remove (DT str); // remove str from the structure - make sure to // check if the list is empty and set it to NULL when // removing the last word from the list. int find (DT str); // find the the string str - return true or false void displayMyNodes (); // display the entire myNodes array (list at each node)
// main function int main() { } char* tempWord = new char [20]; char command; int mainDepth = 0; cin >> mainDepth; // read the depth from redirected input file TrieDS myTrie; // object of TrieDS // TODO: Read in from the redirected input file and perform the commands // You may use a while loop to go till eof() and a switch case inside return 0;
Inserting APPLE Inserting BASE Inserting ZEBRA Inserting TRANSPORT Inserting RESPECTABLE myTrie: APPLE BASE RESPECTABLE TRANSPORT ZEBRA Found APPLE Inserting SURGEON Inserting MUTTER Inserting FANTASY Inserting BRAINSTORM Inserting HEADLINE Found FANTASY Inserting BEAUTIFUL Inserting PROFOUND Inserting TRANSLATE Inserting LOUNGE Inserting MAINSTREAM Inserting DESIGNER Inserting ASTONISHING Inserting CONNECTION Removing MUTTER
Removing MUTTER Inserting MARRIAGE Inserting INVISIBLE Inserting JUNGLE Inserting LABORATORY Inserting RETORT Inserting HEALTHY Inserting MAPPING Not found MUTTER Removing SURGEON Inserting INVADE Inserting SURPLUS Inserting CONCERT Inserting COOPERATIVE Removing SURPLUS Removing CONNECTION Removing BASE Found APPLE Found BRAINSTORM Found LOUNGE myTrie: APPLE ASTONISHING BEAUTIFUL BRAINSTORM CONCERT COOPERATIVE DESIGNER
myTrie: APPLE ASTONISHING BEAUTIFUL BRAINSTORM CONCERT COOPERATIVE DESIGNER FANTASY HEADLINE HEALTHY INVADE INVISIBLE JUNGLE LABORATORY LOUNGE MAINSTREAM MAPPING MARRIAGE PROFOUND RESPECTABLE RETORT TRANSLATE TRANSPORT ZEBRA