Note: No documentation required on this assignment.
Complete and test a HashedDictionary class based on the partially complete files provided below.
Step 1
First complete the "Entry" class. The class declaration is provided below in the file "Entry.h". It just consists of constructors, mutators, and accessors. You need to write the implementation in the same file, below the class declaration.
Step 2
Next complete the "HashedEntry" class. Once again, the class declaration is provided below in the file "HashedEntry.h", it just consists of constructors, mutators, and accessors, and you'll need to write the implementation in the same file, below the class declaration.
Step 3
Next write the HashedDictionary class. The HashedDictionary class must be derived from the DictionaryInterface class provided below. (You can ignore the commented out "traverser()" function.) The add() and remove() functions are provided below in the partially completed file "HashedDictionary.h". You'll need to provide the class declaration above these function definitions. Use the following (and only these) data members in your class, exactly like this:
HashedEntry<KeyType, ItemType>** hashTable; // Array of pointers to entries
int itemCount; // Count of dictionary entries
int hashTableSize; // Table size must be prime
static const int DEFAULT_SIZE = 101;
Don't let the ** intimidate you! It's actually nothing new. A dynamic array declaration looks like this:
<type-of-elements>* <name-of-array>;
The type of our elements (pointer to HashedEntry) will be HashedEntry<KeyType, ItemType>*. So, replacing "<type-of-elements>" in the above pattern with HashedEntry<KeyType, ItemType>*, we get
HashedEntry<KeyType, ItemType>** hashTable;
You may want to add a display() member function to your HashedDictionary class for testing purposes.
Regarding repeated search keys, we will leave the behavior undefined. In other words, don't even think about what should happen if repeated search keys are encountered.
You will need a getHashIndex() function. To keep things simple, we will fudge things a little for it. Normally this function would be provided by the client. We will instead include this function in the HashedDictionary class, and we will simply assume (for this function only) that KeyType is always a string. The word "string" won't occur anywhere in your HashedDictionary code, but you'll treat the search key as if it is a string, using expressions such as searchKey[i]. Here is my function header for the getHashIndex() function:
template <class KeyType, class ItemType>
int HashedDictionary::getHashIndex(const KeyType& searchKey) const
To calculate the hash index, sum the ASCII codes of each character in the searchKey, and then modulus by hashTableSize.
Don't forget that you'll need to implement the big-3.
Step 4
Write a client program to test your class. The program should read a file containing information about famous people (name, age, zip code, etc.) and store the data in a HashedDictionary object. It should then test all of the member functions of the HashedDictionary class. This could get long, but don't worry about decomposing. You can just have a really long main() function.
I've provided the start of the client program, as well as the data file (famous.txt). You'll need to add code to main() to test the remaining member functions. Note that the data file contains quite a lot of randomly generated data that may look like garbage when you run your program, but is actually correct.
Each FamousPerson will have the following data fields:
- a (non-unique) ID number, stored as a string
- an income tax status, stored as a single char (m for married, s for single, h for head of household)
- last name (the search key), stored as a string
- first name, stored as a string
- age, stored as an int
- street, stored as a string
- zip code, stored as a string
Assume that all strings are single words (no spaces)
Here are the files you'll need: