Data structure C++ Hashing assignmnet

COP 3530 Data Structures Summer 2015 ---- Assignment 6---Hashing

Total Points: 100 points

Due Date: 7/18/2014 at 10:00PM

NO LATE ASSIGNMENTS WILL BE ACCEPTED!

Name the program for this assignment "hashing.cpp." The purpose of this program is to give you experience implementing a hash table, handling collisions, and using hashing with a linear function. Hashing is a method that enables access to table items (for adding, deleting, searching and so forth) in time that is relatively constant and independent of the items in the table. When we searched lists, implemented using linked lists and arrays, the time required to determine if an item was in the list, in the worst case, was proportional to the number of items in the list. Hashing uses a hash function to determine the location of an item.  A problem with hashing occurs when the hash function returns the same value for two or more items (a hash function is a function that maps the search key of a table item into a location that will contain that item).  The situation is referred to as a collision. A collision occurs when a hash function maps two or more distinct search keys into the same location.

In this assignment you will write a program that maintains the names (first and last names), addresses and phone numbers in an address book by using a hash table. Use the data file called "client_address_data.txt" to help you create the hash table.  Also, you should be able to enter, delete, modify (names, addresses and phone numbers), or search the data stored in hash table based on the name. A client’s first and last names should be the search key. Once the program is finish execution, the information should be ordered by last name and first name and printed to a file called "sorted_client_address_bk.txt."

Design a class to represent the hash table. Call this class "Client_Address_Book". "Client_Address_Book" contains all the information for each client (first name, last name, address, and phone number).  Use a linear function (eg. h(last name)=[ascii char value of first letter of lastname]-64) to determine the location of a key in the hash table.  Each cell in the hash table will be a sorted doubly linked list.  For example, you will have a doubly linked list for last names that begin with 'A', there will be one for last names that begin with 'B', and so forth.  The linked lists will also be used to handle collisions (clients with the same name) within "Client_Address_Book".  Each linked list will be maintained in alphabetical order.

When the clients address book is printed, the list of all the clients’ information stored in the hash table should be printed in order according to the last and first names.  The information should be printed out in the following order: last name, first name, address, and phone number.  Also, include column titiles.

Declare and implement the following classes: Client_Node, Client_Info_List, and Client_Address_Book.  Store the declaration and implement files in one file callhashing.cpp. You should submit hashing.cpp to blackboard before due date and time. Good Luck....

Consider the following skeleton as a hint to help you:

class Client_Node  //node in the doubly linked list

{

  public:

   //data:  last name, first name, address, and phone number

  Client_Node *prev, *next   //pointer information

};

class Clients_Info_List //doubly linked list

{

   public:

     Clients_Info_List();

     ~Clients_Info_List();

//member functions:  Insert, Remove, Search, Update, Print and so forth.

private:

//  Client_Node *front ---state information

};

class Client_Address_Book

{

    public:

    Client_Address_Book();

     ~Client_Address_Book();

    //member function like your hash function. Also include other functions like Insert,           

    //Remove, Search, Print, and so forth.

    // Hint:  Remember that the insert, remove and search function for

     //Clients_Address_Book will use Client_Info_List’s insert, remove and search

      //                            respectively.

      //

  private:

     Clients_Info_List   hash_table[27] //or 26 or whatever you like

};