Data Structures - Chapter 12 - Programming Assignment
Implementing a the Table class with Chaining

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages


The Assignment:
Implement the Table template class from Chapter 12, using a chained hash table to store the items.
Purposes:
Ensure that you understand and can implement the important data structure of a hash table.
Before Starting:
Read Sections 12.2 and 12.3.
Due Date:
________________
Files that you must write:
  1. table2.h: Header file for this version of the Table class. You don't have to write much of this file. Just copy our version from table2.h and add your name and other information at the top. NOTE: This is a template class. The template parameter, called RecordType, may be instantiated as any struct or class that contains an integer member variable called key.
  2. table2.template: The implementation file for the new Table class. You must write this yourself. NOTE: Some of you have been forgetting to put your name and a clearly written invariant at the top of this file. The TAs will start taking off points for such omissions.
  3. makefile: This is a makefile for the assignment. The file should contain targets for tabtest.o, tabexam.o, tabtest (an executable file) and tabexam (another executable file). The source codes tabtest.cxx and tabexam.cxx are available in the locations listed below. Your makefile should also include "all" and "clean" options. Include your name in a comment at the top.
Other files that you may find helpful:
  1. link2.h and link2.template. A template version of the linked list toolkit, including the Node struct definition with Item as the template parameter. Notice how this Node is used within the table2.h file.
  2. tabtest.cxx: A simple interactive test program.
  3. tabexam.cxx: A non-interactive test program that will be used to grade the correctness of your Table class.

The Table Class Using a Chained Hash Table
Discussion of the Assignment

This version of the Table is a template class with a template parameter called RecordType, as described in Sections 12.2 and 12.3. In an actual program (such as tabtest.cxx or tabexam.cxx), the RecordType may be instantiated as any struct or class type with an integer member variable called key.

Start by understanding the private member variables that have been proposed in table2.h. For example, where are the head pointers stored for the separate linked lists? Write an invariant that describes the use of these private member variables, and put the invariant at the top of your implementation file.

I suggest that you also write some private member functions that can help in the implementations of the public member functions. For example, one of the private member functions that I found useful was:

    Node* find_node(int key);
    // Precondition: none.
    // Postcondition: If there is a node in the Table with the specified
    // key, then the return value is a pointer to this node. Otherwise the
    // return value is NULL.
I made use of find_node in my implementations of remove, find and is_present. If you decide to use something like find_node, then list the prototype in the private section of the Table class. Put the implementation in the implementation file along with a precondition/postcondition contract.

Hints for the remove function:

  1. Set a pointer (called cursor) to point to the node that you're removing. (If there is no such node, then return with no work.)
  2. Set i equal to the hash value of the key.
  3. Copy the data portion of the head node of list i to the cursor node. You have now got rid of the node with the specified key, but you have two copies of the data from the head node.
  4. list_head_remove(array[i]);

NOTE: Since your Table class is using dynamic memory (a bunch of linked lists), the Table must have a copy constructor, assignment operator, and a destructor--RATS! But keep in mind that much of your work can be carried out by the functions of the linked list toolkit.

Use the interactive test program and the debugger to track down errors in your implementation. If you have an error, do not start making changes until you have identified the cause of the error. If you come to me or a TA for help, we will always ask you to do the following:

  1. Show us the invariant that describes how your private member variables implement the Table class.
  2. Use the debugger to show us the problem!


Michael Main (main@colorado.edu)