Data structure C++ Hashing assignmnet

profilef.a.qx8t
assignment_6.zip
Home>Computer Science homework help>Data structure C++ Hashing assignmnet

client_address_data.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

cop3530_summer_2014_Program6_Hash_doubliy_linked.htm

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 call hashing.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

};

 

 

hashing.cpp

hashing.cpp

#include < iostream >
#include < fstream >
#include < string . h >
#include < cstdlib >
#include < iomanip >
#include < ctype . h >

#define  TABLE_SIZE  26
#define  DEFAULT_TABLE_SIZE  26

using   namespace  std ;


class   Client_Node
{
     public :
         char  firstName [ 50 ];
         char  lastName [ 50 ];
         char  address [ 100 ];
         long   int  phoneNumber ;

         Client_Node   * prev ;
         Client_Node   * next ;
         Client_Node ( char * , char * , char * , long   int );
         ~ Client_Node ();
         void  displayNode ();
         Client_Node *  createNewNode ( char * , char * , char * , long   int );
};

class   Clients_Info_List
{
     public :
         Client_Node   * front ;
         Client_Node   * end ;
         int  size ;
         Client_Node *  find ( char   * key );
         Clients_Info_List ();
         ~ Clients_Info_List ();

         void  insert ( Client_Node * );
         void  remove ( Client_Node * );
         void   Update ( Client_Node   * );
         void   Delete ( Client_Node   ** );
         bool  isEmpty ();
         void  printList ();
};

class   Client_Address_Book   :   public   Clients_Info_List
{
     public :
         int  table_size ;
         Clients_Info_List **  hash_table ;
         int  size ;
         Client_Address_Book ( int  T  =  DEFAULT_TABLE_SIZE );
         ~ Client_Address_Book ();   //destructor
         Client_Node *  find ( char   * lname , char   * fname );
         int  hashString ( char * );
         void  createEntry ();
         void  insertClient ( Client_Node   * );
         void  updateRecord ();
         void  deleteRecord ();
         int  getSize ();
         void  displayAddressBook ();
         void  searchRecord ();
};

Client_Address_Book :: Client_Address_Book ( int  T )
{
    size = 0 ;
    table_size  =  T ;
    hash_table  =   new   Clients_Info_List * [ table_size ];
     for ( int  i = 0 ; i < table_size ; i ++ )
     {
        hash_table [ i ]   =   new   Clients_Info_List ();
     }
}

Client_Address_Book ::~ Client_Address_Book (){}

int   Client_Address_Book :: hashString ( char   * key )
{
     char  ch  =  toupper ( key [ 0 ]);
     return   ( ch - 65 );     //returns index in hash_table where list is present for that alphabet
}

Client_Node *   Client_Address_Book ::  find ( char   * lname , char   * fname )
{
     int  bucket  =  hashString ( lname );
     if ( hash_table [ bucket ]   ==  NULL )
     return  NULL ;

     Client_Node   * temp  =  hash_table [ bucket ] -> front ;

     while ( temp )
     {
         if ( strcmp ( lname , temp -> lastName )   ==   0 )
         {
             if ( strcmp ( fname , temp -> firstName )   ==   0 )
                 return  temp ;
         }
         if ( temp -> next )
            temp  =  temp -> next ;
         else
             break ;
     }

     return  NULL ;
}

void   Client_Address_Book :: insertClient ( Client_Node   * node )
{
     int  indx  =  hashString ( node -> lastName );
    hash_table [ indx ] -> insert ( node );
    size ++ ;
}

int   Client_Address_Book :: getSize ()
{
     return  size ;
}

void   Client_Address_Book :: displayAddressBook ()
{
     int  i = 0 ;
     for ( i = 0 ; i < table_size ; i ++ )
     {
         if ( hash_table [ i ]   !=  NULL )
         {
            hash_table [ i ] -> printList ();
         }
     }

}

void   Client_Address_Book :: createEntry ()
{
     char  fname [ 20 ], lname [ 20 ], addr [ 50 ];
     long   int  phno ;
    cout << "\n\tEnter Last name      : " ;
    cin >> lname ;
    cout << "\tEnter First name       : " ;
    cin >> fname ;
    cout << "\tEnter Address          : " ;
    cin >> addr ;
    cout << "\tEnter phone number     : " ;
    cin >> phno ;

     Client_Node *  temp  =   new   Client_Node ( fname , lname , addr , phno );
    insertClient ( temp );
    cout << "\t\tRecord Successfully created!!\n" ;
}

