Name the program for this assignment \" hashing_BST.cpp .\" The purpose of this
ID: 3764501 • Letter: N
Question
Name the program for this assignment "hashing_BST.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 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 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 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 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: 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 <iostream>
#include <string>
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 ";};
// void Remove(const string & s){cout<<" Inside Client_Info_BST Remove ";};
// void Update(const string & s){cout<<" Inside Client_Info_BST Update ";};
// void Print( ){cout<<" Inside Client_Info_BST Print ";};
// BST_Node * Search(const string & s){cout<<" Inside Client_Info_BST Search "; return 0;};
//other member functions you may need.
private:
BST_Node *root; //---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
//~Client_Address_Book();//Destructor
// 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 ";};
// 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 "; 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_BSTs insert, remove and search respectively.
private:
int capacity; //SET THIS VALUE EQUAL TO 27 YOUR DEFAULT CONSTRUCTOR
Clients_Info_BST *hash_table; // USING 1 THROUGH 26 or whatever you like
};
int main()
{
Client_Address_Book My_Book;
//My_Book.Insert("Micheal Jackson 123 peak road 207-2780");
//My_Book.Remove("Micheal Jackson ");
/*******************************************************************************
Notes for Update Function:
1. My_Book_Update(1 James Clark Lofton Bullard 777 Glades Run 527-6623);
If first character is a 1, this means all three fields will be changed.
2. My_Book_Update(2 James Clark Lofton Bullard 777 Glades Run);
If first character is a 2, this means the Name and Address fields will be changed.
3. My_Book_Update(3 James Clark 777 Glades Run 555-6666);
If first character is a 3, this means the Address and Phone Number fields will be changed.
4. My_Book_Update(4 James Clark Lofton Bullard 555-6666);
If first character is a 4, this means the Name and Phone Number fields will be changed.
5. My_Book_Update(5 James Clark Lofton Bullard);
If first character is a 5, this means the Name field will be changed.
6. My_Book_Update(6 James Clark 777 Glades Run);
If first character is a 6, this means the Address field will be changed.
7. My_Book_Update(7 James Clark 555-6666);
If first character is a 7, this means the Phone Number field will be changed.
********************************************************************************/
//My_Book.Update("1 Micheal Jackson Comb Harry 555 Palmetto Park Road 555-3444");
//My_Book.Print_BST("B");
//My_Book.Print_Hash_Table();
//Client_Address_Book Your_Book = My_Book; //Invoke the copy constructor
//Your_Book.Print_Hash_Table_to_File(/* the output filename goes here*/);
return 0;
}
This is the txt
Ramos Rafael 220 SW 3rd Street 447-4533
Enirata Jorge 6200 Miami Avenue 446-6666
Sexy Lady 400 Street East 555-1212
Smith John 444 SW 2nd Ave 420-6868
Winner Mary 3669 W Citrus Trace Drive 434-1717
Valdez Jorge 11885 SW 13th Court 476-8899
Valdes Abel 3353 Davie Blvd 587-1043
Smith Mary 444 SW 2nd Ave 420-6808
Edn Susan 8881 SW 49th Street 746-6998
Harper Fred 6815 NW 12th Street 572-3326
Tempero Douglas 436 NW 81st Street 462-1478
Utnik Richard 182 SW 51st Street 797-9905
Utich Michael 412 6th Street 556-8200
Lehrer Paul 9660 Sunrise Drive 485-6000
Leger George 811 SW 31st Street 390-7915
Harper Mary 6815 NW 12th Street 572-3326
Quass Claude North Ocean Drive 564-0674
Quinn Medicinewoman 4729 SW 42 Street 316-4455
Harper Jean 6815 NW 12th Street 572-3326
Harper James 6815 NW 12th Street 572-3326
Harper Babara 6815 NW 12th Street 572-3326
Edmundson Donald 321 Sunset Drive 745-6666
Ramos Miryam Post Gardens Way 393-6627
Cleary Kay 6250 SW 6th St 584-1023
Cleary Adele 3548 Envioronment Blvd 677-1056
MacDonald John 5601 Dixie Hwy 772-6712
Ilter Mehmet 2173 Bay Court 349-3128
Ilter Kermit 2163 Bay Court 349-3228
Ilter Maha 2163 Bay Court 349-3328
Macci Vicky 3535 Oceana Drive 446-8663
Tann Kyle 3027 N. Oakland Forest Drive 583-3362
Fox Smart 5600 Brian Street East 731-8685
Tanguay Albert 4806 NW 36st Street 731-7686
Tanguay Andre 555 University Drive 741-9728
Bullard Mark 770 SE 2nd Ave 393-7029
Bulldog Fred 555 W. Ocean Drive 737-0824
Bundle Joy 8352 Trent Ct 479-0349
Wickes Helen 1831 NE 38th Street 561-1228
Open Wide 5676 Street Avenue 543-0009
Wickham Fred 353 SW 18th Avenue 763-5252
Dunn Carrey 554 St. James Street 663-8900
Dandy Bread 1500 Publix Drive 555-1212
Nay John Eastlake Way 385-9286
Niwn Ni 6626 20th Street 888-0010
Young David 2121 NE 11th Ave 333-8483
Able Scott 9 NE 5th Court 456-0009
Abby Mary 3562 8th Street 492-4545
Young Andy 111 Cow Pen Road 448-8586
Young Celcil 6324 NW 29th Avenue 792-6327
Yau Kouassi 7801 NW 44th Ct 473-5456
Zangwill Andy 5990 Sunrise Lakes Blvd 746-9427
Jackson Jessie 2620 NW 21st Street 760-7511
Jackson Joanna 220 SW 20st Street 761-7211
Jackson Missy 20000 NW 21st Street 760-7111
Zangrille Juilus 2261 NE 67th Street 938-8919
Xyplex Networks 555 Seabreeze Blvd 713-8156
Xu Xinyun 4195 SW 67th Avenue 467-6556
Good Boy 1000 Heaven Street 111-1111
Kaiser Moe 1905 NW 46st Street 862-1156
Pretty Girl 19 Stay Home Avenue 234-5409
Tom Cat 111 Fish Avenue 333-3333
Kaiser Ronald 1905 NW 46st Street 422-5151
Kaiser Richard 1905 NW 46st Street 434-1106
use hashing function, binary search tree, created sorted file
Explanation / Answer
#include <iostream>
#include <fstream>
#include <string>
#include using namespace std;
class Client_Node
{
public:
Client_Node(const string &lastname,const string &firstname, const string &address, const string &phone_number)
{
m_lastname = lastname;
m_firstname = firstname;
m_address = address;
m_phone_number = phone_number;
prev = NULL;
next = NULL;
}
Client_Node(const string &s)
{
if(extract_details(s))
cout<<"Error in extraction"<<endl;
prev = NULL;
next = NULL;
}
int extract_details(const string &s)
{
std::size_t found = 0;
std::size_t start = 0;
std::size_t last_space;
int error = 0;
last_space = s.rfind(" ");
found = s.find(" ",start);
if(found != std::string::npos)
{
m_lastname = s.substr(start,found - start);
start = found;
}
else error = 1;
cout<<"Trace - lastname "<<m_lastname<<endl;
found = s.find(" ",start);
if(found != std::string::npos)
{
m_firstname = s.substr(start,found - start);
start = found;
}
else error = 1;
cout<<"Trace - firstname "<<m_firstname<<endl;
do
{
found = s.find(" ",start);
}
while(found < last_space);
if(found != std::string::npos)
{
m_address = s.substr(start,found - start);
start = found;
}
else error = 1;
cout<<"Trace - address "<<m_address<<endl;
if(found != std::string::npos)
{
m_phone_number = s.substr(start,s.size());
}
else error = 1;
cout<<"Trace - phone "<<m_phone_number<<endl;
return error;
}
void print_node(std::ostream& os)
{
os<<m_lastname;
os<<" ";
os<<m_firstname;
os<<" ";
os<<m_address;
os<<" ";
os<<m_phone_number;
os<<endl;
}
void update_node(const string &lastname,const string &firstname, const string &address, const string &phone_number, int mask)
{
if(mask & 1)
m_lastname = lastname;
if(mask & 2)
m_firstname = firstname;
if(mask & 4)
m_address = address;
if(mask & 8)
m_phone_number = phone_number;
}
int compare(const string &lname, const string &fname)
{
int res = m_lastname.compare(lname);
if(res == 0)
res = m_firstname.compare(fname);
return res;
}
int compare(Client_Node *node)
{
return compare(node->m_lastname, node->m_firstname);
}
public:string m_lastname, m_firstname, m_address, m_phone_number;
Client_Node *prev, *next;
//pointer information
};
class Clients_Info_List //doubly linked list
{
public:Clients_Info_List()
{
front = NULL;
};//store the data in the hash table
~Clients_Info_List()
{
Client_Node *temp;
while(front)
{
temp = front;
front = front->next;
delete temp;
}
};
void Insert(const string & s)
{
cout<<" Inside Client_Info_List Insert ";
Client_Node *node = new Client_Node(s);
if(front == NULL)
{
front = node;
}
else
{
Client_Node *temp = front;
while(temp)
{
if(temp->compare(node) > 0)
{
node->next = temp;
node->prev = temp->prev;
temp->prev = node;
}
else
{
if(!temp->next)
{
node->prev = temp;
temp->next = node;
temp = NULL;
break;
}
temp = temp->next;
}
}
if(temp == front)
front = node;
}
}
void Remove(const string &lname, const string& fname)
{
cout<<" Inside Client_Info_List Remove ";
Client_Node *temp = front;
while(temp)
{
if(temp->compare(lname,fname) == 0)
{
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
delete temp;
}
else
{
temp = temp->next;
}
}
}
void Update(const string & s)
{
cout<<" Inside Client_Info_List Update ";
}
void Print(std::ostream& os )
{
cout<<" Inside Client_Info_List Print ";
Client_Node *temp = front;
while(temp)
{
temp->print_node(os);
temp = temp->next;
}
}
Client_Node* Search(const string & lname, const string &fname)
{
cout<<" Inside Client_Info_List Search ";
Client_Node *temp = front;
while(temp)
{
if(temp->compare(lname,fname) == 0)
{
return temp;
}
else
{
temp = temp->next;
}
}
return NULL
}
};
private:Client_Node *front;
};
class Client_Address_Book
{
public:Client_Address_Book()
{
}
~Client_Address_Book()
{
}
void Insert(const string & s)
{
cout<<"Inside Client_Address_Book Insert ";
hash_table[Hash_Function(s)].Insert(s);
}
void Remove(const string &lname, const string &fname)
{
cout<<"Inside Client_Address_Book Remove ";
hash_table[Hash_Function(lname)].Remove(lname, fname);
}
void Update(const string & s)
{
cout<<"Inside Client_Address_Book Update ";
hash_table[Hash_Function(s)].Update(s);
}
void Print_List(const string & s)
{
cout<<"Inside Client_Address_Book Print_List ";
hash_table[Hash_Function(s)].Print(std::cout);
}
void Print_Hash_Table()
{
cout<<"Inside Client_Address_Book Print_Hash_Table ";
for(int i=0;i<27;i++)
{
hash_table[i].Print(std::cout);
}
}
void Print_Hash_Table_to_File(const string & filename)
{
cout<<"Inside Client_Address_Book Print_Hash_Table ";
ofstream os;
os.open(filename.c_str(), ios::out | ios::trunc );
for(int i=0;i<27;i++)
{
hash_table[i].Print(os);
}
os.close();
}
Client_Node* Search(const string &lname, const string &fname)
{
cout<<"Inside Client_Address_Book Search ";
hash_table[Hash_Function(lname)].Search(lname,fname);
}
unsigned int Hash_Function(const string & s)
{
cout<<"Inside Client_Address_Book Hash_Function ";
unsigned int val = 26;
string data = s;
transform(data.begin(), data.end(), data.begin(), ::toupper);
if(!data.empty())
val = data[0] - 'A';
else
val = 26;
return val;
}
private:Clients_Info_List hash_table[27];
};
int main()
{
Client_Address_Book address_book;
ifstream is;/*string s;
is.open("client_address_data.txt");
if(is.is_open())
{
while(getline(is,s))
address_book.Insert(s);
is.close();
}*/
string s[] = {"Ramos Rafael 220 SW 3rd Street 447-4533","Enirata Jorge 6200 Miami Avenue 446-6666","Lady 400 Street East 555-1212","Smith John 444 SW 2nd Ave 420-6868","Winner Mary 3669 W Citrus Trace Drive 434-1717"
};
for(int i = 0; i < 5; i++)
address_book.Insert(s[i]);
address_book.Print_Hash_Table();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.