feat: initial commitHEADmain

6 files changed, 623 insertions, 0 deletions

diff --git a/chapter5/bag3.cxx b/chapter5/bag3.cxx
new file mode 100644
index 0000000..ef3465d
--- /dev/null
+++ b/chapter5/bag3.cxx
@@ -0,0 +1,154 @@
+// FILE: bag3.cxx

+// CLASS implemented: bag (see bag3.h for documentation)

+// INVARIANT for the bag ADT:

+//   1. The items in the bag are stored on a linked list;

+//   2. The head pointer of the list is stored in the member variable head_ptr;

+//   3. The total number of items in the list is stored in the member variable

+//      many_nodes.

+

+#include <cassert>  // Provides assert

+#include <cstdlib>  // Provides NULL, rand, size_t

+#include "node1.h"  // Provides node and the linked list functions

+#include "bag3.h"

+using namespace std;

+

+namespace main_savitch_5

+{

+

+    bag::bag( )

+    // Library facilities used: cstdlib

+    {

+        head_ptr = NULL;

+        many_nodes = 0;

+    }

+

+    bag::bag(const bag& source)

+    // Library facilities used: node1.h

+    {

+        node *tail_ptr;  // Needed for argument of list_copy

+

+        list_copy(source.head_ptr, head_ptr, tail_ptr);

+        many_nodes = source.many_nodes;

+    }

+

+    bag::~bag( )

+    // Library facilities used: node1.h

+    {

+        list_clear(head_ptr);

+        many_nodes = 0;

+    }

+

+    bag::size_type bag::count(const value_type& target) const

+    // Library facilities used: cstdlib, node1.h

+    {

+        size_type answer;

+        const node *cursor; // Use const node* since we don't change the nodes.

+

+        answer = 0;

+        cursor = list_search(head_ptr, target);

+        while (cursor != NULL)

+        {

+            // Each time that cursor is not NULL, we have another occurrence of

+            // target, so we add one to answer, and move cursor to the next

+            // occurrence of the target.

+            ++answer;

+            cursor = cursor->link( );

+            cursor = list_search(cursor, target);

+        }

+        return answer;

+    }

+

+    bag::size_type bag::erase(const value_type& target)

+    // Library facilities used: cstdlib, node1.h

+    {

+        size_type answer = 0;

+        node *target_ptr;

+

+        target_ptr = list_search(head_ptr, target);

+        while (target_ptr != NULL)

+        {

+            // Each time that target_ptr is not NULL, we have another occurrence

+            // of target. We remove this target using the same technique that

+            // was used in erase_one.

+            target_ptr->set_data( head_ptr->data( ) );

+            target_ptr = target_ptr->link( );

+            target_ptr = list_search(target_ptr, target);

+            list_head_remove(head_ptr);

+	    --many_nodes;

+            ++answer;

+        }

+        return answer;

+    }

+

+    bool bag::erase_one(const value_type& target)

+    // Library facilities used: cstdlib, node1.h

+    {

+        node *target_ptr;

+

+        target_ptr = list_search(head_ptr, target);

+        if (target_ptr == NULL)

+            return false; // target isn't in the bag, so no work to do

+        target_ptr->set_data( head_ptr->data( ) );

+        list_head_remove(head_ptr);

+        --many_nodes;

+        return true;

+    }

+

+    bag::value_type bag::grab( ) const

+    // Library facilities used: cassert, cstdlib, node1.h

+    {

+        size_type i;

+        const node *cursor; // Use const node* since we don't change the nodes.

+

+        assert(size( ) > 0);

+        i = (rand( ) % size( )) + 1;

+        cursor = list_locate(head_ptr, i);

+        return cursor->data( );

+    }

+

+    void bag::insert(const value_type& entry)

+    // Library facilities used: node1.h

+    {

+        list_head_insert(head_ptr, entry);

+        ++many_nodes;

+    }

+

+    void bag::operator +=(const bag& addend)

+    // Library facilities used: cstdlib, node1.h

+    {

+        node *copy_head_ptr;

+        node *copy_tail_ptr;

+

+        if (addend.many_nodes > 0)

+        {

+            list_copy(addend.head_ptr, copy_head_ptr, copy_tail_ptr);

+            copy_tail_ptr->set_link( head_ptr );

+            head_ptr = copy_head_ptr;

+            many_nodes += addend.many_nodes;

+        }

+    }

+

+    void bag::operator =(const bag& source)

+    // Library facilities used: node1.h

+    {

+        node *tail_ptr; // Needed for argument to list_copy

+

+        if (this == &source)

+                return;

+

+        list_clear(head_ptr);

+        many_nodes = 0;

+        list_copy(source.head_ptr, head_ptr, tail_ptr);

+        many_nodes = source.many_nodes;

+    }

+

+    bag operator +(const bag& b1, const bag& b2)

+    {

+        bag answer;

+

+        answer += b1;

+        answer += b2;

+        return answer;

+    }

+

+}