void   Client_Address_Book :: updateRecord ()
{
     char  lname [ 20 ], fname [ 20 ];
    cout << "\n\t\tUpdating Record...." ;
    cout << "\n\t\tEnter last name            :" ;
    cin >> lname ;
    cout << "\t\tEnter first name     :" ;
    cin >> fname ;
     Client_Node   * temp  =  find ( lname , fname );

     if ( temp )
     {
        cout << "\n\t\tEnter New Last Name        :" ;
        cin >> temp -> lastName ;
        cout << "\t\tEnter New First Name         :" ;
        cin >> temp -> firstName ;
        cout << "\t\tEnter New Address            :" ;
        cin >> temp -> address ;
        cout << "\t\tEnter New Phone Number       :" ;
        cin >> temp -> phoneNumber ;
        cout << "Record Updated Successfully!!\n" ;
     }
     else
        cout << "\nSorry,record not found" ;
}

void   Client_Address_Book :: deleteRecord ()
{
     char  lname [ 20 ], fname [ 20 ];
    cout << "\n\t\tEnter Last Name        :" ;
    cin >> lname ;
    cout << "\t\tEnter First Name         :" ;
    cin >> fname ;
     Client_Node   * temp  =  find ( lname , fname );
     int  indx  =  hashString ( lname );
     if ( temp )
     {
         char  c ;
        temp -> displayNode ();
        cout << "\n\t\tDelete Record....?(y/n)" ;
        cin >> c ;
         if ( c  ==   'y'   ||  c  ==   'Y' )
         {
            hash_table [ indx ] -> Delete ( & temp );
             if ( hash_table [ indx ] -> isEmpty ())
                hash_table [ indx ]   =  NULL ;
                size -- ;

         }
     }
}

void   Client_Address_Book :: searchRecord ()
{
     char  lname [ 20 ], fname [ 20 ];
    cout << "\n\t\tEnter Last Name        :" ;
    cin >> lname ;
    cout << "\t\tEnter First Name         :" ;
    cin >> fname ;

     Client_Node   * temp  =  find ( lname , fname );
     if ( temp )
        temp -> displayNode ();
     else
        cout << "\nNode not found!!" ;     
}

Client_Node :: Client_Node ( char   * fname , char   * lname , char   * addr , long   int  phno )
{
    strcpy ( firstName , fname );
    strcpy ( lastName , lname );
    strcpy ( address , addr );
    phoneNumber  =  phno ;
    prev  =  NULL ;
    next  =  NULL ;
}

Client_Node ::~ Client_Node (){}

Client_Node *   Client_Node :: createNewNode ( char   * fname , char   * lname , char   * addr , long   int  phno )
{
     Client_Node *  temp  =   new   Client_Node ( fname , lname , addr , phno );
    strcpy ( temp -> firstName , fname );
    strcpy ( temp -> lastName , lname );
    strcpy ( temp -> address , addr );
    temp -> phoneNumber  =  phno ;
    temp -> prev  =  NULL ;
    temp -> next  =  NULL ;
     return  temp ;
}

void   Client_Node :: displayNode ()
{
    cout << "\n\tLast Name    :       " << lastName ;
    cout << "\n\tFirst Name   :       " << firstName ;
    cout << "\n\tAddress              :       " << address ;
    cout << "\n\tPhone Number :       " << phoneNumber ;
    cout << "\n" ;
}
 

Clients_Info_List :: Clients_Info_List ()
{
    size = 0 ;
    front  =  NULL ;
    end  =  NULL ;
}

Clients_Info_List ::~ Clients_Info_List (){}

Client_Node *   Clients_Info_List ::  find ( char  key [])
{
     Client_Node   * temp  =  front ;
     if ( front  ==  NULL )
     return  NULL ;

     while ( temp -> next  !=  NULL )
     {
         if ( strcmp ( key , temp -> lastName )   ==   0 ) //duplicate is present
         {
             return  temp ;
         }
        temp  =  temp -> next ;
     }

     return  temp ;
}

void   Clients_Info_List :: insert ( Client_Node   * node )
{
     Client_Node   * temp  =  find ( node -> lastName );
     if ( temp  ==  NULL )
     {
        front  =  node ;
        end  =  node ;
     }
     else
     {
        temp -> next  =  node ;
        node -> prev  =  temp ;
        end  =  node ;
     }
    size ++ ;
}

