diff options
| author | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
|---|---|---|
| committer | Fuwn <[email protected]> | 2024-04-07 23:18:32 -0700 |
| commit | c1b6ffe70bd281c6c230fd63fabcaac2aff47514 (patch) | |
| tree | e8af3b1782a7cd0754590ed618fddc1bdb9b7385 /chapter12 | |
| download | dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.tar.xz dscode-c1b6ffe70bd281c6c230fd63fabcaac2aff47514.zip | |
Diffstat (limited to 'chapter12')
| -rw-r--r-- | chapter12/node2.h | 270 | ||||
| -rw-r--r-- | chapter12/node2.template | 128 | ||||
| -rw-r--r-- | chapter12/search.cxx | 79 | ||||
| -rw-r--r-- | chapter12/table1.h | 84 | ||||
| -rw-r--r-- | chapter12/table1.template | 144 | ||||
| -rw-r--r-- | chapter12/table2.h | 82 | ||||
| -rw-r--r-- | chapter12/table2.template | 1 | ||||
| -rw-r--r-- | chapter12/testtab1.cxx | 130 | ||||
| -rw-r--r-- | chapter12/testtab2.cxx | 130 |
9 files changed, 1048 insertions, 0 deletions
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<Item>.
+// The node_iterator is a forward iterators with two constructors:
+// (1) A constructor (with a node<Item>* 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<Item>* .
+//
+// TYPEDEF for the node<Item> 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<Item>::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<Item>::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<Item> 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<int> *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<int> *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<Item> 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 <class Item>
+// void list_clear(node<Item>*& 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 <class Item>
+// void list_copy
+// (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& 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 <class Item>
+// void list_head_insert(node<Item>*& 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 <class Item>
+// void list_head_remove(node<Item>*& 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 <class Item>
+// void list_insert(node<Item>* 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 <class Item>
+// size_t list_length(const node<Item>* 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 <class NodePtr, class SizeType>
+// NodePtr list_locate(NodePtr head_ptr, SizeType position)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// 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 <class Item>
+// void list_remove(node<Item>* 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 <class NodePtr, class Item>
+// NodePtr list_search
+// (NodePtr head_ptr, const Item& target)
+// The NodePtr may be either node<Item>* or const node<Item>*
+// 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 <cstdlib> // Provides NULL and size_t
+#include <iterator> // Provides iterator and forward_iterator_tag
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ 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 <class Item>
+ void list_clear(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_copy
+ (const node<Item>* source_ptr, node<Item>*& head_ptr, node<Item>*& tail_ptr);
+
+ template <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry);
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr);
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry);
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr);
+
+ template <class NodePtr, class SizeType>
+ NodePtr list_locate(NodePtr head_ptr, SizeType position);
+
+ template <class Item>
+ void list_remove(node<Item>* previous_ptr);
+
+ template <class NodePtr, class Item>
+ 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 Item>
+ class node_iterator
+ : public std::iterator<std::forward_iterator_tag, Item>
+ {
+ public:
+ node_iterator(node<Item>* 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<Item>* current;
+ };
+
+ template <class Item>
+ class const_node_iterator
+ : public std::iterator<std::forward_iterator_tag, const Item>
+ {
+ public:
+ const_node_iterator(const node<Item>* 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<Item>* 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 <cassert> // Provides assert
+#include <cstdlib> // Provides NULL and size_t
+
+namespace main_savitch_6B
+{
+ template <class Item>
+ void list_clear(node<Item>*& head_ptr)
+ // Library facilities used: cstdlib
+ {
+ while (head_ptr != NULL)
+ list_head_remove(head_ptr);
+ }
+
+ template <class Item>
+ void list_copy(
+ const node<Item>* source_ptr,
+ node<Item>*& head_ptr,
+ node<Item>*& 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 <class Item>
+ void list_head_insert(node<Item>*& head_ptr, const Item& entry)
+ {
+ head_ptr = new node<Item>(entry, head_ptr);
+ }
+
+ template <class Item>
+ void list_head_remove(node<Item>*& head_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = head_ptr;
+ head_ptr = head_ptr->link( );
+ delete remove_ptr;
+ }
+
+ template <class Item>
+ void list_insert(node<Item>* previous_ptr, const Item& entry)
+ {
+ node<Item> *insert_ptr;
+
+ insert_ptr = new node<Item>(entry, previous_ptr->link( ));
+ previous_ptr->set_link(insert_ptr);
+ }
+
+ template <class Item>
+ std::size_t list_length(const node<Item>* head_ptr)
+ // Library facilities used: cstdlib
+ {
+ const node<Item> *cursor;
+ std::size_t answer;
+
+ answer = 0;
+ for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
+ ++answer;
+
+ return answer;
+ }
+
+ template <class NodePtr, class SizeType>
+ 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 <class Item>
+ void list_remove(node<Item>* previous_ptr)
+ {
+ node<Item> *remove_ptr;
+
+ remove_ptr = previous_ptr->link( );
+ previous_ptr->set_link(remove_ptr->link( ));
+ delete remove_ptr;
+ }
+
+ template <class NodePtr, class Item>
+ 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 <cstdlib> // Provides EXIT_SUCCESS, size_t
+#include <iostream> // 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<RecordType> (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<RecordType> class:
+// static const size_type CAPACITY = ________
+// table<RecordType>::CAPACITY is the maximum number of records held by a table.
+//
+// CONSTRUCTOR for the table<RecordType> template class:
+// table( )
+// Postcondition: The table has been initialized as an empty table.
+//
+// MODIFICATION MEMBER FUNCTIONS for the table<RecordType> 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<RecordType> 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<RecordType> template class:
+// Assignments and the copy constructor may be used with table objects.
+
+#ifndef TABLE1_H
+#define TABLE1_H
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_12A
+{
+ template <class RecordType>
+ 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 <cassert> // Provides assert
+#include <cstdlib> // Provides size_t
+
+namespace main_savitch_12A
+{
+ template <class RecordType>
+ const std::size_t table<RecordType>::CAPACITY;
+
+ template <class RecordType>
+ const int table<RecordType>::NEVER_USED;
+
+ template <class RecordType>
+ const int table<RecordType>::PREVIOUSLY_USED;
+
+ template <class RecordType>
+ table<RecordType>::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 <class RecordType>
+ void table<RecordType>::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 <class RecordType>
+ void table<RecordType>::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 <class RecordType>
+ bool table<RecordType>::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 <class RecordType>
+ void table<RecordType>::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 <class RecordType>
+ inline std::size_t table<RecordType>::hash(int key) const
+ {
+ return (key % CAPACITY);
+ }
+
+ template <class RecordType>
+ inline std::size_t table<RecordType>::next_index(std::size_t index) const
+ // Library facilities used: cstdlib
+ {
+ return ((index+1) % CAPACITY);
+ }
+
+ template <class RecordType>
+ void table<RecordType>::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 <class RecordType>
+ inline bool table<RecordType>::never_used(std::size_t index) const
+ {
+ return (data[index].key == NEVER_USED);
+ }
+
+ template <class RecordType>
+ inline bool table<RecordType>::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<RecordType> +// 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<RecordType> template class: +// Table( ) +// Postcondition: The Table has been initialized as an empty Table. +// +// MODIFICATION MEMBER FUNCTIONS for the Table<RecordType> 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<RecordType> 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<RecordType> template class: +// Assignments and the copy constructor may be used with Table objects. +// +// DYNAMIC MEMORY USAGE by the Table<RecordType> 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 <cstdlib> // Provides size_t +#include "node2.h" // Provides the node type, from Figure 6.5 on page 306 + +namespace main_savitch_12B +{ + template <class RecordType> + 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<RecordType> *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 <cctype> // Provides toupper
+#include <cstdlib> // Provides EXIT_SUCCESS and size_t
+#include <iostream> // 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_record_type> 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 <cctype> // Provides toupper
+#include <cstdlib> // Provides EXIT_SUCCESS and size_t
+#include <iostream> // 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_record_type> 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;
+}
|