Computer Programming II

Lab Project #5 - Open Hashing

PROBLEM: You are to write a program in C++ to implement a system of storage and retrieval know as Open-Hashing. You are to use an array of 26 elements, so that there is one element in the array for each of the letters in the alphabet. The array elements shall all be pointers to lists. Each node shall be stored in the list on the basis of what letter it starts with. For example, if a key field is the string "Apple" then that node should go in the "A" list. A node with the key field of "Berry" should go in the "B" list, etc.

Each node should be of the same basic structure you created for project 2: FirstName and LastName. The key field should be LastName. This time, however, you don't have to deal with files. To implement the system, you must use a LIST ADT similar to the code you created for the List Project. The LIST ADT shall implement a list, supporting the functions: insert() , remove(), traverse(), create(), destroy(), search() and modify(). Modify operations should be done with first a remove(), followed by an insert() after changing the data in the node.

In addition to the LIST ADT, you must add your own Open-Hashing support functions. You must have functions to destroy and create whole lists from the hash structure, as well as search, insert, edit and remove nodes from the hashing structure. You also need functions to allow node input and printing. To demonstrate these operations, build a working menu of commands that allows the user to perform any of these operations, then traverse the hashing structure after the operation, printing out in a nice fashion what the structure looks like after each step. All sorting and searching should be done on the basis of the string (key) field, not the enum (data) field or other data fields.

EXTRA CREDIT: Implement the list insertions in sorted order. + 25% credit

EXAMPLE Hash table print out:

[B]->(Banner, Melaseth)-> (Bronson, Charles)->(NULL)

[S]->(Schwartz, Arnold)-> (NULL)

.

.

etc.

DESIGN: To get full credit, make sure you follow the standard documentation handout I gave at the start of the class. Fully detail your variables, your classes and a high-level algorithm.

IMPLEMENTATION: Each of the operations on the list should have their own function. It is up to you whether to use recursion or not for each list operation, however you might find easier to do so for some of the operations.

ASSUMPTIONS: Assuming valid input is fine. Your program should be able to handle indefinitely long lists.