Can anyone help me finish this in c++? I need to make a table2.template!!

C++] Write a program implementing chained hashing as described in Section 12-3. You can use the prototypes at the author's web site.

I think I only need 3 more functions completed: table(const table& source); , ~table(); , and void operator =(const table& source);

TABLE.2 HEADER FILE // TEMPLATE CLASS PROVIDED: Table // This class is a container template class for a Table of records. // The template parameter, RecordType, is the data type of the records in the // Table. It may any type with a default constructor, a copy constructor, // an assignment operator, and an integer member variable called key. // // CONSTRUCTOR for the Table template class: // Table( ) // Postcondition: The Table has been initialized as an empty Table. // // MODIFICATION MEMBER FUNCTIONS for the Table class: // void insert(const RecordType& entry) // Precondition: entry.key >= 0. Also if entry.key is not already a key in // the table, then the Table has space for another record // (i.e., size( )

#ifndef TABLE2_H #define TABLE2_H #include // Provides size_t #include "node2.h" // Provides the node type, from Figure 6.5 on page 306

namespace main_savitch_12B { template class table { public: // MEMBER CONSTANT -- See Appendix E if this fails to compile. static const std::size_t TABLE_SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR table( ); table(const table& source); ~table( ); // MODIFICATION MEMBER FUNCTIONS void insert(const RecordType& entry); void remove(int key); void operator =(const table& source); // CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const; bool is_present(int key) const; std::size_t size( ) const { return total_records; } private: main_savitch_6B::node *data[TABLE_SIZE]; std::size_t total_records; // HELPER MEMBER FUNCTION std::size_t hash(int key) const; }; }

#include "table2.template" // Include the implementation

#endif

NODE2.h HEADER FILE(part of the namespace main_savitch_6B) // PROVIDES: A template class for a node in a linked list, and list manipulation // functions. The template parameter is the type of the data in each node. // This file also defines a template class: node_iterator. // The node_iterator is a forward iterators with two constructors: // (1) A constructor (with a node* parameter) that attaches the iterator // to the specified node in a linked list, and (2) a default constructor that // creates a special iterator that marks the position that is beyond the end of a // linked list. There is also a const_node_iterator for use with // const node* . // // TYPEDEF for the node template class: // Each node of the list contains a piece of data and a pointer to the // next node. The type of the data (node::value_type) is the Item type // from the template parameter. The type may be any of the built-in C++ classes // (int, char, ...) or a class with a default constructor, an assignment // operator, and a test for equality (x == y). // NOTE: // Many compilers require the use of the new keyword typename before using // the expression node::value_type. Otherwise // the compiler doesn't have enough information to realize that it is the // name of a data type. // // CONSTRUCTOR for the node class: // node( // const Item& init_data = Item(), // node* init_link = NULL // ) // Postcondition: The node contains the specified data and link. // NOTE: The default value for the init_data is obtained from the default // constructor of the Item. In the ANSI/ISO standard, this notation // is also allowed for the built-in types, providing a default value of // zero. The init_link has a default value of NULL. // // NOTE about two versions of some functions: // The data function returns a reference to the data field of a node and // the link function returns a copy of the link field of a node. // Each of these functions comes in two versions: a const version and a // non-const version. If the function is activated by a const node, then the // compiler choses the const version (and the return value is const). // If the function is activated by a non-const node, then the compiler choses // the non-const version (and the return value will be non-const). // EXAMPLES: // const node *c; // c->link( ) activates the const version of link returning const node* // c->data( ) activates the const version of data returning const Item& // c->data( ) = 42; ... is forbidden // node *p; // p->link( ) activates the non-const version of link returning node* // p->data( ) activates the non-const version of data returning Item& // p->data( ) = 42; ... actually changes the data in p's node // // MEMBER FUNCTIONS for the node class: // const Item& data( ) const 0. // Postcondition: The return value is a pointer that points to the node at // the specified position in the list. (The head node is position 1, the // next node is position 2, and so on). If there is no such position, then // the null pointer is returned. // // template // void list_remove(node* previous_ptr) // Precondition: previous_ptr points to a node in a linked list, and this // is not the tail node of the list. // Postcondition: The node after previous_ptr has been removed from the // linked list. // // template // NodePtr list_search // (NodePtr head_ptr, const Item& target) // The NodePtr may be either node* or const node* // Precondition: head_ptr is the head pointer of a linked list. // Postcondition: The return value is a pointer that points to the first // node containing the specified target in its data member. If there is no // such node, the null pointer is returned. // // DYNAMIC MEMORY usage by the toolkit: // If there is insufficient dynamic memory, then the following functions throw // bad_alloc: the constructor, list_head_insert, list_insert, list_copy.

#ifndef MAIN_SAVITCH_NODE2_H #define MAIN_SAVITCH_NODE2_H #include // Provides NULL and size_t #include // Provides iterator and forward_iterator_tag

namespace main_savitch_6B { template class node { public: // TYPEDEF typedef Item value_type; // CONSTRUCTOR node(const Item& init_data=Item( ), node* init_link=NULL) { data_field = init_data; link_field = init_link; } // MODIFICATION MEMBER FUNCTIONS Item& data( ) { return data_field; } node* link( ) { return link_field; } void set_data(const Item& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; } // CONST MEMBER FUNCTIONS const Item& data( ) const { return data_field; } const node* link( ) const { return link_field; } private: Item data_field; node *link_field; };

// FUNCTIONS to manipulate a linked list: template void list_clear(node*& head_ptr);

template void list_copy (const node* source_ptr, node*& head_ptr, node*& tail_ptr);

template void list_head_insert(node*& head_ptr, const Item& entry);

template void list_head_remove(node*& head_ptr);

template void list_insert(node* previous_ptr, const Item& entry); template std::size_t list_length(const node* head_ptr);

template NodePtr list_locate(NodePtr head_ptr, SizeType position);

template void list_remove(node* previous_ptr); template NodePtr list_search(NodePtr head_ptr, const Item& target);

// FORWARD ITERATORS to step through the nodes of a linked list // A node_iterator of can change the underlying linked list through the // * operator, so it may not be used with a const node. The // node_const_iterator cannot change the underlying linked list // through the * operator, so it may be used with a const node. // WARNING: // This classes use std::iterator as its base class; // Older compilers that do not support the std::iterator class can // delete everything after the word iterator in the second line:

template class node_iterator : public std::iterator { public: node_iterator(node* initial = NULL) { current = initial; } Item& operator *( ) const { return current->data( ); } node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } node_iterator operator ++(int) // Postfix ++ { node_iterator original(current); current = current->link( ); return original; } bool operator ==(const node_iterator other) const { return current == other.current; } bool operator !=(const node_iterator other) const { return current != other.current; } private: node* current; };

template class const_node_iterator : public std::iterator { public: const_node_iterator(const node* initial = NULL) { current = initial; } const Item& operator *( ) const { return current->data( ); } const_node_iterator& operator ++( ) // Prefix ++ { current = current->link( ); return *this; } const_node_iterator operator ++(int) // Postfix ++ { const_node_iterator original(current); current = current->link( ); return original; } bool operator ==(const const_node_iterator other) const { return current == other.current; } bool operator !=(const const_node_iterator other) const { return current != other.current; } private: const node* current; };

}

#include "node2.template" #endif

// FILE: node2.template // IMPLEMENTS: The functions of the node template class and the // linked list toolkit (see node2.h for documentation). // // NOTE: // Since node is a template class, this file is included in node2.h. // Therefore, we should not put any using directives in this file. // // INVARIANT for the node class: // The data of a node is stored in data_field, and the link in link_field.

#include // Provides assert #include // Provides NULL and size_t

namespace main_savitch_6B { template void list_clear(node*& head_ptr) // Library facilities used: cstdlib { while (head_ptr != NULL) list_head_remove(head_ptr); }

template void list_copy( const node* source_ptr, node*& head_ptr, node*& tail_ptr ) // Library facilities used: cstdlib { head_ptr = NULL; tail_ptr = NULL;

// Handle the case of the empty list if (source_ptr == NULL) return;

// Make the head node for the newly created list, and put data in it list_head_insert(head_ptr, source_ptr->data( )); tail_ptr = head_ptr; // Copy rest of the nodes one at a time, adding at the tail of new list source_ptr = source_ptr->link( ); while (source_ptr != NULL) { list_insert(tail_ptr, source_ptr->data( )); tail_ptr = tail_ptr->link( ); source_ptr = source_ptr->link( ); } } template void list_head_insert(node*& head_ptr, const Item& entry) { head_ptr = new node(entry, head_ptr); }

template void list_head_remove(node*& head_ptr) { node *remove_ptr;

remove_ptr = head_ptr; head_ptr = head_ptr->link( ); delete remove_ptr; }

template void list_insert(node* previous_ptr, const Item& entry) { node *insert_ptr; insert_ptr = new node(entry, previous_ptr->link( )); previous_ptr->set_link(insert_ptr); }

template std::size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; std::size_t answer; answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; }

template NodePtr list_locate(NodePtr head_ptr, SizeType position) // Library facilities used: cassert, cstdlib { NodePtr cursor; SizeType i; assert(0 link( ); return cursor; }

template void list_remove(node* previous_ptr) { node *remove_ptr;

remove_ptr = previous_ptr->link( ); previous_ptr->set_link(remove_ptr->link( )); delete remove_ptr; }

template NodePtr list_search(NodePtr head_ptr, const Item& target) // Library facilities used: cstdlib { NodePtr cursor; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) if (target == cursor->data( )) return cursor; return NULL; } }

TESTLAB2.cpp FILE

#include // Provides toupper #include // Provides EXIT_SUCCESS and size_t #include // Provides cin, cout #include "table2.h" // Provides the table class using namespace std; using namespace main_savitch_12B;

// Struct definition for the test_record_type, which has a key and a double. struct test_record_type { int key; double data; };

// PROTOTYPES for functions used by this test program: void print_menu( ); // Postcondition: A menu of choices for this program has been written to cout.

char get_user_command( ); // Postcondition: The user has been prompted to enter a one character command. // The next character has been read (skipping blanks and newline characters), // and this character has been returned.

test_record_type get_record( ); // Postcondition: The user has been prompted to enter data for a record. The // key has been read, echoed to the screen, and returned by the function.

int get_key( ); // Postcondition: The user has been prompted to enter a key for a record. The // items have been read, echoed to the screen, and returned by the function.

int main( ) { table test; // A table that we'll perform tests on char choice; // A command character entered by the user bool found; // Value returned by find function test_record_type result; // Value returned by find function cout

do { print_menu( ); choice = toupper(get_user_command( )); switch (choice) { case 'S': cout

return EXIT_SUCCESS; }

void print_menu( ) // Library facilities used: iostream.h { cout

char get_user_command( ) // Library facilities used: iostream.h { char command;

cout > command; // Input of characters skips blanks and newline character

return command; }

test_record_type get_record( ) // Library facilities used: iostream.h { test_record_type result; cout > result.data; cout

int get_key( ) // Library facilities used: iostream.h { int key; do { cout > key; } while (key

table2.template file!!!

/eed help filling this out.

#include #include

namespace main_savitch_12B { template template const std::size_t table::TABLE_SIZE;

template const int table::NEVER_USED;

template const int table::PREVIOUSLY_USED;

template table::table( ) { std::size_t i;

used = 0; for (i = 0; i

template void table::insert(const RecordType& entry) // Library facilities used: cassert { bool already_present; // True if entry.key is already in the table std::size_t index; // data[index] is location for the new entry

assert(entry.key >= 0);

// Set index so that data[index] is the spot to place the new entry. find_index(entry.key, already_present, index);

// If the key wasn't already there, then find the location for the new entry. if (!already_present) { assert(size( )

data[index] = entry; }

template void table::remove(int key) // Library facilities used: cassert { bool found; // True if key occurs somewhere in the table std::size_t index; // Spot where data[index].key == key

assert(key >= 0);

find_index(key, found, index); if (found) { // The key was found, so remove this record and reduce used by 1. data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use. --used; } }

template void table::find(int key, bool& found, RecordType& result) const // Library facilities used: cassert.h { std::size_t index;

assert(key >= 0);

find_index(key, found, index); if (found) result = data[index]; }

template bool table::is_present(int key) const // Library facilities used: assert.h { bool found; std::size_t index;

assert(key >= 0);

find_index(key, found, index); return found; }

template inline std::size_t table::hash(int key) const { return (key % TABLE_SIZE); } }

123 CHAINED HASHING In open-address hashing, a collision is handled by probing the array for an unused position. Each array component can hold just one entry. When the array is full, no more items can be added to the table. We could handle this problem by resizing the array and rehashing all the entries, placing each entry in a new, larger array. But this would require a careful choice of the new size and proba- bly would require each entry to have a new hash value computed. Another approach is to use a different collision resolution method called chained bashing In chained hashing, also called chaining, each component of the hash table's aray can hold more than one entry. As with all bashing, we still hash the key of each entry to obtain an ary index. But if there is a collision, we don't worry too much. We simply placc the new catry in its proper array component along with other entries that happened to hash to the same array index. How does chaining place more than one entry in each component of the amay? The answer is that each array component must have some underlying structure. The most common structure that you will see for the array's components is to have each data[i] be a head pointer for a linked list. The nodes of the linked list each have an item that is the RecordType of thc table, as diagrammed bere: data Record whose key hashes Record whose Reoord whose key hashes key hashes that hashes that hashes that hashes 616 Chater 12/Seanchirg In this scheme, all the records that hash to location i are placed on the linked list, which has its head pointer stored in datai). To maintain the linked lists, we can usc the template version of our node class (from Section 6.4). With this approach, the table class definition is shown in Figure 12.7 In the figure we have included the file node2.h from Figure 64 on page 32 to provide the node class. We also have defined a static member constan called TABLE SIZE, which determines the size of the table's array. We used the name TABLE SIZE rather than CAPACITY since "CAPACITY Suggests a limit to the namber of entries-but in fact, the chaining hash table ean bold more than TABLE SIZE entries Definifon of the Table Template Class Using Cheining and the Linkod-List Tccolkt A Template Class Definition #include // Provides size.t include "node2.h" Provides the node type, from Figure 6.4 on page 321 nanespace nain savitch 128 template class table I MEMBER CONSTANT-See Appendix E if this faNs to compvle. static const std:size_t TABLE-SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR tablec; table(const tablc& source) tabe I MODIFICATION MEMBER FUNCTIONS void insert (const RecordType& entry): void remove(int key); void operator -(const table& source); T CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const bool is_present int key) const; std::size t ze const return total records; h nainsavitch.68::node data[TABLE_SIZE]: std::size t total_records; /I HELPER MEMBER FUNCTION std::sizet hash int key) const; Each component of the array is a heed pointer for a linked Wst. Time AnalysefHa hing 617 In our example, the table size is 811, so that the data array consists of 811 tead pointers for 811 linked lists. Each list is a linked list where the nodes contain RecordType values. Our class definition has one other private member variable, total records, which keeps track of the total number of records in all 811 linked lists. You can complete this implementation yourself. 123 CHAINED HASHING In open-address hashing, a collision is handled by probing the array for an unused position. Each array component can hold just one entry. When the array is full, no more items can be added to the table. We could handle this problem by resizing the array and rehashing all the entries, placing each entry in a new, larger array. But this would require a careful choice of the new size and proba- bly would require each entry to have a new hash value computed. Another approach is to use a different collision resolution method called chained bashing In chained hashing, also called chaining, each component of the hash table's aray can hold more than one entry. As with all bashing, we still hash the key of each entry to obtain an ary index. But if there is a collision, we don't worry too much. We simply placc the new catry in its proper array component along with other entries that happened to hash to the same array index. How does chaining place more than one entry in each component of the amay? The answer is that each array component must have some underlying structure. The most common structure that you will see for the array's components is to have each data[i] be a head pointer for a linked list. The nodes of the linked list each have an item that is the RecordType of thc table, as diagrammed bere: data Record whose key hashes Record whose Reoord whose key hashes key hashes that hashes that hashes that hashes 616 Chater 12/Seanchirg In this scheme, all the records that hash to location i are placed on the linked list, which has its head pointer stored in datai). To maintain the linked lists, we can usc the template version of our node class (from Section 6.4). With this approach, the table class definition is shown in Figure 12.7 In the figure we have included the file node2.h from Figure 64 on page 32 to provide the node class. We also have defined a static member constan called TABLE SIZE, which determines the size of the table's array. We used the name TABLE SIZE rather than CAPACITY since "CAPACITY Suggests a limit to the namber of entries-but in fact, the chaining hash table ean bold more than TABLE SIZE entries Definifon of the Table Template Class Using Cheining and the Linkod-List Tccolkt A Template Class Definition #include // Provides size.t include "node2.h" Provides the node type, from Figure 6.4 on page 321 nanespace nain savitch 128 template class table I MEMBER CONSTANT-See Appendix E if this faNs to compvle. static const std:size_t TABLE-SIZE = 811; // CONSTRUCTORS AND DESTRUCTOR tablec; table(const tablc& source) tabe I MODIFICATION MEMBER FUNCTIONS void insert (const RecordType& entry): void remove(int key); void operator -(const table& source); T CONSTANT MEMBER FUNCTIONS void find(int key, bool& found, RecordType& result) const bool is_present int key) const; std::size t ze const return total records; h nainsavitch.68::node data[TABLE_SIZE]: std::size t total_records; /I HELPER MEMBER FUNCTION std::sizet hash int key) const; Each component of the array is a heed pointer for a linked Wst. Time AnalysefHa hing 617 In our example, the table size is 811, so that the data array consists of 811 tead pointers for 811 linked lists. Each list is a linked list where the nodes contain RecordType values. Our class definition has one other private member variable, total records, which keeps track of the total number of records in all 811 linked lists. You can complete this implementation yourself