diff --git a/chapter5/bag3.h b/chapter5/bag3.h
new file mode 100644
index 0000000..7907a94
--- /dev/null
+++ b/chapter5/bag3.h
@@ -0,0 +1,94 @@
+// FILE: bag3.h

+// CLASS PROVIDED: bag (part of the namespace main_savitch_5)

+//

+// TYPEDEFS for the bag class:

+//   bag::value_type

+//     is the data type of the items in the bag. It 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 (x == y).

+//

+//   bag::size_type

+//     is the data type of any variable that keeps track of how many items are

+//     in a bag

+//

+// CONSTRUCTOR for the bag class:

+//   bag( )

+//     Postcondition: The bag is empty.

+//

+// MODIFICATION MEMBER FUNCTIONS for the bag class:

+//   size_type erase(const value_type& target)

+//     Postcondition: All copies of target have been removed from the bag.

+//     The return value is the number of copies removed (which could be zero).

+//

+//   bool erase_one(const value_type& target)

+//     Postcondition: If target was in the bag, then one copy of target has

+//     been removed from the bag; otherwise the bag is unchanged. A true

+//     return value indicates that one copy was removed; false indicates that

+//     nothing was removed.

+//

+//   void insert(const value_type& entry)

+//     Postcondition: A new copy of entry has been inserted into the bag.

+//

+//   void operator +=(const bag& addend)

+//     Postcondition: Each item in addend has been added to this bag.

+//

+// CONSTANT MEMBER FUNCTIONS for the bag class:

+//   size_type size( ) const

+//     Postcondition: Return value is the total number of items in the bag.

+//

+//   size_type count(const value_type& target) const

+//     Postcondition: Return value is number of times target is in the bag.

+//

+//   value_type grab( ) const

+//     Precondition: size( ) > 0.

+//     Postcondition: The return value is a randomly selected item from the bag.

+//

+// NONMEMBER FUNCTIONS for the bag class:

+//   bag operator +(const bag& b1, const bag& b2)

+//     Postcondition: The bag returned is the union of b1 and b2.

+//

+// VALUE SEMANTICS for the bag class:

+//    Assignments and the copy constructor may be used with bag objects.

+//

+// DYNAMIC MEMORY USAGE by the bag:

+//   If there is insufficient dynamic memory, then the following functions throw

+//   bad_alloc: The constructors, insert, operator +=, operator +, and the

+//   assignment operator.

+

+#ifndef MAIN_SAVITCH_BAG3_H

+#define MAIN_SAVITCH_BAG3_H

+#include <cstdlib>   // Provides size_t and NULL

+#include "node1.h"   // Provides node class

+namespace main_savitch_5

+{

+    class bag

+    {

+    public:

+        // TYPEDEFS

+        typedef std::size_t size_type;

+        typedef node::value_type value_type;

+        // CONSTRUCTORS and DESTRUCTOR

+        bag( );                 // bag b2;

+        bag(const bag& source); // bag b3(b2);

+        ~bag( );

+        // MODIFICATION MEMBER FUNCTIONS

+        size_type erase(const value_type& target);

+        bool erase_one(const value_type& target);

+        void insert(const value_type& entry);

+        void operator +=(const bag& addend);

+        void operator =(const bag& source);

+        // CONSTANT MEMBER FUNCTIONS

+        size_type size( ) const { return many_nodes; }

+        size_type count(const value_type& target) const;

+        value_type grab( ) const;

+    private:

+        node *head_ptr;       // List head pointer

+        size_type many_nodes; // Number of nodes on the list

+    };

+

+    // NONMEMBER FUNCTIONS for the bag class:

+    bag operator +(const bag& b1, const bag& b2);

+}

+#endif

+

