Question

The goal of this task is to reinforce the implementation of container class concepts using linked lists. Specifically, the task is to create an implementation file using a linked list. You need to use the header files, set3.h and node1.h, and the test program, test_set3.cpp. Your documentation must include the efficiency of each function. Please make your program as efficient and reusable as possible.

set3.h

#ifndef _SET_H
#define _SET_H

#include <cstdlib>
#include <iostream>

class set
{
public:
  typedef int value_type;
  typedef std::size_t size_type;
  static const size_type INITIAL_CAPACITY = 30;

  set(size_type initial_capacity = INITIAL_CAPACITY);
// 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:
  size_type find (const value_type& entry) const;
  // returned location of entry in the set if entry is in the set - used otherwise
  void resize (unsigned int new_size);
  value_type* data;
  size_type used;
  size_type capacity;
};


#endif

node1.h

//File: node1.h
//This program provides the node class

// FILE: node1.h (part of the namespace main_savitch_5)
// PROVIDES: A class for a node in a linked list and a collection of functions for
// manipulating linked lists
//
// TYPEDEF for the node class:
// Each node of the list contains a piece of data and a pointer to the next node. The
// type of the data is defined as node::value_type in a typedef statement. The value_type
// may be any of the C++ built-in types (int, char, etc.), or a class with a default constructor,
// a copy constructor, an assignment operator, and a test for equality.
//
// CONSTRUCTOR for the node class:
// node(const value_type& init_data, node* init_link)
// Postcondition: The node contains the specified data and link.
// NOTE: The init_data parameter has a default value that is obtained from the default
// constructor of the value_type. 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:
// Some of the functions have a return value that is a pointer to a node. Each of these
// functions comes in two versions: a non-const version (where the return value is )
// and a const version (where the return value is ).
// EXAMPLES:
// const node *c;
// c->link( ) activates the const version of link
// list_search(c, ... calls the const version of list_search
// node *p;
// p->link( ) activates the non-const version of link
// list_search(p, ... calls the non-const version of list_search
//
// MEMBER FUNCTIONS for the node class:
// void set_data(const value_type& new_data
// Postcondition: The node now contains the specified new data.
//
// void set_link(node* new_link)
// Postcondition: The node now contains the specified new link.
//
// value_type data() const
// Postcondition: The return value is the data from this node.
//
// <----- const version
// and
// <----- non-const version
// See the previous note about the const version and non-const versions.
// Postcondition: The return value is the link from this node.
//
// FUNCTIONS in the linked-list toolkit:
// size_t list_length(const node* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked list.
//
// void list_head_insert(node*& head_ptr, const node:: value_type& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at the head of
// the linked list; head_ptr now points to the head of the new, longer linked list.
//
// void list_insert(node* previous_ptr, const node:: value_type& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added after the node
// that previous_ptr points to.
//
// const node* list_search (const node* head_ptr, const node::value_type& target)
// and
// node* list_search(node* head_ptr, const node::value_type& target)
// See the previous note about the const version and non-const versions.
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The pointer returned points to the first node containing the specified
// target in its data field. If there is no such node, the null pointer is returned.
//
// const node* list_locate(const node* head_ptr, size_t position)
// and
// node* list_locate(node* head_ptr, size_t position)
// See the previous note about the const version and non-const versions.
// Precondition: head_ptr is the head pointer of a linked list, and position > 0.
// Postcondition: The pointer returned 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.
//
// void list_head_remove(node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// 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.
//
// void list_clear(node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap, and the head_ptr is
// now NULL.
//
// void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr and tail_ptr are the head and tail pointers for a new list that
// contains the same items as the list pointed to by source_ptr.
//
// DYNAMIC MEMORY usage by the functions:
// If there is insufficient dynamic memory, then the following functions throw bad_alloc:
// the node constructor, list_head_insert, list_insert, list_copy.

#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; }
  
// MODIFICATION MEMBER FUNCTIONS
node* link() { return link_field; }
void set_data(const value_type& new_data) { data_field = new_data; }
void set_link(node* new_link) { link_field = new_link; }

// CONST MEMBER FUNCTIONS
value_type data() const { return data_field; }
const node* link() const { 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

test_set3.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;
}

Answer 1

Please let me know if you have any doubts or you want me to modify the answer. And if you find this answer useful then don't forget to rate my answer as thumps up. Thank you! :)

//main.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;
}
----------------------------------------------------------------------------------------------------
//set.cpp
#include "set.h"
#include "node1.h"

namespace main_savitch_5 {
    set::set() {
        head = NULL;
        used = 0;
    }

    set::set(const set& source) {
        node* tail;
        list_copy(source.head, head, tail);
        used = source.used;
    }

    set::set& set::operator =(const set& source) {
        if (head == source.head)
            return *this;
        list_clear(head);
        node* tail;
        list_copy(source.head, head, tail);
        used = source.used;
        return *this;
    }

    void set::insert(const value_type& entry) {
        if (contains(entry))
            return;
        else {
            list_head_insert(head, entry);
            used++;
        }
    }

    void set::remove(const value_type& entry) {
        if (used == 0)
            return;
        if (head->data() == entry)
            list_head_remove(head);
        else {
            node* ptr = head;
            while (ptr->link() != NULL) {
                if (ptr->link()->data() == entry) {
                    list_remove(ptr);
                    used--;
                    return;
                }
            }
        }
    }

    set::size_type set::size() const {
        return used;
    }

    bool set::contains(const value_type& entry) const {
        if (used == 0)
            return false;
        node* ptr;
        ptr = list_search(head, entry);
        if (ptr == NULL)
            return false;
        else
            return true;
    }

    set::set set_union(const set& s1, const set& s2) {
        set su(s1);
        set::size_type i;
        node* ptr;
        i = s2.used;
        ptr = s2.head;
        while(i > 0) {
            if (!s1.contains(ptr->data()))
                su.insert(ptr->data());
            ptr = ptr->link();
            i++;
        }
        return su;
    }

    set::set set_intersection(const set& s1, const set& s2) {
        set si;
        set::size_type i;
        node* ptr;
        i = s2.used;
        ptr = s2.head;
        while(i > 0) {
            if (s1.contains(ptr->data()))
                si.insert(ptr->data());
            i++;
        }
        return si;
    }

    set::set set_difference(const set& s1, const set& s2) {
        set sd(s1);
        node* ptr;
        set::size_type i;
        ptr = sd.head;
        return sd;
    }
}
-----------------------------------------------------------------------------------------
//set.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() { list_clear(head); };
// 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
#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