Lab preparation (at home)
Goal
Implement the hash table data
structure using quadratic probing.
const int MAX_TABLE = 11;
typedef unsigned tableKeyType;
typedef string tableDataType;
class HashTable {
private:
enum slotType {Empty, Deleted,
InUse};
struct slot {
slotType slotStatus;
tableKeyType key;
tableDataType data;
};
slot HT[MAX_TABLE]; // the hash
table
int entries;
// keeps track of the number of entries in the table
int hash(tableKeyType key);
// precondition: key is set to the key value to be hashed, use simple
modulus hashing
// postcondition: none
// returns: home address for the key
int probe(tableKeyType key, int i);
// precondition: i is the index to find ith slot in case of
collisions
//
use the quadratic probing
// postcondition: none
// returns: the ith slot address using quadratic probing
bool search(int &pos, tableKeyType
key);
// precondition: key is set to the search key
// postcondition: if key is in the table, pos is set to the index (address)
of the slot with that key
// returns: true if key is in the table; otherwise false
public:
HashTable();
// constructor
bool insert(tableKeyType key, tableDataType& data);
// precondition: key and data are set to the values to be inserted
// postcondition: data and associated key are stored in the Table
// if key is already in the table, the associated data
are rewritten
// if table is full, do nothing
// returns: false if the table is full; otherwise true
bool lookup(tableKeyType key, tableDataType
&data);
// precondition : key is set to the searched key
// postcondition: if key is in the table, return the associated data
// returns: true if key found, false otherwise
void deleteKey(tableKeyType key);
// precondition : key is set to the key to be deleted
// postcondition: if key is found, delete the key and
associated data form the table
void print();
//print the contents of the hash table
};
Note that you are expected to
use the private member functions to implement the public ones. If you need you
may add/modify auxiliary private member functions and data members.
Lab report
Finish the implementation and test it.
In this lab you will have to present your Homework #3.
