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