Instructions: Complete and test the HashedDictionary class started in the text. It's fine if you want to put each class all into one file, instead of splitting them into header file and implementation file.
Step 1
First complete the "Entry" class. The text provides the header file. It just consists of constructors, mutators, and accessors. You need to write the implementation. You can delete the == and > operator overloads.
Step 2
Next complete the "HashedEntry" class. The text provides the header file. Once again, you'll need to write the implementation, and once again, it's just constructors, accessors, and mutators.
Step 3
Next write the HashedDictionary class. The HashedDictionary class must be derived from the DictionaryInterface class given in the text, except that you should delete the "traverser()" function. The data members are given to you in the text, as are the add() function and the remove() function. 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.
For the getHashIndex() function, you are required to use the technique described at the top of page 549 in the text. (To be specific, you'll use Horner's rule, and you'll modulus by the tableSize after each parenthesized expression in Horner's rule.) I would suggest that you just use something very simple for the getHashIndex() function at first. For example, you could simply add the ASCII codes of each character in the searchKey. Then write your client program to make sure everything is working. Then you'll just need to rewrite the getHashIndex() function to use the required technique.
To keep things simple, we will fudge things a little for the getHashIndex() function. 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 the search key 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
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.
Each FamousPerson will have the following data fields:
Assume that all strings are single words (no spaces)
Here are the files you'll need:
I'm not requiring you to implement the big-3 in this assignment.
Note that the words "throw (something)" in the prototype and function header are no longer allowed in C++. You should delete them wherever you see them. (In the files I've provided above, I have deleted them for you.)
DictionaryInterface.h
// Created by Frank M. Carrano and Tim Henry.
// Copyright (c) 2013 __Pearson Education__. All rights reserved.
/** An interface for the ADT dictionary. (Distinct search keys.)
Listing 18-1
@file DictionaryInterface.h */
#ifndef _DICTIONARY_INTERFACE
#define _DICTIONARY_INTERFACE
template< class KeyType, class ItemType>
class DictionaryInterface
{
public:
/** Sees whether this dictionary is empty.
@return True if the dictionary is empty;
otherwise returns false. */
virtual bool isEmpty() const = 0;
/** Gets the number of items in this dictionary.
@return The number of items in the dictionary. */
virtual int getNumberOfItems() const = 0;
/** Inserts an item into this dictionary according to the item’s search key.
@pre The search key of the new item differs from all search
keys presently in the dictionary.
@post If the insertion is successful, newItem is in its
proper position within the dictionary.
@param searchKey The search key associated with the item to be inserted.
@param newItem The item to add to the dictionary.
@return True if item was successfully added, or false if not. */
virtual bool add(const KeyType& searchKey, const ItemType& newItem) = 0;
/** Removes an item with the given search key from this dictionary.
@post If the item whose search key equals searchKey existed in the dictionary,
the item was removed.
@param searchKey The search key of the item to be removed.
@return True if the item was successfully removed, or false if not. */
virtual bool remove(const KeyType& searchKey) = 0;
/** Removes all entries from this dictionary. */
virtual void clear() = 0;
/** Retrieves an item with a given search key from a dictionary.
@post If the retrieval is successful, the item is returned.
@param searchKey The search key of the item to be retrieved.
@return The item associated with the search key.
@throw NotFoundException if the item does not exist. */
virtual ItemType getItem(const KeyType& searchKey) const = 0;
/** Sees whether this dictionary contains an item with a given
search key.
@post The dictionary is unchanged.
@param searchKey The search key of the item to be retrieved.
@return True if an item with the given search key exists in the dictionary. */
virtual bool contains(const KeyType& searchKey) const = 0;
}; // end DictionaryInterface
#endif
Entry.h