diff options
| author | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
|---|---|---|
| committer | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
| commit | c1b6ffe70bd281c6c230fd63fabcaac2aff47514 (patch) | |
| tree | e8af3b1782a7cd0754590ed618fddc1bdb9b7385 /chapter3 | |
| download | dscode-main.tar.xz dscode-main.zip | |
Diffstat (limited to 'chapter3')
| -rw-r--r-- | chapter3/bag1.cxx | 100 | ||||
| -rw-r--r-- | chapter3/bag1.h | 87 | ||||
| -rw-r--r-- | chapter3/bag_demo.cxx | 62 | ||||
| -rw-r--r-- | chapter3/sequence1.h | 105 | ||||
| -rw-r--r-- | chapter3/sequence_test.cxx | 119 |
5 files changed, 473 insertions, 0 deletions
diff --git a/chapter3/bag1.cxx b/chapter3/bag1.cxx new file mode 100644 index 0000000..9672bc0 --- /dev/null +++ b/chapter3/bag1.cxx @@ -0,0 +1,100 @@ +// FILE: bag1.cxx
+// CLASS IMPLEMENTED: bag (see bag1.h for documentation)
+// INVARIANT for the bag class:
+// 1. The number of items in the bag is in the member variable used;
+// 2. For an empty bag, we do not care what is stored in any of data; for a
+// non-empty bag the items in the bag are stored in data[0] through
+// data[used-1], and we don't care what's in the rest of data.
+
+#include <algorithm> // Provides copy function
+#include <cassert> // Provides assert function
+#include "bag1.h"
+using namespace std;
+
+namespace main_savitch_3
+{
+ const bag::size_type bag::CAPACITY;
+
+ bag::size_type bag::erase(const value_type& target)
+ {
+ size_type index = 0;
+ size_type many_removed = 0;
+
+ while (index < used)
+ {
+ if (data[index] == target)
+ {
+ --used;
+ data[index] = data[used];
+ ++many_removed;
+ }
+ else
+ ++index;
+ }
+
+ return many_removed;
+ }
+
+ bool bag::erase_one(const value_type& target)
+ {
+ size_type index; // The location of target in the data array
+
+ // First, set index to the location of target in the data array,
+ // which could be as small as 0 or as large as used-1. If target is not
+ // in the array, then index will be set equal to used.
+ index = 0;
+ while ((index < used) && (data[index] != target))
+ ++index;
+
+ if (index == used)
+ return false; // target isn�t in the bag, so no work to do.
+
+ // When execution reaches here, target is in the bag at data[index].
+ // So, reduce used by 1 and copy the last item onto data[index].
+ --used;
+ data[index] = data[used];
+ return true;
+ }
+
+ void bag::insert(const value_type& entry)
+ // Library facilities used: cassert
+ {
+ assert(size( ) < CAPACITY);
+
+ data[used] = entry;
+ ++used;
+ }
+
+ void bag::operator +=(const bag& addend)
+ // Library facilities used: algorithm, cassert
+ {
+ assert(size( ) + addend.size( ) <= CAPACITY);
+
+ copy(addend.data, addend.data + addend.used, data + used);
+ used += addend.used;
+ }
+
+ bag::size_type bag::count(const value_type& target) const
+ {
+ size_type answer;
+ size_type i;
+
+ answer = 0;
+ for (i = 0; i < used; ++i)
+ if (target == data[i])
+ ++answer;
+ return answer;
+ }
+
+ bag operator +(const bag& b1, const bag& b2)
+ // Library facilities used: cassert
+ {
+ bag answer;
+
+ assert(b1.size( ) + b2.size( ) <= bag::CAPACITY);
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+}
diff --git a/chapter3/bag1.h b/chapter3/bag1.h new file mode 100644 index 0000000..907e58b --- /dev/null +++ b/chapter3/bag1.h @@ -0,0 +1,87 @@ +// FILE: bag1.h
+// CLASS PROVIDED: bag (part of the namespace main_savitch_3)
+//
+// TYPEDEF and MEMBER CONSTANTS for the bag class:
+// typedef ____ value_type
+// 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, an assignment operator, and operators to
+// test for equality (x == y) and non-equality (x != y).
+//
+// typedef ____ size_type
+// bag::size_type is the data type of any variable that keeps track of how many items
+// are in a bag.
+//
+// static const size_type CAPACITY = _____
+// bag::CAPACITY is the maximum number of items that a bag can hold.
+//
+// CONSTRUCTOR for the bag class:
+// bag( )
+// Postcondition: The bag has been initialized as an empty bag.
+//
+// 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).
+//
+// void erase_one(const value_type& target)
+// Postcondition: If target was in the bag, then one copy has been removed;
+// 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)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been added to the bag.
+//
+// void operator +=(const bag& addend)
+// Precondition: size( ) + addend.size( ) <= CAPACITY.
+// Postcondition: Each item in addend has been added to this bag.
+//
+// CONSTANT MEMBER FUNCTIONS for the bag class:
+// size_type size( ) const
+// Postcondition: The return value is the total number of items in the bag.
+//
+// size_type count(const value_type& target) const
+// Postcondition: The return value is number of times target is in the bag.
+//
+// NONMEMBER FUNCTIONS for the bag class:
+// bag operator +(const bag& b1, const bag& b2)
+// Precondition: b1.size( ) + b2.size( ) <= bag::CAPACITY.
+// 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.
+
+#ifndef MAIN_SAVITCH_BAG1_H
+#define MAIN_SAVITCH_BAG1_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_3
+{
+ class bag
+ {
+ public:
+ // TYPEDEFS and MEMBER CONSTANTS
+ typedef int value_type;
+ typedef std::size_t size_type;
+ static const size_type CAPACITY = 30;
+ // CONSTRUCTOR
+ bag( ) { used = 0; }
+ // 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);
+ // CONSTANT MEMBER FUNCTIONS
+ size_type size( ) const { return used; }
+ size_type count(const value_type& target) const;
+ private:
+ value_type data[CAPACITY]; // The array to store items
+ size_type used; // How much of array is used
+ };
+
+ // NONMEMBER FUNCTIONS for the bag class
+ bag operator +(const bag& b1, const bag& b2);
+}
+
+#endif
diff --git a/chapter3/bag_demo.cxx b/chapter3/bag_demo.cxx new file mode 100644 index 0000000..3ee7900 --- /dev/null +++ b/chapter3/bag_demo.cxx @@ -0,0 +1,62 @@ +// FILE: bag_demo.cxx
+// This is a small demonstration program showing how the bag class is used.
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include "bag1.h" // With value_type defined as an int
+using namespace std;
+using namespace main_savitch_3;
+
+// 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 bag is full or 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;
+
+ cout << "Type the ages in your family." << endl;
+ cout << "Type a negative number when you are done:" << endl;
+ cin >> user_input;
+ while (user_input >= 0)
+ {
+ if (ages.size( ) < ages.CAPACITY)
+ ages.insert(user_input);
+ else
+ cout << "I have run out of room and can�t add that age." << endl;
+ cin >> user_input;
+ }
+}
+
+void check_ages(bag& ages)
+{
+ int user_input;
+
+ 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 will remove it." << endl;
+ else
+ cout << "No, that age does not occur!" << endl;
+ }
+}
diff --git a/chapter3/sequence1.h b/chapter3/sequence1.h new file mode 100644 index 0000000..1a1aea7 --- /dev/null +++ b/chapter3/sequence1.h @@ -0,0 +1,105 @@ +// FILE: sequence1.h
+// CLASS PROVIDED: sequence (part of the namespace main_savitch_3)
+// There is no implementation file provided for this class since it is
+// an exercise from Section 3.2 of "Data Structures and Other Objects Using C++"
+//
+// TYPEDEFS and MEMBER CONSTANTS for the sequence class:
+// typedef ____ value_type
+// sequence::value_type is the data type of the items in the sequence. It
+// may be any of the C++ built-in types (int, char, etc.), or a class with a
+// default constructor, an assignment operator, and a copy constructor.
+//
+// typedef ____ size_type
+// sequence::size_type is the data type of any variable that keeps track of
+// how many items are in a sequence.
+//
+// static const size_type CAPACITY = _____
+// sequence::CAPACITY is the maximum number of items that a sequence can hold.
+//
+// CONSTRUCTOR for the sequence class:
+// sequence( )
+// Postcondition: The sequence has been initialized as an empty sequence.
+//
+// MODIFICATION MEMBER FUNCTIONS for the sequence class:
+// void start( )
+// Postcondition: The first item on the sequence becomes the current item
+// (but if the sequence is empty, then there is no current item).
+//
+// void advance( )
+// Precondition: is_item returns true.
+// Postcondition: If the current item was already the last item in the
+// sequence, then there is no longer any current item. Otherwise, the new
+// current item is the item immediately after the original current item.
+//
+// void insert(const value_type& entry)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been inserted in the sequence
+// before the current item. If there was no current item, then the new entry
+// has been inserted at the front of the sequence. In either case, the newly
+// inserted item is now the current item of the sequence.
+//
+// void attach(const value_type& entry)
+// Precondition: size( ) < CAPACITY.
+// Postcondition: A new copy of entry has been inserted in the sequence after
+// the current item. If there was no current item, then the new entry has
+// been attached to the end of the sequence. In either case, the newly
+// inserted item is now the current item of the sequence.
+//
+// void remove_current( )
+// Precondition: is_item returns true.
+// Postcondition: The current item has been removed from the sequence, and the
+// item after this (if there is one) is now the new current item.
+//
+// CONSTANT MEMBER FUNCTIONS for the sequence class:
+// size_type size( ) const
+// Postcondition: The return value is the number of items in the sequence.
+//
+// bool is_item( ) const
+// Postcondition: A true return value indicates that there is a valid
+// "current" item that may be retrieved by activating the current
+// member function (listed below). A false return value indicates that
+// there is no valid current item.
+//
+// value_type current( ) const
+// Precondition: is_item( ) returns true.
+// Postcondition: The item returned is the current item in the sequence.
+//
+// VALUE SEMANTICS for the sequence class:
+// Assignments and the copy constructor may be used with sequence objects.
+
+#ifndef MAIN_SAVITCH_SEQUENCE_H
+#define MAIN_SAVITCH_SEQUENCE_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_3
+{
+ class sequence
+ {
+ public:
+ // TYPEDEFS and MEMBER CONSTANTS
+ typedef double value_type;
+ typedef std::size_t size_type;
+ static const size_type CAPACITY = 30;
+ // CsONSTRUCTOR
+ sequence( );
+ // MODIFICATION MEMBER FUNCTIONS
+ void start( );
+ void advance( );
+ void insert(const value_type& entry);
+ void attach(const value_type& entry);
+ void remove_current( );
+ // CONSTANT MEMBER FUNCTIONS
+ size_type size( ) const;
+ bool is_item( ) const;
+ value_type current( ) const;
+ private:
+ value_type data[CAPACITY];
+ size_type used;
+ size_type current_index;
+ };
+}
+
+#endif
+
+// g++ -o seq sequence1.cpp sequence_test.cxx
+
diff --git a/chapter3/sequence_test.cxx b/chapter3/sequence_test.cxx new file mode 100644 index 0000000..f140203 --- /dev/null +++ b/chapter3/sequence_test.cxx @@ -0,0 +1,119 @@ +// FILE: sequence_test.cxx
+// An interactive test program for the new sequence class
+#include <cctype> // Provides toupper
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include "sequence1.h" // With value_type defined as double
+using namespace std;
+using namespace main_savitch_3;
+
+// 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.
+
+void show_sequence(sequence display);
+// Postcondition: The items on display have been printed to cout (one per line).
+
+double get_number( );
+// Postcondition: The user has been prompted to enter a real number. The
+// number has been read, echoed to the screen, and returned by the function.
+
+
+int main( )
+{
+ sequence test; // A sequence that we�ll perform tests on
+ char choice; // A command character entered by the user
+
+ cout << "I have initialized an empty sequence of real numbers." << endl;
+
+ do
+ {
+ print_menu( );
+ choice = toupper(get_user_command( ));
+ switch (choice)
+ {
+ case '!': test.start( );
+ break;
+ case '+': test.advance( );
+ break;
+ case '?': if (test.is_item( ))
+ cout << "There is an item." << endl;
+ else
+ cout << "There is no current item." << endl;
+ break;
+ case 'C': if (test.is_item( ))
+ cout << "Current item is: " << test.current( ) << endl;
+ else
+ cout << "There is no current item." << endl;
+ break;
+ case 'P': show_sequence(test);
+ break;
+ case 'S': cout << "Size is " << test.size( ) << '.' << endl;
+ break;
+ case 'I': test.insert(get_number( ));
+ break;
+ case 'A': test.attach(get_number( ));
+ break;
+ case 'R': test.remove_current( );
+ cout << "The current item has been removed." << endl;
+ break;
+ case 'Q': cout << "Ridicule is the best test of truth." << endl;
+ break;
+ default: cout << choice << " is invalid." << endl;
+ }
+ }
+ while ((choice != 'Q'));
+
+ return EXIT_SUCCESS;
+}
+
+void print_menu( )
+// Library facilities used: iostream.h
+{
+ cout << endl; // Print blank line before the menu
+ cout << "The following choices are available: " << endl;
+ cout << " ! Activate the start( ) function" << endl;
+ cout << " + Activate the advance( ) function" << endl;
+ cout << " ? Print the result from the is_item( ) function" << endl;
+ cout << " C Print the result from the current( ) function" << endl;
+ cout << " P Print a copy of the entire sequence" << endl;
+ cout << " S Print the result from the size( ) function" << endl;
+ cout << " I Insert a new number with the insert(...) function" << endl;
+ cout << " A Attach a new number with the attach(...) function" << endl;
+ cout << " R Activate the remove_current( ) function" << endl;
+ cout << " Q Quit this test program" << endl;
+}
+
+char get_user_command( )
+// Library facilities used: iostream
+{
+ char command;
+
+ cout << "Enter choice: ";
+ cin >> command; // Input of characters skips blanks and newline character
+
+ return command;
+}
+
+void show_sequence(sequence display)
+// Library facilities used: iostream
+{
+ for (display.start( ); display.is_item( ); display.advance( ))
+ cout << display.current( ) << endl;
+}
+
+double get_number( )
+// Library facilities used: iostream
+{
+ double result;
+
+ cout << "Please enter a real number for the sequence: ";
+ cin >> result;
+ cout << result << " has been read." << endl;
+ return result;
+}
|