COP 3530 Data Structures Summer 2015 —- Assignment 7
Hashing & BST
Total Points: 100 points
Due Date:7/29/2015 at 10:00PM
NO LATE ASSIGNMENTS WILL BE ACCEPTED!
Name the program for this assignment hashing_bst.cpp. This assignment is very similar to Assignment#6 accept you will be using a BST to handle collisions.As before 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 clients 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 andprinted to a file called sortbst_client_data.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)=[asciichar value of first letter oflastname]-64) to determine the location of a key in the hash table.Each cell in the hash table will be a BST.For example you will have a BST for last names that begin with ‘A’ there will be one for last names that begin with ‘B’ and so forth.The BST will also be used to handle collisions (clients with the same name) within Client_Address_Book.Each BST will maintain the address book in alphabetical order.
When the clients address book is printed the BST 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 titles.
Declare and implement the following classes:BST_NodeClients_Info_BST andClients_Address_Book.Store the declaration and implement files in one file call hashing_BST.cpp. You should submit hashing_BST.cpp to blackboard before due date and time.
Good Luck…. .
Consider the following skeleton as a hint to help you:
#include
#include
usingnamespacestd;
classBST_Node//node in a BST
{
public:
stringlastnamefirstname addressphone_number;
BST_Node*lchild *rchild;//left and right children pointers
};
classClients_Info_BST//Binary Search Tree
{
public:
Clients_Info_BST(){};//store the data in the hash table
//Clients_Info_BST(constClients_Info_BST&);//Copy Constructor
~Clients_Info_BST(){};//destructor
//voidInsert(conststring & s){cout<