CS 14: Programming Assignment 6

Directory to turnin: as6

Due date: Tuesday Nov 21, 2000

Synopsis:

In this assignment, you will implement an open hash table that holds non-negative integer values and uses linear probing.

Details:

This program should consist of 3 source files:

hash.h
hash.cpp
main.cpp

hash.h:

This file should contain the definition for your Hash class.

The public section in this class should be identical to the public section in your your Hash class from the last assignment. Only the implementation is changing; not the functionality. (This is not 100% true. The Hash class in the last assignment could handle negative numbers. This Hash class cannot. This will make the Search and Remove methods easier. Why?

At a minimum, the Hash class should contain declarations for the following public methods:

   Hash()
   ~Hash()
   bool Insert( int value )
   bool Search( int value )
   bool Remove( int value )
   void Dump()

There should also be two private methods:

int Hashf( int value, int sequence );
int Hashf( int value );

You will also need to declare instance variables; make sure you declare them as private variables. For example, you will need an array to use as your hash table. Make the size of this array 101. 101 should be a constant, however, so it could be easily changed in the future.

hash.cpp:

This file will contain the implementation of the Hash class.

Hash()

The constructor should initialize any variables that need to be initialized.

~Hash()

The destructor should free any of memory allocated by the class. (Depending on your implementation, you might not have any dynamically allocated objects, in which case this method will be empty.)

Insert()

This method should insert the integer value passed to it into the hash table using linear probing.

If there is an error (i.e. the table is full), the method should return false; if there is no error, the method should return true.

Search()

This method determines whether or not the integer value passed to it is in the hash table or not. If it is, the method returns true; if not, it returns false.

Remove()

This method searches for and removes the integer value passed to it from the hash table. (Note: the value might have been inserted into the table more than once. This method, then, should make sure it removes all occurances of the value from the hash table.)

If the value was found and removed from the hash table, the method returns true; if the value was not in the hash table, the method returns false.

Dump()

This method should print all the integers in the hash table.

Hashf()

These methods implement your hash function. The Insert, Search, and Remove methods should call the 2-parameter Hashf method which uses the 1-parameter Hashf method and linear probing to return a slot in the hash table.

main.cpp:

This file should contain your main function. It should be identifical to your main function from the last assignment.