this is basically like fill in the blank but for code using a template in windows c++ in visual studio for the mouth the work I need help with is the lab code which i believe is in the header part of...

1 answer below »
this is basically like fill in the blank but for code using a template in windows c++ in visual studio for the mouth the work I need help with is the lab code which i believe is in the header part of the code i hope this explains this well enough for more info check the files its two this time around

Dictionary and std::unordered_map




Data Structures and Algorithms Lab 5: Dictionary.h The Scenario Having slain the dragon, you look out over the land as you emerge from the cave where the dragon once stood. Over the past weeks, you’ve trained and learned the ways of the list, the array, and associated data structures, and the fruits of your labor have finally paid off. The world enters a period of relative peace all thanks to you. You decide to turn to a quiet life of art after such an adventure—to become a master painter. The same tools that were your sword and shield become your new paintbrushes. Visual Studio is the canvas upon which your new life begins post-dragon. As you put your brush to paper to begin, you decide that your first masterpiece must be the culmination of everything you’ve learned—it must combine lists, arrays, and use them in one large data structure—the Dictionary, or Map. Moreover, the Hash Map is what we will be dealing with in our lab today. It is a special type of Dictionary/Map that uses a Hash Function to determine how to access and store entries in the Dictionary. Dictionaries and Hash Maps have some technical differences in the programming world which we won’t explore in too much detail here. It is safe to say, however, that a Dictionary is a data structure comprised of Key, Value pairs. If we are to compare the Dictionary data structure to a physical Dictionary book, the key would be the word and the definition would be the value. So a word, definition pair would be analogous to a key, value pair. A Hash Map is a Dictionary where the key is put through a Hash Function to determine the storage location of the pair. Continuing with our Dictionary book example, we may have a Dictionary comprised of 3 volumes. A-E, F-K, and L-Z. The Hash Function would be the act of looking at the first letter of each word and determining which volume to store the word, definition pair in. In a perfect world, each key, when put through the hash function, would give a unique location. In practice, however, it is rare to find a perfect hash function like this. As a result, most of the time, multiple keys can be stored in one bucket. i.e. if the hash function is “Add up the digits in the key”, 9, 45, 54, and 18 would all be in bucket number 9, while 47, 11, and 8 would be in buckets 11, 2, and 8 respectively. This is why the list is there—to maintain multiple entries for each location. What To Do… Open Dictionary.h. There will be instructions written in the comments on what is expected. Below is the gist of each function and variable. Variables: keyPart of the Pair struct. Used in conjunction with mHashFunc to locate data. valueAlso part of the Pair struct. The data intended to be accessed using the key. mTablemTable is one of the more abstract variables you’ll encounter in this class. It is an array of lists. Each list is full of Pairs. So you have an array of lists of Pairs. Let’s break that down further. mTable being an array of lists means that within each position (bucket) of the array, a list will be stored. Within each position of the list, a Pair will be stored. The list can have zero pairs or many pairs. The syntax of this may be difficult, so here is an example of a valid statement: ex. mTable[indexOfBucketYouWant].front( ).key is valid. mNumBucketsThe number of buckets needed in mTable. mHashFuncA pointer to the hash function. The hash function determines the position within mTable to store and retrieve data. Functions: Pair Overloaded ==You don’t have to worry about this one—it’s already done for you! :) Take a 5 second breather! Dictionary ConstructorInitializes everything for Dictionary using the parameters. Dictionary DestructorDestroys the dynamically allocated memory of our program. Copy ConstructorTakes in a Dictionary and makes a deep copy of it in the current object. Dict. Overloaded =Sets the invoking Dictionary equal to _dict without any memory leaks and ensures it is a deep copy. ClearClears all internal data—every bucket should be empty. The array should still be the same size after this is done and the hash function should still be usable. InsertInsert the key-value pair into the appropriate bucket. Remember how the hash function plays into this. FindAccepts _key, the key to search for. Using the key, finds an associated value if one is present and returns it. Otherwise returns a null pointer. RemoveRemoves a value at a specified key. i.e. takes _key, finds the value associated with it, and removes the pair. Returns True if an item was removed. Tips, Tricks, and Resources · Functions/Data Members available in the List class ( i.e. myList.pop_back( ) ) can be found on the Cplusplus.com documentation for lists and arrays: · http://www.cplusplus.com/reference/list/list/ · http://www.cplusplus.com/reference/array/array/ · In case you want to use it to visualize what’s going on under-the-hood in C++’s list class, here is the illustration of DLists from a previous lab’s handout: · Searching on Google Images for Hash Map may help you visualize it if things get too muddled. Plagiarism Plagiarism and Academic Dishonesty are considered a very serious offense in this class and can have a range of consequences including suspension, and in very serious cases, expulsion. If you either share your code or copy someone else’s code, you will be given a 0 on your lab and can face further disciplinary action. In other words, don’t cheat please! Data Structures and Algorithms Lab 6: DSA_Lab6.h The Scenario Using your Hash Map/Dictionary from last lab, you’ve finished the underpainting of a beautiful masterpiece. It has everything from the dragon to the landscape. With all underpaintings, next comes the overpainting. You need a finer brush—and so you reach for your Unordered Map to start doing detail work. Your Unordered Map is nothing new—it is merely the nicely wrapped up version of what you previously used. It allows you to focus on the details, which is just what you need. You open Visual Studio and begin to paint. Unordered Maps are the C++ Standard Template Library (STL) implementation of the Hash Map. The hash function, order of the buckets, the lists, and the arrays are all handled internally by the Unordered Map. Pairs are a utility in the C++ STL. You’ll remember that last lab we created a struct named pair. The pair struct also exists within the C++ STL by default. Pairs simply let you collect two data types together. i.e. (key, value), , or even the most dangerous of all: . Scrabble is a board game originally published in 1938. The game is centered around spelling words with tiles. Your ultimate goal is to achieve the highest score by spelling words worth the most points. Each letter has a point-value—i.e. ‘Q’ is worth 10 points, while ‘T’ is worth 1. The total value of a word spelled is calculated by adding up the points from each letter. (The word “Qualm” is worth 16 points. (Q:10 + U:1 + A:1 + L:1 + M:3). Today’s lab will have you creating a Dictionary of legal words for a game of scrabble. If you wanted to play with only words found in The Lord of The Rings: The Two Towers, this program would let you do so—but for our purposes, we will use the lesser-known work, “words.txt”. What To Do… Open DSA_Lab6.h. There will be instructions written in the comments on what is expected. Below is the gist of each function and variable… Variables: mLetterValuesUsed to store the values associated with each Scrabble letter. (If you’ve never played scrabble, each letter in a word has a point-value associated with it. Q is a less common letter, so it is worth 10 points, while A is a very common letter and worth 1 point. This array holds that information.) mScrabbleMapThis is your unordered_map. It stores all known Scrabble words and their associated values. valuesThis is the array of letter values. You’ll use this in FindValueInMap once but nowhere else! Functions: PopulateLetterValuesThis method accepts an array of size 26 and populates mLetterValues based on it. GetLetterValueThis method returns the letter’s value. It can be assumed that the letter passed in will always be upper-case. (This poses a problem.) GetWordValueCalculates the value of the string passed in and returns it. CreatePairReturns a pair created based on the word passed in and its calculated score. Having trouble? Look at the return type. LoadWordsLoads a file of all possible Scrabble words and stores them in the map along with their value. The file loaded will have one word per line. FindValueInMapThis method will search for a word in your map, find it, and return the associated score. If a word is not a valid word (i.e. the word is not found in the map), it will then return -1. Note: FindValueInMap will be the only method that uses the variable “values” and also must do the ‘setup’ of your program. i.e. loading “words.txt”, etc. Tips, Tricks, and Resources · Functions/Data Members available in the unordered_map, fstream, and string classes ( i.e. myList.pop_back( ) ) can be found on the Cplusplus.com documentation. The documentation for pairs is also included here, as you will have to use it for this lab: · http://www.cplusplus.com/reference/unordered_map/unordered_map/ · http://www.cplusplus.com/reference/fstream/fstream/ · http://www.cplusplus.com/reference/string/string/ · http://www.cplusplus.com/reference/utility/pair/ Plagiarism Plagiarism and Academic Dishonesty are considered a very serious offense in this class and can have a range of consequences including suspension, and in very serious cases, expulsion. If you either share your code or copy someone else’s code, you will be given a 0 on your lab and can face further disciplinary action. In other words, don’t cheat please!
Answered 2 days AfterMay 18, 2022

Answer To: this is basically like fill in the blank but for code using a template in windows c++ in visual...

Pawan answered on May 21 2022
86 Votes
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here