CIS 11: Data Structures & Algorithms

Project K

Implement the Table template class from Chapter 12, using a chained hash table to store the items.

• Files in the project:
  • table.h: The header file for this version of the Table class. 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. You may find that you want to add to this file (see below).
  • table.cpp: The implementation file for the new Table class. You must write this yourself.
  • link.h and link.cpp: 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 table.h file
  • tabtest.cpp: A simple interactive test program.
  • tabexam.cpp: A non-interactive test program that will be used to grade the correctness of your Table class
• 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.cpp or tabexam.cpp), 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 table.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.
• You may also want to 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 may be useful is:

  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.

• You may want to use find_node() in your 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:
  • 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.)
  • Set i equal to the hash value of the key.
  • 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.
  • 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. Keep in mind that much of your work can be carried out by the functions of the linked list toolkit.

When you're satisfied with the implementation, submit your work via the CATE form for Project K.

2005/04/23