From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter4/bag2.cxx | 157 ++++++++++++++++++++++++++++++++++++++++++++++++++ chapter4/bag2.h | 104 +++++++++++++++++++++++++++++++++ chapter4/bag2demo.cxx | 63 ++++++++++++++++++++ chapter4/dynademo.cxx | 102 ++++++++++++++++++++++++++++++++ chapter4/mystring.h | 117 +++++++++++++++++++++++++++++++++++++ chapter4/str_demo.cxx | 39 +++++++++++++ 6 files changed, 582 insertions(+) create mode 100644 chapter4/bag2.cxx create mode 100644 chapter4/bag2.h create mode 100644 chapter4/bag2demo.cxx create mode 100644 chapter4/dynademo.cxx create mode 100644 chapter4/mystring.h create mode 100644 chapter4/str_demo.cxx (limited to 'chapter4') 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 // Provides copy function +#include // 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 // 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 // Provides cout and cin +#include // 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 // Provides cout and cin +#include // Provides EXIT_SUCCESS and size_t +#include // 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 // 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 // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "mystring.h" // Or use the Standard Library +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; +} -- cgit v1.2.3