Please Help Data Structures problem please help and using only C++ Please read c
ID: 3827093 • Letter: P
Question
Please Help Data Structures problem please help and using only C++
Please read carefully before starting.
The header and test file that are being used are provided below.
Table1 header and template file are only examples, they are not being used for this problem. The table2.h file and testtab2.cpp are the files being used.
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 <list> // Provides the STL list class
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:
std::list<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
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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 ";
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;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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);
}
}
Explanation / Answer
table2.h
#ifndef TABLE2_H
#define TABLE2_H
#include <cstdlib> // Provides size_t
#include <list>
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:
//list<RecordType> *data[TABLE_SIZE]; // Not used this way for our assignment
std::list<RecordType> data[TABLE_SIZE]; // Use the STL list class for this assignment instead
std::size_t total_records;
// HELPER MEMBER FUNCTION
std::size_t hash(int key) const;
};
}
#include "table2.template" // Include the implementation
#endif
table2.template
#include <cassert> // Provides ability to assert
using namespace std;
namespace main_savitch_12B
{
template <class RecordType>
table<RecordType>::table()
{
total_records = 0;
}
template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
{
assert(entry.key >= 0);
std::size_t index = hash(entry.key);
if(!is_present(entry.key)){
data[index].push_back(entry);
++total_records;
}
else{
remove(entry.key);
data[index].push_back(entry);
}
}
template <class RecordType>
void table<RecordType>::remove(int key)
{
std::size_t index = hash(key);
if(!is_present(key))
return;
else{
typename std::list<RecordType>::iterator iter;
for(iter = data[index].begin(); iter != data[index].end(); ++iter){
if(iter->key == key){
data[index].erase(iter);
--total_records;
break;
}
}
}
}
template <class RecordType>
void table<RecordType>::find(int key, bool& found, RecordType& result) const
{
std::size_t index = hash(key);
if(is_present(key)){
found = true;
typename std::list<RecordType>::const_iterator iter;
for(iter = data[index].begin(); iter != data[index].end(); ++iter){
if(iter->key == key)
result = *iter;
return;
}
}
else
found = false;
}
template <class RecordType>
bool table<RecordType>::is_present(int key) const
{
std::size_t index = hash(key);
typename std::list<RecordType>::const_iterator iter;
for(iter = data[index].begin(); iter != data[index].end(); ++iter){
if(iter->key == key)
return true;
}
return false;
}
template <class RecordType>
std::size_t table<RecordType>::hash(int key) const
{
return (key % TABLE_SIZE);
}
}
testtab2.cxx
#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 ";
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;
}