diff options
Diffstat (limited to 'chapter4')
| -rw-r--r-- | chapter4/bag2.cxx | 157 | ||||
| -rw-r--r-- | chapter4/bag2.h | 104 | ||||
| -rw-r--r-- | chapter4/bag2demo.cxx | 63 | ||||
| -rw-r--r-- | chapter4/dynademo.cxx | 102 | ||||
| -rw-r--r-- | chapter4/mystring.h | 117 | ||||
| -rw-r--r-- | chapter4/str_demo.cxx | 39 |
6 files changed, 582 insertions, 0 deletions
diff --git a/chapter4/bag2.cxx b/chapter4/bag2.cxx new file mode 100644 index 0000000..b0dc009 --- /dev/null +++ b/chapter4/bag2.cxx @@ -0,0 +1,157 @@ +// FILE: bag2.cxx
+// CLASS implemented: bag (see bag2.h for documentation)
+// INVARIANT for the bag class:
+// 1. The number of items in the bag is in the member variable used;
+// 2. The actual items of the bag are stored in a partially filled array.
+// The array is a dynamic array, pointed to by the member variable data;
+// 3. The size of the dynamic array is in the member variable capacity.
+
+#include <algorithm> // Provides copy function
+#include <cassert> // Provides assert function
+#include "bag2.h"
+using namespace std;
+
+namespace main_savitch_4
+{
+ const bag::size_type bag::DEFAULT_CAPACITY;
+
+ bag::bag(size_type initial_capacity)
+ {
+ data = new value_type[initial_capacity];
+ capacity = initial_capacity;
+ used = 0;
+ }
+
+ bag::bag(const bag& source) // bag b2(b1);
+ // Library facilities used: algorithm
+ {
+ data = new value_type[source.capacity];
+ capacity = source.capacity;
+ used = source.used;
+ copy(source.data, source.data + used, data);
+ }
+
+ bag::~bag( )
+ {
+ delete [ ] data;
+ }
+
+ void bag::reserve(size_type new_capacity)
+ // Library facilities used: algorithm
+ {
+ value_type *larger_array;
+
+ if (new_capacity == capacity)
+ return; // The allocated memory is already the right size.
+
+ if (new_capacity < used)
+ new_capacity = used; // Can�t allocate less than we are using.
+
+ larger_array = new value_type[new_capacity];
+ copy(data, data + used, larger_array);
+ delete [ ] data;
+ data = larger_array;
+ capacity = new_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
+
+ index = 0;
+ while ((index < used) && (data[index] != target))
+ ++index;
+
+ if (index == used) // target isn't in the bag, so no work to do
+ return false;
+
+ // 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)
+ {
+ if (used == capacity)
+ reserve(used+1);
+ data[used] = entry;
+ ++used;
+ }
+
+ void bag::operator +=(const bag& addend)
+ // Library facilities used: algorithm
+ {
+ if (used + addend.used > capacity)
+ reserve(used + addend.used);
+
+ copy(addend.data, addend.data + addend.used, data + used);
+ used += addend.used;
+ }
+
+ void bag::operator =(const bag& source)
+ // Library facilities used: algorithm
+ {
+ value_type *new_data;
+
+ // Check for possible self-assignment:
+ if (this == &source)
+ return;
+
+ // If needed, allocate an array with a different size:
+ if (capacity != source.capacity)
+ {
+ new_data = new value_type[source.capacity];
+ delete [ ] data;
+ data = new_data;
+ capacity = source.capacity;
+ }
+
+ // Copy the data from the source array:
+ used = source.used;
+ copy(source.data, source.data + used, data);
+ }
+
+ 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)
+ {
+ bag answer(b1.size( ) + b2.size( ));
+
+ answer += b1;
+ answer += b2;
+ return answer;
+ }
+
+}
diff --git a/chapter4/bag2.h b/chapter4/bag2.h new file mode 100644 index 0000000..5c0bb75 --- /dev/null +++ b/chapter4/bag2.h @@ -0,0 +1,104 @@ +// FILE: bag2.h
+// CLASS PROVIDED: bag (a container class for a collection of items)
+//
+// TYPEDEFS 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 DEFAULT_CAPACITY = _____
+// bag::DEFAULT_CAPACITY is the initial capacity of a bag that is created
+// by the default constructor.
+//
+// CONSTRUCTOR for the bag class:
+// bag(size_type initial_capacity = DEFAULT_CAPACITY)
+// Postcondition: The bag is empty with an initial capacity given by the
+// parameter. The insert function will work efficiently (without
+// allocating new memory) until this capacity is reached.
+//
+// MODIFICATION MEMBER FUNCTIONS for the bag class:
+// void reserve(size_type new_capacity)
+// Postcondition: The bag's current capacity is changed to the
+// new_capacity (but not less than the number of items already in the
+// bag). The insert function will work efficiently (without allocating
+// new memory) until the new capacity is reached.
+//
+// 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)
+// 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
+//
+// 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, reserve, insert, operator += ,
+// operator +, and the assignment operator.
+
+#ifndef MAIN_SAVITCH_BAG2_H
+#define MAIN_SAVITCH_BAG2_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_4
+{
+ class bag
+ {
+ public:
+ // TYPEDEFS and MEMBER CONSTANTS
+ typedef int value_type;
+ typedef std::size_t size_type;
+ static const size_type DEFAULT_CAPACITY = 30;
+ // CONSTRUCTORS and DESTRUCTOR
+ bag(size_type initial_capacity = DEFAULT_CAPACITY);
+ bag(const bag& source); // copy constructor -- bag b2(b1);
+ ~bag( );
+ // MODIFICATION MEMBER FUNCTIONS
+ void reserve(size_type new_capacity);
+ bool erase_one(const value_type& target);
+ size_type erase(const value_type& target);
+ void insert(const value_type& entry);
+ void operator +=(const bag& addend); // b2 += b1;
+ void operator =(const bag& source); // b2 = b1;
+ // CONSTANT MEMBER FUNCTIONS
+ size_type size( ) const
+ { return used; }
+ size_type count(const value_type& target) const;
+ private:
+ value_type *data; // Pointer to partially filled dynamic array
+ size_type used; // How much of array is being used
+ size_type capacity; // Current capacity of the bag
+ };
+
+ // NONMEMBER FUNCTIONS for the bag class
+ bag operator +(const bag& b1, const bag& b2); // b3 = b1 + b2;
+}
+
+#endif
diff --git a/chapter4/bag2demo.cxx b/chapter4/bag2demo.cxx new file mode 100644 index 0000000..5a9b8ef --- /dev/null +++ b/chapter4/bag2demo.cxx @@ -0,0 +1,63 @@ +// FILE: bag2demo.cxx
+// Demonstration program for the 2nd version of the bag (bag2.h and bag2.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 "bag2.h" // With Item defined as an int
+using namespace std;
+using namespace main_savitch_4;
+
+// 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(2);
+
+ 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/chapter4/dynademo.cxx b/chapter4/dynademo.cxx new file mode 100644 index 0000000..fa10473 --- /dev/null +++ b/chapter4/dynademo.cxx @@ -0,0 +1,102 @@ +// FILE: dynademo.cxx
+// This is a small demonstration program showing how a dynamic array is used.
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS and size_t
+#include <cassert> // Provides assert
+using namespace std;
+
+// PROTOTYPES for functions used by this demonstration program
+void allocate_doubles(double*& p, size_t& n);
+// Postcondition: The user has been prompted for a size n, and this size has been read.
+// The pointer p has been set to point to a new dynamic array containing n doubles.
+// NOTE: If there is insufficient dynamic memory, then bad_alloc is thrown.
+
+void fill_array(double data[ ], size_t n);
+// Precondition: data is an array with at least n components.
+// Postcondition: The user has been prompted to type n doubles, and these
+// numbers have been read and placed in the first n components of the array.
+
+double average(const double data[ ], size_t n);
+// Precondition: data is an array with at least n components, and n > 0.
+// Postcondition: The value returned is the average of data[0]..data[n-1].
+
+void compare(const double data[ ], size_t n, double value);
+// Precondition: data is an array with at least n components.
+// Postcondition: The values data[0]..data[n-1] have been printed with a
+// message saying whether they are above, below, or equal to value.
+
+
+int main( )
+{
+ double *numbers; // Will point to the first component of an array
+ size_t array_size;
+ double mean_value;
+
+ // Allocate an array of doubles to hold the user�s input.
+ cout << "This program will compute the average of some numbers. The\n";
+ cout << "numbers will be stored in an array of doubles that I allocate.\n";
+ allocate_doubles(numbers, array_size);
+
+ // Read the user�s input and compute the average.
+ fill_array(numbers, array_size);
+ mean_value = average(numbers, array_size);
+
+ // Print the output.
+ cout << "The average is: " << mean_value << endl;
+ compare(numbers, array_size, mean_value);
+ cout << "This was a mean program.";
+
+ return EXIT_SUCCESS;
+}
+
+void allocate_doubles(double*& p, size_t& n)
+// Library facilities used: iostream.h, stdlib.h
+{
+ cout << "How many doubles should I allocate?" << endl;
+ cout << "Please type a positive integer answer: ";
+ cin >> n;
+ p = new double[n];
+}
+
+void fill_array(double data[ ], size_t n)
+// Library facilities used: cstdlib
+{
+ size_t i;
+ cout << "Please type " << n << " double numbers: " << endl;
+
+ // Read the n numbers one at a time.
+ for (i = 0; i < n; ++i)
+ cin >> data[i];
+}
+
+void compare(const double data[ ], size_t n, double value)
+{
+ size_t i;
+
+ for (i = 0; i < n; ++i)
+ {
+ cout << data[i];
+ if (data[i] < value)
+ cout << " is less than ";
+ else if (data[i] > value)
+ cout << " is more than ";
+ else
+ cout << " is equal to ";
+ cout << value << endl;
+ }
+}
+
+double average(const double data[ ], size_t n)
+// Library facilities used: cassert, cstdlib
+{
+ size_t i; // An array index
+ double sum; // The sum of data[0] through data[n - 1]
+
+ assert(n > 0);
+
+ // Add up the n numbers and return the average.
+ sum = 0;
+ for (i = 0; i < n; ++i)
+ sum += data[i];
+ return (sum/n);
+}
diff --git a/chapter4/mystring.h b/chapter4/mystring.h new file mode 100644 index 0000000..2019fc9 --- /dev/null +++ b/chapter4/mystring.h @@ -0,0 +1,117 @@ +// FILE: mystring.h
+// CLASS PROVIDED: string
+// This is a simple version of the Standard Library string.
+// It is part of the namespace main_savitch_4, from the textbook
+// "Data Structures and Other Objects Using C++"
+// by Michal Main and Walter Savitch
+//
+// CONSTRUCTOR for the string class:
+// string(const char str[ ] = "") -- default argument is the empty string.
+// Precondition: str is an ordinary null-terminated string.
+// Postcondition: The string contains the sequence of chars from str.
+//
+// CONSTANT MEMBER FUNCTIONS for the string class:
+// size_t length( ) const
+// Postcondition: The return value is the number of characters in the
+// string.
+//
+// char operator [ ](size_t position) const
+// Precondition: position < length( ).
+// Postcondition: The value returned is the character at the specified
+// position of the string. A string's positions start from 0 at the start
+// of the sequence and go up to length( )-1 at the right end.
+//
+// MODIFICATION MEMBER FUNCTIONS for the string class:
+// void operator +=(const string& addend)
+// Postcondition: addend has been catenated to the end of the string.
+//
+// void operator +=(const char addend[ ])
+// Precondition: addend is an ordinary null-terminated string.
+// Postcondition: addend has been catenated to the end of the string.
+//
+// void operator +=(char addend)
+// Postcondition: The single character addend has been catenated to the
+// end of the string.
+//
+// void reserve(size_t n)
+// Postcondition: All functions will now work efficiently (without
+// allocating new memory) until n characters are in the string.
+//
+// NON-MEMBER FUNCTIONS for the string class:
+// string operator +(const string& s1, const string& s2)
+// Postcondition: The string returned is the catenation of s1 and s2.
+//
+// istream& operator >>(istream& ins, string& target)
+// Postcondition: A string has been read from the istream ins, and the
+// istream ins is then returned by the function. The reading operation
+// skips white space (i.e., blanks, newlines, tabs) at the start of ins.
+// Then the string is read up to the next white space or the end of the
+// file. The white space character that terminates the string has not
+// been read.
+//
+// ostream& operator <<(ostream& outs, const string& source)
+// Postcondition: The sequence of characters in source has been written
+// to outs. The return value is the ostream outs.
+//
+// void getline(istream& ins, string& target, char delimiter)
+// Postcondition: A string has been read from the istream ins. The reading
+// operation starts by skipping any white space, then reading all characters
+// (including white space) until the delimiter is read and discarded (but
+// not added to the end of the string). The return value is ins.
+//
+// VALUE SEMANTICS for the string class:
+// Assignments and the copy constructor may be used with string objects.
+//
+// TOTAL ORDER SEMANTICS for the string class:
+// The six comparison operators (==, !=, >=, <=, >, and <) are implemented
+// for the string class, forming a total order semantics, using the usual
+// lexicographic order on strings.
+//
+// DYNAMIC MEMORY usage by the string class:
+// If there is insufficient dynamic memory then the following functions call
+// new_handler: The constructors, resize, operator +=, operator +, and the
+// assignment operator.
+
+#ifndef MAIN_SAVITCH_CHAPTER4_MYSTRING_H
+#define MAIN_SAVITCH_CHAPTER4_MYSTRING_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_4
+{
+ class string
+ {
+ public:
+ // CONSTRUCTORS and DESTRUCTOR
+ string(const char str[ ] = "");
+ string(const string& source);
+ ~string( );
+ // MODIFICATION MEMBER FUNCTIONS
+ void operator +=(const string& addend);
+ void operator +=(const char addend[ ]);
+ void operator +=(char addend);
+ void reserve(size_t n);
+ void operator =(const string& source);
+ // CONSTANT MEMBER FUNCTIONS
+ size_t length( ) const { return current_length; }
+ char operator [ ](size_t position) const;
+ // FRIEND FUNCTIONS
+ friend ostream& operator <<(ostream& outs, const string& source);
+ friend bool operator ==(const string& s1, const string& s2);
+ friend bool operator !=(const string& s1, const string& s2);
+ friend bool operator >=(const string& s1, const string& s2);
+ friend bool operator <=(const string& s1, const string& s2);
+ friend bool operator > (const string& s1, const string& s2);
+ friend bool operator < (const string& s1, const string& s2);
+ private:
+ char *sequence;
+ size_t allocated;
+ size_t current_length;
+ };
+
+ // NON-MEMBER FUNCTIONS for the string class
+ string operator +(const string& s1, const string& s2);
+ istream& operator >>(istream& ins, string& target);
+ void getline(istream& ins, string& target, char delimiter);
+}
+
+#endif
diff --git a/chapter4/str_demo.cxx b/chapter4/str_demo.cxx new file mode 100644 index 0000000..df7877e --- /dev/null +++ b/chapter4/str_demo.cxx @@ -0,0 +1,39 @@ +// FILE: str_demo.cxx
+// This is a small demonstration program showing how the string class is used.
+#include <iostream> // Provides cout and cin
+#include <cstdlib> // Provides EXIT_SUCCESS
+#include "mystring.h" // Or use the Standard Library <string>
+using namespace std;
+using namespace main_savitch_4;
+
+// PROTOTYPES for functions used by this demonstration program:
+void match(const string& variety, const string& mine, const string& yours);
+// The two strings, mine and yours, are compared. If they are the same, then a
+// message is printed saying they are the same; otherwise mine is printed
+// in a message. In either case, the string variety is part of the message.
+
+int main( )
+{
+ const string BLANK(" ");
+ string me_first("Demo"), me_last("Program");
+ string you_first, you_last, you;
+
+ cout << "What is your first name? ";
+ cin >> you_first;
+ match("first name", me_first, you_first);
+ cout << "What is your last name? ";
+ cin >> you_last;
+ match("last name", me_last, you_last);
+
+ you = you_first + BLANK + you_last;
+ cout << "I am happy to meet you, " << you << "." << endl;
+ return EXIT_SUCCESS;
+}
+
+void match(const string& variety, const string& mine, const string& yours)
+{
+ if (mine == yours)
+ cout << "That is the same as my " << variety << "!" << endl;
+ else
+ cout << "My " << variety << " is " << mine << "." << endl;
+}
|