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.hand 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.
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.
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.
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.
tabtest.cxx:A simple interactive test program.
tabexam.cxx: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.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:
NodeI 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.
* 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.
Hints for the remove function:
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: