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 a
ay, 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 paint
ushes. Visual Studio is the canvas upon which your new life begins post-dragon.
As you put your
ush to paper to begin, you decide that your first masterpiece must be the culmination of everything you’ve learned—it must combine lists, a
ays, 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:
key Part of the Pair struct. Used in conjunction with mHashFunc to locate data.
value Also part of the Pair struct. The data intended to be accessed using the key.
mTable mTable is one of the more abstract variables you’ll encounter in this class. It is an a
ay of lists. Each list is full of Pairs. So you have an a
ay of lists of Pairs. Let’s
eak that down further.
mTable being an a
ay of lists means that within each position (bucket) of the a
ay, 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.
mNumBuckets The number of buckets needed in mTable.
mHashFunc A 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 wo
y about this one—it’s already done for you! :) Take a 5 second
eather!
Dictionary Constructor Initializes everything for Dictionary using the parameters.
Dictionary Destructor Destroys the dynamically allocated memory of our program.
Copy Constructor Takes in a Dictionary and makes a deep copy of it in the cu
ent object.
Dict. Overloaded = Sets the invoking Dictionary equal to _dict without any memory leaks and ensures it is a deep copy.
Clear Clears all internal data—every bucket should be empty. The a
ay should still be the same size after this is done and the hash function should still be usable.
Insert Insert the key-value pair into the appropriate bucket. Remember how the hash function plays into this.
Find Accepts _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.
Remove Removes 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 a
ays:
· http:
www.cplusplus.com
eference/list/list
· http:
www.cplusplus.com
eference/a
ay/a
ay
· 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
ush—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 Li
ary (STL) implementation of the Hash Map. The hash function, order of the buckets, the lists, and the a
ays 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: .
Scra
le 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 scra
le. 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:
mLetterValues Used to store the values associated with each Scra
le letter. (If you’ve never played scra
le, 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 a
ay holds that information.)
mScra
leMap This is your unordered_map. It stores all known Scra
le words and their associated values.
values This is the a
ay of letter values. You’ll use this in FindValueInMap once but nowhere else!
Functions:
PopulateLetterValues This method accepts an a
ay of size 26 and populates mLetterValues based on it.
GetLetterValue This method returns the letter’s value. It can be assumed that the letter passed in will always be upper-case. (This poses a problem.)
GetWordValue Calculates the value of the string passed in and returns it.
CreatePair Returns a pair created based on the word passed in and its calculated score. Having trouble? Look at the return type.
LoadWords Loads a file of all possible Scra
le words and stores them in the map along with their value. The file loaded will have one word per line.
FindValueInMap This 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
eference/unordered_map/unordered_map
· http:
www.cplusplus.com
eference/fstream/fstream
· http:
www.cplusplus.com
eference/string/string
· http:
www.cplusplus.com
eference/utility/pai
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!