(C++) Implement a set using linked lists in the code below. The following set operations must be implemented:

union intersection relative complement insertion - if the element is already in the set, then nothing happens deletion - if the element is not in the set, then nothing happens query to check whether an element is in a set query to find the number of number of elements in a set display the set destructor copy constructor overloading assignment operator

node1.h

#ifndef MAIN_SAVITCH_NODE1_H #define MAIN_SAVITCH_NODE1_H #include // Provides size_t and NULL

namespace main_savitch_5 { class node { public: // TYPEDEF typedef double value_type; // CONSTRUCTOR node( const value_type& init_data = value_type( ), node* init_link = NULL ) { data_field = init_data; link_field = init_link; }

// Member functions to set the data and link fields: void set_data(const value_type& new_data) { data_field = new_data; } void set_link(node* new_link) { link_field = new_link; }

// Constant member function to retrieve the current data: value_type data( ) const { return data_field; }

// Two slightly different member functions to retreive // the current link: const node* link( ) const { return link_field; } node* link( ) { return link_field; } private: value_type data_field; node* link_field; };

// FUNCTIONS for the linked list toolkit std::size_t list_length(const node* head_ptr); void list_head_insert(node*& head_ptr, const node::value_type& entry); void list_insert(node* previous_ptr, const node::value_type& entry); node* list_search(node* head_ptr, const node::value_type& target); const node* list_search (const node* head_ptr, const node::value_type& target); node* list_locate(node* head_ptr, std::size_t position); const node* list_locate(const node* head_ptr, std::size_t position); void list_head_remove(node*& head_ptr); void list_remove(node* previous_ptr); void list_clear(node*& head_ptr); void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr); }

#endif

--------------------------------------------------------------------------------------------------------------------

node1.cpp

// IMPLEMENTS: The functions of the node class and the // linked list toolkit (see node1.h for documentation). // INVARIANT for the node class: // The data of a node is stored in data_field, and the link in link_field.

#include "node1.h" #include // Provides assert #include // Provides NULL and size_t using namespace std;

namespace main_savitch_5 { size_t list_length(const node* head_ptr) // Library facilities used: cstdlib { const node *cursor; size_t answer;

answer = 0; for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) ++answer; return answer; } void list_head_insert(node*& head_ptr, const node::value_type& entry) { head_ptr = new node(entry, head_ptr); }

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

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

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

node* list_locate(node* head_ptr, size_t position) // Library facilities used: cassert, cstdlib { node *cursor; size_t i; assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link( ); return cursor; }

const node* list_locate(const node* head_ptr, size_t position) // Library facilities used: cassert, cstdlib { const node *cursor; size_t i; assert (0 < position); cursor = head_ptr; for (i = 1; (i < position) && (cursor != NULL); i++) cursor = cursor->link( ); return cursor; }

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

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

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

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

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

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 the 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( ); } }

}