From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- appendix/useful.cxx | 80 ++++++++++++ appendix/useful.h | 45 +++++++ chapter1/guess.cxx | 43 +++++++ chapter1/temperature.cxx | 65 ++++++++++ chapter10/animal.cxx | 149 +++++++++++++++++++++++ chapter10/bag6.h | 94 ++++++++++++++ chapter10/bintree.h | 169 ++++++++++++++++++++++++++ chapter10/bintree.template | 100 +++++++++++++++ chapter10/bt_class.h | 126 +++++++++++++++++++ chapter10/useful.cxx | 80 ++++++++++++ chapter10/useful.h | 46 +++++++ chapter11/set.h | 94 ++++++++++++++ chapter12/node2.h | 270 +++++++++++++++++++++++++++++++++++++++++ chapter12/node2.template | 128 +++++++++++++++++++ chapter12/search.cxx | 79 ++++++++++++ chapter12/table1.h | 84 +++++++++++++ chapter12/table1.template | 144 ++++++++++++++++++++++ chapter12/table2.h | 82 +++++++++++++ chapter12/table2.template | 1 + chapter12/testtab1.cxx | 130 ++++++++++++++++++++ chapter12/testtab2.cxx | 130 ++++++++++++++++++++ chapter13/heapsort.cxx | 166 +++++++++++++++++++++++++ chapter13/merge.cxx | 122 +++++++++++++++++++ chapter13/quick.cxx | 107 ++++++++++++++++ chapter13/select.cxx | 71 +++++++++++ chapter14/Makefile | 14 +++ chapter14/blob.cxx | 32 +++++ chapter14/clocks.cxx | 137 +++++++++++++++++++++ chapter14/clocks.h | 102 ++++++++++++++++ chapter14/connect4.cxx | 225 ++++++++++++++++++++++++++++++++++ chapter14/connect4.h | 58 +++++++++ chapter14/game.cxx | 167 +++++++++++++++++++++++++ chapter14/game.h | 86 +++++++++++++ chapter14/organism.cxx | 126 +++++++++++++++++++ chapter14/organism.h | 193 +++++++++++++++++++++++++++++ chapter14/play_connect4.cxx | 30 +++++ chapter14/pondlife.cxx | 126 +++++++++++++++++++ chapter15/graph.h | 99 +++++++++++++++ chapter15/graph.template | 100 +++++++++++++++ chapter15/searches.h | 48 ++++++++ chapter15/searches.template | 93 ++++++++++++++ chapter2/demo1.cxx | 79 ++++++++++++ chapter2/demo2.cxx | 31 +++++ chapter2/newpoint.cxx | 120 ++++++++++++++++++ chapter2/newpoint.h | 82 +++++++++++++ chapter2/point.cxx | 33 +++++ chapter2/point.h | 49 ++++++++ chapter2/throttle.cxx | 35 ++++++ chapter2/throttle.h | 58 +++++++++ chapter3/bag1.cxx | 100 +++++++++++++++ chapter3/bag1.h | 87 +++++++++++++ chapter3/bag_demo.cxx | 62 ++++++++++ chapter3/sequence1.h | 105 ++++++++++++++++ chapter3/sequence_test.cxx | 119 ++++++++++++++++++ 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 ++++++ chapter5/bag3.cxx | 154 +++++++++++++++++++++++ chapter5/bag3.h | 94 ++++++++++++++ chapter5/bag3.zip | Bin 0 -> 6629 bytes chapter5/bag3demo.cxx | 63 ++++++++++ chapter5/node1.cxx | 137 +++++++++++++++++++++ chapter5/node1.h | 175 ++++++++++++++++++++++++++ chapter6/author.cxx | 63 ++++++++++ chapter6/author.exe | Bin 0 -> 109616 bytes chapter6/author.o | Bin 0 -> 79390 bytes chapter6/bag4.h | 113 +++++++++++++++++ chapter6/bag4.template | 194 +++++++++++++++++++++++++++++ chapter6/bag4demo.cxx | 64 ++++++++++ chapter6/bag5.h | 128 +++++++++++++++++++ chapter6/bag5.template | 164 +++++++++++++++++++++++++ chapter6/maximal.cxx | 36 ++++++ chapter6/maximal.exe | Bin 0 -> 95225 bytes chapter6/maximal.o | Bin 0 -> 65610 bytes chapter6/node2.h | 204 +++++++++++++++++++++++++++++++ chapter6/node2.template | 128 +++++++++++++++++++ chapter7/calc.cxx | 101 +++++++++++++++ chapter7/calc.exe | Bin 0 -> 123748 bytes chapter7/calc.o | Bin 0 -> 112994 bytes chapter7/ch7files-stack.zip | Bin 0 -> 9653 bytes chapter7/node2.h | 204 +++++++++++++++++++++++++++++++ chapter7/node2.template | 128 +++++++++++++++++++ chapter7/parens.cxx | 54 +++++++++ chapter7/parens.exe | Bin 0 -> 99658 bytes chapter7/parens.o | Bin 0 -> 73250 bytes chapter7/stack1.h | 79 ++++++++++++ chapter7/stack1.template | 41 +++++++ chapter7/stack2.h | 78 ++++++++++++ chapter7/stack2.template | 59 +++++++++ chapter8/carwash.cxx | 73 +++++++++++ chapter8/ch8queueFiles.zip | Bin 0 -> 12208 bytes chapter8/node2.h | 270 +++++++++++++++++++++++++++++++++++++++++ chapter8/node2.template | 128 +++++++++++++++++++ chapter8/pal.cxx | 44 +++++++ chapter8/pal.exe | Bin 0 -> 95181 bytes chapter8/pal.o | Bin 0 -> 64111 bytes chapter8/queue1.h | 81 +++++++++++++ chapter8/queue1.template | 55 +++++++++ chapter8/queue2.h | 76 ++++++++++++ chapter8/queue2.template | 88 ++++++++++++++ chapter8/queueFiles.zip | Bin 0 -> 8274 bytes chapter8/washing.cxx | 80 ++++++++++++ chapter8/washing.h | 113 +++++++++++++++++ chapter9/fractal.cxx | 48 ++++++++ chapter9/fractal.o | Bin 0 -> 3233 bytes chapter9/maze.cxx | 75 ++++++++++++ chapter9/powers.cxx | 59 +++++++++ chapter9/powers.exe | Bin 0 -> 62407 bytes chapter9/powers.o | Bin 0 -> 3858 bytes chapter9/recursionPrograms.zip | Bin 0 -> 4930 bytes chapter9/useful.cxx | 80 ++++++++++++ chapter9/useful.h | 46 +++++++ chapter9/vertical.cxx | 47 +++++++ chapter9/vertical.exe | Bin 0 -> 58448 bytes chapter9/vertical.o | Bin 0 -> 3912 bytes 118 files changed, 9607 insertions(+) create mode 100644 appendix/useful.cxx create mode 100644 appendix/useful.h create mode 100644 chapter1/guess.cxx create mode 100644 chapter1/temperature.cxx create mode 100644 chapter10/animal.cxx create mode 100644 chapter10/bag6.h create mode 100644 chapter10/bintree.h create mode 100644 chapter10/bintree.template create mode 100644 chapter10/bt_class.h create mode 100644 chapter10/useful.cxx create mode 100644 chapter10/useful.h create mode 100644 chapter11/set.h create mode 100644 chapter12/node2.h create mode 100644 chapter12/node2.template create mode 100644 chapter12/search.cxx create mode 100644 chapter12/table1.h create mode 100644 chapter12/table1.template create mode 100644 chapter12/table2.h create mode 100644 chapter12/table2.template create mode 100644 chapter12/testtab1.cxx create mode 100644 chapter12/testtab2.cxx create mode 100644 chapter13/heapsort.cxx create mode 100644 chapter13/merge.cxx create mode 100644 chapter13/quick.cxx create mode 100644 chapter13/select.cxx create mode 100644 chapter14/Makefile create mode 100644 chapter14/blob.cxx create mode 100644 chapter14/clocks.cxx create mode 100644 chapter14/clocks.h create mode 100644 chapter14/connect4.cxx create mode 100644 chapter14/connect4.h create mode 100644 chapter14/game.cxx create mode 100644 chapter14/game.h create mode 100644 chapter14/organism.cxx create mode 100644 chapter14/organism.h create mode 100644 chapter14/play_connect4.cxx create mode 100644 chapter14/pondlife.cxx create mode 100644 chapter15/graph.h create mode 100644 chapter15/graph.template create mode 100644 chapter15/searches.h create mode 100644 chapter15/searches.template create mode 100644 chapter2/demo1.cxx create mode 100644 chapter2/demo2.cxx create mode 100644 chapter2/newpoint.cxx create mode 100644 chapter2/newpoint.h create mode 100644 chapter2/point.cxx create mode 100644 chapter2/point.h create mode 100644 chapter2/throttle.cxx create mode 100644 chapter2/throttle.h create mode 100644 chapter3/bag1.cxx create mode 100644 chapter3/bag1.h create mode 100644 chapter3/bag_demo.cxx create mode 100644 chapter3/sequence1.h create mode 100644 chapter3/sequence_test.cxx 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 create mode 100644 chapter5/bag3.cxx create mode 100644 chapter5/bag3.h create mode 100644 chapter5/bag3.zip create mode 100644 chapter5/bag3demo.cxx create mode 100644 chapter5/node1.cxx create mode 100644 chapter5/node1.h create mode 100644 chapter6/author.cxx create mode 100644 chapter6/author.exe create mode 100644 chapter6/author.o create mode 100644 chapter6/bag4.h create mode 100644 chapter6/bag4.template create mode 100644 chapter6/bag4demo.cxx create mode 100644 chapter6/bag5.h create mode 100644 chapter6/bag5.template create mode 100644 chapter6/maximal.cxx create mode 100644 chapter6/maximal.exe create mode 100644 chapter6/maximal.o create mode 100644 chapter6/node2.h create mode 100644 chapter6/node2.template create mode 100644 chapter7/calc.cxx create mode 100644 chapter7/calc.exe create mode 100644 chapter7/calc.o create mode 100644 chapter7/ch7files-stack.zip create mode 100644 chapter7/node2.h create mode 100644 chapter7/node2.template create mode 100644 chapter7/parens.cxx create mode 100644 chapter7/parens.exe create mode 100644 chapter7/parens.o create mode 100644 chapter7/stack1.h create mode 100644 chapter7/stack1.template create mode 100644 chapter7/stack2.h create mode 100644 chapter7/stack2.template create mode 100644 chapter8/carwash.cxx create mode 100644 chapter8/ch8queueFiles.zip create mode 100644 chapter8/node2.h create mode 100644 chapter8/node2.template create mode 100644 chapter8/pal.cxx create mode 100644 chapter8/pal.exe create mode 100644 chapter8/pal.o create mode 100644 chapter8/queue1.h create mode 100644 chapter8/queue1.template create mode 100644 chapter8/queue2.h create mode 100644 chapter8/queue2.template create mode 100644 chapter8/queueFiles.zip create mode 100644 chapter8/washing.cxx create mode 100644 chapter8/washing.h create mode 100644 chapter9/fractal.cxx create mode 100644 chapter9/fractal.o create mode 100644 chapter9/maze.cxx create mode 100644 chapter9/powers.cxx create mode 100644 chapter9/powers.exe create mode 100644 chapter9/powers.o create mode 100644 chapter9/recursionPrograms.zip create mode 100644 chapter9/useful.cxx create mode 100644 chapter9/useful.h create mode 100644 chapter9/vertical.cxx create mode 100644 chapter9/vertical.exe create mode 100644 chapter9/vertical.o diff --git a/appendix/useful.cxx b/appendix/useful.cxx new file mode 100644 index 0000000..79dff57 --- /dev/null +++ b/appendix/useful.cxx @@ -0,0 +1,80 @@ +// FILE: useful.cxx +// IMPLEMENTS: A toolkit of functions (See useful.h for documentation.) + +#include // Provides assert +#include // Provides toupper +#include // Provides cout, cin, get +#include // Provides rand, RAND_MAX +#include "useful.h" + +void display(double x) +// Library facilities used: iostream.h, stdlib.h +{ + const char STAR = '*'; + const char BLANK = ' '; + const char VERTICAL_BAR = '|'; + const int LIMIT = 39; + int i; + + if (x < -LIMIT) + x = -LIMIT; + else if (x > LIMIT) + x = LIMIT; + + for (i = -LIMIT; i < 0; i++) + { + if (i >= x) + cout << STAR; + else + cout << BLANK; + } + cout << VERTICAL_BAR; + for (i = 1; i <= LIMIT; i++) + { + if (i <= x) + cout << STAR; + else + cout << BLANK; + } + cout << endl; +} + +double random_fraction( ) +// Library facilities used: stdlib.h +{ + return rand( ) / double(RAND_MAX); +} + +double random_real(double low, double high) +// Library facilities used: assert.h +{ + assert(low <= high); + return low + random_fraction( ) * (high - low); +} + +void eat_line( ) +// Library facilities used: iostream.h +// +{ + char next; + + do + cin.get(next); + while (next != '\n'); +} + +bool inquire(const char query[ ]) +// Library facilities used: ctype.h, iostream.h +{ + char answer; + do + { + cout << query << " [Yes or No]" << endl; + cin >> answer; + answer = toupper(answer); + eat_line( ); + } + while ((answer != 'Y') && (answer != 'N')); + return (answer == 'Y'); +} + diff --git a/appendix/useful.h b/appendix/useful.h new file mode 100644 index 0000000..4513936 --- /dev/null +++ b/appendix/useful.h @@ -0,0 +1,45 @@ +// FILE: useful.h +// PROVIDES: A toolkit of useful functions for random numbers and displays. +// +// FUNCTIONS in the toolkit: +// double random_fraction( ) +// Postcondition: The return value is a random real number in the closed +// interval [0..1] (including the endpoints). +// +// double random_real(double low, double high) +// Precondition: low <= high. +// Postcondition: The return value is a random real number in the closed +// interval [low..high] (including the endpoints). +// +// void display(double x) +// Postcondition: The function has written one line of output to the +// standard ouput, with a vertical bar in the middle. If x is positive, +// then approximately x stars are printed to the right of the vertical +// bar. If x is negative, then approximately -x stars are printed to the +// left of the vertical bar. If the absolute value of x is more than +// 39, then only 39 stars are printed. +// Examples: +// display(8) prints: |******** +// display(-4) prints: ****| +// +// void eat_line( ) +// Postcondition: Up to next newline has been read and discarded from cin. +// +// bool inquire(const char query[ ]) +// Precondition: query is a null-terminated string of characters. +// Postcondition: query has been printed, and a one-line response read +// from the user. The function returns true if the user's response begins +// with 'Y' or 'y', and returns false if the user's response begins with +// 'N' or 'n'. (If the response begins with some other letter, then the +// query is repeated.) + +#ifndef USEFUL_H // Prevent duplicate definition +#define USEFUL_H + + double random_fraction( ); + double random_real(double low, double high); + void display(double x); + void eat_line( ); + bool inquire(const char query[ ]); + +#endif diff --git a/chapter1/guess.cxx b/chapter1/guess.cxx new file mode 100644 index 0000000..899c3bc --- /dev/null +++ b/chapter1/guess.cxx @@ -0,0 +1,43 @@ +// FILE: guess.cxx +// Demostrates a guessing game function that's used as a time analysis example. + +#include // Provides assert +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +using namespace std; // Allows all Standard Library items to be used + +// Prototype for the function used in this demonstration program +void guess_game(int n); +// Precondition: n > 0. +// Postcondition: The user has been asked to think of a number between 1 and n. +// The function asks a series of questions, until the number is found. + + +int main( ) +{ + guess_game(100); + return EXIT_SUCCESS; +} + +void guess_game(int n) +// Library facilities used: cassert, iostream +{ + int guess; + char answer; + + assert(n >= 1); + + cout << "Think of a whole number from 1 to " << n << "." << endl; + answer = 'N'; + for (guess = n; (guess > 0) && (answer != 'Y') && (answer != 'y'); --guess) + { + cout << "Is your number " << guess << "?" << endl; + cout << "Please answer Y or N, and press return: "; + cin >> answer; + } + + if ((answer == 'Y') || (answer == 'y')) + cout << "I knew it all along." << endl; + else + cout << "I think you are cheating!" << endl; +} diff --git a/chapter1/temperature.cxx b/chapter1/temperature.cxx new file mode 100644 index 0000000..beeb4b7 --- /dev/null +++ b/chapter1/temperature.cxx @@ -0,0 +1,65 @@ +// File: temperature.cxx +// This program prints a table to convert numbers from one unit to another. +// The program illustrases some implementation techniques. + +#include // Provides cout +#include // Provides setw function for setting output width +#include // Provides EXIT_SUCCESS +#include // Provides assert function +using namespace std; // Allows all standard library items to be used + +double celsius_to_fahrenheit(double c) +// Precondition: c is a Celsius temperature no less than absolute +// zero (-273.16). +// Postcondition: The return value is the temperature c converted to Fahrenheit +// degrees. +{ + const double MINIMUM_CELSIUS = -273.16; // Absolute zero in Celsius degrees + assert(c >= MINIMUM_CELSIUS); + return (9.0 / 5.0) * c + 32; +} + +void setup_cout_fractions(int fraction_digits) +// Precondition: fraction_digits is not negative. +// Postcondition: All double or float numbers printed to cout will now be +// rounded to the specified digits on the right of the decimal. +{ + assert(fraction_digits > 0); + cout.precision(fraction_digits); + cout.setf(ios::fixed, ios::floatfield); + if (fraction_digits == 0) + cout.unsetf(ios::showpoint); + else + cout.setf(ios::showpoint); +} + +int main( ) +{ + const char HEADING1[] = " Celsius"; // Heading for table's 1st column + const char HEADING2[] = "Fahrenheit"; // Heading for table's 2nd column + const char LABEL1 = 'C'; // Label for numbers in 1st column + const char LABEL2 = 'F'; // Label for numbers in 2nd column + const double TABLE_BEGIN = -50.0; // The table's first Celsius temp. + const double TABLE_END = 50.0; // The table's final Celsius temp. + const double TABLE_STEP = 10.0; // Increment between temperatures + const int WIDTH = 9; // Number chars in output numbers + const int DIGITS = 1; // Number digits right of decimal pt + + double value1; // A value from the table's first column + double value2; // A value from the table's second column + + // Set up the output for fractions and print the table headings. + setup_cout_fractions(DIGITS); + cout << "CONVERSIONS from " << TABLE_BEGIN << " to " << TABLE_END << endl; + cout << HEADING1 << " " << HEADING2 << endl; + + // Each iteration of the loop prints one line of the table. + for (value1 = TABLE_BEGIN; value1 <= TABLE_END; value1 += TABLE_STEP) + { + value2 = celsius_to_fahrenheit(value1); + cout << setw(WIDTH) << value1 << LABEL1 << " "; + cout << setw(WIDTH) << value2 << LABEL2 << endl; + } + + return EXIT_SUCCESS; +} diff --git a/chapter10/animal.cxx b/chapter10/animal.cxx new file mode 100644 index 0000000..74f291b --- /dev/null +++ b/chapter10/animal.cxx @@ -0,0 +1,149 @@ +// FILE: animal.cxx +// An animal-guessing program to illustrate the use of the binary tree toolkit. + +#include // Provides EXIT_SUCCESS +#include // Provides cout +#include // Provides string class +#include "bintree.h" // Provides the binary tree node functions +#include "useful.h" // Provides eat_line, inquire (from Appendix I) +using namespace std; +using namespace main_savitch_10; + +// PROTOTYPES for functions used by this game program: +void ask_and_move(binary_tree_node*& current_ptr); +// Precondition: current_ptr points to a non-leaf node in a binary taxonomy tree. +// Postcondition: The question at the current node has been asked. The current +// pointer has been shifted left (if the user answered yes) or right +// (for a no answer). + +binary_tree_node* beginning_tree( ); +// Postcondition: The function has created a small taxonomy tree. The return +// value is the root pointer of the new tree. + +void instruct( ); +// Postcondition: Instructions for playing the game have been printed to the +// screen. + +void learn(binary_tree_node*& leaf_ptr); +// Precondition: leaf_ptr is a pointer to a leaf in a taxonomy tree. The leaf +// contains a wrong guess that was just made. +// Postcondition: Information has been elicited from the user, and the tree has +// been improved. + +void play(binary_tree_node* current_ptr); +// Precondition: current_ptr points to the root of a binary taxonomy tree with +// at least two leaves. +// Postcondition: One round of the animal game has been played, and maybe the +// tree has been improved. + + +int main( ) +{ + binary_tree_node *taxonomy_root_ptr; + + instruct( ); + taxonomy_root_ptr = beginning_tree( ); + do + play(taxonomy_root_ptr); + while (inquire("Shall we play again?")); + + cout << "Thank you for teaching me a thing or two." << endl; + return EXIT_SUCCESS; +} + +void ask_and_move(binary_tree_node*& current_ptr) +// Library facilities used: bintree.h, string, useful.h +{ + cout << current_ptr->data( ); + if (inquire(" Please answer:")) + current_ptr = current_ptr->left( ); + else + current_ptr = current_ptr->right( ); +} + +binary_tree_node* beginning_tree( ) +// Library facilities used: bintree.h, string +{ + binary_tree_node *root_ptr; + binary_tree_node *child_ptr; + + const string root_question("Are you a mammal?"); + const string left_question("Are you bigger than a cat?"); + const string right_question("Do you live underwater?"); + const string animal1("Kangaroo"); + const string animal2("Mouse"); + const string animal3("Trout"); + const string animal4("Robin"); + + // Create the root node with the question “Are you a mammal?” + root_ptr = new binary_tree_node(root_question); + + // Create and attach the left subtree. + child_ptr = new binary_tree_node(left_question); + child_ptr->set_left( new binary_tree_node(animal1) ); + child_ptr->set_right( new binary_tree_node(animal2) ); + root_ptr->set_left(child_ptr); + + // Create and attach the right subtree. + child_ptr = new binary_tree_node(right_question); + child_ptr->set_left( new binary_tree_node(animal3) ); + child_ptr->set_right( new binary_tree_node(animal4) ); + root_ptr->set_right(child_ptr); + + return root_ptr; +} + +void instruct( ) +// Library facilities used: iostream +{ + cout << "Let's play!" << endl; + cout << "You pretend to be an animal, and I try to guess what you are.\n"; +} + +void learn(binary_tree_node*& leaf_ptr) +// Library facilities used: bintree.h, iostream, string, useful.h +{ + string guess_animal; // The animal that was just guessed + string correct_animal; // The animal that the user was thinking of + string new_question; // A question to distinguish the two animals + + // Set strings for the guessed animal, correct animal and a new question. + guess_animal = leaf_ptr->data( ); + cout << "I give up. What are you? " << endl; + getline(cin, correct_animal); + cout << "Please type a yes/no question that will distinguish a" << endl; + cout << correct_animal << " from a " << guess_animal << "." << endl; + cout << "Your question: " << endl; + getline(cin, new_question); + + // Put the new question in the current node, and add two new children. + leaf_ptr->set_data(new_question); + cout << "As a " << correct_animal << ", " << new_question << endl; + if (inquire("Please answer")) + { + leaf_ptr->set_left( new binary_tree_node (correct_animal) ); + leaf_ptr->set_right( new binary_tree_node (guess_animal) ); + } + else + { + leaf_ptr->set_left( new binary_tree_node (guess_animal) ); + leaf_ptr->set_right( new binary_tree_node (correct_animal) ); + } +} + +void play(binary_tree_node* current_ptr) +// Library facilities used: bintree.h, iostream, string, useful.h +{ + cout << "Think of an animal, then press the return key."; + eat_line( ); + + while (!current_ptr->is_leaf( )) + ask_and_move(current_ptr); + + cout << ("My guess is " + current_ptr->data( ) + ". "); + if (!inquire("Am I right?")) + learn(current_ptr); + else + cout << "I knew it all along!" << endl; +} + diff --git a/chapter10/bag6.h b/chapter10/bag6.h new file mode 100644 index 0000000..8959658 --- /dev/null +++ b/chapter10/bag6.h @@ -0,0 +1,94 @@ +// FILE: bag6.h (part of the namespace main_savitch_10) +// TEMPLATE CLASS PROVIDED: bag +// (a container template class for a collection of items) +// +// TYPEDEFS for the bag class: +// bag::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, a copy constructor, an assignment operator, and a +// less-than operator forming a strict weak ordering. +// +// bag::size_type +// 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 Item& 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 Item& 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 Item& 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 Item& 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, insert, operator +=, operator +, and +// the assignment operator. + +#ifndef BAG6_H +#define BAG6_H +#include // Provides NULL and size_t +#include "bintree.h" // Provides binary_tree_node and related functions + +namespace main_savitch_10 +{ + template + class bag + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + // CONSTRUCTORS and DESTRUCTOR + bag( ); + bag(const bag& source); + ~bag( ); + // MODIFICATION functions + size_type erase(const Item& target); + bool erase_one(const Item& target); + void insert(const Item& entry); + void operator +=(const bag& addend); + void operator =(const bag& source); + // CONSTANT functions + size_type size( ) const; + size_type count(const Item& target) const; + private: + binary_tree_node *root_ptr; // Root pointer of binary search tree + void insert_all(binary_tree_node* addroot_ptr); + }; + + // NONMEMBER functions for the bag template class + template + bag operator +(const bag& b1, const bag& b2); +} + +#include "bag6.template" // Include the implementation. +#endif diff --git a/chapter10/bintree.h b/chapter10/bintree.h new file mode 100644 index 0000000..386fcd4 --- /dev/null +++ b/chapter10/bintree.h @@ -0,0 +1,169 @@ +// FILE: bintree.h (part of the namespace main_savitch_10) +// PROVIDES: A template class for a node in a binary tree and functions for +// manipulating binary trees. The template parameter is the type of data in +// each node. +// +// TYPEDEF for the binary_tree_node template class: +// Each node of the tree contains a piece of data and pointers to its +// children. The type of the data (binary_tree_node::value_type) is +// the Item type from the template parameter. The type may be any of the C++ +// built-in types (int, char, etc.), or a class with a default constructor, +// and an assignment operator. +// +// CONSTRUCTOR for the binary_tree_node class: +// binary_tree_node( +// const item& init_data = Item( ), +// binary_tree_node* init_left = NULL, +// binary_tree_node* init_right = NULL +// ) +// Postcondition: The new node has its data equal to init_data, +// and it's child pointers equal to init_left and init_right. +// +// MEMBER FUNCTIONS for the binary_tree_node class: +// const item& data( ) const <----- const version +// and +// Item& data( ) <----- non-const version +// Postcondition: The return value is a reference to the data from +// this binary_tree_node. +// +// const binary_tree_node* left( ) const <----- const version +// and +// binary_tree_node* left( ) <----- non-const version +// and +// const binary_tree_node* right( ) const <----- const version +// and +// binary_tree_node* right( ) <----- non-const version +// Postcondition: The return value is a pointer to the left or right child +// (which will be NULL if there is no child). +// +// void set_data(const Item& new_data) +// Postcondition: The binary_tree_node now contains the specified new data. +// +// void set_left(binary_tree_node* new_link) +// and +// void set_right(binary_tree_node* new_link) +// Postcondition: The binary_tree_node now contains the specified new link +// to a child. +// +// bool is_leaf( ) +// Postcondition: The return value is true if the node is a leaf; +// otherwise the return value is false. +// +// NON-MEMBER FUNCTIONS to maniplulate binary tree nodes: +// tempate +// void inorder(Process f, BTNode* node_ptr) +// Precondition: node_ptr is a pointer to a node in a binary tree (or +// node_ptr may be NULL to indicate the empty tree). +// Postcondition: If node_ptr is non-NULL, then the function f has been +// applied to the contents of *node_ptr and all of its descendants, using +// an in-order traversal. +// Note: BTNode may be a binary_tree_node or a const binary tree node. +// Process is the type of a function f that may be called with a single +// Item argument (using the Item type from the node). +// +// tempate +// void postorder(Process f, BTNode* node_ptr) +// Same as the in-order function, except with a post-order traversal. +// +// tempate +// void preorder(Process f, BTNode* node_ptr) +// Same as the in-order function, except with a pre-order traversal. +// +// template +// void print(const binary_tree_node* node_ptr, SizeType depth) +// Precondition: node_ptr is a pointer to a node in a binary tree (or +// node_ptr may be NULL to indicate the empty tree). If the pointer is +// not NULL, then depth is the depth of the node pointed to by node_ptr. +// Postcondition: If node_ptr is non-NULL, then the contents of *node_ptr +// and all its descendants have been written to cout with the << operator, +// using a backward in-order traversal. Each node is indented four times +// its depth. +// +// template +// void tree_clear(binary_tree_node*& root_ptr) +// Precondition: root_ptr is the root pointer of a binary tree (which may +// be NULL for the empty tree). +// Postcondition: All nodes at the root or below have been returned to the +// heap, and root_ptr has been set to NULL. +// +// template +// binary_tree_node* tree_copy(const binary_tree_node* root_ptr) +// Precondition: root_ptr is the root pointer of a binary tree (which may +// be NULL for the empty tree). +// Postcondition: A copy of the binary tree has been made, and the return +// value is a pointer to the root of this copy. +// +// template +// size_t tree_size(const binary_tree_node* node_ptr) +// Precondition: node_ptr is a pointer to a node in a binary tree (or +// node_ptr may be NULL to indicate the empty tree). +// Postcondition: The return value is the number of nodes in the tree. + +#ifndef BINTREE_H +#define BINTREE_H +#include // Provides NULL and size_t + +namespace main_savitch_10 +{ + + template + class binary_tree_node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + binary_tree_node( + const Item& init_data = Item( ), + binary_tree_node* init_left = NULL, + binary_tree_node* init_right = NULL + ) + { + data_field = init_data; + left_field = init_left; + right_field = init_right; + } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + binary_tree_node* left( ) { return left_field; } + binary_tree_node* right( ) { return right_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_left(binary_tree_node* new_left) { left_field = new_left; } + void set_right(binary_tree_node* new_right) { right_field = new_right; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const binary_tree_node* left( ) const { return left_field; } + const binary_tree_node* right( ) const { return right_field; } + bool is_leaf( ) const + { return (left_field == NULL) && (right_field == NULL); } + private: + Item data_field; + binary_tree_node *left_field; + binary_tree_node *right_field; + }; + + // NON-MEMBER FUNCTIONS for the binary_tree_node: + template + void inorder(Process f, BTNode* node_ptr); + + template + void preorder(Process f, BTNode* node_ptr); + + template + void postorder(Process f, BTNode* node_ptr); + + template + void print(binary_tree_node* node_ptr, SizeType depth); + + template + void tree_clear(binary_tree_node*& root_ptr); + + template + binary_tree_node* tree_copy(const binary_tree_node* root_ptr); + + template + std::size_t tree_size(const binary_tree_node* node_ptr); +} + +#include "bintree.template" +#endif diff --git a/chapter10/bintree.template b/chapter10/bintree.template new file mode 100644 index 0000000..815aea5 --- /dev/null +++ b/chapter10/bintree.template @@ -0,0 +1,100 @@ +// FILE: bintree.template +// IMPLEMENTS: The binary_tree node class (see bintree.h for documentation). +#include // Provides assert +#include // Provides NULL, std::size_t +#include // Provides std::setw +#include // Provides std::cout + +namespace main_savitch_10 +{ + template + void inorder(Process f, BTNode* node_ptr) + // Library facilities used: cstdlib + { + if (node_ptr != NULL) + { + inorder(f, node_ptr->left( )); + f( node_ptr->data( ) ); + inorder(f, node_ptr->right( )); + } + } + + template + void postorder(Process f, BTNode* node_ptr) + // Library facilities used: cstdlib + { + if (node_ptr != NULL) + { + postorder(f, node_ptr->left( )); + postorder(f, node_ptr->right( )); + f(node_ptr->data( )); + } + } + + template + void preorder(Process f, BTNode* node_ptr) + // Library facilities used: cstdlib + { + if (node_ptr != NULL) + { + f( node_ptr->data( ) ); + preorder(f, node_ptr->left( )); + preorder(f, node_ptr->right( )); + } + } + + template + void print(binary_tree_node* node_ptr, SizeType depth) + // Library facilities used: iomanip, iostream, stdlib + { + if (node_ptr != NULL) + { + print(node_ptr->right( ), depth+1); + std::cout << std::setw(4*depth) << ""; // Indent 4*depth spaces. + std::cout << node_ptr->data( ) << std::endl; + print(node_ptr->left( ), depth+1); + } + } + + template + void tree_clear(binary_tree_node*& root_ptr) + // Library facilities used: cstdlib + { + if (root_ptr != NULL) + { + tree_clear( root_ptr->left( ) ); + tree_clear( root_ptr->right( ) ); + delete root_ptr; + root_ptr = NULL; + } + } + + template + binary_tree_node* tree_copy(const binary_tree_node* root_ptr) + // Library facilities used: cstdlib + { + binary_tree_node *l_ptr; + binary_tree_node *r_ptr; + + if (root_ptr == NULL) + return NULL; + else + { + l_ptr = tree_copy( root_ptr->left( ) ); + r_ptr = tree_copy( root_ptr->right( ) ); + return + new binary_tree_node( root_ptr->data( ), l_ptr, r_ptr); + } + } + + template + size_t tree_size(const binary_tree_node* node_ptr) + // Library facilities used: cstdlib + { + if (node_ptr == NULL) + return 0; + else + return + 1 + tree_size(node_ptr->left( )) + tree_size(node_ptr->right( )); + } +} diff --git a/chapter10/bt_class.h b/chapter10/bt_class.h new file mode 100644 index 0000000..e35b3a2 --- /dev/null +++ b/chapter10/bt_class.h @@ -0,0 +1,126 @@ +// FILE: bt_class.h +// For Project 2 in Chapter 10 of "Data Structures and Other Objects Using C++" +// TEMPLATE CLASS PROVIDED: binary_tree (a binary tree where each node has +// an item) The template parameter, Item, is the data type of the items in the +// tree's nodes. It may be any of the C++ built-in types (int, char, etc.), +// or a class with a default constructor, a copy constructor and an assignment +// operator. +// +// NOTE: Each non-empty tree always has a "current node." The location of +// the current node is controlled by three member functions: shift_up, +// shift_to_root, shift_left, and shift_right. +// +// CONSTRUCTOR for the binary_tree template class: +// binary_tree( ) +// Postcondition: The binary tree has been initialized as an empty tree +// (with no nodes). +// +// MODIFICATION MEMBER FUNCTIONS for the binary_tree template class: +// void create_first_node(const Item& entry) +// Precondition: size( ) is zero. +// Postcondition: The tree now has one node (a root node), containing the +// specified entry. This new root node is the "current node." +// +// void shift_to_root( ) +// Precondition: size( ) > 0. +// Postcondition: The "current node" is now the root of the tree. +// +// void shift_up( ) +// Precondition: has_parent( ) returns true. +// Postcondition: The "current node" has been shifted up to the parent of +// the old current node. +// +// void shift_left( ) +// Precondition: has_left_child( ) returns true. +// Postcondition: The "current node" been shifted down to the left child +// of the original current node. +// +// void shift_right( ) +// Precondition: has_right_child( ) returns true. +// Postcondition: The "current node" been shifted down to the right child +// of the original current node. +// +// void change(const Item& new_entry) +// Precondition: size( ) > 0. +// Postcondition: The data at the "current node" has been changed to the +// new entry. +// +// void add_left(const Item& entry) +// Precondition: size( ) > 0, and has_left_child( ) returns false. +// Postcondition: A left child has been added to the "current node," +// with the given entry. +// +// void add_right(const Item& entry) +// Precondition: size( ) > 0, and has_right_child( ) returns false. +// Postcondition: A right child has been added to the "current node," +// with the given entry. +// +// CONSTANT MEMBER FUNCTIONS for the binary_tree template class: +// size_t size( ) const +// Postcondition: The return value is the number of nodes in the tree. +// +// Item retrieve( ) const +// Precondition: size( ) > 0. +// Postcondition: The return value is the data from the "current node." +// +// bool has_parent( ) const +// Postcondition: Returns true if size( ) > 0, and the "current node" +// has a parent. +// +// bool has_left_child( ) const +// Postcondition: Returns true if size( ) > 0, and the "current node" +// has a left child. +// +// bool has_right_child( ) const +// Postcondition: Returns true if size( ) > 0, and the "current node" +// has a right child. +// +// VALUE SEMANTICS for the binary_tree template class: +// Assignments and the copy constructor may be used with binary_tree objects. +// +// DYNAMIC MEMORY USAGE by the binary_tree template class: +// If there is insufficient dynamic memory, then the following functions +// throw bad_alloc: +// create_first_node, add_left, add_right, the copy constructor, and the +// assignment operator. + +#ifndef BT_CLASS_H +#define BT_CLASS_H +#include // Provides size_t +#include "bintree.h" // Provides binary_tree_node template class + +namespace main_savitch_chapter10 +{ + template + class binary_tree + { + public: + // CONSTRUCTORS and DESTRUCTOR + binary_tree( ); + binary_tree(const binary_tree& source); + ~binary_tree( ); + // MODIFICATION MEMBER FUNCTIONS + void create_first_node(const Item& entry); + void shift_to_root( ); + void shift_up( ); + void shift_left( ); + void shift_right( ); + void change(const Item& new_entry); + void add_left(const Item& entry); + void add_right(const Item& entry); + // CONSTANT MEMBER FUNCTIONS + std::size_t size( ) const; + Item retrieve( ) const; + bool has_parent( ) const; + bool has_left_child( ) const; + bool has_right_child( ) const; + private: + // Private member variables to be specified by the student. + // My own implementation has a root pointer and a pointer to + // the "current" node, plus a member variable to keep track of + // the number of nodes in this tree. + }; +} + +#include "bt_class.template" // To be written by the student +#endif diff --git a/chapter10/useful.cxx b/chapter10/useful.cxx new file mode 100644 index 0000000..694016b --- /dev/null +++ b/chapter10/useful.cxx @@ -0,0 +1,80 @@ +// FILE: useful.cxx +// IMPLEMENTS: A toolkit of functions (See useful.h for documentation.) + +#include // Provides assert +#include // Provides toupper +#include // Provides rand, RAND_MAX +#include // Provides cout, cin, get +#include "useful.h" + +void display(double x) +// Library facilities used: iostream.h, stdlib.h +{ + const char STAR = '*'; + const char BLANK = ' '; + const char VERTICAL_BAR = '|'; + const int LIMIT = 39; + int i; + + if (x < -LIMIT) + x = -LIMIT; + else if (x > LIMIT) + x = LIMIT; + + for (i = -LIMIT; i < 0; i++) + { + if (i >= x) + cout << STAR; + else + cout << BLANK; + } + cout << VERTICAL_BAR; + for (i = 1; i <= LIMIT; i++) + { + if (i <= x) + cout << STAR; + else + cout << BLANK; + } + cout << endl; +} + +double random_fraction( ) +// Library facilities used: stdlib.h +{ + return rand( ) / double(RAND_MAX); +} + +double random_real(double low, double high) +// Library facilities used: assert.h +{ + assert(low <= high); + return low + random_fraction( ) * (high - low); +} + +void eat_line( ) +// Library facilities used: iostream.h +// +{ + char next; + + do + cin.get(next); + while (next != '\n'); +} + +bool inquire(const char query[ ]) +// Library facilities used: ctype.h, iostream.h +{ + char answer; + do + { + cout << query << " [Yes or No]" << endl; + cin >> answer; + answer = toupper(answer); + eat_line( ); + } + while ((answer != 'Y') && (answer != 'N')); + return (answer == 'Y'); +} + diff --git a/chapter10/useful.h b/chapter10/useful.h new file mode 100644 index 0000000..25dd03e --- /dev/null +++ b/chapter10/useful.h @@ -0,0 +1,46 @@ +// FILE: useful.h +// PROVIDES: A toolkit of useful functions for random numbers and displays. +// Note that these are in the global namespace. +// +// FUNCTIONS in the toolkit: +// double random_fraction( ) +// Postcondition: The return value is a random real number in the closed +// interval [0..1] (including the endpoints). +// +// double random_real(double low, double high) +// Precondition: low <= high. +// Postcondition: The return value is a random real number in the closed +// interval [low..high] (including the endpoints). +// +// void display(double x) +// Postcondition: The function has written one line of output to the +// standard ouput, with a vertical bar in the middle. If x is positive, +// then approximately x stars are printed to the right of the vertical +// bar. If x is negative, then approximately -x stars are printed to the +// left of the vertical bar. If the absolute value of x is more than +// 39, then only 39 stars are printed. +// Examples: +// display(8) prints: |******** +// display(-4) prints: ****| +// +// void eat_line( ) +// Postcondition: Up to next newline has been read and discarded from cin. +// +// bool inquire(const char query[ ]) +// Precondition: query is a null-terminated string of characters. +// Postcondition: query has been printed, and a one-line response read +// from the user. The function returns true if the user's response begins +// with 'Y' or 'y', and returns false if the user's response begins with +// 'N' or 'n'. (If the response begins with some other letter, then the +// query is repeated.) + +#ifndef USEFUL_H // Prevent duplicate definition +#define USEFUL_H + + double random_fraction( ); + double random_real(double low, double high); + void display(double x); + void eat_line( ); + bool inquire(const char query[ ]); + +#endif diff --git a/chapter11/set.h b/chapter11/set.h new file mode 100644 index 0000000..f65cacd --- /dev/null +++ b/chapter11/set.h @@ -0,0 +1,94 @@ +// FILE: set.h (part of the namespace main_savitch_11) +// TEMPLATE CLASS PROVIDED: set +// (a container template class for a set of items) +// +// TYPEDEFS for the set class: +// set::value_type +// set::value_type is the data type of the items in the set. 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 +// less-than operator forming a strict weak ordering. +// +// CONSTRUCTOR for the set class: +// set( ) +// Postcondition: The set is empty. +// +// MODIFICATION MEMBER FUNCTIONS for the set class: +// void clear( ) +// Postcondition: The set is empty. +// +// bool insert(const Item& entry) +// Postcondition: If an equal entry was already in the set, the set is +// unchanged and the return value is false. Otherwise, entry was added +// to the set and the return value is true. This is slightly different than +// the C++ Standard Library set (see Appendix H). +// +// size_t erase(const Item& target) +// Postcondition: If target was in the set, then it has been removed from +// the set and the return value is 1. Otherwise the set is unchanged and the +// return value is zero. +// +// CONSTANT MEMBER FUNCTIONS for the Set class: +// size_t count(const Item& target) const +// Postcondition: Returns the number of items equal to the target +// (either 0 or 1 for a set). +// +// bool empty( ) const +// Postcondition: Returns true if the set is empty; otherwise returns false. +// +// VALUE SEMANTICS for the set class: +// Assignments and the copy constructor may be used with set objects. +// +// DYNAMIC MEMORY USAGE by the set class: +// If there is insufficient dynamic memory, then the following functions throw +// bad_alloc: +// The constructors, insert, and the assignment operator. + +#ifndef MAIN_SAVITCH_SET_H +#define MAIN_SAVITCH_SET_H +#include // Provides size_t + +namespace main_savitch_11 +{ + template + class set + { + public: + // TYPEDEFS + typedef Item value_type; + // CONSTRUCTORS and DESTRUCTOR + set( ); + set(const set& source); + ~set( ) { clear( ); } + // MODIFICATION MEMBER FUNCTIONS + void operator =(const set& source); + void clear( ); + bool insert(const Item& entry); + std::size_t erase(const Item& target); + // CONSTANT MEMBER FUNCTIONS + std::size_t count(const Item& target) const; + bool empty( ) const { return (data_count == 0); } + // SUGGESTED FUNCTION FOR DEBUGGING + void print(int indent) const; + private: + // MEMBER CONSTANTS + static const std::size_t MINIMUM = 200; + static const std::size_t MAXIMUM = 2 * MINIMUM; + // MEMBER VARIABLES + std::size_t data_count; + Item data[MAXIMUM+1]; + std::size_t child_count; + set *subset[MAXIMUM+2]; + // HELPER MEMBER FUNCTIONS + bool is_leaf( ) const { return (child_count == 0); } + bool loose_insert(const Item& entry); + bool loose_erase(const Item& target); + void remove_biggest(Item& removed_entry); + void fix_excess(std::size_t i); + void fix_shortage(std::size_t i); + // NOTE: The implementor may want to have additional helper functions + }; +} +#include "set.template" // Include the implementation. + +#endif diff --git a/chapter12/node2.h b/chapter12/node2.h new file mode 100644 index 0000000..9b0df72 --- /dev/null +++ b/chapter12/node2.h @@ -0,0 +1,270 @@ +// FILE: node2.h (part of the namespace main_savitch_6B) +// PROVIDES: A template class for a node in a linked list, and list manipulation +// functions. The template parameter is the type of the data in each node. +// This file also defines a template class: node_iterator. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* parameter) that attaches the iterator +// to the specified node in a linked list, and (2) a default constructor that +// creates a special iterator that marks the position that is beyond the end of a +// linked list. There is also a const_node_iterator for use with +// const node* . +// +// TYPEDEF for the node template class: +// Each node of the list contains a piece of data and a pointer to the +// next node. The type of the data (node::value_type) is the Item type +// from the template parameter. The type may be any of the built-in C++ classes +// (int, char, ...) or a class with a default constructor, an assignment +// operator, and a test for equality (x == y). +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expression node::value_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the node class: +// node( +// const Item& init_data = Item(), +// 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 Item. 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 about two versions of some functions: +// The data function returns a reference to the data field of a node and +// the link function returns a copy of the link field of a node. +// Each of these functions comes in two versions: a const version and a +// non-const version. If the function is activated by a const node, then the +// compiler choses the const version (and the return value is const). +// If the function is activated by a non-const node, then the compiler choses +// the non-const version (and the return value will be non-const). +// EXAMPLES: +// const node *c; +// c->link( ) activates the const version of link returning const node* +// c->data( ) activates the const version of data returning const Item& +// c->data( ) = 42; ... is forbidden +// node *p; +// p->link( ) activates the non-const version of link returning node* +// p->data( ) activates the non-const version of data returning Item& +// p->data( ) = 42; ... actually changes the data in p's node +// +// MEMBER FUNCTIONS for the node class: +// const Item& data( ) const <----- const version +// and +// Item& data( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is a reference to the data from this node. +// +// const node* link( ) const <----- const version +// and +// 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. +// +// void set_data(const Item& 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. +// +// FUNCTIONS in the linked list toolkit: +// template +// 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. +// +// template +// 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. +// +// template +// void list_head_insert(node*& head_ptr, const Item& 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. +// +// template +// 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. +// +// template +// void list_insert(node* previous_ptr, const Item& 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. +// +// template +// 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. +// +// template +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list, and +// position > 0. +// Postcondition: The return value is a pointer that 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. +// +// template +// 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. +// +// template +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The return value is a pointer that points to the first +// node containing the specified target in its data member. If there is no +// such node, the null pointer is returned. +// +// 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. + +#ifndef MAIN_SAVITCH_NODE2_H +#define MAIN_SAVITCH_NODE2_H +#include // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + class node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + node(const Item& init_data=Item( ), node* init_link=NULL) + { data_field = init_data; link_field = init_link; } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + node* link( ) { return link_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_link(node* new_link) { link_field = new_link; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const node* link( ) const { return link_field; } + private: + Item data_field; + node *link_field; + }; + + // FUNCTIONS to manipulate a linked list: + template + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + NodePtr list_search(NodePtr head_ptr, const Item& target); + + // FORWARD ITERATORS to step through the nodes of a linked list + // A node_iterator of can change the underlying linked list through the + // * operator, so it may not be used with a const node. The + // node_const_iterator cannot change the underlying linked list + // through the * operator, so it may be used with a const node. + // WARNING: + // This classes use std::iterator as its base class; + // Older compilers that do not support the std::iterator class can + // delete everything after the word iterator in the second line: + + template + class node_iterator + : public std::iterator + { + public: + node_iterator(node* initial = NULL) + { current = initial; } + Item& operator *( ) const + { return current->data( ); } + node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + node_iterator operator ++(int) // Postfix ++ + { + node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const node_iterator other) const + { return current == other.current; } + bool operator !=(const node_iterator other) const + { return current != other.current; } + private: + node* current; + }; + + template + class const_node_iterator + : public std::iterator + { + public: + const_node_iterator(const node* initial = NULL) + { current = initial; } + const Item& operator *( ) const + { return current->data( ); } + const_node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + const_node_iterator operator ++(int) // Postfix ++ + { + const_node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const const_node_iterator other) const + { return current == other.current; } + bool operator !=(const const_node_iterator other) const + { return current != other.current; } + private: + const node* current; + }; + +} + +#include "node2.template" +#endif diff --git a/chapter12/node2.template b/chapter12/node2.template new file mode 100644 index 0000000..45c3470 --- /dev/null +++ b/chapter12/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template +// IMPLEMENTS: The functions of the node template class and the +// linked list toolkit (see node2.h for documentation). +// +// NOTE: +// Since node is a template class, this file is included in node2.h. +// Therefore, we should not put any using directives in this file. +// +// INVARIANT for the node class: +// The data of a node is stored in data_field, and the link in link_field. + +#include // Provides assert +#include // Provides NULL and size_t + +namespace main_savitch_6B +{ + template + void list_clear(node*& head_ptr) + // Library facilities used: cstdlib + { + while (head_ptr != NULL) + list_head_remove(head_ptr); + } + + template + 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 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( ); + } + } + + template + void list_head_insert(node*& head_ptr, const Item& entry) + { + head_ptr = new node(entry, head_ptr); + } + + template + void list_head_remove(node*& head_ptr) + { + node *remove_ptr; + + remove_ptr = head_ptr; + head_ptr = head_ptr->link( ); + delete remove_ptr; + } + + template + void list_insert(node* previous_ptr, const Item& entry) + { + node *insert_ptr; + + insert_ptr = new node(entry, previous_ptr->link( )); + previous_ptr->set_link(insert_ptr); + } + + template + std::size_t list_length(const node* head_ptr) + // Library facilities used: cstdlib + { + const node *cursor; + std::size_t answer; + + answer = 0; + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + ++answer; + + return answer; + } + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position) + // Library facilities used: cassert, cstdlib + { + NodePtr cursor; + SizeType i; + + assert(0 < position); + cursor = head_ptr; + for (i = 1; (i < position) && (cursor != NULL); ++i) + cursor = cursor->link( ); + return cursor; + } + + template + void list_remove(node* previous_ptr) + { + node *remove_ptr; + + remove_ptr = previous_ptr->link( ); + previous_ptr->set_link(remove_ptr->link( )); + delete remove_ptr; + } + + template + NodePtr list_search(NodePtr head_ptr, const Item& target) + // Library facilities used: cstdlib + { + NodePtr cursor; + + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + if (target == cursor->data( )) + return cursor; + return NULL; + } +} diff --git a/chapter12/search.cxx b/chapter12/search.cxx new file mode 100644 index 0000000..c5ff881 --- /dev/null +++ b/chapter12/search.cxx @@ -0,0 +1,79 @@ +// FILE: search.cxx +// Demonstration program for the binary search function + +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cin, cout +using namespace std; + +// PROTOTYPE for function used in demonstration program: +void search( + const int a[ ], + size_t first, + size_t size, + int target, + bool& found, + size_t& location +); + + +int main( ) +{ + const size_t MANY = 10; + int fibonacci[MANY] = { 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 }; + int target; + bool found; + size_t location; + + do + { + cout << "Please type an integer from 0 to 100: "; + cin >> target; + } + while ((target < 0) || (target > 100)); + search(fibonacci, 0, MANY, target, found, location); + + if (found) + cout << target << " is a Fibonacci number at [" + << location << "] in my array." << endl; + else + cout << target << " is not a Fibonacci number." << endl; + + return EXIT_SUCCESS; +} + +void search( + const int a[ ], + size_t first, + size_t size, + int target, + bool& found, + size_t& location +) +// Precondition: The array segment starting at a[first] and containing size +// elements is sorted from smallest to largest. +// Postcondition: The array segment starting at a[first] and containing size +// elements has been searched for the target. If the target was present, then +// found is true, and location is set so that target == a[location]; +// Otherwise, found is set to false. +// Library facilities used: stdlib.h (provides size_t). +{ + size_t middle; + + if (size == 0) + found = false; + else + { + middle = first + size/2; + if (target == a[middle]) + { + location = middle; + found = true; + } + else if (target < a[middle]) + // The target is less than a[middle], so search before the middle + search(a, first, size/2, target, found, location); + else + // The target must be greater than a[middle], so search after the middle + search(a, middle+1, (size-1)/2, target, found, location); + } +} diff --git a/chapter12/table1.h b/chapter12/table1.h new file mode 100644 index 0000000..180ede7 --- /dev/null +++ b/chapter12/table1.h @@ -0,0 +1,84 @@ +// FILE: table1.h (part of the namespace main_savitch_12A) +// TEMPLATE CLASS PROVIDED: table (a table of records with keys). +// This class is a container template class for a table of records. +// The template parameter, RecordType, is the data type of the records in the +// table. It may be any of the bulit-in C++ types (int, char, etc.), or a +// class with a default constructor, an assignment operator, and an integer +// member variable called key. +// +// MEMBER CONSTANT for the table class: +// static const size_type CAPACITY = ________ +// table::CAPACITY is the maximum number of records held by a table. +// +// CONSTRUCTOR for the table template class: +// table( ) +// Postcondition: The table has been initialized as an empty table. +// +// MODIFICATION MEMBER FUNCTIONS for the table class: +// void insert(const RecordType& entry) +// Precondition: entry.key >= 0. Also if entry.key is not already a key in +// the table, then the table has space for another record +// (i.e., size( ) < CAPACITY). +// Postcondition: If the table already had a record with a key equal to +// entry.key, then that record is replaced by entry. Otherwise, entry has +// been added as a new record of the table. +// +// void remove(int key) +// Postcondition: If a record was in the table with the specified key, then +// that record has been removed; otherwise the table is unchanged. +// +// CONSTANT MEMBER FUNCTIONS for the table class: +// bool is_present(const Item& target) const +// Postcondition: The return value is true if there is a record in the +// table with the specified key. Otherwise, the return value is false. +// +// void find(int key, bool& found, RecordType& result) const +// Postcondition: If a record is in the table with the specified key, then +// found is true and result is set to a copy of the record with that key. +// Otherwise found is false and the result contains garbage. +// +// size_type size( ) const +// Postcondition: Return value is the total number of records in the +// table. +// +// VALUE SEMANTICS for the table template class: +// Assignments and the copy constructor may be used with table objects. + +#ifndef TABLE1_H +#define TABLE1_H +#include // Provides size_t + +namespace main_savitch_12A +{ + template + class table + { + public: + // MEMBER CONSTANT -- See Appendix E if this fails to compile. + static const std::size_t CAPACITY = 811; + // CONSTRUCTOR + table( ); + // MODIFICATION MEMBER FUNCTIONS + void insert(const RecordType& entry); + void remove(int key); + // CONSTANT MEMBER FUNCTIONS + bool is_present(int key) const; + void find(int key, bool& found, RecordType& result) const; + std::size_t size( ) const { return used; } + private: + // MEMBER CONSTANTS -- These are used in the key field of special records. + static const int NEVER_USED = -1; + static const int PREVIOUSLY_USED = -2; + // MEMBER VARIABLES + RecordType data[CAPACITY]; + std::size_t used; + // HELPER FUNCTIONS + std::size_t hash(int key) const; + std::size_t next_index(std::size_t index) const; + void find_index(int key, bool& found, std::size_t& index) const; + bool never_used(std::size_t index) const; + bool is_vacant(std::size_t index) const; + }; +} +#include "table1.template" // Include the implementation. +#endif diff --git a/chapter12/table1.template b/chapter12/table1.template new file mode 100644 index 0000000..d7f8e8a --- /dev/null +++ b/chapter12/table1.template @@ -0,0 +1,144 @@ +// FILE: table1.template +// TEMPLATE CLASS IMPLEMENTED: table (see table1.h for documentation) +// INVARIANT for the table ADT: +// 1. The number of records in the table is in the member variable used. +// 2. The actual records of the table are stored in the array data, with +// a maximum of CAPACITY entries. Each used spot in the array has a +// non-negative key. Any unused record in the array has a key field of +// NEVER_USED (if it has never been used) or PREVIOUSLY_USED (if it once +// was used, but is now vacant). + +#include // Provides assert +#include // Provides size_t + +namespace main_savitch_12A +{ + template + const std::size_t table::CAPACITY; + + template + const int table::NEVER_USED; + + template + const int table::PREVIOUSLY_USED; + + template + table::table( ) + { + std::size_t i; + + used = 0; + for (i = 0; i < CAPACITY; ++i) + data[i].key = NEVER_USED; // Indicates a spot that's never been used. + } + + template + void table::insert(const RecordType& entry) + // Library facilities used: cassert + { + bool already_present; // True if entry.key is already in the table + std::size_t index; // data[index] is location for the new entry + + assert(entry.key >= 0); + + // Set index so that data[index] is the spot to place the new entry. + find_index(entry.key, already_present, index); + + // If the key wasn't already there, then find the location for the new entry. + if (!already_present) + { + assert(size( ) < CAPACITY); + index = hash(entry.key); + while (!is_vacant(index)) + index = next_index(index); + ++used; + } + + data[index] = entry; + } + + template + void table::remove(int key) + // Library facilities used: cassert + { + bool found; // True if key occurs somewhere in the table + std::size_t index; // Spot where data[index].key == key + + assert(key >= 0); + + find_index(key, found, index); + if (found) + { // The key was found, so remove this record and reduce used by 1. + data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use. + --used; + } + } + + template + bool table::is_present(int key) const + // Library facilities used: assert.h + { + bool found; + std::size_t index; + + assert(key >= 0); + + find_index(key, found, index); + return found; + } + + template + void table::find(int key, bool& found, RecordType& result) const + // Library facilities used: cassert.h + { + std::size_t index; + + assert(key >= 0); + + find_index(key, found, index); + if (found) + result = data[index]; + } + + template + inline std::size_t table::hash(int key) const + { + return (key % CAPACITY); + } + + template + inline std::size_t table::next_index(std::size_t index) const + // Library facilities used: cstdlib + { + return ((index+1) % CAPACITY); + } + + template + void table::find_index(int key, bool& found, std::size_t& i) const + // Library facilities used: cstdlib + { + std::size_t count; // Number of entries that have been examined + + count = 0; + i = hash(key); + while((count < CAPACITY) && (data[i].key != NEVER_USED) && (data[i].key != key)) + { + ++count; + i = next_index(i); + } + found = (data[i].key == key); + } + + template + inline bool table::never_used(std::size_t index) const + { + return (data[index].key == NEVER_USED); + } + + template + inline bool table::is_vacant(std::size_t index) const + { + return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED); + } +} + diff --git a/chapter12/table2.h b/chapter12/table2.h new file mode 100644 index 0000000..b249990 --- /dev/null +++ b/chapter12/table2.h @@ -0,0 +1,82 @@ +// FILE: table2.h +// TEMPLATE CLASS PROVIDED: Table +// This class is a container template class for a Table of records. +// The template parameter, RecordType, is the data type of the records in the +// Table. It may any type with a default constructor, a copy constructor, +// an assignment operator, and an integer member variable called key. +// +// CONSTRUCTOR for the Table template class: +// Table( ) +// Postcondition: The Table has been initialized as an empty Table. +// +// MODIFICATION MEMBER FUNCTIONS for the Table class: +// void insert(const RecordType& entry) +// Precondition: entry.key >= 0. Also if entry.key is not already a key in +// the table, then the Table has space for another record +// (i.e., size( ) < CAPACITY). +// Postcondition: If the table already had a record with a key equal to +// entry.key, then that record is replaced by entry. Otherwise, entry has +// been added as a new record of the Table. +// +// void remove(int key) +// Postcondition: If a record was in the Table with the specified key, then +// that record has been removed; otherwise the table is unchanged. +// +// CONSTANT MEMBER FUNCTIONS for the Table class: +// bool is_present(const Item& target) const +// Postcondition: The return value is true if there is a record in the +// Table with the specified key. Otherwise, the return value is false. +// +// void find(int key, bool& found, RecordType& result) const +// Postcondition: If a record is in the Table with the specified key, then +// found is true and result is set to a copy of the record with that key. +// Otherwise found is false and the result contains garbage. +// +// size_t size( ) const +// Postcondition: Return value is the total number of records in the +// Table. +// +// VALUE SEMANTICS for the Table template class: +// Assignments and the copy constructor may be used with Table objects. +// +// DYNAMIC MEMORY USAGE by the Table template class: +// If there is insufficient dynamic memory, then the following functions +// can call new_handler: the copy constructor, insert, the assignment +// operator. + +#ifndef TABLE2_H +#define TABLE2_H +#include // Provides size_t +#include "node2.h" // Provides the node type, from Figure 6.5 on page 306 + +namespace main_savitch_12B +{ + template + class table + { + public: + // MEMBER CONSTANT -- See Appendix E if this fails to compile. + static const std::size_t TABLE_SIZE = 811; + // CONSTRUCTORS AND DESTRUCTOR + table( ); + table(const table& source); + ~table( ); + // MODIFICATION MEMBER FUNCTIONS + void insert(const RecordType& entry); + void remove(int key); + void operator =(const table& source); + // CONSTANT MEMBER FUNCTIONS + void find(int key, bool& found, RecordType& result) const; + bool is_present(int key) const; + std::size_t size( ) const { return total_records; } + private: + main_savitch_6B::node *data[TABLE_SIZE]; + std::size_t total_records; + // HELPER MEMBER FUNCTION + std::size_t hash(int key) const; + }; +} + +#include "table2.template" // Include the implementation + +#endif diff --git a/chapter12/table2.template b/chapter12/table2.template new file mode 100644 index 0000000..a74be98 --- /dev/null +++ b/chapter12/table2.template @@ -0,0 +1 @@ +// To be written by the student. diff --git a/chapter12/testtab1.cxx b/chapter12/testtab1.cxx new file mode 100644 index 0000000..a1b7e13 --- /dev/null +++ b/chapter12/testtab1.cxx @@ -0,0 +1,130 @@ +// FILE: testtab1.cxx +// An interactive test program for the first Table ADT. + +#include // Provides toupper +#include // Provides EXIT_SUCCESS and size_t +#include // Provides cin, cout +#include "table1.h" // Provides the Table class +using namespace std; +using namespace main_savitch_12A; + +// Struct definition for the test_record_type, which has a key and a double. +struct test_record_type +{ + int key; + double data; +}; + +// 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. + +test_record_type get_record( ); +// Postcondition: The user has been prompted to enter data for a record. The +// key has been read, echoed to the screen, and returned by the function. + +int get_key( ); +// Postcondition: The user has been prompted to enter a key for a record. The +// items have been read, echoed to the screen, and returned by the function. + + +int main( ) +{ + table test; // A table that we'll perform tests on + char choice; // A command character entered by the user + bool found; // Value returned by find function + test_record_type result; // Value returned by find function + + cout << "I have initialized an empty table. Each record in the table\n"; + cout << "has an integer key and a real number as data." << endl; + + do + { + print_menu( ); + choice = toupper(get_user_command( )); + switch (choice) + { + case 'S': cout << "The table size is " << test.size( ) << endl; + break; + case 'I': test.insert(get_record( )); + cout << "The record has been inserted." << endl; + break; + case 'R': test.remove(get_key( )); + cout << "Remove has been called with that key." << endl; + break; + case '?': if (test.is_present(get_key( ))) + cout << "That key is present." << endl; + else + cout << "That key is not present." << endl; + break; + case 'F': test.find(get_key( ), found, result); + if (found) + cout << "The key's data is: " << result.data << endl; + else + cout << "That key is not present." << endl; + break; + case 'Q': cout << "Ridicule is the best test of truth." << endl; + break; + default: cout << choice << " is invalid. Sorry." << 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 << " S Print the result from the size( ) function" << endl; + cout << " I Insert a new record with the insert(...) function" << endl; + cout << " R Remove a record with the remove(...) function" << endl; + cout << " ? Check whether a particular key is present" << endl; + cout << " F Find the data associated with a specified key" << endl; + cout << " Q Quit this test program" << endl; +} + +char get_user_command( ) +// Library facilities used: iostream.h +{ + char command; + + cout << "Enter choice: "; + cin >> command; // Input of characters skips blanks and newline character + + return command; +} + +test_record_type get_record( ) +// Library facilities used: iostream.h +{ + test_record_type result; + + cout << "Please enter a real number for a record's data: "; + cin >> result.data; + cout << result.data << " has been read." << endl; + result.key = get_key( ); + return result; +} + +int get_key( ) +// Library facilities used: iostream.h +{ + int key; + + do + { + cout << "Please enter a non-negative integer for a key: "; + cin >> key; + } + while (key < 0); + cout << key << " has been read." << endl; + return key; +} diff --git a/chapter12/testtab2.cxx b/chapter12/testtab2.cxx new file mode 100644 index 0000000..5e66b6a --- /dev/null +++ b/chapter12/testtab2.cxx @@ -0,0 +1,130 @@ +// FILE: testtab2.cxx +// An interactive test program for the second table ADT. + +#include // Provides toupper +#include // Provides EXIT_SUCCESS and size_t +#include // Provides cin, cout +#include "table2.h" // Provides the table class +using namespace std; +using namespace main_savitch_12B; + +// Struct definition for the test_record_type, which has a key and a double. +struct test_record_type +{ + int key; + double data; +}; + +// 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. + +test_record_type get_record( ); +// Postcondition: The user has been prompted to enter data for a record. The +// key has been read, echoed to the screen, and returned by the function. + +int get_key( ); +// Postcondition: The user has been prompted to enter a key for a record. The +// items have been read, echoed to the screen, and returned by the function. + + +int main( ) +{ + table test; // A table that we'll perform tests on + char choice; // A command character entered by the user + bool found; // Value returned by find function + test_record_type result; // Value returned by find function + + cout << "I have initialized an empty table. Each record in the table\n"; + cout << "has an integer key and a real number as data." << endl; + + do + { + print_menu( ); + choice = toupper(get_user_command( )); + switch (choice) + { + case 'S': cout << "The table size is " << test.size( ) << endl; + break; + case 'I': test.insert(get_record( )); + cout << "The record has been inserted." << endl; + break; + case 'R': test.remove(get_key( )); + cout << "Remove has been called with that key." << endl; + break; + case '?': if (test.is_present(get_key( ))) + cout << "That key is present." << endl; + else + cout << "That key is not present." << endl; + break; + case 'F': test.find(get_key( ), found, result); + if (found) + cout << "The key's data is: " << result.data << endl; + else + cout << "That key is not present." << endl; + break; + case 'Q': cout << "Ridicule is the best test of truth." << endl; + break; + default: cout << choice << " is invalid. Sorry." << 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 << " S Print the result from the size( ) function" << endl; + cout << " I Insert a new record with the insert(...) function" << endl; + cout << " R Remove a record with the remove(...) function" << endl; + cout << " ? Check whether a particular key is present" << endl; + cout << " F Find the data associated with a specified key" << endl; + cout << " Q Quit this test program" << endl; +} + +char get_user_command( ) +// Library facilities used: iostream.h +{ + char command; + + cout << "Enter choice: "; + cin >> command; // Input of characters skips blanks and newline character + + return command; +} + +test_record_type get_record( ) +// Library facilities used: iostream.h +{ + test_record_type result; + + cout << "Please enter a real number for a record's data: "; + cin >> result.data; + cout << result.data << " has been read." << endl; + result.key = get_key( ); + return result; +} + +int get_key( ) +// Library facilities used: iostream.h +{ + int key; + + do + { + cout << "Please enter a non-negative integer for a key: "; + cin >> key; + } + while (key < 0); + cout << key << " has been read." << endl; + return key; +} diff --git a/chapter13/heapsort.cxx b/chapter13/heapsort.cxx new file mode 100644 index 0000000..7c44599 --- /dev/null +++ b/chapter13/heapsort.cxx @@ -0,0 +1,166 @@ +// FILE: heapsort.cxx +// An interactive test program for the selectionsort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void heapsort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. + +size_t parent(size_t k); +// Precondition: k> 0. +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the parent of node k, using +// the formula from rule 3 on page 624. + +size_t left_child(size_t k); +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the left child of node k, +// using the formula from rule 2 on page 624. + +size_t right_child(size_t k); +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the right child of node k, +// using the formula from rule 2 on page 624. + +void make_heap(int data[ ], size_t n); +// Precondition: data is an array with at least n elements. +// Postcondition: The elements of data have been rearranged so that the +// complete binary tree represented by this array is a heap. + +void reheapify_down(int data[ ], size_t n); +// Precondition: n > 0, and data is an array with at least n elements. These elements form a +// heap **except** that data[0] may be in an incorrect location. +// location. +// Postcondition: The data values have been rearranged so that the first n elements of data now +// form a heap. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + ++number_of_elements; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + heapsort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; ++i) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void heapsort(int data[ ], size_t n) +// Library facilities used: algorithm, cstdlib +{ + size_t unsorted; + + make_heap(data, n); + + unsorted = n; + + while (unsorted > 1) + { + --unsorted; + swap(data[0], data[unsorted]); + reheapify_down(data, unsorted); + } +} + +size_t parent(size_t k) +// Library facilities used: cstdlib +{ + return (k-1)/2; +} + +size_t left_child(size_t k) +// Library facilities used: cstdlib +{ + return 2*k + 1; +} + +size_t right_child(size_t k) +// Library facilities used: cstdlib +{ + return 2*k + 2; +} + +void make_heap(int data[ ], size_t n) +// Library facilities used: itemtool.h (from page 277), cstdlib +// +{ + size_t i; // Index of next element to be added to heap + size_t k; // Index of new element as it is being pushed upward through the heap + + for (i = 1; i < n; ++i) + { + k = i; + while ((k > 0) && (data[k] > data[parent(k)])) + { + swap(data[k], data[parent(k)]); + k = parent(k); + } + } +} + +void reheapify_down(int data[ ], size_t n) +// Library facilities used: itemtool.h (from page 277), cstdlib +{ + size_t current; // Index of the node that's moving down + size_t big_child_index; // Index of the larger child of the node that's moving down + bool heap_ok = false; // Will change to true when the heap becomes correct + + current = 0; + + // Note: The loop keeps going while the heap is not okay, and while the current node has + // at least a left child. The test to see whether the current node has a left child is + // left_child(current) < n. + while ((!heap_ok) && (left_child(current) < n)) + { + // Compute the index of the larger child: + if (right_child(current) >= n) + // There is no right child, so left child must be largest + big_child_index = left_child(current); + else if (data[left_child(current)] > data[right_child(current)]) + // The left child is the bigger of the two children + big_child_index = left_child(current); + else + // The right child is the bigger of the two children + big_child_index = right_child(current); + + // Check whether the larger child is bigger than the current node. If so, then swap + // the current node with its bigger child and continue; otherwise we are finished. + if (data[current] < data[big_child_index]) + { + swap(data[current], data[big_child_index]); + current = big_child_index; + } + else + heap_ok = true; + } +} + diff --git a/chapter13/merge.cxx b/chapter13/merge.cxx new file mode 100644 index 0000000..0d53978 --- /dev/null +++ b/chapter13/merge.cxx @@ -0,0 +1,122 @@ +// FILE: merge.cxx +// An interactive test program for the mergesort function + +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void mergesort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. +// NOTE: If there is insufficient dynamic memory, then new_handler is called. + +void merge(int data[ ], size_t n1, size_t n2); +// Precondition: data is an array (or subarray) with at least n1+n2 elements. +// The first n1 elements (from data[0] to data[n1-1]) are sorted from smallest +// to largest, and the last n2 (from data[n1] to data[n1+n2-1]) are also +// sorted from smallest to largest. +// Postcondition: The first n1+n2 elements of data have been +// rearranged to be sorted from smallest to largest. +// NOTE: If there is insufficient dynamic memory, then new_handler is called. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + mergesort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void mergesort(int data[ ], size_t n) +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. +// NOTE: If there is insufficient dynamic memory, thenbad_alloc is thrown. +// Library facilities used: cstdlib +{ + size_t n1; // Size of the first subarray + size_t n2; // Size of the second subarray + + if (n > 1) + { + // Compute sizes of the subarrays. + n1 = n / 2; + n2 = n - n1; + + mergesort(data, n1); // Sort from data[0] through data[n1-1] + mergesort((data + n1), n2); // Sort from data[n1] to the end + + // Merge the two sorted halves. + merge(data, n1, n2); + } +} + +void merge(int data[ ], size_t n1, size_t n2) +// Precondition: data is an array (or subarray) with at least n1 + n2 elements. +// The first n1 elements (from data[0] to data[n1 - 1]) are sorted from +// smallest to largest, and the last n2 (from data[n1] to data[n1 + n2 - 1]) +// also are sorted from smallest to largest. +// Postcondition: The first n1 + n2 elements of data have been rearranged to be +// sorted from smallest to largest. +// NOTE: If there is insufficient dynamic memory, then bad_alloc is thrown. +// Library facilities used: cstdlib +{ + int *temp; // Points to dynamic array to hold the sorted elements + size_t copied = 0; // Number of elements copied from data to temp + size_t copied1 = 0; // Number copied from the first half of data + size_t copied2 = 0; // Number copied from the second half of data + size_t i; // Array index to copy from temp back into data + + // Allocate memory for the temporary dynamic array. + temp = new int[n1+n2]; + + // Merge elements, copying from two halves of data to the temporary array. + while ((copied1 < n1) && (copied2 < n2)) + { + if (data[copied1] < (data + n1)[copied2]) + temp[copied++] = data[copied1++]; // Copy from first half + else + temp[copied++] = (data + n1)[copied2++]; // Copy from second half + } + + // Copy any remaining entries in the left and right subarrays. + while (copied1 < n1) + temp[copied++] = data[copied1++]; + while (copied2 < n2) + temp[copied++] = (data+n1)[copied2++]; + + // Copy from temp back to the data array, and release temp's memory. + for (i = 0; i < n1+n2; i++) + data[i] = temp[i]; + delete [ ] temp; +} + + diff --git a/chapter13/quick.cxx b/chapter13/quick.cxx new file mode 100644 index 0000000..4a978a3 --- /dev/null +++ b/chapter13/quick.cxx @@ -0,0 +1,107 @@ +// FILE: quick.cxx +// An interactive test program for the quicksort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void quicksort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. + +void partition(int data[ ], size_t n, size_t& pivot_index); +// Precondition: n > 1, and data is an array (or subarray) +// with at least n elements. +// Postcondition: The function has selected some "pivot value" +// that occurs in data[0]..data[n-1]. The elements of data +// have then been rearranged, and the pivot index set so that: +// -- data[pivot_index] is equal to the pivot; +// -- Each item before data[pivot_index] is <= the pivot; +// -- Each item after data[pivot_index] is >= the pivot. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + quicksort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void quicksort(int data[ ], size_t n) +// Library facilities used: cstdlib +{ + size_t pivot_index; // Array index for the pivot element + size_t n1; // Number of elements before the pivot element + size_t n2; // Number of elements after the pivot element + + if (n > 1) + { + // Partition the array, and set the pivot index. + partition(data, n, pivot_index); + + // Compute the sizes of the subarrays. + n1 = pivot_index; + n2 = n - n1 - 1; + + // Recursive calls will now sort the subarrays. + quicksort(data, n1); + quicksort((data + pivot_index + 1), n2); + } +} + +void partition(int data[ ], size_t n, size_t& pivot_index) +// Library facilities used: itemtool.h, stdlib.h +// +// NOTES FROM THE IMPLEMENTOR: +// How the partition works on small arrays: +// +// Notice that n=0 is not permitted by the precondition. +// +// If n=1, then too_big_index is initialized as 1, and too_small_index is +// initialized as 0. Therefore, the body of the loop is never executed, +// and after the loop pivot_index is set to zero. +// +// If n=2, then both too_big_index and too_small_index are initialized as 1. +// The loop is entered, and there are two cases to consider: +// -- if data[1] <= pivot, then too_big_index increases to 2, and +// too_small_index stays at 1. The if-statement at the bottom of the loop +// is then skipped, and after the loop we copy data[1] down to data[0], +// and copy the pivot into data[0]. Thus, the smaller element is in +// data[0], and the larger element (the pivot) is in data[1]. +// -- if data[1] > pivot, then too_big_index stays at 1, and too_small_index +// decreases to 0. The if-statement at the bottom of the loop is then +// skipped, and after the loop we end up copying the pivot onto data[0] +// (leaving data[1] alone). Thus, the smaller element (the pivot) remains +// at data[0], leaving the larger element at data[1]. +{ + -- Implementation is left to the student +} diff --git a/chapter13/select.cxx b/chapter13/select.cxx new file mode 100644 index 0000000..44514e9 --- /dev/null +++ b/chapter13/select.cxx @@ -0,0 +1,71 @@ +// FILE: select.cxx +// An interactive test program for the selectionsort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPE of the function used in this test program: +void selectionsort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements are rearranged so that +// data[0] <= data[1] <= ... <= data[n-1]. + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions. + cout << "Please type up to " << ARRAY_SIZE << " positive integers. "; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers. + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers, and print the result with two blanks after each number. + selectionsort(data, number_of_elements); + cout << "In sorted order, your numbers are: "<< endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void selectionsort(int data[ ], size_t n) +// Library facilities used: algorithm, cstdlib +{ + size_t i, j, index_of_largest; + int largest; + + if (n == 0) + return; // No work for an empty array. + + for (i = n-1; i > 0; --i) + { + largest = data[0]; + index_of_largest = 0; + for (j = 1; j <= i; ++j) + { + if (data[j] > largest) + { + largest = data[j]; + index_of_largest = j; + } + } + swap(data[i], data[index_of_largest]); + } +} diff --git a/chapter14/Makefile b/chapter14/Makefile new file mode 100644 index 0000000..fc66f53 --- /dev/null +++ b/chapter14/Makefile @@ -0,0 +1,14 @@ +play_connect4.exe: connect4.h play_connect4.cxx game.o connect4.o + g++ -Wall -gstabs play_connect4.cxx game.o connect4.o -o play_connect4 + +play_othello.exe: othello.h play_othello.cxx game.o othello.o + g++ -Wall -gstabs play_othello.cxx game.o othello.o -o othello + +game.o: game.h game.cxx + g++ -Wall -gstabs -c game.cxx + +connect4.o: connect4.h game.h connect4.cxx + g++ -Wall -gstabs -c connect4.cxx + +othello.o: othello.h game.h othello.cxx + g++ -Wall -gstabs -c othello.cxx diff --git a/chapter14/blob.cxx b/chapter14/blob.cxx new file mode 100644 index 0000000..e2c09a3 --- /dev/null +++ b/chapter14/blob.cxx @@ -0,0 +1,32 @@ +// FILE: blob.cxx +// This small demonstration shows how the organism class is used. +#include // Provides EXIT_SUCCESS +#include // Provides cout and cin +#include "organism.h" // Provides the organism class + +int main( ) +{ + main_savitch_14::organism blob(20.0, 100000.0); + int week; + + // Untroubled by conscience or intellect, the Blob grows for three weeks. + for (week = 1; week <= 3; ++week) + { + blob.simulate_week( ); + cout << "Week " << week << ":" << " the Blob is "; + cout << blob.get_size( ) << " ounces." << endl; + } + + // Steve McQueen reverses the growth rate to -80000 ounces per week. + blob.assign_rate(-80000.0); + while (blob.is_alive( )) + { + blob.simulate_week( ); + cout << "Week " << week << ":" << " the Blob is "; + cout << blob.get_size( ) << " ounces." << endl; + ++week; + } + + cout << "The Blob (or its son) shall return." << endl; + return EXIT_SUCCESS; +} diff --git a/chapter14/clocks.cxx b/chapter14/clocks.cxx new file mode 100644 index 0000000..c3ed0ae --- /dev/null +++ b/chapter14/clocks.cxx @@ -0,0 +1,137 @@ +// FILE: clocks.cxx (part of the namespace main_savitch_14) +// CLASSES IMPLEMENTED: clock, cuckoo_clock, clock24 (see clock.h) +// INVARIANT for the clock ADT: +// 1. The current hour is stored in my_hour, using 12-hour notation. +// 2. The current minute is stored in my_minute. +// 3. If the time is from midnight to 11:59 am (inclusive), then +// my_morning is true; otherwise my_morning is false. + +#include +#include "clocks.h" + +namespace main_savitch_14 +{ + clock::clock( ) + { + my_hour = 12; + my_minute = 0; + my_morning = true; + } + + void clock::set_time(int hour, int minute, bool morning) + // Library facilities used: cassert + { + assert(1 <= hour); + assert(hour <= 12); + assert(0 <= minute); + assert(minute <= 59); + + my_hour = hour; + my_minute = minute; + my_morning = morning; + } + + void clock::advance(int minutes) + { + const int MINUTES_IN_DAY = 24*60; + const int MINUTES_IN_HOUR = 60; + + // Change the minutes so that 0 <= minutes < MINUTES_IN_DAY + if (minutes < 0) + minutes += MINUTES_IN_DAY * (1 - minutes/MINUTES_IN_DAY); + if (minutes >= MINUTES_IN_DAY) + minutes -= MINUTES_IN_DAY * (minutes/MINUTES_IN_DAY); + + // Advance the clock any full hours + while (minutes > 60) + { + minutes -= MINUTES_IN_HOUR; + my_hour++; + if (my_hour == 12) + my_morning = !my_morning; + if (my_hour == 13) + my_hour = 1; + } + + // Advance any remaining minutes + my_minute += minutes; + if (my_minute >= MINUTES_IN_HOUR) + { + my_minute -= MINUTES_IN_HOUR; + my_hour++; + if (my_hour == 12) + my_morning = !my_morning; + if (my_hour == 13) + my_hour = 1; + } + } + + int clock::get_hour( ) const + { + return my_hour; + } + + int clock::get_minute( ) const + { + return my_minute; + } + + bool clock::is_morning( ) const + { + return my_morning; + } + + bool cuckoo_clock::is_cuckooing( ) const + { + return (get_minute( ) == 0); + } + + bool operator <(const clock& c1, const clock& c2) + { + // Check whether one is morning and the other is not + if (c1.is_morning( ) && !c2.is_morning( )) + return true; + else if (c2.is_morning( ) && !c1.is_morning( )) + return false; + + // Check whether one is 12 o'clock and the other is not + else if ((c1.get_hour( ) == 12) && (c2.get_hour( ) != 12)) + return true; + else if ((c2.get_hour( ) == 12) && (c1.get_hour( ) != 12)) + return false; + + // Check whether the hours are different from each other + else if (c1.get_hour( ) < c2.get_hour( )) + return true; + else if (c2.get_hour( ) < c1.get_hour( )) + return false; + + // The hours are the same, so check the minutes + else if (c1.get_minute( ) < c2.get_minute( )) + return true; + else + return false; + } + + int clock24::get_hour( ) const + { + int ordinary_hour; + + ordinary_hour = clock::get_hour( ); + if (is_morning( )) + { + if (ordinary_hour == 12) + return 0; + else + return ordinary_hour; + } + else + { + if (ordinary_hour == 12) + return 12; + else + return ordinary_hour + 12; + } + } + +} diff --git a/chapter14/clocks.h b/chapter14/clocks.h new file mode 100644 index 0000000..f918983 --- /dev/null +++ b/chapter14/clocks.h @@ -0,0 +1,102 @@ +// FILE: clocks.h (part of namespace main_savitch_14) +// CLASSES PROVIDED: +// clock (keeps track of a single time value) +// cuckoo_clock (clock descendant with a cuckoo that makes noise on the hour) +// clock24 (clock descendant for time in 24-hour version) +// +// CONSTRUCTOR for the clock class: +// clock( ) +// Postcondition: The clock is set to 12:00 (midnight). +// +// MODIFICATION MEMBER FUNCTIONS for the clock class: +// void set_time(int hour, int minute, bool morning) +// Precondition: 1 <= hour <= 12, and 0 <= minute <= 59. +// Postcondition: The clock's time has been set to the given hour and +// minute (using usual 12-hour time notation). If the third parameter, +// morning, is true, then this time is from 12:00 midnight to 11:59am. +// Otherwise this time is from 12:00 noon to 11:59pm. +// +// void advance(int minutes) +// Postcondition: The clock has been moved forward by the indicated +// number of minutes. +// Note: A negative argument moves the clock backward. +// +// CONSTANT MEMBER FUNCTIONS for the clock class: +// int get_hour( ) const +// Postcondition: The value returned is the current hour using a 12-hour +// clock. +// +// int get_minute( ) const +// Postcondition: The value returned is the current minute on the clock. +// +// bool is_morning( ) const +// Postcondition: If the clock's time lies from 12:00 midnight to +// 11:59am (inclusive), the function returns true; otherwise it +// returns false. +// +// NONMEMBER FUNCTIONS for the clock class: +// bool operator <(const clock& c1, const clock& c2) +// Postcondition: Returns true if the time on c1 is earlier than the time +// on c2 over a usual day (starting at midnight); otherwise returns false. +// +// INHERITED MEMBER FUNCTIONS for the cuckoo_clock class: +// The cuckoo_clock inherits all public members from the clock class. +// +// ADDITIONAL CONSTANT MEMBER FUNCTION for the cuckoo_clock class: +// bool is_cuckooing( ) const; +// Postcondition: The return value is true if the current minute is zero +// (so that the cuckoo is making noise). +// +// INHERITED MEMBER FUNCTIONS for the clock24 class: +// The clock24 class inherits all public members from the clock class, +// except for get_hour, which is overriden (as described below): +// +// OVERRIDEN CONSTANT MEMBER FUNCTION for the clock24 class: +// int get_hour( ) const +// Postcondition: The value returned is the current hour using a 24-hour +// clock. +// +// VALUE SEMANTICS for the clock, cuckoo_clock, and clock24 classes: +// Assignments and the copy constructor may be used with any of +// these objects. + +#ifndef CLOCK_H +#define CLOCK_H + +namespace main_savitch_14 +{ + class clock + { + public: + // CONSTRUCTOR + clock( ); + // MODIFICATION FUNCTIONS + void set_time(int hour, int minute, bool morning); + void advance(int minutes); + // CONSTANT FUNCTIONS + int get_hour( ) const; + int get_minute( ) const; + bool is_morning( ) const; + private: + int my_hour; + int my_minute; + int my_morning; + }; + + class cuckoo_clock : public clock + { + public: + bool is_cuckooing( ) const; + }; + + class clock24 : public clock + { + public: + int get_hour( ) const; + }; + + // NONMEMBER FUNCTION for the clock class: + bool operator <(const clock& c1, const clock& c2); +} + +#endif diff --git a/chapter14/connect4.cxx b/chapter14/connect4.cxx new file mode 100644 index 0000000..53d87ba --- /dev/null +++ b/chapter14/connect4.cxx @@ -0,0 +1,225 @@ +// File: connect4.cxx + +#include // Provides fill_n +#include // Provides isdigit +#include // Provides setw +#include // Provides cin, cout +#include // Provides queue class +#include // Provides string +#include "connect4.h" // Provides definition of connect4 class (derived from game) +using namespace std; + +namespace main_savitch_14 +{ + // Public static member constants. These were defined in connect.h: + const int connect4::ROWS; + const int connect4::COLUMNS; + + // Private static member constants, defined here. The COLUMN_DISPLAY_WIDTH + // is the number of characters to use in the display( ) function for each + // column in the output display. The FOUR_VALUE is the value returned by + // the value function when it finds four-in-a-row. For the current + // implementation of evaluate to work, the FOUR_VALUE should be at least + // 24 times as large as the total number of spots on the board. + // MOVE_STRINGS is an array of all possible moves, which must be strings + // corresponding to the integers 0 through COLUMNS-1. + const int connect4::COLUMN_DISPLAY_WIDTH = 3; + const int connect4::FOUR_VALUE = 24*ROWS*COLUMNS; + const string connect4::MOVE_STRINGS[COLUMNS] = {"0","1","2","3","4","5","6"}; + + connect4::connect4( ) + : game( ) + { + restart( ); + } + + game* connect4::clone( ) const + { + // Return a pointer to a copy of myself, made with the automatic copy + // constructor. If I used dynamic memory, I would have to alter this + // copy so that it used its own dynamic memory instead of mine. But + // the connect4 class does not use any dynamic memory, so this is ok: + return new connect4(*this); + } + + void connect4::compute_moves(queue& moves) const + { + int i; + + for (i = 0; i < COLUMNS; i++) + { + if (many_used[i] < ROWS) + moves.push(MOVE_STRINGS[i]); + } + } + + void connect4::display_status( ) const + { + int row, column; + + cout << "\nCurrent game status\n(HUMAN = # and COMPUTER = @):\n"; + if (moves_completed( ) != 0) + cout << "Most recent move in column " << most_recent_column << endl; + for (row = ROWS-1; row >= 0; --row) + { + for (column = 0; column < COLUMNS; ++column) + { + switch (data[row][column]) + { + case HUMAN: cout << setw(COLUMN_DISPLAY_WIDTH) << "#"; break; + case COMPUTER: cout << setw(COLUMN_DISPLAY_WIDTH) << "@"; break; + case NEUTRAL: cout << setw(COLUMN_DISPLAY_WIDTH) << "."; break; + } + } + cout << endl; + } + for (column = 0; column < COLUMNS; ++column) + cout << setw(COLUMN_DISPLAY_WIDTH) << column; + if (is_game_over( )) + cout << "\nGame over." << endl; + else if (last_mover( ) == COMPUTER) + cout << "\nHuman's turn to move (by typing a column number)" << endl; + else + cout << "\nComputer's turn to move (please wait)..." << endl; + } + + int connect4::evaluate( ) const + { + // NOTE: Positive answer is good for the last_mover( ). + int row, column; + int answer = 0; + + // For each possible starting spot, calculate the value of the spot for + // a potential four-in-a-row, heading down, left, and to the lower-left. + // Normally, this value is in the range [-3...+3], but if a + // four-in-a-row is found for the player, the result is FOUR_VALUE which + // is large enough to make the total answer larger than any evaluation + // that occurs with no four-in-a-row. + + // Value moving down from each spot: + for (row = 3; row < ROWS; ++row) + for (column = 0; column < COLUMNS; ++column) + answer += value(row, column, -1, 0); + + // Value moving left from each spot: + for (row = 0; row < ROWS; ++row) + for (column = 3; column < COLUMNS; ++column) + answer += value(row, column, 0, -1); + + // Value heading diagonal (lower-left) from each spot: + for (row = 3; row < ROWS; ++row) + for (column = 3; column < COLUMNS; ++column) + answer += value(row, column, -1, -1); + + // Value heading diagonal (lower-right) from each spot: + for (row = 3; row < ROWS; ++row) + for (column = 0; column <= COLUMNS-4; ++column) + answer += value(row, column, -1, +1); + + return (last_mover( ) == COMPUTER) ? answer : -answer; + } + + bool connect4::is_game_over( ) const + { + + int row, column; + int i; + + // Two simple cases: + if (moves_completed( ) == 0) + return false; + if (moves_completed( ) == ROWS*COLUMNS) + return true; + + // Check whether most recent move is part of a four-in-a-row + // for the player who just moved. + column = most_recent_column; + row = many_used[column] - 1; + // Vertical: + if (abs(value(row, column, -1, 0)) == FOUR_VALUE) return true; + for (i = 0; i <= 3; i++) + { + // Diagonal to the upper-right: + if (abs(value(row-i, column-i, 1, 1)) == FOUR_VALUE) return true; + // Diagonal to the lower-right: + if (abs(value(row-i, column+i, 1, -1)) == FOUR_VALUE) return true; + // Horizontal: + if (abs(value(row, column-i, 0, 1)) == FOUR_VALUE) return true; + } + + return false; + } + + bool connect4::is_legal(const string& move) const + { + int column = atoi(move.c_str( )); + + return + (!is_game_over( )) + && + (move.length( ) > 0) + && + (isdigit(move[0])) + && + (column < COLUMNS) + && + (many_used[column] < ROWS); + } + + void connect4::make_move(const string& move) + { + int row, column; + + assert(is_legal(move)); + column = atoi(move.c_str( )); + row = many_used[column]++; + data[row][column] = next_mover( ); + most_recent_column = column; + game::make_move(move); + } + + void connect4::restart( ) + { + fill_n(&(data[0][0]), ROWS*COLUMNS, NEUTRAL); + fill_n(&(many_used[0]), COLUMNS, 0); + game::restart( ); + } + + int connect4::value(int row, int column, int delta_r, int delta_c) const + { + // NOTE: Positive return value is good for the computer. + int i; + int end_row = row + 3*delta_r; + int end_column = column + 3*delta_c; + int computer_count= 0; + int opponent_count = 0; + + if ( + (row < 0) || (column < 0) || (end_row < 0) || (end_column < 0) + || + (row >= ROWS) || (end_row >= ROWS) + || + (column >= COLUMNS) || (end_column >= COLUMNS) + ) + return 0; + + for (i = 1; i <= 4; ++i) + { + if (data[row][column] == COMPUTER) + ++computer_count; + else if (data[row][column] != NEUTRAL) + ++opponent_count; + row += delta_r; + column += delta_c; + } + + if ((computer_count > 0) && (opponent_count > 0)) + return 0; // Neither player can get four-in-a-row here. + else if (computer_count == 4) + return FOUR_VALUE; + else if (opponent_count == 4) + return -FOUR_VALUE; + else + return computer_count - opponent_count; + } +} diff --git a/chapter14/connect4.h b/chapter14/connect4.h new file mode 100644 index 0000000..459f2f3 --- /dev/null +++ b/chapter14/connect4.h @@ -0,0 +1,58 @@ +// File: connect4.h (part of the namespace main_savitch_14) +#ifndef MAIN_SAVITCH_CONNECT4 +#define MAIN_SAVITCH_CONNECT4 +#include // Provides queue +#include // Provides string +#include "game.h" // Provides the game base class + +namespace main_savitch_14 +{ + class connect4 : public game + { + public: + // STATIC CONSTANTS + static const int ROWS = 6; + static const int COLUMNS = 7; + + // CONSTRUCTOR + connect4( ); + + protected: + // ******************************************************************* + // VIRTUAL FUNCTIONS (these are overridden from the game base class) + // ******************************************************************* + // Return a pointer to a copy of myself: + virtual game* clone( ) const; + // Compute all the moves that the next player can make: + virtual void compute_moves(std::queue& moves) const; + // Display the status of the current game: + virtual void display_status( ) const; + // Evaluate the current board position. + // NOTE: Positive values are good for the last_mover( ). + virtual int evaluate( ) const; + // Return true if the current game is finished: + virtual bool is_game_over( ) const; + // Return true if the given move is legal for the next player: + virtual bool is_legal(const std::string& move) const; + // Have the next player make a specified move: + virtual void make_move(const std::string& move); + // Restart the game from the beginning: + virtual void restart( ); + + private: + // HELPER FUNCTIONS + int value(int row, int column, int delta_r, int delta_c) const; + + // HELPER CONSTANTS. See connect4.cxx for their values. + static const int COLUMN_DISPLAY_WIDTH; + static const int FOUR_VALUE; + static const std::string MOVE_STRINGS[COLUMNS]; + + // MEMBER VARIABLES TO TRACK THE STATE OF THE GAME + who data[ROWS][COLUMNS]; + int many_used[COLUMNS]; + int most_recent_column; + }; +} + +#endif diff --git a/chapter14/game.cxx b/chapter14/game.cxx new file mode 100644 index 0000000..e9c45ec --- /dev/null +++ b/chapter14/game.cxx @@ -0,0 +1,167 @@ +// File: game.cxx + +#include // Provides assert +#include // Provides INT_MAX and INT_MIN +#include // Provides cin, cout +#include // Provides queue +#include // Provides string +#include "game.h" // Provides definition of game class +using namespace std; + +namespace main_savitch_14 +{ + //************************************************************************* + // STATIC MEMBER CONSTANTS + const int game::SEARCH_LEVELS; + + //************************************************************************* + // PUBLIC MEMBER FUNCTIONS + + game::who game::play( ) + // The play function should not be overridden. It plays one round of the + // game, with the human player moving first and the computer second. + // The return value is the winner of the game (or NEUTRAL for a tie). + { + restart( ); + + while (!is_game_over( )) + { + display_status( ); + if (last_mover( ) == COMPUTER) + make_human_move( ); + else + make_computer_move( ); + } + display_status( ); + return winning( ); + } + + + + //************************************************************************* + // OPTIONAL VIRTUAL FUNCTIONS (overriding these functions is optional) + + void game::display_message(const string& message) const + { + cout << message; + } + + string game::get_user_move( ) const + { + string answer; + + display_message("Your move, please: "); + getline(cin, answer); + return answer; + } + + game::who game::winning( ) const + { + // Positive evaluation is good for last_mover( ). + int value = evaluate( ); + + if (value > 0) + return last_mover( ); + else if (value < 0) + return next_mover( ); + else + return NEUTRAL; + } + + + + //************************************************************************* + // PRIVATE FUNCTIONS (these are the same for every game) + + int game::eval_with_lookahead(int look_ahead, int beat_this) + // Evaluate a board position with lookahead. + // --int look_aheads: How deep the lookahead should go to evaluate the move. + // --int beat_this: Value of another move that we're considering. If the + // current board position can't beat this, then cut it short. + // The return value is large if the position is good for the player who just + // moved. + { + queue moves; // All possible opponent moves + int value; // Value of a board position after opponent moves + int best_value; // Evaluation of best opponent move + game* future; // Pointer to a future version of this game + + // Base case: + if (look_ahead == 0 || is_game_over( )) + return evaluate( ); + + // Recursive case: + // The level is above 0, so try all possible opponent moves. Keep the + // value of the best of these moves from the opponent's perspective. + compute_moves(moves); + assert(!moves.empty( )); + best_value = INT_MIN; + while (!moves.empty( )) + { + future = clone( ); + future->make_move(moves.front( )); + value = future->eval_with_lookahead(look_ahead-1, best_value); + delete future; + if (value > best_value) + { + if (-value <= beat_this) + return INT_MIN + 1; // Alpha-beta pruning + best_value = value; + } + moves.pop( ); + } + + // The value was calculated from the opponent's perspective. + // The answer we return should be from player's perspective, so multiply times -1: + return -best_value; + } + + void game::make_computer_move( ) + { + queue moves; + int value; + int best_value; + string best_move; + game* future; + + // Compute all legal moves that the computer could make. + compute_moves(moves); + assert(!moves.empty( )); + + // Evaluate each possible legal move, saving the index of the best + // in best_index and saving its value in best_value. + best_value = INT_MIN; + while (!moves.empty( )) + { + future = clone( ); + future->make_move(moves.front( )); + value = future->eval_with_lookahead(SEARCH_LEVELS, best_value); + delete future; + if (value >= best_value) + { + best_value = value; + best_move = moves.front( ); + } + moves.pop( ); + } + + // Make the best move. + make_move(best_move); + } + + void game::make_human_move( ) + { + string move; + + move = get_user_move( ); + while (!is_legal(move)) + { + display_message("Illegal move.\n"); + move = get_user_move( ); + } + make_move(move); + } + +} + + diff --git a/chapter14/game.h b/chapter14/game.h new file mode 100644 index 0000000..e1c27e8 --- /dev/null +++ b/chapter14/game.h @@ -0,0 +1,86 @@ +// File: game.h (part of the namespace main_savitch_14) + + +#ifndef MAIN_SAVITCH_GAME +#define MAIN_SAVITCH_GAME +#include // Provides queue +#include // Provides string + +namespace main_savitch_14 +{ + class game + { + public: + // ENUM TYPE + enum who { HUMAN, NEUTRAL, COMPUTER }; // Possible game outcomes + + // CONSTRUCTOR and DESTRUCTOR + game( ) { move_number = 0; } + virtual ~game( ) { } + + // PUBLIC MEMBER FUNCTIONS + // The play function should not be overridden. It plays one game, + // with the human player moving first and the computer second. + // The computer uses an alpha-beta look ahead algorithm to select its + // moves. The return value is the winner of the game (or NEUTRAL for + // a tie). + who play( ); + + protected: + // ******************************************************************* + // OPTIONAL VIRTUAL FUNCTIONS (overriding these is optional) + // ******************************************************************* + virtual void display_message(const std::string& message) const; + virtual std::string get_user_move( ) const; + virtual who last_mover( ) const + { return (move_number % 2 == 1 ? HUMAN : COMPUTER); } + virtual int moves_completed( ) const { return move_number; } + virtual who next_mover( ) const + { return (move_number % 2 == 0 ? HUMAN : COMPUTER); } + virtual who opposite(who player) const + { return (player == HUMAN) ? COMPUTER : HUMAN; } + virtual who winning( ) const; + + // ******************************************************************* + // VIRTUAL FUNCTIONS THAT MUST BE OVERRIDDEND: + // The overriding function should call the original when it finishes. + // ******************************************************************* + // Have the next player make a specified move: + virtual void make_move(const std::string& move) { ++move_number; } + // Restart the game from the beginning: + virtual void restart( ) { move_number = 0; } + + // ******************************************************************* + // PURE VIRTUAL FUNCTIONS + // ******************************************************************* + // (these must be provided for each derived class) + // Return a pointer to a copy of myself: + virtual game* clone( ) const = 0; + // Compute all the moves that the next player can make: + virtual void compute_moves(std::queue& moves) const = 0; + // Display the status of the current game: + virtual void display_status( ) const = 0; + // Evaluate a board position: + // NOTE: positive values are good for the player who most recently moved + // (positive values are good for last_mover). + virtual int evaluate( ) const = 0; + // Return true if the current game is finished: + virtual bool is_game_over( ) const = 0; + // Return true if the given move is legal for the next player: + virtual bool is_legal(const std::string& move) const = 0; + + private: + // MEMBER VARIABLES + int move_number; // Number of moves made so far + + // STATIC MEMBER CONSTANT + static const int SEARCH_LEVELS = 4; // Levels for look-ahead evaluation + + // PRIVATE FUNCTIONS (these are the same for every game) + int eval_with_lookahead(int look_ahead, int beat_this); + void make_computer_move( ); + void make_human_move( ); + }; +} + +#endif diff --git a/chapter14/organism.cxx b/chapter14/organism.cxx new file mode 100644 index 0000000..3a544d0 --- /dev/null +++ b/chapter14/organism.cxx @@ -0,0 +1,126 @@ +// FILE: organism.cxx +// CLASSES IMPLEMENTED: +// organism, plant, animal, herbivore (see organism.h for documentation) +// +// INVARIANT for the organism class: +// 1. The member variable size contains the organism's size, in ounces. +// 2. The member variable rate contains the organism's growth rate, in +// ounces per week. +// +// INVARIANT for the animal class: +// 1. The member variable need_each_week contains the organism's food +// requirement, in ounces per week. +// 2. The member variable eaten_this_week contains the number of ounces of +// food eaten by the organism in the current week. +// +// The plant and herbivore classes have no extra member variables, so there +// is no need for an invariant. + +#include // Provides assert +#include "organism.h" + +namespace main_savitch_14 +{ + organism::organism(double init_size, double init_rate) + { + if (init_size == 0) + assert(init_rate == 0); + else + assert(init_size >= 0); + + size = init_size; + rate = init_rate; + } + + void organism::alter_size(double amount) + { + size += amount; + if (size <= 0) + death( ); + } + + void organism::death( ) + { + size = rate = 0; + } + + plant::plant(double init_size, double init_rate) + : organism(init_size, init_rate) + { + // All work is done by the organism constructor + } + + void plant::nibbled_on(double amount) + // Library functions used: cassert + { + assert(amount >= 0); + assert(amount <= get_size( )); + alter_size(-amount); + } + + animal::animal(double init_size, double init_rate, double init_need) + : organism(init_size, init_rate) + // Library facilities used: cassert + { + assert(0 <= init_need); + need_each_week = init_need; + eaten_this_week = 0; + } + + void animal::assign_need(double new_need) + // Library facilities used: cassert + { + assert(new_need >= 0); + need_each_week = new_need; + } + + void animal::eat(double amount) + // Library facilities used: cassert + { + assert(amount >= 0); + eaten_this_week += amount; + } + + void animal::simulate_week( ) + { + organism::simulate_week( ); + if (eaten_this_week < need_each_week) + death( ); + eaten_this_week = 0; + } + + double animal::still_need( ) const + { + if (eaten_this_week >= need_each_week) + return 0; + else + return need_each_week - eaten_this_week; + } + + herbivore::herbivore(double init_size, double init_rate, double init_need) + : animal(init_size, init_rate, init_need) + { + // All work is done by the animal constructor + } + + void herbivore::nibble(plant& meal) + { + const double PORTION = 0.5; // Eat no more than this portion of plant + const double MAX_FRACTION = 0.1; // Eat no more than this fraction of weekly need + double amount; // How many ounces of the plant will be eaten + + // Set amount to some portion of the plant, but no more than a given + // maximum fraction of the total weekly need, and no more than what the + // herbivore still needs to eat this week. + amount = PORTION * meal.get_size( ); + if (amount > MAX_FRACTION * total_need( )) + amount = MAX_FRACTION * total_need( ); + if (amount > still_need( )) + amount = still_need( ); + + // Eat the plant + eat(amount); + meal.nibbled_on(amount); + } + +} diff --git a/chapter14/organism.h b/chapter14/organism.h new file mode 100644 index 0000000..e551056 --- /dev/null +++ b/chapter14/organism.h @@ -0,0 +1,193 @@ +// FILE: organism.h (part of the namespace main_savitch_14) +// CLASSES PROVIDED: organism, plant, animal, herbivore +// +// +// DOCUMENTATION for the organism class: +// The organism class can simulate any growing organism, such as a plant or +// animal. +// +// CONSTRUCTOR for the organism class: +// organism(double init_size = 1, double init_rate = 0) +// Precondition: init_size >= 0. Also, if init_size = 0, then init_rate is +// also zero. +// Postcondition: The organism being simulated has been initialized. The +// value returned from get_size( ) is now init_size (measured in ounces), +// and the value returned from get_rate( ) is now init_rate (measured in +// ounces per week). +// +// MODIFICATION MEMBER FUNCTIONS for the organism class: +// void simulate_week( ) +// Postcondition: The size of the organism has been changed by its current +// growth rate. If the new size is less than zero, then the actual size is +// set to zero rather than to a negative value, and the growth rate is also +// set to zero. +// +// void assign_rate(double new_rate) +// Postcondition: The organism's growth rate has been changed to new_rate +// (measured in ounces per week). +// +// void alter_size(double amount) +// Postcondition: The given amount (in ounces) has been added to the +// organism's current size. If this results in a new size less than zero, +// then the actual size is set to zero rather than to a negative value, and +// the growth rate is also set to zero. +// +// void death( ) +// Postcondition: The organism's current size and growth rate have been +// set to zero. +// +// CONSTANT MEMBER FUNCTIONS for the organism class: +// double get_size( ) const +// Postcondition: The value returned is the organism's current size +// (in ounces). +// +// double get_rate( ) const +// Postcondition: The value returned is the organism's current growth rate +// (in oz/week). +// +// bool is_alive( ) const +// Postcondition: If the current size is greater than zero, then the return +// value is true; otherwise the return value is false. +// +// +// DOCUMENTATION for the plant class: +// plant is a derived class of the organism class. All the organism public +// member functions are inherited by a plant. In addition, a plant has +// these extra member functions: +// +// CONSTRUCTOR for the plant class: +// plant(double init_size=0, double init_rate=0) +// Same as the organism constructor. +// +// MODIFICATION MEMBER FUNCTIONS for the plant class: +// void nibbled_on(double amount) +// Precondition: 0 <= amount <= get_size( ). +// Postcondition: The size of the plant has been reduced by amount. +// If this reduces the size to zero, then death is activated. +// +// +// DOCUMENTATION for the animal class: +// animal is a derived class of the organism class. All the organism public +// member functions are inherited by an animal. In addition, an animal has +// these extra member functions: +// +// CONSTRUCTOR for the animal class: +// animal(double init_size=0, double init_rate=0, double init_need=0) +// Precondition: init_size >= 0, and init_need >= 0. Also, if +// init_size = 0, then init_rate is also zero. +// Postcondition: The organism being simulated has been initialized. The +// value returned from get_size( ) is now init_size (measured in ounces), +// the value returned from get_rate( ) is now init_rate (measured in ounces +// per week), and the animal must eat at least init_need ounces of food +// each week to survive. +// +// MODIFICATION MEMBER FUNCTIONS for the animal class: +// void assign_need(double new_need) +// Precondition: new_need >= 0. +// Postcondition: The animal's weekly food requirement has been changed to +// new_need (measured in ounces per week). +// +// void eat(double amount) +// Precondition: amount >= 0. +// Postcondition: The given amount (in ounces) has been added to the amount +// of food that the animal has eaten this week. +// +// void simulate_week( ) -- overriden from the organism class +// Postcondition: The size of the organism has been changed by its current +// growth rate. If the new size is less than zero, then the actual size is +// set to zero rather than to a negative value, and the growth rate is also +// set to zero. Also, if the animal has eaten less than its required need +// over the past week, then death has been activated. +// +// CONSTANT MEMBER FUNCTIONS for the animal class: +// double still_need( ) const +// Postcondition: The return value is the ounces of food that the animal +// still needs to survive the current week (i.e., its total weekly need +// minus the amount that it has already eaten this week.) +// +// double total_need( ) const +// Postcondition: The return value is the total amount of food that the +// animal needs to survive one week (measured in ounces). +// +// +// DOCUMENTATION for the herbivore class: +// plant is a derived class of the animal class. All the animal public +// member functions are inherited by a herbivore. In addition, a herbivore has +// this extra member function: +// +// CONSTRUCTOR for the herbivore class: +// herbivore(double init_size=0, double init_rate=0, double init_need=0) +// Same as the animal constructor. +// +// MODIFICATION MEMBER FUNCTIONS for the herbivore class: +// void nibble(plant& meal) +// Postcondition: eat(amount) and meal.nibbled_on(amount) have both been +// activated. The amount is usually half of the plant, but it will never be +// more than 10% of the herbivore's weekly need, nor more than the amount that +// the animal still needs to eat to survive this week. +// +// +// VALUE SEMANTICS for the organism class and its derived classes: +// Assignments and the copy constructor may be used with all objects. + +#ifndef ORGANISM_H // Prevent duplicate definition +#define ORGANISM_H + +namespace main_savitch_14 +{ + class organism + { + public: + // CONSTRUCTOR + organism(double init_size = 1, double init_rate = 0); + // MODIFICATION FUNCTIONS + void simulate_week( ) { alter_size(rate); } + void assign_rate(double new_rate) { rate = new_rate; } + void alter_size(double amount); + void death( ); + // CONSTANT FUNCTIONS + double get_size( ) const { return size; } + double get_rate( ) const { return rate; } + bool is_alive( ) const { return (size > 0); } + private: + double size; + double rate; + }; + + class plant : public organism + { + public: + // CONSTRUCTOR + plant(double init_size = 1, double init_rate = 0); + // MODIFICATION FUNCTIONS + void nibbled_on(double amount); + }; + + class animal : public organism + { + public: + // CONSTRUCTOR + animal(double init_size = 1, double init_rate = 0, double init_need = 0); + // MODIFICATION FUNCTIONS + void assign_need(double new_need); + void eat(double amount); + void simulate_week( ); // Overriden from the organism class + // CONSTANT FUNCTIONS + double still_need( ) const; + double total_need( ) const { return need_each_week; } + private: + double need_each_week; + double eaten_this_week; + }; + + class herbivore : public animal + { + public: + // CONSTRUCTOR + herbivore(double init_size = 1, double init_rate = 0, double init_need = 0); + // MODIFICATION FUNCTIONS + void nibble(plant& meal); + }; +} + +#endif diff --git a/chapter14/play_connect4.cxx b/chapter14/play_connect4.cxx new file mode 100644 index 0000000..c15bf5c --- /dev/null +++ b/chapter14/play_connect4.cxx @@ -0,0 +1,30 @@ +#include +#include +#include +#include "connect4.h" +using namespace main_savitch_14; + +int main( ) +{ + connect4 instance; + connect4::who winner; + char answer; + string restline; + + do + { + winner = instance.play( ); + switch (winner) + { + case connect4::HUMAN: cout << "You win" << endl; break; + case connect4::COMPUTER: cout << "I win" << endl; break; + case connect4::NEUTRAL: cout << "A draw" << endl; break; + } + cout << "Do you want to play again? [Y/N] "; + cin >> answer; + getline(cin, restline); + } while (toupper(answer) == 'Y'); + + return EXIT_SUCCESS; +} + diff --git a/chapter14/pondlife.cxx b/chapter14/pondlife.cxx new file mode 100644 index 0000000..87fc20e --- /dev/null +++ b/chapter14/pondlife.cxx @@ -0,0 +1,126 @@ +// FILE: pondlife.cxx +// A simple simulation program to model the fish and weeds in a pond + +#include // Provides cin, cout +#include // Provides setw +#include // Provides EXIT_SUCCESS, rand, size_t +#include // Provides the vector template class +#include "organism.h" // Provides Herbivore, Plant classes +using namespace std; +using namespace main_savitch_14; + +// PROGRAM CONSTANTS +const size_t MANY_WEEDS = 2000; // Number of weeds in the pond +const double WEED_SIZE = 15; // Initial size of each weed, in ounces +const double WEED_RATE = 2.5; // Growth rate of weeds, in ounces/week +const size_t INIT_FISH = 300; // Initial number of fish in the pond +const double FISH_SIZE = 50; // Fish size, in ounces +const double FRACTION = 0.5; // A fish must eat FRACTION times its size + // during one week or it will die. +const int AVERAGE_NIBBLES = 30; // Average number of plants nibbled by + // a fish over one week. +const double BIRTH_RATE = 0.05; // At the end of each week, some fish have + // babies. The total number of new fish + // born is the current number of fish times + // the BIRTH_RATE (rounded down to an + // integer). + +// Samples weed and fish objects to copy into the vectors of the main program: +const plant SAMPLE_WEED(WEED_SIZE, WEED_RATE); +const herbivore SAMPLE_FISH(FISH_SIZE, 0, FISH_SIZE * FRACTION); + +// PROTOTYPES for the functions used in the program: +void pond_week(vector& fish, vector& weeds); +// Precondition: weeds.size( ) > 0. +// Postcondition: On average, each fish has nibbled on AVERAGE_NIBBLES plants, +// and then simulate_week has been activated for each fish and each weed. Any +// fish that died are removed from the fish bag, and then +// BIRTH_RATE * fish.size( ) new fish have been added to the fish bag. + +double total_mass(const vector& collection); +// Postcondition: The return value is the total mass of all the plants in the +// collection. + + +int main( ) +{ + vector weeds(MANY_WEEDS, SAMPLE_WEED); // A vector of weeds + vector fish(INIT_FISH, SAMPLE_FISH); // A vector of weeds + int many_weeks; // Number of weeks to simulate + int i; // Loop control variable + + // Get number of weeks, and format the output. + cout << "How many weeks shall I simulate? "; + cin >> many_weeks; + cout.setf(ios::fixed); + cout << "Week Number Plant Mass" << endl; + cout << " of Fish (in ounces)" << endl; + + // Simulate the weeks. + for (i = 1; i <= many_weeks; i++) + { + pond_week(fish, weeds); + cout << setw(4) << i; + cout << setw(10) << fish.size( ); + cout << setw(14) << setprecision(0) << total_mass(weeds); + cout << endl; + } + + return EXIT_SUCCESS; +} + +double total_mass(const vector& collection) +{ + double answer; + vector::const_iterator p; + answer = 0; + for (p = collection.begin( ); p != collection.end( ); ++p) + answer += p->get_size( ); + + return answer; +} + +void pond_week(vector& fish, vector& weeds) +{ + // Variables for an index and an iterator for the weeds: + vector::iterator wi; + vector::size_type weed_index; + + // Variables for an index, an iterator, and counters for the fish: + vector::iterator fi; + vector::size_type fish_index; + vector::size_type new_fish_population; + + size_t many_iterations; // How many random nibbles to simulate + size_t i; // Loop counter + + // Have randomly selected fish nibble on randomly selected plants. + many_iterations = AVERAGE_NIBBLES * fish.size( ); + for (i = 0; i < many_iterations; ++i) + { + fish_index = rand( ) % fish.size( ); // Index of a random fish + weed_index = rand( ) % weeds.size( ); // Index of a random weed + fish[fish_index].nibble(weeds[weed_index]); + } + + // Simulate the weeks for the weeds. + for (wi = weeds.begin( ); wi != weeds.end( ); ++wi) + wi->simulate_week( ); + + // Simulate the weeks for the fish, and count how many died. + fi = fish.begin( ); + while (fi != fish.end( )) + { + fi->simulate_week( ); + if (!fi->is_alive( )) + fish.erase(fi); + else + ++fi; + } + + // Calculate the new number of fish, and reset the fish vector to this size. + // If this adds new fish to the vector, then those new fish will be equal to + // the SAMPLE_FISH that is used for all our fish: + new_fish_population = (1 + BIRTH_RATE) * fish.size( ); + fish.resize(new_fish_population, SAMPLE_FISH); +} diff --git a/chapter15/graph.h b/chapter15/graph.h new file mode 100644 index 0000000..7bfb1ac --- /dev/null +++ b/chapter15/graph.h @@ -0,0 +1,99 @@ +// FILE: graph.h (part of the namespace main_savitch_15) +// TEMPLATE CLASS PROVIDED: graph (a class for labeled graphs) +// The vertices of an n-vertex graph are numbered from zero to n-1. Each vertex +// has a label of type Item. It may be any of the C++ built-in types (int, +// char, etc.), or any class with a default constructor and an assignment +// operator. The graph may not have multiple edges. +// +// MEMBER CONSTANTS for the graph template class: +// static const size_t MAXIMUM = ______ +// graph::MAXIMUM is the maximum number of vertices that a graph can have. +// +// CONSTRUCTOR for the graph template class: +// graph( ) +// Postcondition: The graph has been initialized with no vertices and no edges. +// +// MODIFICATION MEMBER FUNCTIONS for the graph template class: +// void add_vertex(const Item& label) +// Precondition: size( ) < MAXIMUM. +// Postcondition: The size of the graph has been increased by adding one new +// vertex. This new vertex has the specified label and no edges. +// +// void add_edge(size_t source, size_t target) +// Precondition: (source < size( )) and (target < size( )). +// Postcondition: The graph has all the edges that it originally had, and it +// also has another edge from the specified source to the specified target. +// (If this edge was already present, then the graph is unchanged.) +// +// void remove_edge(size_t soure, size_t target) +// Precondition: (source < size( )) and (target < size( )). +// Postcondition: The graph has all the edges that it originally had except +// for the edge from the specified source to the specified target. (If this +// edge was not originally present, then the graph is unchanged.) +// +// Item& operator [ ] (size_t vertex) +// Precondition: vertex < size( ). +// Postcondition: The return value is a reference to the label of the +// specified vertex. +// +// CONSTANT MEMBER FUNCTIONS for the graph template class: +// size_t size( ) const +// Postcondition: The return value is the number of vertices in the graph. +// +// bool is_edge(size_t source, size_t target) const +// Precondition: (source < size( )) and (target < size( )). +// Postcondition: The return value is true if the graph has an edge from +// source to target. Otherwise the return value is false. +// +// set neighbors(size_t vertex) const +// Precondition: (vertex < size( )). +// Postcondition: The return value is a set that contains all the vertex +// numbers of vertices that are the target of an edge whose source is at +// the specified vertex. +// +// Item operator [ ] (size_t vertex) const +// Precondition: vertex < size( ). +// Postcondition: The return value is a reference to the label of the +// specified vertex. +// NOTE: This function differs from the other operator [ ] because its +// return value is simply a copy of the Item (rather than a reference of +// type Item&). Since this function returns only a copy of the Item, it is +// a const member function. +// +// VALUE SEMANTICS for the graph template class: +// Assignments and the copy constructor may be used with graph objects. + +#ifndef MAIN_SAVITCH_GRAPH_H +#define MAIN_SAVITCH_GRAPH_H +#include // Provides size_t +#include // Provides set + +namespace main_savitch_15 +{ + template + class graph + { + public: + // MEMBER CONSTANTS + static const std::size_t MAXIMUM = 20; + // CONSTRUCTOR + graph( ) { many_vertices = 0; } + // MODIFICATION MEMBER FUNCTIONS + void add_vertex(const Item& label); + void add_edge(std::size_t source, std::size_t target); + void remove_edge(std::size_t source, std::size_t target); + Item& operator [ ] (std::size_t vertex); + // CONSTANT MEMBER FUNCTIONS + std::size_t size( ) const { return many_vertices; } + bool is_edge(std::size_t source, std::size_t target) const; + std::set neighbors(std::size_t vertex) const; + Item operator[ ] (std::size_t vertex) const; + private: + bool edges[MAXIMUM][MAXIMUM]; + Item labels[MAXIMUM]; + std::size_t many_vertices; + }; +} + +#include "graph.template" // Include the implementation. +#endif diff --git a/chapter15/graph.template b/chapter15/graph.template new file mode 100644 index 0000000..781568a --- /dev/null +++ b/chapter15/graph.template @@ -0,0 +1,100 @@ +// FILE: graph.template (part of the namespace main_savitch_15) +// TEMPLATE CLASS IMPLEMENTED: graph (See graph.h for documentation.) +// This file is included in the header file and not compiled separately. +// INVARIANT for the graph class: +// 1. The number of vertices in the graph is stored in the member variable +// many_vertices. +// 1. These vertices are numbered from 0 to many_vertices-1. +// 2. edges is the adjacency matrix for the graph (with true in edges[i][j] +// to indicate an edge from vertex i to vertex j). +// 3. For each i < many_vertices, labels[i] is the label of vertex i. + +#include // Provides assert +#include // Provides size_t +#include // Provides set + +namespace main_savitch_15 +{ + template + const std::size_t graph::MAXIMUM; + + template + void graph::add_edge(std::size_t source, std::size_t target) + // Library facilities used: cassert, cstdlib + { + assert(source < size( )); + assert(target < size( )); + edges[source][target] = true; + } + + template + void graph::add_vertex(const Item& label) + // Library facilities used: cassert, cstdlib + { + std::size_t new_vertex_number; + std::size_t other_number; + + assert(size( ) < MAXIMUM); + new_vertex_number = many_vertices; + many_vertices++; + for (other_number = 0; other_number < many_vertices; ++other_number) + { + edges[other_number][new_vertex_number] = false; + edges[new_vertex_number][other_number] = false; + } + labels[new_vertex_number] = label; + } + + template + bool graph::is_edge(std::size_t source, std::size_t target) const + // Library facilities used: cassert, cstdlib + { + assert(source < size( )); + assert(target < size( )); + return edges[source][target]; + } + + template + Item& graph::operator[ ] (std::size_t vertex) + // Library facilities used: cassert, cstdlib + { + assert(vertex < size( )); + return labels[vertex]; // Returns a reference to the label + } + + template + Item graph::operator[ ] (std::size_t vertex) const + // Library facilities used: cassert, cstdlib + { + assert(vertex < size( )); + return labels[vertex]; // Returns only a copy of the label + } + + template + std::set graph::neighbors(std::size_t vertex) const + // Library facilities used: cassert, cstdlib, set + { + std::set answer; + std::size_t i; + + assert(vertex < size( )); + + for (i = 0; i < size( ); ++i) + { + if (edges[vertex][i]) + answer.insert(i); + } + return answer; + } + + template + void graph::remove_edge(std::size_t source, std::size_t target) + // Library facilities used: cassert, cstdlib + { + assert(source < size( )); + assert(target < size( )); + edges[source][target] = false; + } +} + + diff --git a/chapter15/searches.h b/chapter15/searches.h new file mode 100644 index 0000000..1570a1f --- /dev/null +++ b/chapter15/searches.h @@ -0,0 +1,48 @@ +// FILE: searches.h (part of namespace main_savitch_15) +// This file provides three template functions for searching graphs +// from the graph template class of graph.h +// +// template +// void rec_dfs(Process f, graph& g, SizeType v, bool marked[]) +// Precondition: g is a labeled graph that is being traversed by a +// depth-first search. For each vertex x, marked[x] is true if x has +// already been visited by this search, otherwise marked[x] is false. +// The vertex v is an unmakred vertex that the search has just arrived at. +// Postcondition: the depth-first search of g has been continued +// through vertex v and beyond to all the vertices that can be reached +// from v via a path of unmarked vertices. The function f has been +// applied to the labe of each vertex visited by the search, and each +// such vertex x has also been marked by setting marked[x] to true. +// +// template +// void depth_first(Process f, graph& g, SizeType start) +// Precondion: start is a vertex number of the labeled graph g. +// Postcondition: A depth-first search of g has been executed, +// starting at the start vertex. The function f has been applied to the +// label of each vertex visited by the search. +// +// template +// void breadth_first(Process f, graph& g, SizeType start) +// Precondition: start is a vertex number of the labeled graph g. +// Postcondition: A breadth-first search of g has been executed, +// starting at the start vertex. The function f has been applied to the +// label of each vertex visited by the search. + +#ifndef SEARCHES_H +#define SEARCHES_H +#include "graph.h" + +namespace main_savitch_15 +{ + template + void rec_dfs(Process f, graph& g, SizeType v, bool marked[]); + + template + void depth_first(Process f, graph& g, SizeType start); + + template + void breadth_first(Process f, graph& g, SizeType start); +} + +#include "searches.template" // Include the implementation. +#endif diff --git a/chapter15/searches.template b/chapter15/searches.template new file mode 100644 index 0000000..536ba27 --- /dev/null +++ b/chapter15/searches.template @@ -0,0 +1,93 @@ +// FILE: searches.template +// TEMPLATE FUNCTIONS IMPLEMENTED: rec_dfs, depth_first, and breadth_first. +// Please see searches.h for documentation of these functions. +// This file is included at the bottom of searches.h, and should not be +// separately compiled. + +#include +#include +#include +#include +#include +#include "graph.h" + +namespace main_savitch_15 +{ + template + void rec_dfs(Process f, graph& g, SizeType v, bool marked[]) + // Precondition: g is a labeled graph that is being traversed by a + // depth-first search. For each vertex x, marked[x] is true if x has + // already been visited by this search, otherwise marked[x] is false. + // The vertex v is an unmakred vertex that the search has just arrived at. + // Postcondition: the depth-first search of g has been continued + // through vertex v and beyond to all the vertices that can be reached + // from v via a path of unmarked vertices. The function f has been + // applied to the labe of each vertex visited by the search, and each + // such vertex x has also been marked by setting marked[x] to true. + // Library facilities used: cstdlib, graph.h, set + { + std::set connections = g.neighbors(v); + std::set::iterator it; + + marked[v] = true; // Mark vertex v + f(g[v]); // Process the label of vertex v with the function f + + // Traverse all the neighbors, looking for unmarked vertices: + for (it = connections.begin( ); it != connections.end( ); ++it) + { + if (!marked[*it]) + rec_dfs(f, g, *it, marked); + } + } + + template + void depth_first(Process f, graph& g, SizeType start) + // Precondion: start is a vertex number of the labeled graph g. + // Postcondition: A depth-first search of g has been executed, + // starting at the start vertex. The function f has been applied to the + // label of each vertex visited by the search. + // Library facilities used: algorithm, cassert, graph.h + { + bool marked[g.MAXIMUM]; + + assert(start < g.size( )); + std::fill_n(marked, g.size( ), false); + rec_dfs(f, g, start, marked); + } + + template + void breadth_first(Process f, graph& g, SizeType start) + // Precondition: start is a vertex number of the labeled graph g. + // Postcondition: A breadth-first search of g has been executed, + // starting at the start vertex. The function f has been applied to the + // label of each vertex visited by the search. + // Library facilities used: algorithm, cassert, cstdlib, graph.h, queue + { + bool marked[g.MAXIMUM]; + std::set connections; + std::set::iterator it; + std::queue vertex_queue; + assert(start < g.size( )); + std::fill_n(marked, g.size( ), false); + marked[start] = true; + f(g[start]); + vertex_queue.push(start); + do + { + connections = g.neighbors(vertex_queue.front( )); + vertex_queue.pop( ); + // Mark and process the unmarked neighbors, + // and place them in the queue. + for (it = connections.begin( ); it != connections.end( ); ++it) + { + if (!marked[*it]) + { + marked[*it] = true; + f(g[*it]); + vertex_queue.push(*it); + } + } + } + while (!vertex_queue.empty( )); + } +} diff --git a/chapter2/demo1.cxx b/chapter2/demo1.cxx new file mode 100644 index 0000000..4c8bcca --- /dev/null +++ b/chapter2/demo1.cxx @@ -0,0 +1,79 @@ +// FILE: demo1.cxx +// This small demonstration shows how the throttle class is used. + +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +using namespace std; // Allows all Standard Library items to be used +class throttle +{ +public: + // MODIFICATION MEMBER FUNCTIONS + void shut_off( ); + void shift(int amount); + // CONSTANT MEMBER FUNCTIONS + double flow( ) const; + bool is_on( ) const; +private: + int position; +}; + +int main( ) +{ + throttle sample; + int user_input; + // Set the sample throttle to a position indicated by the user. + cout << "I have a throttle with 6 positions." << endl; + cout << "Where would you like to set the throttle? " << endl; + cout << "Please type a number from 0 to 6: "; + cin >> user_input; + sample.shut_off( ); + sample.shift(user_input); + // Shift the throttle down to zero, printing the flow along the way. + while (sample.is_on( )) + { + cout << "The flow is now " << sample.flow( ) << endl; + sample.shift(-1); + } + cout << "The flow is now off" << endl; + return EXIT_SUCCESS; +} + +void throttle::shut_off( ) +// Precondition: None. +// Postcondition: The throttle has been turned off. +{ + position = 0; +} + +double throttle::flow( ) const +// Precondition: shut_off has been called at least once to initialize the +// throttle. +// Postcondition: The value returned is the current flow as a proportion of +// the maximum flow. +{ + return position / 6.0; +} + +void throttle::shift(int amount) +// Precondition: shut_off has been called at least once to initialize the +// throttle. +// Postcondition: The throttle's position has been moved by amount (but not +// below 0 or above 6). +{ + position += amount; + + // Adjust the throttle if it went too high or too low + if (position < 0) + position = 0; + else if (position > 6) + position = 6; +} + +bool throttle::is_on( ) const +// Precondition: shut_off has been called at least once to initialize the +// throttle. +// Postcondition: If the throttle's flow is above 0 then the function +// returns true; otherwise it returns false. +{ + return (flow( ) > 0); +} diff --git a/chapter2/demo2.cxx b/chapter2/demo2.cxx new file mode 100644 index 0000000..89f4bb6 --- /dev/null +++ b/chapter2/demo2.cxx @@ -0,0 +1,31 @@ +// FILE: demo2.cxx +// This small demonstration shows how the revised throttle class is used. +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "throttle.h" // Provides the throttle class +using namespace std; // Allows all Standard Library items to be used +using main_savitch_2A::throttle; + +const int DEMO_SIZE = 5; // Number of positions in a demonstration throttle + +int main( ) +{ + throttle sample(DEMO_SIZE); // A throttle to use for our demonstration + int user_input; // The position that we set the throttle to + + // Set the sample throttle to a position indicated by the user. + cout << "I have a throttle with " << DEMO_SIZE << " positions." << endl; + cout << "Where would you like to set the throttle?" << endl; + cout << "Please type a number from 0 to " << DEMO_SIZE << ": "; + cin >> user_input; + sample.shift(user_input); + + // Shift the throttle down to zero, printing the flow along the way. + while (sample.is_on( )) + { + cout << "The flow is now " << sample.flow( ) << endl; + sample.shift(-1); + } + cout << "The flow is now off" << endl; + return EXIT_SUCCESS; +} diff --git a/chapter2/newpoint.cxx b/chapter2/newpoint.cxx new file mode 100644 index 0000000..f3f40f4 --- /dev/null +++ b/chapter2/newpoint.cxx @@ -0,0 +1,120 @@ +// FILE: newpoint.cxx +// CLASS IMPLEMENTED: point (See newpoint.h for documentation.) + +#include +#include +#include "newpoint.h" +using namespace std; + +namespace main_savitch_2B +{ + point::point(double initial_x, double initial_y) + { + x = initial_x; // Constructor sets point to a given position + y = initial_y; + } + + void point::shift(double x_amount, double y_amount) + { + x += x_amount; + y += y_amount; + } + + void point::rotate90( ) + { + double new_x; + double new_y; + + new_x = y; // For a 90 degree clockwise rotation the new y is -1 + new_y = -x; // times original x, and the new x is the original y + x = new_x; + y = new_y; + } + + bool operator ==(const point& p1, const point& p2) + { + return + (p1.get_x( ) == p2.get_x( )) + && + (p1.get_y( ) == p2.get_y( )); + } + + bool operator !=(const point& p1, const point& p2) + { + return !(p1 == p2); + } + + point operator +(const point& p1, const point& p2) + { + double x_sum, y_sum; + + // Compute the x and y of the sum + x_sum = (p1.get_x( ) + p2.get_x( )); + y_sum = (p1.get_y( ) + p2.get_y( )); + point sum(x_sum, y_sum); + return sum; + } + + ostream& operator <<(ostream& outs, const point& source) + // Library facilities used: iostream + { + outs << source.get_x( ) << " " << source.get_y( ); + return outs; + } + + istream& operator >>(istream& ins, point& target) + // Library facilities used: iostream + // Friend of: point class + { + ins >> target.x >> target.y; + return ins; + } + + int rotations_needed(point p) + { + int answer; + + answer = 0; + while ((p.get_x( ) < 0) || (p.get_y( ) < 0)) + { + p.rotate90( ); + ++answer; + } + return answer; + } + + void rotate_to_upper_right(point& p) + { + while ((p.get_x( ) < 0) || (p.get_y( ) < 0)) + p.rotate90( ); + } + + double distance(const point& p1, const point& p2) + // Library facilities used: cmath + { + double a, b, c_squared; + + // Calculate differences in x and y coordinates + a = p1.get_x( ) - p2.get_x( ); // Difference in x coordinates + b = p1.get_y( ) - p2.get_y( ); // Difference in y coordinates + + // Pythagorean Theorem to calculate square of distance between points + c_squared = a*a + b*b; + + return sqrt(c_squared); // sqrt calculates square root (from math.h) + } + + point middle(const point& p1, const point& p2) + { + double x_midpoint, y_midpoint; + + // Compute the x and y midpoints + x_midpoint = (p1.get_x( ) + p2.get_x( )) / 2; + y_midpoint = (p1.get_y( ) + p2.get_y( )) / 2; + + // Construct a new point and return it + point midpoint(x_midpoint, y_midpoint); + return midpoint; + } +} + diff --git a/chapter2/newpoint.h b/chapter2/newpoint.h new file mode 100644 index 0000000..159f1fb --- /dev/null +++ b/chapter2/newpoint.h @@ -0,0 +1,82 @@ +// FILE: newpoint.h (revised from point.h in Figure 2.9 on page 58) +// CLASS PROVIDED: point (an ADT for a point on a two-dimensional plane) +// +// CONSTRUCTOR for the point class: +// point(double initial_x = 0.0, double initial_y = 0.0) +// Postcondition: The point has been set to (initial_x, initial_y). +// +// MODIFICATION MEMBER FUNCTIONS for the point class: +// void shift(double x_amount, double y_amount) +// Postcondition: The point has been moved by x_amount along the x axis +// and by y_amount along the y axis. +// +// void rotate90( ) +// Postcondition: The point has been rotated clockwise 90 degrees. +// +// CONSTANT MEMBER FUNCTIONS for the point class: +// double get_x( ) const +// Postcondition: The value returned is the x coordinate of the point. +// +// double get_y( ) const +// Postcondition: The value returned is the y coordinate of the point. +// +// NONMEMBER FUNCTIONS for the point class: +// double distance(const point& p1, const point& p2) +// Postcondition: The value returned is the distance between p1 and p2. +// +// point middle(const point& p1, const point& p2) +// Postcondition: The point returned is halfway between p1 and p2. +// +// point operator +(const point& p1, const point& p2) +// Postcondition: The sum of p1 and p2 is returned. +// +// bool operator ==(const point& p1, const point& p2) +// Postcondition: The return value is true if p1 and p2 are identical. +// +// bool operator !=(const point& p1, const point& p2) +// Postcondition: The return value is true if p1 and p2 are not identical. +// +// ostream& operator <<(ostream& outs, const point& source) +// Postcondition: The x and y coordinates of source have been +// written to outs. The return value is the ostream outs. +// +// istream& operator >>(istream& ins, point& target) +// Postcondition: The x and y coordinates of target have been +// read from ins. The return value is the istream ins. +// +// VALUE SEMANTICS for the point class: +// Assignments and the copy constructor may be used with point objects. + +#ifndef MAIN_SAVITCH_NEWPOINT_H +#define MAIN_SAVITCH_NEWPOINT_H +#include // Provides ostream and istream + +namespace main_savitch_2B +{ + class point + { + public: + // CONSTRUCTOR + point(double initial_x = 0.0, double initial_y = 0.0); + // MODIFICATION MEMBER FUNCTIONS + void shift(double x_amount, double y_amount); + void rotate90( ); + // CONSTANT MEMBER FUNCTIONS + double get_x( ) const { return x; } + double get_y( ) const { return y; } + // FRIEND FUNCTION + friend std::istream& operator >>(std::istream& ins, point& target); + private: + double x, y; // x and y coordinates of this point + }; + + // NONMEMBER FUNCTIONS for the point class + double distance(const point& p1, const point& p2); + point middle(const point& p1, const point& p2); + point operator +(const point& p1, const point& p2); + bool operator ==(const point& p1, const point& p2); + bool operator !=(const point& p1, const point& p2); + std::ostream& operator <<(std::ostream & outs, const point& source); +} + +#endif diff --git a/chapter2/point.cxx b/chapter2/point.cxx new file mode 100644 index 0000000..9b56f9e --- /dev/null +++ b/chapter2/point.cxx @@ -0,0 +1,33 @@ +// FILE: point.cxx +// CLASS IMPLEMENTED: point (See point.h for documentation.) + +#include "point.h" + +namespace main_savitch_2A +{ + + point::point(double initial_x, double initial_y) + { + x = initial_x; // Constructor sets the point to a given position. + y = initial_y; + } + + + void point::shift(double x_amount, double y_amount) + { + x += x_amount; + y += y_amount; + } + + + void point::rotate90( ) + { + double new_x; + double new_y; + + new_x = y; // For a 90 degree clockwise rotation, the new x is the original y, + new_y = -x; // and the new y is -1 times the original x. + x = new_x; + y = new_y; + } +} diff --git a/chapter2/point.h b/chapter2/point.h new file mode 100644 index 0000000..d1da6a0 --- /dev/null +++ b/chapter2/point.h @@ -0,0 +1,49 @@ +// FILE: point.h +// CLASS PROVIDED: point (part of the namespace main_savitch_chapter2) +// +// CONSTRUCTOR for the point class: +// point(double initial_x = 0.0, double initial_y = 0.0) +// Postcondition: The point has been set to (initial_x, initial_y). +// +// MODIFICATION MEMBER FUNCTIONS for the point class: +// void shift(double x_amount, double y_amount) +// Postcondition: The point has been moved by x_amount along the x axis +// and by y_amount along the y axis. +// +// void rotate90( ) +// Postcondition: The point has been rotated clockwise 90 degrees around +// the origin. +// +// CONSTANT MEMBER FUNCTIONS for the point class: +// double get_x( ) const +// Postcondition: The value returned is the x coordinate of the point. +// +// double get_y( ) const +// Postcondition: The value returned is the y coordinate of the point. +// +// VALUE SEMANTICS for the point class: +// Assignments and the copy constructor may be used with point objects. + +#ifndef MAIN_SAVITCH_POINT_H +#define MAIN_SAVITCH_POINT_H + +namespace main_savitch_2A +{ + class point + { + public: + // CONSTRUCTOR + point(double initial_x = 0.0, double initial_y = 0.0); + // MODIFICATION MEMBER FUNCTIONS + void shift(double x_amount, double y_amount); + void rotate90( ); + // CONSTANT MEMBER FUNCTIONS + double get_x( ) const { return x; } + double get_y( ) const { return y; } + private: + double x; // x coordinate of this point + double y; // y coordinate of this point + }; +} + +#endif diff --git a/chapter2/throttle.cxx b/chapter2/throttle.cxx new file mode 100644 index 0000000..18b0b6a --- /dev/null +++ b/chapter2/throttle.cxx @@ -0,0 +1,35 @@ +// FILE: throttle.cxx +// CLASS IMPLEMENTED: throttle (See throttle.h for documentation.) + +#include // Provides assert +#include "throttle.h" // Provides the throttle class definition +using namespace std; // Allows all Standard Library items to be used + +namespace main_savitch_2A +{ + + throttle::throttle( ) + { // A simple on-off throttle + top_position = 1; + position = 0; + } + + throttle::throttle(int size) + // Library facilities used: cassert + { + assert(size > 0); + top_position = size; + position = 0; + } + + void throttle::shift(int amount) + { + position += amount; + + if (position < 0) + position = 0; + else if (position > top_position) + position = top_position; + } + +} diff --git a/chapter2/throttle.h b/chapter2/throttle.h new file mode 100644 index 0000000..8707b37 --- /dev/null +++ b/chapter2/throttle.h @@ -0,0 +1,58 @@ +// FILE: throttle.h +// CLASS PROVIDED: throttle (part of the namespace main_savitch_chapter2) +// +// CONSTRUCTORS for the throttle class: +// throttle( ) +// Postcondition: The throttle has one position above the shut_off position, +// and it is currently shut off. +// +// throttle(int size) +// Precondition: size > 0. +// Postcondition: The throttle has size positions above the shut_off +// position, and it is currently shut off. +// +// MODIFICATION MEMBER FUNCTIONS for the throttle class: +// void shut_off( ) +// Postcondition: The throttle has been turned off. +// +// void shift(int amount) +// Postcondition: The throttle's position has been moved by +// amount (but not below 0 or above the top position). +// +// CONSTANT MEMBER FUNCTIONS for the throttle class: +// double flow( ) const +// Postcondition: The value returned is the current flow as a +// proportion of the maximum flow. +// +// bool is_on( ) const +// Postcondition: If the throttle's flow is above 0 then +// the function returns true; otherwise it returns false. +// +// VALUE SEMANTICS for the throttle class: (See discussion on page 51.) +// Assignments and the copy constructor may be used with throttle objects. + +#ifndef MAIN_SAVITCH_THROTTLE +#define MAIN_SAVITCH_THROTTLE + +namespace main_savitch_2A +{ + class throttle + { + public: + // CONSTRUCTORS + throttle( ); + throttle(int size); + // MODIFICATION MEMBER FUNCTIONS + void shut_off( ) { position = 0; } + void shift(int amount); + // CONSTANT MEMBER FUNCTIONS + double flow( ) const { return position / double(top_position); } + bool is_on( ) const { return (position > 0); } + private: + int top_position; + int position; + }; + +} + +#endif 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 // Provides copy function +#include // 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 // 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 // Provides cout and cin +#include // 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 // 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 // Provides toupper +#include // Provides cout and cin +#include // 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; +} 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; +} 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 // Provides assert +#include // 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 // 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 Binary files /dev/null and b/chapter5/bag3.zip differ 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 // Provides cout and cin +#include // 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 // Provides assert +#include // 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 // 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 diff --git a/chapter6/author.cxx b/chapter6/author.cxx new file mode 100644 index 0000000..04156a1 --- /dev/null +++ b/chapter6/author.cxx @@ -0,0 +1,63 @@ +// FILE: author.cxx +// A demonstration program showing how the bag template class is used. +// The program reads some words into bags of Strings, and some numbers into +// a bag of integers. Then a silly story is written using these words. + +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include // Provides string class +#include "bag4.h" // Provides the bag template class +using namespace std; +using namespace main_savitch_6A; + +const int ITEMS_PER_BAG = 4; // Number of items to put into each bag +const int MANY_SENTENCES = 3; // Number of sentences in the silly story + +// PROTOTYPE for a function used by this demonstration program +template +void get_items(bag& collection, SizeType n, MessageType description) +// Postcondition: The string description has been written as a prompt to the +// screen. Then n items have been read from cin and added to the collection. +// Library facilities used: iostream, bag4.h +{ + Item user_input; // An item typed by the program's user + SizeType i; + + cout << "Please type " << n << " " << description; + cout << ", separated by spaces.\n"; + cout << "Press the key after the final entry:\n"; + for (i = 1; i <= n; ++i) + { + cin >> user_input; + collection.insert(user_input); + } + cout << endl; +} + +int main( ) +{ + bag adjectives; // Contains adjectives typed by user + bag ages; // Contains ages in the teens typed by user + bag names; // Contains names typed by user + int line_number; // Number of the output line + + // Fill the three bags with items typed by the program's user. + cout << "Help me write a story.\n"; + get_items(adjectives, ITEMS_PER_BAG, "adjectives that describe a mood"); + get_items(ages, ITEMS_PER_BAG, "integers in the teens"); + get_items(names, ITEMS_PER_BAG, "first names"); + cout << "Thank you for your kind assistance.\n\n"; + + // Use the items to write a silly story. + cout << "LIFE\n"; + cout << "by A. Computer\n"; + for (line_number = 1; line_number <= MANY_SENTENCES; ++line_number) + cout << names.grab( ) << " was only " + << ages.grab( ) << " years old, but he/she was " + << adjectives.grab( ) << ".\n"; + cout << "Life is " << adjectives.grab( ) << ".\n"; + cout << "The (" << adjectives.grab( ) << ") end\n"; + + return EXIT_SUCCESS; +} + diff --git a/chapter6/author.exe b/chapter6/author.exe new file mode 100644 index 0000000..2cb1e66 Binary files /dev/null and b/chapter6/author.exe differ diff --git a/chapter6/author.o b/chapter6/author.o new file mode 100644 index 0000000..c372ee6 Binary files /dev/null and b/chapter6/author.o differ diff --git a/chapter6/bag4.h b/chapter6/bag4.h new file mode 100644 index 0000000..3dfc532 --- /dev/null +++ b/chapter6/bag4.h @@ -0,0 +1,113 @@ +// FILE: bag4.h (part of the namespace main_savitch_6A) +// TEMPLATE CLASS PROVIDED: bag +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the bag class: +// The template parameter, Item, is the data type of the items in the bag, +// also defined as bag::value_type. 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). The definition bag::size_type is the data type +// of any variable that keeps track of how many items are in a bag. The static +// const DEFAULT_CAPACITY is the initial capacity of a bag created by the +// default constructor. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions bag::value_type and bag::size_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the bag template 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 template class: +// size_type erase(const Item& 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 Item& target) +// Postcondition: If target was in the bag, then one copy of target 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 Item& entry) +// Postcondition: A new copy of entry has been added to the bag. +// +// void operator +=(const bag& addend) +// Postcondition: Each item in addend has been added to this bag. +// +// void reserve(size_type new_capacity) +// Postcondition: The bag's current capacity is changed to new_capacity +// (but not less than the number of items currently in the bag). The insert +// function will work efficiently without allocating new memory) until the +// capacity is reached. +// +// CONSTANT MEMBER FUNCTIONS for the bag template class: +// size_type count(const Item& target) const +// Postcondition: Return value is number of times target is in the bag. +// +// Item grab( ) const +// Precondition: size( ) > 0 +// Postcondition: The return value is a randomly selected item from the bag. +// +// size_type size( ) const +// Postcondition: The return value is the total number of items in the bag. +// +// NONMEMBER FUNCTIONS for the bag template class: +// template +// bag operator +(const bag& b1, const bag& b2) +// Postcondition: The bag returned is the union of b1 and b2. +// +// VALUE SEMANTICS for the bag template class: +// Assignments and the copy constructor may be used with bag objects. +// +// DYNAMIC MEMORY USAGE by the bag template class: +// If there is insufficient dynamic memory, then the following functions call +// new_handler: the constructors, resize, insert, operator += , operator +, +// and the assignment operator. + +#ifndef MAIN_SAVITCH_BAG4_H +#define MAIN_SAVITCH_BAG4_H +#include // Provides size_t + +namespace main_savitch_6A +{ + template + class bag + { + public: + // TYPEDEFS and MEMBER CONSTANTS + typedef Item 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); + ~bag( ); + // MODIFICATION MEMBER FUNCTIONS + size_type erase(const Item& target); + bool erase_one(const Item& target); + void insert(const Item& entry); + void operator =(const bag& source); + void operator +=(const bag& addend); + void reserve(size_type capacity); + // CONSTANT MEMBER FUNCTIONS + size_type count(const Item& target) const; + Item grab( ) const; + size_type size( ) const { return used; } + private: + Item *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 + template + bag operator +(const bag& b1, const bag& b2); +} + +#include "bag4.template" // Include the implementation +#endif diff --git a/chapter6/bag4.template b/chapter6/bag4.template new file mode 100644 index 0000000..6ccccff --- /dev/null +++ b/chapter6/bag4.template @@ -0,0 +1,194 @@ +// FILE: bag4.template +// TEMPLATE CLASS IMPLEMENTED: bag (see bag4.h for documentation) +// NOTE: +// Since node is a template class, this file is included in node2.h. +// Therefore, we should not put any using directives in this file. +// INVARIANT for the bag ADT: +// 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 +#include // Provides assert +#include // Provides rand + +namespace main_savitch_6A +{ + // MEMBER CONSTANTS *********************************************: + template + const typename bag::size_type bag::DEFAULT_CAPACITY; + + + // CONSTRUCTORS and DESTRUCTORS *********************************: + template + bag::bag(size_type initial_capacity) + { + data = new Item[initial_capacity]; + capacity = initial_capacity; + used = 0; + } + + template + bag::bag(const bag& source) + // Library facilities used: algorithm + { + data = new Item[source.capacity]; + capacity = source.capacity; + used = source.used; + std::copy(source.data, source.data + used, data); + } + + template + bag::~bag( ) + { + delete [ ] data; + } + + + // MODIFICATION MEMBER FUNCTIONS (alphabetically): ***************: + template + typename bag::size_type bag::erase(const Item& 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; + } + + template + bool bag::erase_one(const Item& 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. + for (index = 0; (index < used) && (data[index] != target); ++index) + ; // No work in the body of this loop. + + 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; + } + + template + void bag::insert(const Item& entry) + { + if (used == capacity) + reserve(used+1); + data[used] = entry; + ++used; + } + + template + void bag::operator =(const bag& source) + // Library facilities used: algorithm + { + Item *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 Item[source.capacity]; + delete [ ] data; + data = new_data; + capacity = source.capacity; + } + + // Copy the data from the source array: + used = source.used; + std::copy(source.data, source.data + used, data); + } + + template + void bag::operator +=(const bag& addend) + // Library facilities used: algorithm + { + if (used + addend.used > capacity) + reserve(used + addend.used); + + std::copy(addend.data, addend.data + addend.used, data + used); + used += addend.used; + } + + template + void bag::reserve(size_type new_capacity) + // Library facilities used: algorithm + { + Item *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 Item[new_capacity]; + std::copy(data, data + used, larger_array); + delete [ ] data; + data = larger_array; + capacity = new_capacity; + } + + + // CONST MEMBER FUNCTIONS (alphabetically): *********************: + template + typename bag::size_type bag::count + (const Item& target) const + { + size_type answer; + size_type i; + + answer = 0; + for (i = 0; i < used; ++i) + if (target == data[i]) + ++answer; + return answer; + } + + template + Item bag::grab( ) const + // Library facilities used: cassert, cstdlib + { + size_type i; + + assert(size( ) > 0); + i = (std::rand( ) % size( )); // i is in the range of 0 to size( ) - 1. + return data[i]; + } + + + // NON-MEMBER FUNCTIONS: ****************************************: + template + bag operator +(const bag& b1, const bag& b2) + { + bag answer(b1.size( ) + b2.size( )); + + answer += b1; + answer += b2; + return answer; + } + +} diff --git a/chapter6/bag4demo.cxx b/chapter6/bag4demo.cxx new file mode 100644 index 0000000..994bb3d --- /dev/null +++ b/chapter6/bag4demo.cxx @@ -0,0 +1,64 @@ +// FILE: bag4demo.cxx +// Demonstration program for the 4th version of the bag +// (from bag4.h and bag4.template). +// This is a the same as the demonstration program for bag1, +// except that we are now using a template class, and we no longer need to +// check whether the bag reaches its capacity. + +#include // Provides cout and cin +#include // Provides EXIT_SUCCESS +#include "bag4.h" // Provides the bag template class +using namespace std; +using namespace main_savitch_6A; + +// 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/chapter6/bag5.h b/chapter6/bag5.h new file mode 100644 index 0000000..a71435c --- /dev/null +++ b/chapter6/bag5.h @@ -0,0 +1,128 @@ +// FILE: bag5.h (part of the namespace main_savitch_chapter6) +// TEMPLATE CLASS PROVIDED: +// bag (a collection of items; each item may appear multiple times) +// +// TYPEDEFS for the bag template class: +// bag::value_type +// This is the Item type from the template parameter. +// It 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 +// This is the data type of any variable that keeps track of how many items +// are in a bag +// +// bag::iterator and bag::const_iterator +// Forward iterators for a bag or a const bag. +// +// CONSTRUCTOR for the bag class: +// bag( ) +// Postcondition: The bag is empty. +// +// MODIFICATION MEMBER FUNCTIONS for the bag class: +// size_type erase(const Item& 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 Item& 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 Item& 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 count(const Item& target) const +// Postcondition: Return value is number of times target is in the bag. +// +// Item grab( ) const +// Precondition: size( ) > 0. +// Postcondition: The return value is a randomly selected item from the bag. +// +// size_type size( ) const +// Postcondition: Return value is the total number of items in the bag. +// +// STANDARD ITERATOR MEMBER FUNCTIONS (provide a forward iterator): +// iterator begin( ) +// const_iterator begin( ) const +// iterator end( ) +// const iterator end( ) const +// +// NONMEMBER FUNCTIONS for the bag class: +// template +// 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_BAG5_H +#define MAIN_SAVITCH_BAG5_H +#include // Provides NULL and size_t and NULL +#include "node2.h" // Provides node class + +namespace main_savitch_6B +{ + template + class bag + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + typedef node_iterator iterator; + typedef const_node_iterator const_iterator; + + // CONSTRUCTORS and DESTRUCTOR + bag( ); + bag(const bag& source); + ~bag( ); + + // MODIFICATION MEMBER FUNCTIONS + size_type erase(const Item& target); + bool erase_one(const Item& target); + void insert(const Item& entry); + void operator +=(const bag& addend); + void operator =(const bag& source); + + // CONST MEMBER FUNCTIONS + size_type count(const Item& target) const; + Item grab( ) const; + size_type size( ) const { return many_nodes; } + + // FUNCTIONS TO PROVIDE ITERATORS + iterator begin( ) + { return iterator(head_ptr); } + const_iterator begin( ) const + { return const_iterator(head_ptr); } + iterator end( ) + { return iterator( ); } // Uses default constructor + const_iterator end( ) const + { return const_iterator( ); } // Uses default constructor + + private: + node *head_ptr; // Head pointer for the list of items + size_type many_nodes; // Number of nodes on the list + }; + + // NONMEMBER functions for the bag + template + bag operator +(const bag& b1, const bag& b2); +} + +// The implementation of a template class must be included in its header file: +#include "bag5.template" +#endif + diff --git a/chapter6/bag5.template b/chapter6/bag5.template new file mode 100644 index 0000000..9d22436 --- /dev/null +++ b/chapter6/bag5.template @@ -0,0 +1,164 @@ +// FILE: bag5.template +// CLASS implemented: bag (see bag5.h for documentation) +// NOTE: +// Since bag is a template class, this file is included in node2.h. +// INVARIANT for the bag class: +// 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 // Provides assert +#include // Provides NULL, rand +#include "node2.h" // Provides node + +namespace main_savitch_6B +{ + template + bag::bag( ) + // Library facilities used: cstdlib + { + head_ptr = NULL; + many_nodes = 0; + } + + template + bag::bag(const bag& source) + // Library facilities used: node2.h + { + node *tail_ptr; // Needed for argument of list_copy + + list_copy(source.head_ptr, head_ptr, tail_ptr); + many_nodes = source.many_nodes; + } + + template + bag::~bag( ) + // Library facilities used: node2.h + { + list_clear(head_ptr); + many_nodes = 0; + } + + template + typename bag::size_type bag::count(const Item& target) const + // Library facilities used: cstdlib, node2.h + { + size_type answer; + const node *cursor; + + 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; + } + + template + typename bag::size_type bag::erase(const Item& target) + // Library facilities used: cstdlib, node2.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. + ++answer; + target_ptr->set_data( head_ptr->data( ) ); + target_ptr = target_ptr->link( ); + target_ptr = list_search(target_ptr, target); + list_head_remove(head_ptr); + } + return answer; + } + + template + bool bag::erase_one(const Item& target) + // Library facilities used: cstdlib, node2.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; + } + + template + Item bag::grab( ) const + // Library facilities used: cassert, cstdlib, node2.h + { + size_type i; + const node *cursor; + + assert(size( ) > 0); + i = (std::rand( ) % size( )) + 1; + cursor = list_locate(head_ptr, i); + return cursor->data( ); + } + + template + void bag::insert(const Item& entry) + // Library facilities used: node2.h + { + list_head_insert(head_ptr, entry); + ++many_nodes; + } + + template + void bag::operator +=(const bag& addend) + // Library facilities used: node2.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; + } + } + + template + void bag::operator =(const bag& source) + // Library facilities used: node2.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; + } + + template + bag operator +(const bag& b1, const bag& b2) + { + bag answer; + + answer += b1; + answer += b2; + return answer; + } + +} diff --git a/chapter6/maximal.cxx b/chapter6/maximal.cxx new file mode 100644 index 0000000..aecd5a9 --- /dev/null +++ b/chapter6/maximal.cxx @@ -0,0 +1,36 @@ +// FILE: maximal.cxx +// A demonstration program for a template function called maximal. + +#include // Provides EXIT_SUCCESS +#include // Provides cout +#include // Provides string class +using namespace std; + +// TEMPLATE FUNCTION used in this demonstration program: +// Note that some compilers require the entire function definition to appear +// before its use (rather than a mere prototype). This maximal function is +// similar to max from . +template +Item maximal(Item a, Item b) +// Postcondition: Returns the larger of a and b. +// Note: Item may be any of the C++ built-in types (int, char, etc.), or a +// class with the > operator and a copy constructor. +{ + if (a > b) + return a; + else + return b; +} + +int main( ) +{ + string s1("frijoles"); + string s2("beans"); + + cout << "Larger of frijoles and beans: " << maximal(s1, s2) << endl; + cout << "Larger of 10 and 20 : " << maximal(10, 20) << endl; + cout << "Larger of $ and @ : " << maximal('$', '@') << endl; + cout << "It's a large world." << endl; + + return EXIT_SUCCESS; +} diff --git a/chapter6/maximal.exe b/chapter6/maximal.exe new file mode 100644 index 0000000..8031ba8 Binary files /dev/null and b/chapter6/maximal.exe differ diff --git a/chapter6/maximal.o b/chapter6/maximal.o new file mode 100644 index 0000000..fe3b6d4 Binary files /dev/null and b/chapter6/maximal.o differ diff --git a/chapter6/node2.h b/chapter6/node2.h new file mode 100644 index 0000000..a161683 --- /dev/null +++ b/chapter6/node2.h @@ -0,0 +1,204 @@ +// FILE: node2.h (part of the namespace main_savitch_6B) +// PROVIDES: A template class for a node in a linked list, and list manipulation +// functions. The template parameter is the type of the data in each node. +// This file also defines a template class: node_iterator. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* parameter) that attaches the iterator +// to the specified node in a linked list, and (2) a default constructor that +// creates a special iterator that marks the position that is beyond the end of a +// linked list. There is also a const_node_iterator for use with +// const node* . +// +// TYPEDEF for the node template class: +// Each node of the list contains a piece of data and a pointer to the +// next node. The type of the data (node::value_type) is the Item type +// from the template parameter. The type may be any of the built-in C++ classes +// (int, char, ...) or a class with a default constructor, an assignment +// operator, and a test for equality (x == y). +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expression node::value_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the node class: +// node( +// const Item& init_data = Item(), +// 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 Item. 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 about two versions of some functions: +// The data function returns a reference to the data field of a node and +// the link function returns a copy of the link field of a node. +// Each of these functions comes in two versions: a const version and a +// non-const version. If the function is activated by a const node, then the +// compiler choses the const version (and the return value is const). +// If the function is activated by a non-const node, then the compiler choses +// the non-const version (and the return value will be non-const). +// EXAMPLES: +// const node *c; +// c->link( ) activates the const version of link returning const node* +// c->data( ) activates the const version of data returning const Item& +// c->data( ) = 42; ... is forbidden +// node *p; +// p->link( ) activates the non-const version of link returning node* +// p->data( ) activates the non-const version of data returning Item& +// p->data( ) = 42; ... actually changes the data in p's node +// +// MEMBER FUNCTIONS for the node class: +// const Item& data( ) const <----- const version +// and +// Item& data( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is a reference to the data from this node. +// +// const node* link( ) const <----- const version +// and +// 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. +// +// void set_data(const Item& 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. +// +// FUNCTIONS in the linked list toolkit: +// template +// 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. +// +// template +// 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. +// +// template +// void list_head_insert(node*& head_ptr, const Item& 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. +// +// template +// 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. +// +// template +// void list_insert(node* previous_ptr, const Item& 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. +// +// template +// 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. +// +// template +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list, and +// position > 0. +// Postcondition: The return value is a pointer that 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. +// +// template +// 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. +// +// template +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The return value is a pointer that points to the first +// node containing the specified target in its data member. If there is no +// such node, the null pointer is returned. +// +// 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. + +#ifndef MAIN_SAVITCH_NODE2_H +#define MAIN_SAVITCH_NODE2_H +#include // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + class node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + node(const Item& init_data=Item( ), node* init_link=NULL) + { data_field = init_data; link_field = init_link; } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + node* link( ) { return link_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_link(node* new_link) { link_field = new_link; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const node* link( ) const { return link_field; } + private: + Item data_field; + node *link_field; + }; + + // FUNCTIONS to manipulate a linked list: + template + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + NodePtr list_search(NodePtr head_ptr, const Item& target); + +} + +#include "node2.template" +#endif diff --git a/chapter6/node2.template b/chapter6/node2.template new file mode 100644 index 0000000..6b3a56a --- /dev/null +++ b/chapter6/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template +// IMPLEMENTS: The functions of the node template class and the +// linked list toolkit (see node2.h for documentation). +// +// NOTE: +// Since node is a template class, this file is included in node2.h. +// Therefore, we should not put any using directives in this file. +// +// INVARIANT for the node class: +// The data of a node is stored in data_field, and the link in link_field. + +#include // Provides assert +#include // Provides NULL and size_t + +namespace main_savitch_6B +{ + template + void list_clear(node*& head_ptr) + // Library facilities used: cstdlib + { + while (head_ptr != NULL) + list_head_remove(head_ptr); + } + + template + 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 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( ); + } + } + + template + void list_head_insert(node*& head_ptr, const Item& entry) + { + head_ptr = new node(entry, head_ptr); + } + + template + void list_head_remove(node*& head_ptr) + { + node *remove_ptr; + + remove_ptr = head_ptr; + head_ptr = head_ptr->link( ); + delete remove_ptr; + } + + template + void list_insert(node* previous_ptr, const Item& entry) + { + node *insert_ptr; + + insert_ptr = new node(entry, previous_ptr->link( )); + previous_ptr->set_link(insert_ptr); + } + + template + std::size_t list_length(const node* head_ptr) + // Library facilities used: cstdlib + { + const node *cursor; + std::size_t answer; + + answer = 0; + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + ++answer; + + return answer; + } + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position) + // Library facilities used: cassert, cstdlib + { + NodePtr cursor; + SizeType i; + + assert(0 < position); + cursor = head_ptr; + for (i = 1; (i < position) && (cursor != NULL); ++i) + cursor = cursor->link( ); + return cursor; + } + + template + void list_remove(node* previous_ptr) + { + node *remove_ptr; + + remove_ptr = previous_ptr->link( ); + previous_ptr->set_link(remove_ptr->link( )); + delete remove_ptr; + } + + template + NodePtr list_search(NodePtr head_ptr, const Item& target) + // Library facilities used: cstdlib + { + NodePtr cursor; + + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + if (target == cursor->data( )) + return cursor; + return NULL; + } +} diff --git a/chapter7/calc.cxx b/chapter7/calc.cxx new file mode 100644 index 0000000..795617a --- /dev/null +++ b/chapter7/calc.cxx @@ -0,0 +1,101 @@ +// FILE: calc.cxx +// Basic calculator program that takes a fully parenthesized arithmetic +// expression as input, and evaluates the arithmetic expression. +// The purpose is to illustrate a fundamental use of stacks. + +#include // Provides isdigit +#include // Provides EXIT_SUCCESS +#include // Provides strchr +#include // Provides cout, cin, peek, ignore +#include // Provides the stack template class +using namespace std; + +// PROTOTYPES for functions used by this demonstration program: +double read_and_evaluate(istream& ins); +// Precondition: The next line of characters in the istream ins is a fully +// parenthesized arithmetic expression formed from non-negative numbers and +// the four operations + - * /. +// Postcondition: A line has been read from the istream ins, and this line has +// been evaluated as an arithmetic expression. The value of the expression has +// been returned by the function. + +void evaluate_stack_tops(stack& numbers, stack& operations); +// Precondition: The top of the operations stack contains + - * or /, and the +// numbers stack contains at least two numbers. +// Postcondition: The top two numbers have been popped from the number stack, +// and the top operation has been popped from the operation stack. The two +// numbers have been combined using the operation (with the second number +// popped as the left operand). The result of the operation has then been +// pushed back onto the numbers stack. + + +int main( ) +{ + double answer; + + cout << "Type a fully parenthesized arithmetic expression:" << endl; + answer = read_and_evaluate(cin); + cout << "That evaluates to " << answer << endl; + + return EXIT_SUCCESS; +} + + +double read_and_evaluate(istream& ins) +// Library facilities used: cstring, iostream, stack +{ + const char DECIMAL = '.'; + const char RIGHT_PARENTHESIS = ')'; + + stack numbers; + stack operations; + double number; + char symbol; + + // Loop continues while istream is not “bad” (tested by ins) and next character isn’t newline. + while (ins && ins.peek( ) != '\n') + { + if (isdigit(ins.peek( )) || (ins.peek( ) == DECIMAL)) + { + ins >> number; + numbers.push(number); + } + else if (strchr("+-*/", ins.peek( )) != NULL) + { + ins >> symbol; + operations.push(symbol); + } + else if (ins.peek( ) == RIGHT_PARENTHESIS) + { + ins.ignore( ); + evaluate_stack_tops(numbers, operations); + } + else + ins.ignore( ); + } + + return numbers.top( ); +} + +void evaluate_stack_tops(stack& numbers, stack& operations) +// Library facilities used: stack +{ + double operand1, operand2; + + operand2 = numbers.top( ); + numbers.pop( ); + operand1 = numbers.top( ); + numbers.pop( ); + switch (operations.top( )) + { + case '+': numbers.push(operand1 + operand2); + break; + case '-': numbers.push(operand1 - operand2); + break; + case '*': numbers.push(operand1 * operand2); + break; + case '/': numbers.push(operand1 / operand2); + break; + } + operations.pop( ); +} diff --git a/chapter7/calc.exe b/chapter7/calc.exe new file mode 100644 index 0000000..6d9a552 Binary files /dev/null and b/chapter7/calc.exe differ diff --git a/chapter7/calc.o b/chapter7/calc.o new file mode 100644 index 0000000..d8095aa Binary files /dev/null and b/chapter7/calc.o differ diff --git a/chapter7/ch7files-stack.zip b/chapter7/ch7files-stack.zip new file mode 100644 index 0000000..2e25458 Binary files /dev/null and b/chapter7/ch7files-stack.zip differ diff --git a/chapter7/node2.h b/chapter7/node2.h new file mode 100644 index 0000000..a161683 --- /dev/null +++ b/chapter7/node2.h @@ -0,0 +1,204 @@ +// FILE: node2.h (part of the namespace main_savitch_6B) +// PROVIDES: A template class for a node in a linked list, and list manipulation +// functions. The template parameter is the type of the data in each node. +// This file also defines a template class: node_iterator. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* parameter) that attaches the iterator +// to the specified node in a linked list, and (2) a default constructor that +// creates a special iterator that marks the position that is beyond the end of a +// linked list. There is also a const_node_iterator for use with +// const node* . +// +// TYPEDEF for the node template class: +// Each node of the list contains a piece of data and a pointer to the +// next node. The type of the data (node::value_type) is the Item type +// from the template parameter. The type may be any of the built-in C++ classes +// (int, char, ...) or a class with a default constructor, an assignment +// operator, and a test for equality (x == y). +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expression node::value_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the node class: +// node( +// const Item& init_data = Item(), +// 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 Item. 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 about two versions of some functions: +// The data function returns a reference to the data field of a node and +// the link function returns a copy of the link field of a node. +// Each of these functions comes in two versions: a const version and a +// non-const version. If the function is activated by a const node, then the +// compiler choses the const version (and the return value is const). +// If the function is activated by a non-const node, then the compiler choses +// the non-const version (and the return value will be non-const). +// EXAMPLES: +// const node *c; +// c->link( ) activates the const version of link returning const node* +// c->data( ) activates the const version of data returning const Item& +// c->data( ) = 42; ... is forbidden +// node *p; +// p->link( ) activates the non-const version of link returning node* +// p->data( ) activates the non-const version of data returning Item& +// p->data( ) = 42; ... actually changes the data in p's node +// +// MEMBER FUNCTIONS for the node class: +// const Item& data( ) const <----- const version +// and +// Item& data( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is a reference to the data from this node. +// +// const node* link( ) const <----- const version +// and +// 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. +// +// void set_data(const Item& 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. +// +// FUNCTIONS in the linked list toolkit: +// template +// 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. +// +// template +// 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. +// +// template +// void list_head_insert(node*& head_ptr, const Item& 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. +// +// template +// 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. +// +// template +// void list_insert(node* previous_ptr, const Item& 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. +// +// template +// 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. +// +// template +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list, and +// position > 0. +// Postcondition: The return value is a pointer that 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. +// +// template +// 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. +// +// template +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The return value is a pointer that points to the first +// node containing the specified target in its data member. If there is no +// such node, the null pointer is returned. +// +// 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. + +#ifndef MAIN_SAVITCH_NODE2_H +#define MAIN_SAVITCH_NODE2_H +#include // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + class node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + node(const Item& init_data=Item( ), node* init_link=NULL) + { data_field = init_data; link_field = init_link; } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + node* link( ) { return link_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_link(node* new_link) { link_field = new_link; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const node* link( ) const { return link_field; } + private: + Item data_field; + node *link_field; + }; + + // FUNCTIONS to manipulate a linked list: + template + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + NodePtr list_search(NodePtr head_ptr, const Item& target); + +} + +#include "node2.template" +#endif diff --git a/chapter7/node2.template b/chapter7/node2.template new file mode 100644 index 0000000..6b3a56a --- /dev/null +++ b/chapter7/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template +// IMPLEMENTS: The functions of the node template class and the +// linked list toolkit (see node2.h for documentation). +// +// NOTE: +// Since node is a template class, this file is included in node2.h. +// Therefore, we should not put any using directives in this file. +// +// INVARIANT for the node class: +// The data of a node is stored in data_field, and the link in link_field. + +#include // Provides assert +#include // Provides NULL and size_t + +namespace main_savitch_6B +{ + template + void list_clear(node*& head_ptr) + // Library facilities used: cstdlib + { + while (head_ptr != NULL) + list_head_remove(head_ptr); + } + + template + 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 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( ); + } + } + + template + void list_head_insert(node*& head_ptr, const Item& entry) + { + head_ptr = new node(entry, head_ptr); + } + + template + void list_head_remove(node*& head_ptr) + { + node *remove_ptr; + + remove_ptr = head_ptr; + head_ptr = head_ptr->link( ); + delete remove_ptr; + } + + template + void list_insert(node* previous_ptr, const Item& entry) + { + node *insert_ptr; + + insert_ptr = new node(entry, previous_ptr->link( )); + previous_ptr->set_link(insert_ptr); + } + + template + std::size_t list_length(const node* head_ptr) + // Library facilities used: cstdlib + { + const node *cursor; + std::size_t answer; + + answer = 0; + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + ++answer; + + return answer; + } + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position) + // Library facilities used: cassert, cstdlib + { + NodePtr cursor; + SizeType i; + + assert(0 < position); + cursor = head_ptr; + for (i = 1; (i < position) && (cursor != NULL); ++i) + cursor = cursor->link( ); + return cursor; + } + + template + void list_remove(node* previous_ptr) + { + node *remove_ptr; + + remove_ptr = previous_ptr->link( ); + previous_ptr->set_link(remove_ptr->link( )); + delete remove_ptr; + } + + template + NodePtr list_search(NodePtr head_ptr, const Item& target) + // Library facilities used: cstdlib + { + NodePtr cursor; + + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + if (target == cursor->data( )) + return cursor; + return NULL; + } +} diff --git a/chapter7/parens.cxx b/chapter7/parens.cxx new file mode 100644 index 0000000..c388ed6 --- /dev/null +++ b/chapter7/parens.cxx @@ -0,0 +1,54 @@ +// FILE: parens.cxx +// A small demonstration program for a stack. +#include // Provides EXIT_SUCCESS +#include // Provides cin, cout +#include // Provides stack +#include // Provides string +using namespace std; + +// PROTOTYPE for a function used by this demonstration program +bool is_balanced(const string& expression); +// Postcondition: A true return value indicates that the parentheses in the +// given expression are balanced. Otherwise, the return value is false. + +int main( ) +{ + string user_input; + + cout << "Type a string with some parentheses:\n"; + getline(cin, user_input); + + if (is_balanced(user_input)) + cout << "Those parentheses are balanced.\n"; + else + cout << "Those parentheses are not balanced.\n"; + + cout << "That ends this balancing act.\n"; + return EXIT_SUCCESS; +} + +bool is_balanced(const string& expression) +// Library facilities used: stack, string +{ + // Meaningful names for constants + const char LEFT_PARENTHESIS = '('; + const char RIGHT_PARENTHESIS = ')'; + + stack store; // Stack to store the left parentheses as they occur + string::size_type i; // An index into the string + char next; // The next character from the string + bool failed = false; // Becomes true if a needed parenthesis is not found + + for (i = 0; !failed && (i < expression.length( )); ++i) + { + next = expression[i]; + if (next == LEFT_PARENTHESIS) + store.push(next); + else if ((next == RIGHT_PARENTHESIS) && (!store.empty( ))) + store.pop( ); // Pops the corresponding left parenthesis. + else if ((next == RIGHT_PARENTHESIS) && (store.empty( ))) + failed = true; + } + + return (store.empty( ) && !failed); +} diff --git a/chapter7/parens.exe b/chapter7/parens.exe new file mode 100644 index 0000000..094d044 Binary files /dev/null and b/chapter7/parens.exe differ diff --git a/chapter7/parens.o b/chapter7/parens.o new file mode 100644 index 0000000..a06a15f Binary files /dev/null and b/chapter7/parens.o differ diff --git a/chapter7/stack1.h b/chapter7/stack1.h new file mode 100644 index 0000000..d6ea8fe --- /dev/null +++ b/chapter7/stack1.h @@ -0,0 +1,79 @@ +// FILE: stack1.h (part of the namespace main_savitch_7A) +// TEMPLATE CLASS PROVIDED: stack +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack class: +// The template parameter, Item, is the data type of the items in the stack, +// also defined as stack::value_type. It may be any of the C++ built-in +// types (int, char, etc.), or a class with a default constructor, a copy +// constructor, and an assignment operator. The definition +// stack::size_type is the data type of any variable that keeps track of +// how many items are in a stack. The static const CAPACITY is the +// maximum capacity of a stack for this first stack implementation. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions stack::value_type and stack::size_type. +// Otherwise the compiler doesn't have enough information to realize that it +// is the name of a data type. +// +// CONSTRUCTOR for the stack template class: +// stack( ) +// Postcondition: The stack has been initialized as an empty stack. +// +// MODIFICATION MEMBER FUNCTIONS for the stack class: +// void push(const Item& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been pushed onto the stack. +// +// Item pop( ) +// Precondition: size( ) > 0. +// Postcondition: The top item of the stack has been removed. +// +// CONSTANT MEMBER FUNCTIONS for the stack class: +// bool empty( ) const +// Postcondition: Return value is true if the stack is empty. +// +// size_type size( ) const +// Postcondition: Return value is the total number of items in the stack. +// +// Item top( ) +// Precondition: size( ) > 0. +// Postcondition: The return value is the top item of the stack but the +// stack is unchanged. This differs slightly from the STL stack (where +// the top function returns a reference to the item on top of the stack). +// +// VALUE SEMANTICS for the stack class: +// Assignments and the copy constructor may be used with stack +// objects. + +#ifndef MAIN_SAVITCH_STACK1_H +#define MAIN_SAVITCH_STACK1_H +#include // Provides size_t + +namespace main_savitch_7A +{ + template + class stack + { + public: + // TYPEDEFS AND MEMBER CONSTANT -- See Appendix E if this fails to compile. + typedef std::size_t size_type; + typedef Item value_type; + static const size_type CAPACITY = 30; + // CONSTRUCTOR + stack( ) { used = 0; } + // MODIFICATION MEMBER FUNCTIONS + void push(const Item& entry); + void pop( ); + // CONSTANT MEMBER FUNCTIONS + bool empty( ) const { return (used == 0); } + size_type size( ) const { return used; } + Item top( ) const; + private: + Item data[CAPACITY]; // Partially filled array + size_type used; // How much of array is being used + }; +} + +#include "stack1.template" // Include the implementation. +#endif + diff --git a/chapter7/stack1.template b/chapter7/stack1.template new file mode 100644 index 0000000..ad311c2 --- /dev/null +++ b/chapter7/stack1.template @@ -0,0 +1,41 @@ +// FILE: stack1.template +// TEMPLATE CLASS IMPLEMENTED: stack (see stack1.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the stack class: +// 1. The number of items in the stack is in the member variable used. +// 2. The actual items of the stack are stored in a partially-filled +// array data[0]..data[used-1]. The stack elements appear from the +// bottom (at data[0]) to the top (at data[used-1]). + +#include // Provides assert + +namespace main_savitch_7A +{ + template + const typename stack::size_type stack::CAPACITY; + + template + void stack::push(const Item& entry) + // Library facilities used: cassert + { + assert(size( ) < CAPACITY); + data[used] = entry; + ++used; + } + + template + void stack::pop( ) + // Library facilities used: cassert + { + assert(!empty( )); + --used; + } + + template + Item stack::top( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return data[used-1]; + } +} diff --git a/chapter7/stack2.h b/chapter7/stack2.h new file mode 100644 index 0000000..739f1ad --- /dev/null +++ b/chapter7/stack2.h @@ -0,0 +1,78 @@ +// FILE: stack2.h (part of the namespace main_savitch_7B) +// TEMPLATE CLASS PROVIDED: stack (a stack of items) +// The template parameter, Item, is the data type of the items in the stack, +// also defined as stack::value_type. +// It may be any of the C++ built-in types (int, char, etc.), or a class +// with a default constructor, a copy constructor, and an assignment +// operator. The definition stack::size_type is the data type of +// any variable that keeps track of how many items are in a stack. +// +// CONSTRUCTOR for the stack template class: +// stack( ) +// Postcondition: The stack has been initialized as an empty stack. +// +// MODIFICATION MEMBER FUNCTIONS for the stack class: +// void push(const Item& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been pushed onto the stack. +// +// Item pop( ) +// Precondition: size( ) > 0. +// Postcondition: The top item of the stack has been removed. +// +// CONSTANT MEMBER FUNCTIONS for the stack class: +// bool empty( ) const +// Postcondition: Return value is true if the stack is empty. +// +// size_type size( ) const +// Postcondition: Return value is the total number of items in the stack. +// +// Item top( ) +// Precondition: size( ) > 0. +// Postcondition: The return value is the top item of the stack (but the +// stack is unchanged. This differs slightly from the STL stack (where +// the top function returns a reference to the item on top of the stack). +// +// VALUE SEMANTICS for the stack class: +// Assignments and the copy constructor may be used with stack +// objects. +// +// DYNAMIC MEMORY USAGE by the stack template class: +// If there is insufficient dynamic memory, then the following functions +// throw bad_alloc: +// the copy constructor, push, and the assignment operator. + +#ifndef MAIN_SAVITCH_STACK2_H +#define MAIN_SAVITCH_STACK2_H +#include // Provides NULL and size_t +#include "node2.h" // Node template class from Figure 6.5 on page 308 + +namespace main_savitch_7B +{ + template + class stack + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + // CONSTRUCTORS and DESTRUCTOR + stack( ) { top_ptr = NULL; } + stack(const stack& source); + ~stack( ) { list_clear(top_ptr); } + // MODIFICATION MEMBER FUNCTIONS + void push(const Item& entry); + void pop( ); + void operator =(const stack& source); + // CONSTANT MEMBER FUNCTIONS + size_type size( ) const + { return main_savitch_6B::list_length(top_ptr); } + bool empty( ) const { return (top_ptr == NULL); } + Item top( ) const; + private: + main_savitch_6B::node *top_ptr; // Points to top of stack + }; +} + +#include "stack2.template" // Include the implementation +#endif diff --git a/chapter7/stack2.template b/chapter7/stack2.template new file mode 100644 index 0000000..e02d827 --- /dev/null +++ b/chapter7/stack2.template @@ -0,0 +1,59 @@ +// FILE: stack2.template +// TEMPLATE CLASS IMPLEMENTED: stack (see stack2.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the stack class: +// 1. The items in the stack are stored in a linked list, with the top of the +// stack stored at the head node, down to the bottom of the stack at the +// final node. +// 2. The member variable top_ptr is the head pointer of the linked list. + +#include // Provides assert +#include "node2.h" // Node template class + +namespace main_savitch_7B +{ + template + stack::stack(const stack& source) + // Library facilities used: node2.h + { + main_savitch_6B::node *tail_ptr; // Needed for argument of list_copy + + list_copy(source.top_ptr, top_ptr, tail_ptr); + } + + template + void stack::push(const Item& entry) + // Library facilities used: node2.h + { + list_head_insert(top_ptr, entry); + } + + template + void stack::pop( ) + // Library facilities used: cassert, node2.h + { + assert(!empty( )); + list_head_remove(top_ptr); + } + + template + void stack::operator =(const stack& source) + // Library facilities used: node2.h + { + main_savitch_6B::node *tail_ptr; // Needed for argument of list_copy + + if (this == &source) // Handle self-assignment + return; + + list_clear(top_ptr); + list_copy(source.top_ptr, top_ptr, tail_ptr); + } + + template + Item stack::top( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return top_ptr->data( ); + } +} diff --git a/chapter8/carwash.cxx b/chapter8/carwash.cxx new file mode 100644 index 0000000..09c074f --- /dev/null +++ b/chapter8/carwash.cxx @@ -0,0 +1,73 @@ +// FILE: carwash.cxx +// A small test program to test the car_wash_simulate function. + +#include // Provides cout +#include // Provides EXIT_SUCCESS +#include // Provides queue +#include "washing.h" // Provides averager, bool_source, washer +using namespace std; +using namespace main_savitch_8A; + +void car_wash_simulate +(unsigned int wash_time, double arrival_prob, unsigned int total_time); +// Precondition: 0 <= arrival_prob <= 1. +// Postcondition: The function has simulated a car wash where wash_time is the +// number of seconds needed to wash one car, arrival_prob is the probability +// of a customer arriving in any second, and total_time is the total number +// of seconds for the simulation. Before the simulation, the function has +// written its three parameters to cout. After the simulation, the function +// has written two pieces of information to cout: (1) The number of +// cars washed, and (2) The average waiting time of a customer. + +int main( ) +{ + // Wash takes 240 seconds + // Customers arrive on average once every 400 seconds + // Total simulation time is 6000 seconds + car_wash_simulate(240, 1.0/400, 6000); + + return EXIT_SUCCESS; +} + +void car_wash_simulate +(unsigned int wash_time, double arrival_prob, unsigned int total_time) +// Library facilities used: iostream, queue, washing.h +{ + queue arrival_times; // Waiting customer’s time stamps + unsigned int next; // A value taken from the queue + bool_source arrival(arrival_prob); + washer machine(wash_time); + averager wait_times; + unsigned int current_second; + + // Write the parameters to cout. + cout << "Seconds to wash one car: " << wash_time << endl; + cout << "Probability of customer arrival during a second: "; + cout << arrival_prob << endl; + cout << "Total simulation seconds: " << total_time << endl; + + for (current_second = 1; current_second <= total_time; ++current_second) + { // Simulate the passage of one second of time. + + // Check whether a new customer has arrived. + if (arrival.query( )) + arrival_times.push(current_second); + + // Check whether we can start washing another car. + if ((!machine.is_busy( )) && (!arrival_times.empty( ))) + { + next = arrival_times.front( ); + arrival_times.pop( ); + wait_times.next_number(current_second - next); + machine.start_washing( ); + } + + // Tell the washer to simulate the passage of one second. + machine.one_second( ); + } + + // Write the summary information about the simulation. + cout << "Customers served: " << wait_times.how_many_numbers( ) << endl; + if (wait_times.how_many_numbers( ) > 0) + cout << "Average wait: " << wait_times.average( ) << " sec" << endl; +} diff --git a/chapter8/ch8queueFiles.zip b/chapter8/ch8queueFiles.zip new file mode 100644 index 0000000..27a7522 Binary files /dev/null and b/chapter8/ch8queueFiles.zip differ diff --git a/chapter8/node2.h b/chapter8/node2.h new file mode 100644 index 0000000..9b0df72 --- /dev/null +++ b/chapter8/node2.h @@ -0,0 +1,270 @@ +// FILE: node2.h (part of the namespace main_savitch_6B) +// PROVIDES: A template class for a node in a linked list, and list manipulation +// functions. The template parameter is the type of the data in each node. +// This file also defines a template class: node_iterator. +// The node_iterator is a forward iterators with two constructors: +// (1) A constructor (with a node* parameter) that attaches the iterator +// to the specified node in a linked list, and (2) a default constructor that +// creates a special iterator that marks the position that is beyond the end of a +// linked list. There is also a const_node_iterator for use with +// const node* . +// +// TYPEDEF for the node template class: +// Each node of the list contains a piece of data and a pointer to the +// next node. The type of the data (node::value_type) is the Item type +// from the template parameter. The type may be any of the built-in C++ classes +// (int, char, ...) or a class with a default constructor, an assignment +// operator, and a test for equality (x == y). +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expression node::value_type. Otherwise +// the compiler doesn't have enough information to realize that it is the +// name of a data type. +// +// CONSTRUCTOR for the node class: +// node( +// const Item& init_data = Item(), +// 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 Item. 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 about two versions of some functions: +// The data function returns a reference to the data field of a node and +// the link function returns a copy of the link field of a node. +// Each of these functions comes in two versions: a const version and a +// non-const version. If the function is activated by a const node, then the +// compiler choses the const version (and the return value is const). +// If the function is activated by a non-const node, then the compiler choses +// the non-const version (and the return value will be non-const). +// EXAMPLES: +// const node *c; +// c->link( ) activates the const version of link returning const node* +// c->data( ) activates the const version of data returning const Item& +// c->data( ) = 42; ... is forbidden +// node *p; +// p->link( ) activates the non-const version of link returning node* +// p->data( ) activates the non-const version of data returning Item& +// p->data( ) = 42; ... actually changes the data in p's node +// +// MEMBER FUNCTIONS for the node class: +// const Item& data( ) const <----- const version +// and +// Item& data( ) <----------------- non-const version +// See the note (above) about the const version and non-const versions: +// Postcondition: The return value is a reference to the data from this node. +// +// const node* link( ) const <----- const version +// and +// 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. +// +// void set_data(const Item& 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. +// +// FUNCTIONS in the linked list toolkit: +// template +// 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. +// +// template +// 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. +// +// template +// void list_head_insert(node*& head_ptr, const Item& 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. +// +// template +// 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. +// +// template +// void list_insert(node* previous_ptr, const Item& 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. +// +// template +// 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. +// +// template +// NodePtr list_locate(NodePtr head_ptr, SizeType position) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list, and +// position > 0. +// Postcondition: The return value is a pointer that 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. +// +// template +// 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. +// +// template +// NodePtr list_search +// (NodePtr head_ptr, const Item& target) +// The NodePtr may be either node* or const node* +// Precondition: head_ptr is the head pointer of a linked list. +// Postcondition: The return value is a pointer that points to the first +// node containing the specified target in its data member. If there is no +// such node, the null pointer is returned. +// +// 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. + +#ifndef MAIN_SAVITCH_NODE2_H +#define MAIN_SAVITCH_NODE2_H +#include // Provides NULL and size_t +#include // Provides iterator and forward_iterator_tag + +namespace main_savitch_6B +{ + template + class node + { + public: + // TYPEDEF + typedef Item value_type; + // CONSTRUCTOR + node(const Item& init_data=Item( ), node* init_link=NULL) + { data_field = init_data; link_field = init_link; } + // MODIFICATION MEMBER FUNCTIONS + Item& data( ) { return data_field; } + node* link( ) { return link_field; } + void set_data(const Item& new_data) { data_field = new_data; } + void set_link(node* new_link) { link_field = new_link; } + // CONST MEMBER FUNCTIONS + const Item& data( ) const { return data_field; } + const node* link( ) const { return link_field; } + private: + Item data_field; + node *link_field; + }; + + // FUNCTIONS to manipulate a linked list: + template + void list_clear(node*& head_ptr); + + template + void list_copy + (const node* source_ptr, node*& head_ptr, node*& tail_ptr); + + template + void list_head_insert(node*& head_ptr, const Item& entry); + + template + void list_head_remove(node*& head_ptr); + + template + void list_insert(node* previous_ptr, const Item& entry); + + template + std::size_t list_length(const node* head_ptr); + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position); + + template + void list_remove(node* previous_ptr); + + template + NodePtr list_search(NodePtr head_ptr, const Item& target); + + // FORWARD ITERATORS to step through the nodes of a linked list + // A node_iterator of can change the underlying linked list through the + // * operator, so it may not be used with a const node. The + // node_const_iterator cannot change the underlying linked list + // through the * operator, so it may be used with a const node. + // WARNING: + // This classes use std::iterator as its base class; + // Older compilers that do not support the std::iterator class can + // delete everything after the word iterator in the second line: + + template + class node_iterator + : public std::iterator + { + public: + node_iterator(node* initial = NULL) + { current = initial; } + Item& operator *( ) const + { return current->data( ); } + node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + node_iterator operator ++(int) // Postfix ++ + { + node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const node_iterator other) const + { return current == other.current; } + bool operator !=(const node_iterator other) const + { return current != other.current; } + private: + node* current; + }; + + template + class const_node_iterator + : public std::iterator + { + public: + const_node_iterator(const node* initial = NULL) + { current = initial; } + const Item& operator *( ) const + { return current->data( ); } + const_node_iterator& operator ++( ) // Prefix ++ + { + current = current->link( ); + return *this; + } + const_node_iterator operator ++(int) // Postfix ++ + { + const_node_iterator original(current); + current = current->link( ); + return original; + } + bool operator ==(const const_node_iterator other) const + { return current == other.current; } + bool operator !=(const const_node_iterator other) const + { return current != other.current; } + private: + const node* current; + }; + +} + +#include "node2.template" +#endif diff --git a/chapter8/node2.template b/chapter8/node2.template new file mode 100644 index 0000000..45c3470 --- /dev/null +++ b/chapter8/node2.template @@ -0,0 +1,128 @@ +// FILE: node2.template +// IMPLEMENTS: The functions of the node template class and the +// linked list toolkit (see node2.h for documentation). +// +// NOTE: +// Since node is a template class, this file is included in node2.h. +// Therefore, we should not put any using directives in this file. +// +// INVARIANT for the node class: +// The data of a node is stored in data_field, and the link in link_field. + +#include // Provides assert +#include // Provides NULL and size_t + +namespace main_savitch_6B +{ + template + void list_clear(node*& head_ptr) + // Library facilities used: cstdlib + { + while (head_ptr != NULL) + list_head_remove(head_ptr); + } + + template + 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 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( ); + } + } + + template + void list_head_insert(node*& head_ptr, const Item& entry) + { + head_ptr = new node(entry, head_ptr); + } + + template + void list_head_remove(node*& head_ptr) + { + node *remove_ptr; + + remove_ptr = head_ptr; + head_ptr = head_ptr->link( ); + delete remove_ptr; + } + + template + void list_insert(node* previous_ptr, const Item& entry) + { + node *insert_ptr; + + insert_ptr = new node(entry, previous_ptr->link( )); + previous_ptr->set_link(insert_ptr); + } + + template + std::size_t list_length(const node* head_ptr) + // Library facilities used: cstdlib + { + const node *cursor; + std::size_t answer; + + answer = 0; + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + ++answer; + + return answer; + } + + template + NodePtr list_locate(NodePtr head_ptr, SizeType position) + // Library facilities used: cassert, cstdlib + { + NodePtr cursor; + SizeType i; + + assert(0 < position); + cursor = head_ptr; + for (i = 1; (i < position) && (cursor != NULL); ++i) + cursor = cursor->link( ); + return cursor; + } + + template + void list_remove(node* previous_ptr) + { + node *remove_ptr; + + remove_ptr = previous_ptr->link( ); + previous_ptr->set_link(remove_ptr->link( )); + delete remove_ptr; + } + + template + NodePtr list_search(NodePtr head_ptr, const Item& target) + // Library facilities used: cstdlib + { + NodePtr cursor; + + for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( )) + if (target == cursor->data( )) + return cursor; + return NULL; + } +} diff --git a/chapter8/pal.cxx b/chapter8/pal.cxx new file mode 100644 index 0000000..11153e8 --- /dev/null +++ b/chapter8/pal.cxx @@ -0,0 +1,44 @@ +// FILE: pal.cxx +// Program to test whether an input line is a palindrome. Spaces, +// punctuation, and the difference between upper- and lowercase are ignored. + +#include // Provides assert +#include // Provides isalpha, toupper +#include // Provides EXIT_SUCCESS +#include // Provides cout, cin, peek +#include // Provides the queue template class +#include // Provides the stack template class +using namespace std; + +int main( ) +{ + queue q; + stack s; + char letter; + queue::size_type mismatches = 0; // Mismatches between queue and stack + cout << "Enter a line and I will see if it's a palindrome:" << endl; + + while (cin.peek( ) != '\n') + { + cin >> letter; + if (isalpha(letter)) + { + q.push(toupper(letter)); + s.push(toupper(letter)); + } + } + + while ((!q.empty( )) && (!s.empty( ))) + { + if (q.front( ) != s.top( )) + ++mismatches; + q.pop( ); + s.pop( ); + } + + if (mismatches == 0) + cout << "That is a palindrome." << endl; + else + cout << "That is not a palindrome." << endl; + return EXIT_SUCCESS; +} diff --git a/chapter8/pal.exe b/chapter8/pal.exe new file mode 100644 index 0000000..bc9a38f Binary files /dev/null and b/chapter8/pal.exe differ diff --git a/chapter8/pal.o b/chapter8/pal.o new file mode 100644 index 0000000..8bf34b4 Binary files /dev/null and b/chapter8/pal.o differ diff --git a/chapter8/queue1.h b/chapter8/queue1.h new file mode 100644 index 0000000..bbf47b7 --- /dev/null +++ b/chapter8/queue1.h @@ -0,0 +1,81 @@ +// FILE: queue1.h (part of the namespace main_savitch_8B) +// TEMPLATE CLASS PROVIDED: queue (a queue of items) +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack class: +// The template parameter, Item, is the data type of the items in the queue, +// also defined as queue::value_type. It may be any of the C++ built-in +// types (int, char, etc.), or a class with a default constructor, a copy +// constructor, and an assignment operator. The definition +// queue::size_type is the data type of any variable that keeps track of +// how many items are in a queue. The static const CAPACITY is the +// maximum capacity of a queue for this first queue implementation. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions queue::value_type and queue::size_type. +// Otherwise the compiler doesn't have enough information to realize that it +// is the name of a data type. +// +// CONSTRUCTOR for the queue template class: +// queue( ) +// Postcondition: The queue has been initialized as an empty queue. +// +// MODIFICATION MEMBER FUNCTIONS for the queue template class: +// void pop( ) +// Precondition: size( ) > 0. +// Postcondition: The front item of the queue has been removed. +// +// void push(const Item& entry) +// Precondition: size( ) < CAPACITY. +// Postcondition: A new copy of entry has been inserted at the rear of the +// queue. +// +// CONSTANT MEMBER FUNCTIONS for the queue template class: +// bool empty( ) const +// Postcondition: The return value is true if the queue is empty. +// +// Item front( ) const +// Precondition: size( ) > 0. +// Postcondition: The return value is the front item of the queue (but the queue is +// unchanged). +// +// size_type size( ) const +// Postcondition: The return value is the total number of items in the queue. +// +// VALUE SEMANTICS for the queue template class: +// Assignments and the copy constructor may be used with queue objects. + +#ifndef MAIN_SAVITCH_QUEUE1_H +#define MAIN_SAVITCH_QUEUE1_H +#include // Provides size_t + +namespace main_savitch_8B +{ + template + class queue + { + public: + // TYPEDEFS and MEMBER CONSTANTS -- See Appendix E if this fails to compile. + typedef std::size_t size_type; + typedef Item value_type; + static const size_type CAPACITY = 30; + // CONSTRUCTOR + queue( ); + // MODIFICATION MEMBER FUNCTIONS + void pop( ); + void push(const Item& entry); + // CONSTANT MEMBER FUNCTIONS + bool empty( ) const { return (count == 0); } + Item front( ) const; + size_type size( ) const { return count; } + private: + Item data[CAPACITY]; // Circular array + size_type first; // Index of item at front of the queue + size_type last; // Index of item at rear of the queue + size_type count; // Total number of items in the queue + // HELPER MEMBER FUNCTION + size_type next_index(size_type i) const { return (i+1) % CAPACITY; } + }; +} + +#include "queue1.template" // Include the implementation. +#endif diff --git a/chapter8/queue1.template b/chapter8/queue1.template new file mode 100644 index 0000000..5feee78 --- /dev/null +++ b/chapter8/queue1.template @@ -0,0 +1,55 @@ +// FILE: queue1.template +// TEMPLATE CLASS IMPLEMENTED: queue (see queue1.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the queue class: +// 1. The number of items in the queue is in the member variable count; +// 2. For a non-empty queue, the items are stored in a circular array +// beginning at data[front] and continuing through data[rear]. +// The array's total capacity of the array is CAPACITY. +// 3. For an empty array, rear is some valid index, and front is +// always equal to next_index(rear). +// + +#include // Provides assert + +namespace main_savitch_8B +{ + template + const typename queue::size_type queue::CAPACITY; + + template + queue::queue( ) + { + count = 0; + first = 0; + last = CAPACITY - 1; + } + + template + Item queue::front( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return data[first]; + } + + template + void queue::pop( ) + // Library facilities used: cassert + { + assert(!empty( )); + first = next_index(first); + --count; + } + + template + void queue::push(const Item& entry) + // Library facilities used: cassert + { + assert(size( ) < CAPACITY); + last = next_index(last); + data[last] = entry; + ++count; + } + +} diff --git a/chapter8/queue2.h b/chapter8/queue2.h new file mode 100644 index 0000000..a9a7003 --- /dev/null +++ b/chapter8/queue2.h @@ -0,0 +1,76 @@ +// FILE: queue2.h (part of the namespace +// TEMPLATE CLASS PROVIDED: queue (a queue of items) +// +// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack class: +// The template parameter, Item, is the data type of the items in the queue, +// also defined as queue::value_type. It may be any of the C++ built-in +// types (int, char, etc.), or a class with a default constructor, a copy +// constructor, and an assignment operator. The definition +// queue::size_type is the data type of any variable that keeps track of +// how many items are in a queue. +// NOTE: +// Many compilers require the use of the new keyword typename before using +// the expressions queue::value_type and queue::size_type. +// Otherwise the compiler doesn't have enough information to realize that it +// is the name of a data type. +// +// CONSTRUCTOR for the queue template class: +// queue( ) +// Postcondition: The queue has been initialized as an empty queue. +// +// MODIFICATION MEMBER FUNCTIONS for the queue template class: +// void pop( ) +// Precondition: size( ) > 0. +// Postcondition: The front item of the queue has been removed. +// +// void push(const Item& entry) +// Postcondition: A new copy of entry has been inserted at the rear of the +// queue. +// +// CONSTANT MEMBER FUNCTIONS for the queue template class: +// bool empty( ) const +// Postcondition: The return value is true if the queue is empty. +// +// Item front( ) const +// +// size_type size( ) const +// Postcondition: The return value is the total number of items in the queue. +// +// VALUE SEMANTICS for the queue template class: +// Assignments and the copy constructor may be used with queue objects. + +#ifndef MAIN_SAVITCH_QUEUE2_H // Prevent duplicate definition +#define MAIN_SAVITCH_QUEUE2_H +#include // Provides std::size_t +#include "node2.h" // Node template class + +namespace main_savitch_8C +{ + template + class queue + { + public: + // TYPEDEFS + typedef std::size_t size_type; + typedef Item value_type; + // CONSTRUCTORS and DESTRUCTOR + queue( ); + queue(const queue& source); + ~queue( ); + // MODIFICATION MEMBER FUNCTIONS + void pop( ); + void push(const Item& entry); + void operator =(const queue& source); + // CONSTANT MEMBER FUNCTIONS + bool empty( ) const { return (count == 0); } + Item front( ) const; + size_type size( ) const { return count; } + private: + main_savitch_6B::node *front_ptr; // head_ptr + main_savitch_6B::node *rear_ptr; + size_type count; // Total number of items in the queue + }; +} +#include "queue2.template" // Include the implementation + +#endif diff --git a/chapter8/queue2.template b/chapter8/queue2.template new file mode 100644 index 0000000..d08c1cb --- /dev/null +++ b/chapter8/queue2.template @@ -0,0 +1,88 @@ +// FILE: queue2.template +// TEMPLATE CLASS IMPLEMENTED: Queue (see queue2.h for documentation) +// This file is included in the header file, and not compiled separately. +// INVARIANT for the Queue class: +// 1. The number of items in the queue is stored in the member variable +// count. +// 2. The items in the queue are stored in a linked list, with the front of +// the queue stored at the head node, and the rear of the queue stored at +// the final node. +// 3. The member variable front_ptr is the head pointer of the linked list of +// items. For a non-empty queue, the member variable rear_ptr is the +// tail pointer of the linked list; for an empty list, we don't care +// what's stored in rear_ptr. + +#include // Provides assert +#include "node2.h" // Node template class + +namespace main_savitch_8C +{ + template + queue::queue( ) + { + count = 0; + front_ptr = NULL; + rear_ptr = NULL; + } + + template + queue::queue(const queue& source) + // Library facilities used: node2.h + { + count = source.count; + list_copy(source.front_ptr, front_ptr, rear_ptr); + } + + template + queue::~queue( ) + { + list_clear(front_ptr); + } + + template + void queue::operator =(const queue& source) + // Library facilities used: node2.h + { + if (this == &source) // Handle self-assignment + return; + list_clear(front_ptr); + list_copy(source.front_ptr, front_ptr, rear_ptr); + count = source.count; + } + + template + Item queue::front( ) const + // Library facilities used: cassert + { + assert(!empty( )); + return front_ptr->data( ); + } + + template + void queue::pop( ) + // Library facilities used: cassert, node2.h + { + assert(!empty( )); + list_head_remove(front_ptr); + --count; + } + + template + void queue::push(const Item& entry) + // Library facilities used: node2.h + { + if (empty( )) + { // Insert first entry. + list_head_insert(front_ptr, entry); + rear_ptr = front_ptr; + } + else + { // Insert an entry that is not the first. + list_insert(rear_ptr, entry); + rear_ptr = rear_ptr->link( ); + } + ++count; + } + +} + diff --git a/chapter8/queueFiles.zip b/chapter8/queueFiles.zip new file mode 100644 index 0000000..b1ec1a5 Binary files /dev/null and b/chapter8/queueFiles.zip differ diff --git a/chapter8/washing.cxx b/chapter8/washing.cxx new file mode 100644 index 0000000..d806704 --- /dev/null +++ b/chapter8/washing.cxx @@ -0,0 +1,80 @@ +// FILE: washing.cxx +// CLASSES implemented: bool_source, averager, washer +// +// INVARIANT for the bool_source ADT: +// 1. The member variable probability is the appoximate probability that +// query( ) returns true. +// +// INVARIANT for the averager ADT: +// 1. The member variable count indicates how many numbers the averager has +// been given. +// 2. The member variable sum is the sum of all the numbers that the +// averager has been given. +// +// INVARIANT for the washer class: +// 1. The member variable seconds_for_wash is the number of seconds required +// for one wash. +// 2. The member varible wash_time_left is 0 if the washer is not busy; +// otherwise it is the number of seconds until the washer is free. + +#include // Provides assert +#include // Provides rand, RAND_MAX, size_t +#include "washing.h" // Provides bool_source, averager, washer definitions +using namespace std; + +namespace main_savitch_8A +{ + bool_source::bool_source(double p) + // Library facilities used: cassert + { + assert(p >= 0); + assert(p <= 1); + probability = p; + } + + bool bool_source::query( ) const + // Library facilities used: cstdlib + { + return (rand( ) < probability * RAND_MAX); + } + + averager::averager( ) + { + count = 0; + sum = 0; + } + + void averager::next_number(double value) + { + ++count; + sum += value; + } + + double averager::average( ) const + // Library facilities used: cassert + { + assert(how_many_numbers( ) > 0); + return sum/count; + } + + washer::washer(unsigned int s) + { + seconds_for_wash = s; + wash_time_left = 0; + } + + + void washer::one_second( ) + { + if (is_busy( )) + --wash_time_left; + } + + + void washer::start_washing( ) + // Library facilities used: cassert + { + assert(!is_busy( )); + wash_time_left = seconds_for_wash; + } +} diff --git a/chapter8/washing.h b/chapter8/washing.h new file mode 100644 index 0000000..d019fba --- /dev/null +++ b/chapter8/washing.h @@ -0,0 +1,113 @@ +// FILE: washing.h (part of the namespace main_savitch_8A) +// CLASSES PROVIDED: bool_source, averager, washer. +// +// CONSTRUCTOR for the bool_source class: +// bool_source(double p = 0.5) +// Precondition: 0 <= p <= 1. +// Postcondition: The bool_source has been initialized so that p is the +// approximate probability of returning true in any subsequent activation +// of query( ). +// +// CONSTANT MEMBER FUNCTION for the bool_source class: +// bool query( ) const +// Postcondition: The return value is either true or false, with the +// probability of a true value being approximately p (from the constructor). +// +// CONSTRUCTOR for the averager class: +// averager( ) +// Postcondition: The averager has been initialized so that it +// is ready to accept a sequence of numbers to average. +// +// MODIFICATION MEMBER FUNCTION for the averager class: +// void next_number(double value) +// Postcondition: The averager has accepted value as the next +// number in the sequence of numbers which it is averaging. +// +// CONSTANT MEMBER FUNCTIONS for the averager class: +// size_t how_many_numbers( ) const +// Postcondition: The value returned is a count of how many +// times next_number has been activated. +// +// double average( ) const +// Precondition: how_many_numbers > 0. +// Postcondition: The value returned is the average of all the +// numbers which have been given to the averager. +// +// CONSTRUCTOR for the washer class: +// washer(unsigned int s = 60) +// Precondition: The value of s is the number of seconds needed for +// the completion of one wash cycle. +// Postcondition: The washer has been initialized so that all +// other member functions may be used. +// +// MODIFICATION MEMBER FUNCTIONS for the washer class: +// void one_second( ) +// Postcondition: The washer has recorded (and simulated) the +// passage of one more second of time. +// +// void start_washing( ) +// Precondition: The washer is not busy. +// Postcondition: The washer has started simulating one wash +// cycle. Therefore, is_busy( ) will return true until +// the required number of simulated seconds have occured. +// +// CONSTANT MEMBER FUNCTIONS for the washer class: +// bool is_busy( ) const +// Postcondition: Return value is true if the washer is busy +// (in a wash cycle); otherwise the return value is false. +// +// VALUE SEMANTICS for the bool_source, averager, and washer classes: +// Assignments and the copy constructor may be used with the three classes. +// + +#ifndef MAIN_SAVITCH_WASHING_H +#define MAIN_SAVITCH_WASHING_H +#include // Provides std::size_t + +namespace main_savitch_8A +{ + class bool_source + { + public: + // CONSTRUCTOR + bool_source(double p = 0.5); + // CONSTANT function + bool query( ) const; + private: + double probability; // Probability of query( ) returning true + }; + + class averager + { + public: + // CONSTRUCTOR + averager( ); + // MODIFICATION function + void next_number(double value); + // CONSTANT functions + std::size_t how_many_numbers( ) const { return count; } + double average( ) const; + private: + std::size_t count; // How many numbers have been given to the averager + double sum; // Sum of all the numbers given to the averager + }; + + class washer + { + public: + // CONSTRUCTOR + washer(unsigned int s = 60); + // MODIFICATION functions + void one_second( ); + void start_washing( ); + // CONSTANT function + bool is_busy( ) const { return (wash_time_left > 0); } + private: + unsigned int seconds_for_wash; // Seconds for a single wash + unsigned int wash_time_left; // Seconds until washer no longer busy + }; +} + +#endif + + diff --git a/chapter9/fractal.cxx b/chapter9/fractal.cxx new file mode 100644 index 0000000..be61a84 --- /dev/null +++ b/chapter9/fractal.cxx @@ -0,0 +1,48 @@ +// File: fractal.cxx +// A demonstration program for the random_fractal function from Chapter 9. + +#include // Provides assert +#include // Provides EXIT_SUCCESS +#include // Provides cin, cout +#include "useful.h" // From Appendix H. Provides random_real, display +using namespace std; + +// PROTOTYPE for the function used in this demonstration program. +void random_fractal +(double left_height, double right_height, double width, double epsilon); +// Precondition: width and epsilon are both positive. +// Postcondition: The function has generated a random fractal from a line +// segment. The parameters left_height and right_height are the heights of the +// two endpoints of the line segment, and the parameter width is the segment's +// width. The generation of the random fractal stops when the width of the +// line segments reaches epsilon or less. +// Method of displaying the output: The height of the right endpoint of +// each line segment in the random fractal is displayed by calling the +// function display(...). + +int main() +{ + cout << "Turn your head sideways to see a nice landscape:" << endl; + random_fractal(0, 0, 16, 1); + return EXIT_SUCCESS; +} + +void random_fractal +(double left_height, double right_height, double width, double epsilon) +// Library facilities used: cassert, useful.h (From Appendix I). +{ + double mid_height; // Height of the midpoint of the line segment + + assert(width > 0); + assert(epsilon > 0); + + if (width <= epsilon) + display(right_height); + else + { + mid_height = (left_height + right_height) / 2; + mid_height += random_real(-width, width); + random_fractal(left_height, mid_height, width/2, epsilon); + random_fractal(mid_height, right_height, width/2, epsilon); + } +} diff --git a/chapter9/fractal.o b/chapter9/fractal.o new file mode 100644 index 0000000..2882d05 Binary files /dev/null and b/chapter9/fractal.o differ diff --git a/chapter9/maze.cxx b/chapter9/maze.cxx new file mode 100644 index 0000000..df4ff46 --- /dev/null +++ b/chapter9/maze.cxx @@ -0,0 +1,75 @@ +// FILE: maze.cxx +// An interactive program to lead the user into a maze and back out again, +// while searching for a magic tapestry. + +#include // Provides toupper +#include // Provides EXIT_SUCCESS +#include // Provides cin, cout +#include "useful.h" // From Appendix I; Provides eatline, inquire +using namespace std; + +// PROTOTYPES of functions used in this program. +bool dead_end(); +// Postcondition:The return value is true if the direction directly in front +// is a deadend (i.e., a direction that cannot contain the tapestry). + +bool traverse_maze(); +// Precondition: The user of the program is facing an unblocked spot in the +// maze which has not previously been visited by the user. +// Postcondition: The function has asked a series of questions and provided +// various directions to the user. The questions and directions have led the +// user through the maze and back to the exact same position that the user +// started at. The return value of the function is a true/false value +// indicating whether or not the user found a magic tapestry in the maze. + + +int main() +{ + if (traverse_maze()) + cout << "You found it!" << endl; + else + cout << "It wasn't found!" << endl; + return EXIT_SUCCESS; +} + +bool dead_end() +// Library facilities used: useful.h (From Appendix I) +{ + return inquire("Are you facing a wall?") + || + inquire("Is your name written in front of you?"); +} + +bool traverse_maze() +// Library facilities used: iostream.h +{ + int direction; // Counts 1, 2, 3 for the three directions to explore + bool found; // Will be set to true if we find the tapestry + + cout << "Step forward & write your name on the ground." << endl; + found = inquire("Have you found the tapestry?"); + + if (found) + { // Pick up the tapestry and step back from whence you came. + cout << "Pick up the tapestry and take a step backward." << endl; + } + else + { // Explore the three directions (not counting the one that you just + // came from). Start with the direction on your left, and then + // turn through each of the other possible directions one at a time. + + cout << "Please turn left 90 degrees." << endl; + for (direction = 1; direction <= 3; direction++) + { + if ( !found && !dead_end( ) ) + found = traverse_maze( ); + cout << "Please turn right 90 degrees." << endl; + } + + // You're now facing the direction from whence you came, so step + // forward and turn around. This will put you in the exact + // spot that you were at when the function call began. + cout << "Please step forward, then turn 180 degrees." << endl; + } + return found; +} diff --git a/chapter9/powers.cxx b/chapter9/powers.cxx new file mode 100644 index 0000000..3120f3e --- /dev/null +++ b/chapter9/powers.cxx @@ -0,0 +1,59 @@ +// FILE: powers.cxx +// A demonstration program for two recursive functions that compute powers. +#include // Provides assert +#include // Provides EXIT_SUCCESS +#include // Provides cin, cout +using namespace std; + +double power(double x, int n); +double pow(double x, int n); + +int main( ) +{ + double x; + int n; + + cout << "Please type a value for x (double) and n (int) : "; + cin >> x >> n; + cout << "The value of x to the n is: " << power(x, n) << endl; + + cout << "Please type a value for x (double) and n (int) : "; + cin >> x >> n; + cout << "The value of x to the n is: " << power(x, n) << endl; + + return EXIT_SUCCESS; +} + +double power(double x, int n) +{ + double product; // The product of x with itself n times + int count; + + if (x == 0) + assert(n > 0); + + if (n >= 0) + { + product = 1; + for (count = 1; count <= n; count++) + product = product * x; + return product; + } + else + return 1/power(x, -n); +} + +double pow(double x, int n) +{ + if (x == 0) + { + assert(n > 0); + return 0; + } + else if (n == 0) + return 1; + else if (n > 0) + return x * pow(x, n-1); + else // x is nonzero, and n is negative + return 1/pow(x, -n); +} diff --git a/chapter9/powers.exe b/chapter9/powers.exe new file mode 100644 index 0000000..1799a42 Binary files /dev/null and b/chapter9/powers.exe differ diff --git a/chapter9/powers.o b/chapter9/powers.o new file mode 100644 index 0000000..c966897 Binary files /dev/null and b/chapter9/powers.o differ diff --git a/chapter9/recursionPrograms.zip b/chapter9/recursionPrograms.zip new file mode 100644 index 0000000..a454335 Binary files /dev/null and b/chapter9/recursionPrograms.zip differ diff --git a/chapter9/useful.cxx b/chapter9/useful.cxx new file mode 100644 index 0000000..694016b --- /dev/null +++ b/chapter9/useful.cxx @@ -0,0 +1,80 @@ +// FILE: useful.cxx +// IMPLEMENTS: A toolkit of functions (See useful.h for documentation.) + +#include // Provides assert +#include // Provides toupper +#include // Provides rand, RAND_MAX +#include // Provides cout, cin, get +#include "useful.h" + +void display(double x) +// Library facilities used: iostream.h, stdlib.h +{ + const char STAR = '*'; + const char BLANK = ' '; + const char VERTICAL_BAR = '|'; + const int LIMIT = 39; + int i; + + if (x < -LIMIT) + x = -LIMIT; + else if (x > LIMIT) + x = LIMIT; + + for (i = -LIMIT; i < 0; i++) + { + if (i >= x) + cout << STAR; + else + cout << BLANK; + } + cout << VERTICAL_BAR; + for (i = 1; i <= LIMIT; i++) + { + if (i <= x) + cout << STAR; + else + cout << BLANK; + } + cout << endl; +} + +double random_fraction( ) +// Library facilities used: stdlib.h +{ + return rand( ) / double(RAND_MAX); +} + +double random_real(double low, double high) +// Library facilities used: assert.h +{ + assert(low <= high); + return low + random_fraction( ) * (high - low); +} + +void eat_line( ) +// Library facilities used: iostream.h +// +{ + char next; + + do + cin.get(next); + while (next != '\n'); +} + +bool inquire(const char query[ ]) +// Library facilities used: ctype.h, iostream.h +{ + char answer; + do + { + cout << query << " [Yes or No]" << endl; + cin >> answer; + answer = toupper(answer); + eat_line( ); + } + while ((answer != 'Y') && (answer != 'N')); + return (answer == 'Y'); +} + diff --git a/chapter9/useful.h b/chapter9/useful.h new file mode 100644 index 0000000..25dd03e --- /dev/null +++ b/chapter9/useful.h @@ -0,0 +1,46 @@ +// FILE: useful.h +// PROVIDES: A toolkit of useful functions for random numbers and displays. +// Note that these are in the global namespace. +// +// FUNCTIONS in the toolkit: +// double random_fraction( ) +// Postcondition: The return value is a random real number in the closed +// interval [0..1] (including the endpoints). +// +// double random_real(double low, double high) +// Precondition: low <= high. +// Postcondition: The return value is a random real number in the closed +// interval [low..high] (including the endpoints). +// +// void display(double x) +// Postcondition: The function has written one line of output to the +// standard ouput, with a vertical bar in the middle. If x is positive, +// then approximately x stars are printed to the right of the vertical +// bar. If x is negative, then approximately -x stars are printed to the +// left of the vertical bar. If the absolute value of x is more than +// 39, then only 39 stars are printed. +// Examples: +// display(8) prints: |******** +// display(-4) prints: ****| +// +// void eat_line( ) +// Postcondition: Up to next newline has been read and discarded from cin. +// +// bool inquire(const char query[ ]) +// Precondition: query is a null-terminated string of characters. +// Postcondition: query has been printed, and a one-line response read +// from the user. The function returns true if the user's response begins +// with 'Y' or 'y', and returns false if the user's response begins with +// 'N' or 'n'. (If the response begins with some other letter, then the +// query is repeated.) + +#ifndef USEFUL_H // Prevent duplicate definition +#define USEFUL_H + + double random_fraction( ); + double random_real(double low, double high); + void display(double x); + void eat_line( ); + bool inquire(const char query[ ]); + +#endif diff --git a/chapter9/vertical.cxx b/chapter9/vertical.cxx new file mode 100644 index 0000000..fc84e14 --- /dev/null +++ b/chapter9/vertical.cxx @@ -0,0 +1,47 @@ +// FILE: vertical.cxx +// two recursive functions that write the digits of a number vertically. +#include // Provides cin, cout +#include // Provides EXIT_SUCCESS +using namespace std; + +void write_vertical(unsigned int number); +void super_write_vertical(int number); + +int main( ) { + int i; + + cout << "Please type a non-negative number: "; + cin >> i; + cout << "The digits of that number are:" << endl; + write_vertical(i); + + cout << "Please type a negative number: "; + cin >> i; + cout << "The digits of that number are:" << endl; + super_write_vertical(i); + + cout << "Let's get vertical!" << endl; + return EXIT_SUCCESS; +} +void write_vertical(unsigned int number) { + if (number < 10) + cout << number << endl; // Write the one digit + else { + write_vertical(number/10); // Write all but the last digit + cout << number % 10 << endl; // Write the last digit + } +} +void super_write_vertical(int number) { + if (number < 0) { + cout << '-' << endl; // print a negative sign + super_write_vertical(abs(number)); // abs computes absolute value + // This is Spot #1 referred to in the text. + } + else if (number < 10) + cout << number << endl; // Write the one digit + else { + super_write_vertical(number/10); // Write all but the last digit + // This is Spot #2 referred to in the text. + cout << number % 10 << endl; // Write the last digit + } +} diff --git a/chapter9/vertical.exe b/chapter9/vertical.exe new file mode 100644 index 0000000..baab1ee Binary files /dev/null and b/chapter9/vertical.exe differ diff --git a/chapter9/vertical.o b/chapter9/vertical.o new file mode 100644 index 0000000..e68fe41 Binary files /dev/null and b/chapter9/vertical.o differ -- cgit v1.2.3