From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- 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 ++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 623 insertions(+) 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 (limited to 'chapter5') 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 -- cgit v1.2.3