CSc 300 – Assignment #6 solution

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.
sellfy