Implement the set class using linked lists Please use the provided header file (
ID: 3871876 • Letter: I
Question
Implement the set class using linked lists
Please use the provided header file (set2.h), as specification for the class, and the test program (set2_test.cpp) to test your program. Ensure your program passes the test and capture the printout of the test results.
//set2_test.cpp
#include "set.h"
#include <cassert>
#include <iostream>
int main ()
{
set s;
assert (!s.contains (7));
s.insert (7);
assert (s.contains (7));
s.remove (7);
assert (!s.contains (7));
set s1;
s1.insert (4);
s1.insert (5);
s1.insert (-24);
s1.insert (89);
s1.insert (34);
s1.insert (11);
s1.insert (0);
s1.insert (3);
s1.insert (14);
s1.insert (28);
std::cout << s1 << std::endl;
set s2;
s2.insert (6);
s2.insert (-5);
s2.insert (-24);
s2.insert (-89);
s2.insert (34);
s2.insert (-11);
s2.insert (0);
s2.insert (3);
std::cout << s2 << std::endl;
set s3 = set_union (s1, s2);
assert (s3.contains (4));
assert (s3.contains (0));
assert (s3.contains (-5));
std::cout << s3 << std::endl;
set s4 = set_intersection (s1, s2);
assert (s4.contains (34));
assert (!s4.contains (4));
assert (!s4.contains (-5));
std::cout << s4 << std::endl;
set s5 = set_difference (s1, s2);
assert (s5.contains (4));
assert (!s5.contains (0));
assert (!s5.contains (-5));
std::cout << s5 << std::endl;
assert (is_subset (s5, s1));
set s6(s2);
assert (s6 == s2);
std::cout << "all tests passed" << std::endl;
return 0;
}
//set2.h
#ifndef _SET_H
#define _SET_H
#include <cstdlib>
#include <iostream>
#include "node1.h"
using namespace main_savitch_5;
class set
{
public:
typedef node::value_type value_type;
typedef std::size_t size_type;
set();
// postcondition: empty set has been created
~set();
// postcondition: set has been deallocated
set (const set& source);
// postcondition: a copy of source has been created
set& operator = (const set& source);
// postcondition:
void insert (const value_type& entry);
// postcondition: entry is in the set
void remove (const value_type& entry);
// postcondition: entry is not in the set
size_type size() const;
// postcondition: number of elements in the set has been returned
bool contains (const value_type& entry) const;
// postcondition: whether entry is in the set has been returned
friend set set_union (const set& s1, const set& s2);
//postcondition: union of s1 & s2 has been returned
friend set set_intersection (const set& s1, const set& s2);
// postcondition: intersection of s1 & s2 has been returned
friend set set_difference (const set& s1, const set& s2);
// postcondition: difference of s1 - s2 has been returned
friend bool is_subset (const set& s1, const set& s2);
// postcondition: returned whether s1 is a subset of s2
friend bool operator == (const set& s1, const set& s2);
// postcondition: returned whether s1 & s2 are equal
friend std::ostream& operator << (std::ostream& output, const set& s);
// postcondition: s has been displayed on output
private:
node* head;
size_type used;
};
#endif
//node1.cpp
// FILE: node1.cxx
// 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 <cassert> // Provides assert
#include <cstdlib> // 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( );
}
}
}
//node1.h
#ifndef MAIN_SAVITCH_NODE1_H
#define MAIN_SAVITCH_NODE1_H
#include <cstdlib> // 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
Explanation / Answer
Code Below :
/*set.cpp*/
#include "set.h"
set::set() {
head = NULL;
}
// postcondition: empty set has been created
set::~set() {
list_clear(head);
}
// postcondition: set has been deallocated
set::set(const set& source) {
node *tailptr;
list_copy(source.head, head, tailptr);
}
// postcondition: a copy of source has been created
set& set::operator = (const set& source) {
if (head != source.head) {
list_clear(head);
set(source);
}
}
// postcondition:
void set::insert(const value_type& entry) {
node *newNode = NULL;
if (list_search(head, entry) == NULL) {
newNode = new node(entry, NULL);
newNode->set_link(head);
head = newNode;
}
}
// postcondition: entry is in the set
void set::remove(const value_type& entry) {
node * elem = list_search(head, entry);
if (elem != NULL) {
int pos = list_length(head) - list_length(elem) -1;
list_remove(list_locate(head, pos));
}
}
// postcondition: entry is not in the set
set::size_type set::size() const {
return list_length(head);
}
// postcondition: number of elements in the set has been returned
bool set::contains(const value_type& entry) const {
if (list_search(head, entry) != NULL)
return true;
else
return false;
}
// postcondition: whether entry is in the set has been returned
set set_union(const set& s1, const set& s2) {
set newSet;
node *tailptr;
list_copy(s1.head, newSet.head, tailptr);
node *headptr = NULL;
tailptr = NULL;
list_copy(newSet.head, headptr, tailptr);
newSet.head = headptr;
return newSet;
}
//postcondition: union of s1 & s2 has been returned
set set_intersection(const set& s1, const set& s2) {
node *temp;
temp = s1.head;
set newSet;
node *headptr=NULL;
node *tailptr = NULL;
while (temp != NULL) {
node *elem = list_locate(s2.head, temp->data());
if (elem != NULL) {
if (headptr == NULL) {
headptr = new node(elem->data());
tailptr = headptr;
}
else {
list_insert(tailptr, elem->data());
tailptr = tailptr->link();
}
}
temp = temp->link();
}
newSet.head = headptr;
return newSet;
}
// postcondition: intersection of s1 & s2 has been returned
set set_difference(const set& s1, const set& s2);
// postcondition: difference of s1 - s2 has been returned
bool is_subset(const set& s1, const set& s2) {
node * temp;
temp = s1.head;
while (temp != NULL) {
if (list_search(s2.head, temp->data()) == NULL)
break;
temp = temp->link();
}
if (temp == NULL)
return true;
else
return false;
}
// postcondition: returned whether s1 is a subset of s2
bool operator == (const set& s1, const set& s2) {
node * temp;
temp = s1.head;
if (list_length(s1.head) != list_length(s2.head))
return false;
return is_subset(s1, s2);
}
// postcondition: returned whether s1 & s2 are equal
std::ostream& operator << (std::ostream& output, const set& s) {
node * temp;
temp = s.head;
while (temp != NULL) {
output << temp->data() << " ";
temp = temp->link();
}
output << std::endl;
return output;
}
// postcondition: s has been displayed on output