Suppose that you are the coach for Carleton’s swimming team and want to maintain an “all time” list of Carleton swimmers. Swimmers are to be ranked by their personal best times. The fastest swimmer ever tops the list, the second fastest swimmer ever comes next, and so on.
The basic operations required are as follows:
In addition it must be possible to go through the list in order.
Because you are a very busy person, it is essential that all operations be performed quickly. You therefore decide to use a hash table with an auxiliary linked list, as shown below.
The hash table makes it possible to rapidly locate the data for a particular swimmer, while the linked list (dashed arrows) keeps swimmers in their correct order. The head pointer for this list points to the fastest ever swimmer, and so on.
In the interest of clarity, the diagram shows the “by time” linked list as singly linked. In fact it is doubly linked. Consider what happens when a new time is reported for a swimmer. If the new time is a personal best, it may be necessary to move the swimmer up the all time list. Having a doubly linked list allows us to do this without having to run through the entire list. We can simply compare the swimmer’s new personal best time with that for the previous swimmer in the list and, if necessary, perform the necessary “pointer surgery”.
If “Anthony Shark” (note the two spaces and uppercase letters) has been added to the list, and we subsequently look up the best time for “anthony shark” (note the single space and lowercase letters), we would like to get an answer, and not be told that the person does not exist. The problem exists with all kinds of data structures, but is particularly troublesome when hashing is used, as hashing even a slightly different String2002 object will typically produce a different hash key. The solution is to convert all names entered to a standard form before working with them. The code supplied includes a function (called “standardize”) that looks after this. Given a String2002 object, it produces the standard equivalent. All leading blanks and trailing are stripped, all groups of blanks are reduced to a single blank, and the first letters only of all names are capitalized. Both of the examples given above would convert to “Anthony Shark”.
You have been supplied with a test program, a complete “Time” class, the header for class “AllTimeList” (“AllTime.h”), and a good part of the implementation for this class (file “skeleton.cpp”). All you have to do is rename “skeleton.cpp” to “AllTime.cpp”, work out what is going on, and fill in the missing parts.
If you would prefer to do things your own way, this is fine as long as you don’t change the public portion of the class definition supplied and your class behaves as it is supposed to. You may do whatever you want in the private portion of the class definition and in the implementation file.
You are free to use either linear rehashing or hashing with buckets. Note that, if you choose hashing with buckets, you will have to modify the header file supplied (see the definition of class “Node”).
It is suggested that you start by getting the hash table working (comment out option 4 of the test program) and that you add the linked list afterwards. This will reduce the amount of bugs that you have to deal with at one time.
Submit files “AllTime.h” and “AllTime.cpp”.
Updated: Thursday, March 12th, 2009.