Description
Create a user-defined Abstract Data Type (ADT) that implements a hash table using a C++ class named
HTableType and an appropriate set of C++ header/implementation files as discussed in class.
• The HTableType ADT must be implemented using a dynamically allocated array.
• Each element stored in the HTableType ADT is of type ElementType.
The HTableType class automatically performs two operations when instantiated:
1. initializes the hash table to empty
o table size is passed to the constructor when instantiated
2. populates the hash table by reading and inserting words from a text file
o name of the text file containing words is passed to the constructor when instantiated
o one word per line in the text file
Once the hash table has been populated it can be used to:
1. search for words
2. display the contents of the hash table
The following hash function is used to manage the hash table and its contents:
• hash( word ) = ∑ ASCII character values times 8 divided by the hash table size
Examples (based on a prime hash table size of 53):
hash( “and” ) = ((97 + 110 + 100) << 3) % MAX_TABLE = 18
hash( “And” ) = ((65 + 110 + 100) << 3) % MAX_TABLE = 27
hash( “global” ) = ((103 + 108 + 111 + 98 + 97 + 108) << 3) % MAX_TABLE = 18
hash( “return” ) = ((114 + 101 + 116 + 117 + 114 + 110) << 3) % MAX_TABLE = 23
Notes:
• Inserting words into the hash table:
o Store the actual hashed address – actual stored address may be different after collision resolution
o Store the probe count – number of addresses probed/tested while performing the insert operation
• Searching for words in the hash table:
o Update the individual match count associated with each successfully located word
• Collision resolution scheme:
o Quadratic probing from the actual hashed address
Required Output Format Example (based on a prime hash table size of 53):
Address Word Actual Address Probe Count Match Count
… … … … …
21 –1 0 0
22 global 18 3 1
23 return 23 1 2
… … … … …
Note:
• Do not let the output scroll off the screen.
o Tera Term – default 20 lines with 80 columns per line
Make sure that you completely document the header/implementation files.
• The header (.h) file tells the user exactly how to use your ADT
o General descriptions only – do not include implementation details
• The implementation file (.cpp) tells the implementer/programmer exactly how the ADT works
o Detailed descriptions – include implementation details
Zip together and e-mail your header/implementation files using the following naming convention.
• Do not e-mail your main/driver program
o I will create my own main/driver program to test your ADT
username6.h for the header file // I would use gamradtk6.h
username6.cpp for the implementation file // I would use gamradtk6.cpp
username6.zip for the submission file // I would use gamradtk6.zip
List the class number, your username, and assignment number as the e-mail message
SUBJECT: csc300 – gamradtk – a6 // I would use
Required header file (.h). (only partially specified)
const int MAX_STRING = 80;
typedef char ElementType[ MAX_STRING + 1 ]; // C-style string data type
class HTableType {
public: // user specified word file name
HTableType( const ElementType, const int ); // user specified hash table size
~HTableType();
void search( const ElementType );
void view() const; // output screen length 20 lines
private:
const int MAX_TABLE; // MUST BE INITIALIZED
struct NodeType {
ElementType element;
int actualAddress, probeCount, matchCount;
};
NodeType * theTable;
HTableType(); // cannot be used to instantiate class
int hash( const ElementType ) const;
void initialize();
void populate( const ElementType );
};
Define a macro to prevent multiple inclusion of the header file.
• I would use _GAMRADTK6_H for a header file with the filename gamradtk6.h.
I will write a test program that will include your ADT so all header/implementation files tested must use
common names. So you MUST use:
• the EXACT same names for each data type and function in the header/implementation files.
• the EXACT same function argument sequence in the header/implementation files.
Throughout the textbook examples are shown using Templates.
• Do not use Templates unless you are explicitly told to do so.