void   Clients_Info_List :: printList ()
{
     Client_Node   * temp  =  front ;
     while ( temp )
     {
        temp -> displayNode ();
        temp = temp -> next ;
     }
}

void   Clients_Info_List :: Delete ( Client_Node   ** node )
{
         //if first node
     if ( front  ==   * node )
     {
        cout << "\nfirst node" ;
        front  =  front -> next ;
         ( * node ) -> next  =  NULL ;
         delete   * node ;
     }
     else   if ( end  ==   * node ) //last node
     {
        cout << "\nlast node" ;
        end  =  end -> prev ;
         ( * node ) -> prev  =  NULL ;
         delete   * node ;
     }
     else
     {
         ( * node ) -> prev -> next  =   ( * node ) -> next ;
         ( * node ) -> next -> prev  =   ( * node ) -> prev ;
         ( * node ) -> next  =  NULL ;
         ( * node ) -> prev  =  NULL ;
         delete   * node ;
     }
    size -- ;
    cout << "\n\tRecord successfully deleted!!" ;
}

bool   Clients_Info_List :: isEmpty ()
{
     if ( size  ==   0 )
         return   true ;
     else
         return   false ;
}

void  readFile (   Client_Address_Book   * addressbook )
{
     char  fname [ 20 ], lname [ 20 ], addr [ 50 ];
     long   int  phno ;
    ifstream myfile  ( "client_address_data.txt" );
     if   ( myfile . is_open ())
     {
         while   (  myfile >> lname >> fname >> addr >> phno )
         {
             Client_Node *  temp  =   new   Client_Node ( fname , lname , addr , phno );
            addressbook -> insertClient ( temp );
         }
        myfile . close ();
     }
     else  cout  <<   "Unable to open file" ;
}

void  createSortedFile ( Client_Address_Book   * addr_book )
{
    ofstream outfile  ( "sorted_client_address_bk.txt" );
     int  i = 0 ;
     for ( i = 0 ; i < TABLE_SIZE ; ++ i )
     {
         if ( addr_book -> hash_table [ i ])
         {
             Client_Node   * temp  =  addr_book -> hash_table [ i ] -> front ;
             while ( temp )
             {
                outfile << temp -> lastName << " " ;
                outfile << temp -> firstName << " " ;
                outfile << temp -> address << " " ;
                outfile << temp -> phoneNumber << "\n" ;
                temp  =  temp -> next ;
             }
         }
     }
    cout << "\n\nsorted_client_address_bk.txt file succfully created!!\n" ;
    outfile . close ();
}

int  main ()
{

     Client_Address_Book   * addressbook  =   new   Client_Address_Book ( TABLE_SIZE );
    readFile ( addressbook );
     char  ch ;

     do
     {
         int  option ;
        cout << "\n***********************MENU**********************\n" ;
        cout << "\t\t1. Display Address Book\n" ;
        cout << "\t\t2. Enter New Record\n" ;
        cout << "\t\t3. Update Client Record\n" ;
        cout << "\t\t4. Delete Client Record\n" ;
        cout << "\t\t5. Search Client Record\n" ;
        cout << "\t\t6. Quit" ;
        cout << "\nEnter your choice : " ;
        cin >> option ;

         switch ( option )
         {
             case   1 :  addressbook -> displayAddressBook ();
                 break ;
             case   2 :  addressbook -> createEntry ();
                 break ;
             case   3 :  addressbook -> updateRecord ();
                 break ;
             case   4 :  addressbook -> deleteRecord ();
                 break ;
             case   5 :  addressbook -> searchRecord ();
                 break ;
             case   6 :  cout << "\nExiting...\n" ;
                createSortedFile ( addressbook );    //copy sorted file to sorted_client_address_bk.txt
                exit ( - 1 );
                 break ;
             default :  cout << "Please enter valid option!!" ;
                 break ;
         }
        cout << "\nWant to continue?(y/n) : " ;
        cin >> ch ;
     } while ( ch  ==   'y' ||  ch  ==   'Y' );

    createSortedFile ( addressbook );    //copy sorted file to sorted_client_address_bk.txt
     return   0 ;
}

sorted_client_address_bk.txt

ahmad mousa 470ne 2147483647