diff --git a/chapter5/bag3.zip b/chapter5/bag3.zip
new file mode 100644
index 0000000..b2b572e
--- /dev/null
+++ b/chapter5/bag3.zip
diff --git a/chapter5/bag3demo.cxx b/chapter5/bag3demo.cxx
new file mode 100644
index 0000000..136a8e3
--- /dev/null
+++ b/chapter5/bag3demo.cxx
@@ -0,0 +1,63 @@
+// FILE: bag3demo.cxx

+// Demonstration program for the 3rd version of the bag (bag3.h and bag3.cxx).

+// This is a the same as the demonstration program for bag1,

+// except that we no longer need to check whether the bag reaches its

+// capacity.

+

+#include <iostream>     // Provides cout and cin

+#include <cstdlib>      // Provides EXIT_SUCCESS

+#include "bag3.h"       // With Item defined as an int

+using namespace std;

+using namespace main_savitch_5;

+

+// PROTOTYPES for functions used by this demonstration program:

+void get_ages(bag& ages);

+// Postcondition: The user has been prompted to type in the ages of family

+// members. These ages have been read and placed in the ages bag, stopping

+// when the user types a negative number.

+

+void check_ages(bag& ages);

+// Postcondition: The user has been prompted to type in the ages of family

+// members once again. Each age is removed from the ages bag when it is typed,

+// stopping when the bag is empty.

+

+

+int main( )

+{

+    bag ages;

+

+    get_ages(ages);

+    check_ages(ages);

+    cout << "May your family live long and prosper." << endl;

+    return EXIT_SUCCESS;  

+}

+

+

+void get_ages(bag& ages)

+{

+    int user_input; // An age from the user's family

+

+    cout << "Type the ages in your family. ";

+    cout << "Type a negative number when you are done:" << endl;

+    cin >> user_input;

+    while (user_input >= 0)

+    {

+        ages.insert(user_input);

+        cin >> user_input;

+    }

+}

+

+void check_ages(bag& ages)

+{

+    int user_input; // An age from the user's family

+

+    cout << "Type those ages again. Press return after each age:" << endl;

+    while (ages.size( ) > 0)

+    {

+        cin >> user_input;

+        if (ages.erase_one(user_input))

+            cout << "Yes, I've got that age and have removed it." << endl;

+        else

+            cout << "No, that age does not occur!" << endl;

+    }

+}

diff --git a/chapter5/node1.cxx b/chapter5/node1.cxx
new file mode 100644
index 0000000..9a0be7a
--- /dev/null
+++ b/chapter5/node1.cxx
@@ -0,0 +1,137 @@
+// 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( );

+        }

+    }

+

+}

diff --git a/chapter5/node1.h b/chapter5/node1.h
new file mode 100644
index 0000000..ed88fb0
--- /dev/null
+++ b/chapter5/node1.h
@@ -0,0 +1,175 @@
+// FILE: node1.h

+// PROVIDES: A class for a node in a linked list, and list manipulation

+// functions, all within the namespace main_savitch_5

+//

+// 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 built-in C++ classes (int, char, ...) or a class with a copy

+//     constructor, an assignment operator, and a test for equality (x == y).

+//

+// CONSTRUCTOR for the node class:

+//   node(

+//     const value_type& init_data = value_type(),

+//     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 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 which is a pointer to a node.

+//   Each of these  functions comes in two versions: a non-const version (where

+//   the return value is node*) and a const version (where the return value

+//   is const node*).

+// 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 node* link( ) const <----- const version

+//   node* link( ) <----------------- non-const version

+//   See the note (above) 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)

+//   node* list_search(node* head_ptr, const node::value_type& target)

+//   See the note (above) 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 member. If there is no such node, the

+//     null pointer is returned.

+//

+//   const node* list_locate(const node* head_ptr, size_t position)

+//   node* list_locate(node* head_ptr, size_t position)

+//   See the note (above) 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. The original list is unaltered.

+//  void list_piece(

+//    const node* start_ptr, const node* end_ptr,

+//    node*& head_ptr, node*& tail_ptr

+//  )

+//    Precondition: start_ptr and end_ptr are pointers to nodes on the same

+//    linked list, with the start_ptr node at or before the end_ptr node

+//    Postcondition: head_ptr and tail_ptr are the head and tail pointers for a

+//    new list that contains the items from start_ptr up to but not including

+//    end_ptr.  The end_ptr may also be NULL, in which case the new list

+//    contains elements from start_ptr to the end of the list.

+//

+// 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,

+//   list_piece.

+

+#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 n1;   // Node n2(5);  // Node n3(3, temp_ptr);

+        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