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 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 "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)=[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 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_Node, Clients_Info_BST, and Clients_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

using namespace std;

class BST_Node //node in a BST

{

public:

string lastname, firstname, address, phone_number;

BST_Node *lchild, *rchild; //left and right children pointers

};

class Clients_Info_BST //Binary Search Tree

{

public:

Clients_Info_BST(){};//store the data in the hash table

//Clients_Info_BST(const Clients_Info_BST &);//Copy Constructor

~Clients_Info_BST(){};//destructor

//void Insert(const string & s){cout<<" Inside Client_Info_BST Insert\n";};

// void Remove(const string & s){cout<<" Inside Client_Info_BST Remove\n";};

// void Update(const string & s){cout<<" Inside Client_Info_BST Update\n";};

// void Print( ){cout<<" Inside Client_Info_BST Print\n";};

// BST_Node * Search(const string & s){cout<<" Inside Client_Info_BST Search\n"; return 0;};

//other member functions you may need.

private:

BST_Node *front; //---state information
};

class Client_Address_Book

{

public:

Client_Address_Book(){};//default constructor will read data from input file "client_address_data.txt".

//Client_Address_Book(const Client_Address_Book &);//Copy Constructor

// void Insert(const string & s);// insert record

// void Remove(const string & s);//remove record

// void Update(const string & s);//update record

// void Print_BST(const string & s);//ornt

// void Print_Hash_Table(){"Inside Client_Address_Book Print_Hash_Table\n";};

// void Print_Hash_Table_to_File(const string & filename);///function will print hash table to output file

// BST_Node * Search(const string & s){"Inside Client_Address_Book Search\n"; return 0;};

// unsigned int Hash_Function(const string & s);

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

//Client_Info_BST's insert, remove and search respectively.

private:

Clients_Info_BST hash_table[27]; //or 26 or whatever you like

};

int main()

{

};