C++ Programming Lab 10. Please only answer if you can do the ENTIRE problem. DO
ID: 3869308 • Letter: C
Question
C++ Programming Lab 10. Please only answer if you can do the ENTIRE problem. DO NOT MAKE YOUR OWN CPP FILES, VARIABLES, ETC. UPLOAD ALL OF THE EXACT .CPP AND .H FILES AS I HAVE THEM JUST COMPLETED. Reattach all files I have below even if you didn't have to edit one. Program MUST compile and all these instructions followed in order for me to give a thumbs up, thank you :-)
Parts to complete:
- Implement the Hash Table ADT (80 points)
- Programming Exercise 3 (20 points)
BSTree.cpp
#include "BSTree.h"
template <typename DataType, class KeyType>
BSTree<DataType, KeyType>::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ()
{
root = NULL;
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::BSTree ( const BSTree<DataType,KeyType>& other )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>& BSTree<DataType, KeyType>:: operator= ( const BSTree<DataType,KeyType>& other )
{
}
template < typename DataType, class KeyType >
BSTree<DataType, KeyType>::~BSTree ()
{
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::insert ( const DataType& newDataItem )
{
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const
{
return false;
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::remove ( const KeyType& deleteKey )
{
return false;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeKeys () const
{
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::clear ()
{
}
template < typename DataType, class KeyType >
bool BSTree<DataType, KeyType>::isEmpty () const
{
return false;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getHeight () const
{
return -1;
}
template < typename DataType, class KeyType >
int BSTree<DataType, KeyType>::getCount () const
{
return -1;
}
template < typename DataType, class KeyType >
void BSTree<DataType, KeyType>::writeLessThan ( const KeyType& searchKey ) const
{
}
#include "show9.cpp"
BSTree.h
//--------------------------------------------------------------------
//
// Laboratory 9 BSTree.h
//
// Class declarations for the linked implementation of the Binary
// Search Tree ADT -- including the recursive helpers of the
// public member functions
//
//--------------------------------------------------------------------
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template < typename DataType, class KeyType > // DataType : tree data item
class BSTree // KeyType : key field
{
public:
// Constructor
BSTree (); // Default constructor
BSTree ( const BSTree<DataType,KeyType>& other ); // Copy constructor
BSTree& operator= ( const BSTree<DataType,KeyType>& other );
// Overloaded assignment operator
// Destructor
~BSTree ();
// Binary search tree manipulation operations
void insert ( const DataType& newDataItem ); // Insert data item
bool retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const;
// Retrieve data item
bool remove ( const KeyType& deleteKey ); // Remove data item
void writeKeys () const; // Output keys
void clear (); // Clear tree
// Binary search tree status operations
bool isEmpty () const; // Tree is empty
// !! isFull() has been retired. Not very useful in a linked structure.
// Output the tree structure -- used in testing/debugging
void showStructure () const;
// In-lab operations
int getHeight () const; // Height of tree
int getCount () const; // Number of nodes in tree
void writeLessThan ( const KeyType& searchKey ) const; // Output keys < searchKey
protected:
class BSTreeNode // Inner class: facilitator for the BSTree class
{
public:
// Constructor
BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr );
// Data members
DataType dataItem; // Binary search tree data item
BSTreeNode *left, // Pointer to the left child
*right; // Pointer to the right child
};
// Recursive helpers for the public member functions -- insert
// prototypes of these functions here.
void showHelper ( BSTreeNode *p, int level ) const;
// Data member
BSTreeNode *root; // Pointer to the root node
};
#endif // define BSTREE_H
example1.cpp
// lab10-example1.cpp
#include <iostream>
#include <cmath>
#include "HashTable.cpp"
using namespace std;
struct Account
{
int acctNum; // (Key) Account number
float balance; // Account balance
int getKey () const { return acctNum; }
static unsigned int hash(const int& key) { return abs( key ); }
};
int main()
{
HashTable<Account,int> accounts(11); // List of accounts
Account acct; // A single account
int searchKey; // An account key
// Read in information on a set of accounts.
cout << endl << "Enter account information (num balance) for 5 accounts: "
<< endl;
for ( int i = 0; i < 5; i++ )
{
cin >> acct.acctNum >> acct.balance;
accounts.insert(acct);
}
// Checks for accounts and prints records if found
cout << endl;
cout << "Enter account number (<EOF> to end): ";
while ( cin >> searchKey )
{
if ( accounts.retrieve(searchKey,acct) )
cout << acct.acctNum << " " << acct.balance << endl;
else
cout << "Account " << searchKey << " not found." << endl;
}
return 0;
}
HashTable.cpp
#include "HashTable.h"
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(int initTableSize)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(const HashTable& other)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>& HashTable<DataType, KeyType>::operator=(const HashTable& other)
{
}
template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::~HashTable()
{
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::insert(const DataType& newDataItem)
{
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::remove(const KeyType& deleteKey)
{
return false;
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::retrieve(const KeyType& searchKey, DataType& returnItem) const
{
return false;
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::clear()
{
}
template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::isEmpty() const
{
return true;
}
#include "show10.cpp"
template <typename DataType, typename KeyType>
double HashTable<DataType, KeyType>::standardDeviation() const
{
}
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::copyTable(const HashTable& source)
{
}
HashTable.h
// HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdexcept>
#include <iostream>
using namespace std;
#include "BSTree.cpp"
template <typename DataType, typename KeyType>
class HashTable {
public:
HashTable(int initTableSize);
HashTable(const HashTable& other);
HashTable& operator=(const HashTable& other);
~HashTable();
void insert(const DataType& newDataItem);
bool remove(const KeyType& deleteKey);
bool retrieve(const KeyType& searchKey, DataType& returnItem) const;
void clear();
bool isEmpty() const;
void showStructure() const;
double standardDeviation() const;
private:
void copyTable(const HashTable& source);
int tableSize;
BSTree<DataType, KeyType>* dataTable;
};
#endif // ifndef HASHTABLE_H
show9.cpp
#include "BSTree.h"
//--------------------------------------------------------------------
//
// Laboratory 9 show9.cpp
//
// Linked implementation of the showStructure operation for the
// Binary Search Tree ADT
//
//--------------------------------------------------------------------
//--------------------------------------------------------------------
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showStructure () const
// Outputs the keys in a binary search tree. The tree is output
// rotated counterclockwise 90 degrees from its conventional
// orientation using a "reverse" inorder traversal. This operation is
// intended for testing and debugging purposes only.
{
if ( root == 0 )
cout << "Empty tree" << endl;
else
{
cout << endl;
showHelper(root,1);
cout << endl;
}
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
template < typename DataType, typename KeyType >
void BSTree<DataType,KeyType>:: showHelper ( BSTreeNode *p,
int level ) const
// Recursive helper for showStructure.
// Outputs the subtree whose root node is pointed to by p.
// Parameter level is the level of this node within the tree.
{
int j; // Loop counter
if ( p != 0 )
{
showHelper(p->right,level+1); // Output right subtree
for ( j = 0 ; j < level ; j++ ) // Tab over to level
cout << " ";
cout << " " << p->dataItem.getKey(); // Output key
if ( ( p->left != 0 ) && // Output "connector"
( p->right != 0 ) )
cout << "<";
else if ( p->right != 0 )
cout << "/";
else if ( p->left != 0 )
cout << "\";
cout << endl;
showHelper(p->left,level+1); // Output left subtree
}
}
show10.cpp
#include "HashTable.h"
// show10.cpp: contains implementation of the HashTable showStructure function
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::showStructure() const {
for (int i = 0; i < tableSize; ++i) {
cout << i << ": ";
dataTable[i].writeKeys();
}
}
test10.cpp
#include <iostream>
#include <string>
using namespace std;
#include "HashTable.cpp"
class TestData {
public:
TestData();
void setKey(const string& newKey);
string getKey() const;
int getValue() const;
static unsigned int hash(const string& str);
private:
string key;
int value;
static int count;
};
int TestData::count = 0;
TestData::TestData() : value(++count) {
}
void TestData::setKey(const string& newKey) {
key = newKey;
}
string TestData::getKey() const {
return key;
}
int TestData::getValue() const {
return value;
}
unsigned int TestData::hash(const string& str) {
unsigned int val = 0;
for (unsigned int i = 0; i < str.length(); ++i) {
val += str[i];
}
return val;
}
void print_help() {
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Insert (or update) data item with key x" << endl;
cout << " -x : Remove the data element with the key x" << endl;
cout << " ?x : Retrieve the data element with the key x" << endl;
cout << " E : Empty table?" << endl;
cout << " C : Clear the table" << endl;
cout << " Q : Quit the test program" << endl;
}
int main(int argc, char **argv) {
HashTable<TestData, string> table(7);
print_help();
do {
table.showStructure();
cout << endl << "Command: ";
char cmd;
cin >> cmd;
TestData item;
if (cmd == '+' || cmd == '?' || cmd == '-') {
string key;
cin >> key;
item.setKey(key);
}
switch (cmd) {
case 'H':
case 'h':
print_help();
break;
case '+':
table.insert(item);
cout << "Inserted data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
break;
case '-':
if (table.remove(item.getKey())) {
cout << "Removed data item with key ("
<< item.getKey() << ")" << endl;
} else {
cout << "Could not remove data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case '?':
if (table.retrieve(item.getKey(), item)) {
cout << "Retrieved data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
} else {
cout << "Could not retrieve data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case 'C':
case 'c':
cout << "Clear the hash table" << endl;
table.clear();
break;
case 'E':
case 'e':
cout << "Hash table is "
<< (table.isEmpty() ? "" : "NOT")
<< " empty" << endl;
break;
case 'Q':
case 'q':
return 0;
default:
cout << "Invalid command" << endl;
}
} while (1);
return 0;
}
test10std.cpp
//--------------------------------------------------------------------
//
// Laboratory 10 test10std.cpp
//
// Test program for the standard deviation operation in the Hash Table ADT
//
//--------------------------------------------------------------------
#include <cmath>
#include <string>
#include <iostream>
#include <fstream>
#include "HashTable.cpp"
using namespace std;
struct Data
{
public:
void setKey ( string newKey ) { key = newKey; }
string getKey () const { return key; }
static unsigned int hash(const string& str)
{
// Uncomment each of these as you try them out.
//-----------------------
// Hash Algorithm 1
//-----------------------
// return 0;
//-----------------------
// Hash Algorithm 2
//-----------------------
// return int(str[0])*10 + str.length();
//-----------------------
// Hash Algorithm 3
//-----------------------
// double val = 0;
// for (int i=0; i<str.length(); i++)
// val += (val*1.1)+str[i];
// return int (val);
// Add your two hash algorithms below
//-----------------------
// Hash Algorithm 4
//-----------------------
//-----------------------
// Hash Algorithm 5
//-----------------------
}
private:
string key;
};
int main()
{
HashTable<Data, string> testTbl(64);
Data testData;
string key;
ifstream data("std-dev.dat");
if( ! data )
{
cerr << "Error opening 'std-dev.dat'" << endl;
}
else
{
while( data >> key )
{
testData.setKey( key );
testTbl.insert( testData );
}
testTbl.showStructure();
cout << endl << endl;
cout << "The standard deviation is "
<< testTbl.standardDeviation() << endl;
}
}
Explanation / Answer
BSTree.cpp
--------------------------
#include "HashTable.h"
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(int initTableSize) {
tableSize = initTableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(const HashTable &other) {
tableSize = other.tableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>&HashTable<T, KeyType>::operator=(const HashTable &other) {
clear();
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::~HashTable() {
clear();
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::insert(const T &newDataItem) {
uint loc = T::hash(newDataItem.getKey()) % tableSize;
dataTable[loc].insert(newDataItem);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::remove(const KeyType &deleteKey) {
uint loc = T::hash(deleteKey) % tableSize;
return dataTable[loc].remove(deleteKey);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::retrieve(const KeyType &searchKey, T &returnItem) const {
uint loc = T::hash(searchKey) % tableSize;
return dataTable[loc].retrieve(searchKey, returnItem);
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::clear() {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
dataTable[i].clear();
}
}
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::isEmpty() const {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
return false;
}
}
return true;
}
#include "show10.cpp"
template<typename T, typename KeyType>
double HashTable<T, KeyType>::standardDeviation() const {
double xbar, sumOfSquares;
int i, n = 0, totalNodes = 0;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
totalNodes += dataTable[i].getCount();
n++;
}
xbar = totalNodes / n;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
sumOfSquares += pow((dataTable[i].getCount() - xbar), 2);
}
return (n - 1) == 0 ? 0 : sqrt(sumOfSquares / (n - 1));
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::copyTable(const HashTable &source) {}
---------------------------------------------------------------------
BSTree.h
------------------------------
#ifndef BSTREE_H
#define BSTREE_H
#include <stdexcept>
#include <iostream>
using namespace std;
template<typename T, class KeyType>
class BSTree {
public:
BSTree();
BSTree(const BSTree<T, KeyType> &other);
BSTree& operator=(const BSTree<T, KeyType> &other);
~BSTree();
// Binary search tree manipulation operations
void insert(const T &newDataItem);
bool retrieve(const KeyType &searchKey, T &searchDataItem) const;
bool remove(const KeyType &deleteKey);
void writeKeys() const;
void clear();
// Binary search tree status operations
bool isEmpty() const;
// Output the tree structure -- used in testing/debugging
void showStructure() const;
// In-lab operations
int getHeight() const;
int getCount() const;
void writeLessThan(const KeyType &searchKey) const; // Output keys < searchKey
protected:
class BSTreeNode {
public:
BSTreeNode(const T &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr);
T dataItem;
BSTreeNode *left;
BSTreeNode *right;
};
// Recursive helpers for the public member functions
void insertHelper(BSTreeNode* &p, const T &newDataItem);
bool retrieveHelper(BSTreeNode *p, const KeyType &searchKey, T &searchDataItem) const;
bool removeHelper(BSTreeNode* &p, const KeyType &deleteKey);
// cutRightmost used in one implementation of remove.
void cutRightmost(BSTreeNode* &r, BSTreeNode* &delPtr);
void writeKeysHelper(BSTreeNode *p) const;
void clearHelper(BSTreeNode *p);
void showHelper(BSTreeNode *p, int level) const;
int getHeightHelper(BSTreeNode *p) const;
int getCountHelper(BSTreeNode *p) const;
void writeLTHelper(BSTreeNode *p, const KeyType &searchKey) const;
void copyTree(const BSTree<T, KeyType> &otherTree);
void copyTreeHelper(BSTreeNode* &p, const BSTreeNode *otherPtr);
// Data member
BSTreeNode *root;
};
#endif // define BSTREE_H
--------------------------------------------------------------------------
HashTable.cpp
------------------------
#include "HashTable.h"
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(int initTableSize) {
tableSize = initTableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(const HashTable &other) {
tableSize = other.tableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>&HashTable<T, KeyType>::operator=(const HashTable &other) {
clear();
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::~HashTable() {
clear();
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::insert(const T &newDataItem) {
uint loc = T::hash(newDataItem.getKey()) % tableSize;
dataTable[loc].insert(newDataItem);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::remove(const KeyType &deleteKey) {
uint loc = T::hash(deleteKey) % tableSize;
return dataTable[loc].remove(deleteKey);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::retrieve(const KeyType &searchKey, T &returnItem) const {
uint loc = T::hash(searchKey) % tableSize;
return dataTable[loc].retrieve(searchKey, returnItem);
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::clear() {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
dataTable[i].clear();
}
}
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::isEmpty() const {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
return false;
}
}
return true;
}
#include "show10.cpp"
template<typename T, typename KeyType>
double HashTable<T, KeyType>::standardDeviation() const {
double xbar, sumOfSquares;
int i, n = 0, totalNodes = 0;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
totalNodes += dataTable[i].getCount();
n++;
}
xbar = totalNodes / n;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
sumOfSquares += pow((dataTable[i].getCount() - xbar), 2);
}
return (n - 1) == 0 ? 0 : sqrt(sumOfSquares / (n - 1));
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::copyTable(const HashTable &source) {}
----------------------------------------------------------------
HashTable.h
--------------------------------
#include "HashTable.h"
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(int initTableSize) {
tableSize = initTableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::HashTable(const HashTable &other) {
tableSize = other.tableSize;
dataTable = new BSTree<T, KeyType>[tableSize];
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>&HashTable<T, KeyType>::operator=(const HashTable &other) {
clear();
copyTable(other);
}
template<typename T, typename KeyType>
HashTable<T, KeyType>::~HashTable() {
clear();
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::insert(const T &newDataItem) {
uint loc = T::hash(newDataItem.getKey()) % tableSize;
dataTable[loc].insert(newDataItem);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::remove(const KeyType &deleteKey) {
uint loc = T::hash(deleteKey) % tableSize;
return dataTable[loc].remove(deleteKey);
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::retrieve(const KeyType &searchKey, T &returnItem) const {
uint loc = T::hash(searchKey) % tableSize;
return dataTable[loc].retrieve(searchKey, returnItem);
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::clear() {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
dataTable[i].clear();
}
}
}
template<typename T, typename KeyType>
bool HashTable<T, KeyType>::isEmpty() const {
for (int i = 0; i < tableSize; i++) {
if (!dataTable[i].isEmpty()) {
return false;
}
}
return true;
}
#include "show10.cpp"
template<typename T, typename KeyType>
double HashTable<T, KeyType>::standardDeviation() const {
double xbar, sumOfSquares;
int i, n = 0, totalNodes = 0;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
totalNodes += dataTable[i].getCount();
n++;
}
xbar = totalNodes / n;
for (i = 0; i < tableSize; i++) {
if (dataTable[i].isEmpty()) { continue; }
sumOfSquares += pow((dataTable[i].getCount() - xbar), 2);
}
return (n - 1) == 0 ? 0 : sqrt(sumOfSquares / (n - 1));
}
template<typename T, typename KeyType>
void HashTable<T, KeyType>::copyTable(const HashTable &source) {}
------------------------------------------------------------
example1.cpp
--------------------------
#include <iostream>
#include <cmath>
#include "HashTable.cpp"
using namespace std;
struct Account
{
int acctNum; // (Key) Account number
float balance; // Account balance
int getKey () const { return acctNum; }
static unsigned int hash(const int& key) { return abs( key ); }
};
int main()
{
HashTable<Account,int> accounts(11); // List of accounts
Account acct; // A single account
int searchKey; // An account key
// Read in information on a set of accounts.
cout << endl << "Enter account information (num balance) for 5 accounts: "
<< endl;
for ( int i = 0; i < 5; i++ )
{
cin >> acct.acctNum >> acct.balance;
accounts.insert(acct);
}
// Checks for accounts and prints records if found
cout << endl;
cout << "Enter account number (<EOF> to end): ";
while ( cin >> searchKey )
{
if ( accounts.retrieve(searchKey,acct) )
cout << acct.acctNum << " " << acct.balance << endl;
else
cout << "Account " << searchKey << " not found." << endl;
}
return 0;
}
--------------------------------------------------------------
show9.cpp
----------------------------------
#include "BSTree.h"
template<typename T, typename KeyType>
void BSTree<T, KeyType>::showStructure() const {
if (root == 0) {
cout << "Empty tree" << endl;
}
else {
cout << endl;
showHelper(root, 1);
cout << endl;
}
}
// Recursive helper for showStructure.
// Outputs the subtree whose root node is pointed to by p.
// Parameter level is the level of this node within the tree.
template<typename T, typename KeyType>
void BSTree<T, KeyType>::showHelper(BSTreeNode *p, int level) const {
int j; // Loop counter
if (p != 0) {
showHelper(p->right, level + 1); // Output right subtree
for (j = 0; j < level; j++) { // Tab over to level
cout << " ";
}
cout << " " << p->dataItem.getKey(); // Output key
if ((p->left != 0) && // Output "connector"
(p->right != 0)) {
cout << "<";
}
else if (p->right != 0) {
cout << "/";
}
else if (p->left != 0) {
cout << "\";
}
cout << endl;
showHelper(p->left, level + 1); // Output left subtree
}
}
------------------------------------------------------
show10.cpp
---------------------------
#include "HashTable.h"
// show10.cpp: contains implementation of the HashTable showStructure function
template<typename T, typename KeyType>
void HashTable<T, KeyType>::showStructure() const {
for (int i = 0; i < tableSize; ++i) {
cout << i << ": ";
dataTable[i].writeKeys();
}
}
------------------------------------------------
test10.cpp
-----------------------
#include <iostream>
#include <string>
using namespace std;
#include "HashTable.cpp"
class TestData {
public:
TestData();
void setKey(const string &newKey);
string getKey() const;
int getValue() const;
static unsigned int hash(const string &str);
private:
string key;
int value;
static int count;
};
int TestData::count = 0;
TestData::TestData(): value(++count) {}
void TestData::setKey(const string &newKey) {
key = newKey;
}
string TestData::getKey() const {
return key;
}
int TestData::getValue() const {
return value;
}
unsigned int TestData::hash(const string &str) {
unsigned int val = 0;
for (unsigned int i = 0; i < str.length(); ++i) {
val += str[i];
}
return val;
}
void print_help() {
cout << endl << "Commands:" << endl;
cout << " H : Help (displays this message)" << endl;
cout << " +x : Insert (or update) data item with key x" << endl;
cout << " -x : Remove the data element with the key x" << endl;
cout << " ?x : Retrieve the data element with the key x" << endl;
cout << " E : Empty table?" << endl;
cout << " C : Clear the table" << endl;
cout << " Q : Quit the test program" << endl;
}
// int main(int argc, char **argv) {
int main() {
HashTable<TestData, string> table(7);
print_help();
do {
table.showStructure();
cout << endl << "Command: ";
char cmd;
cin >> cmd;
TestData item;
if (cmd == '+' || cmd == '?' || cmd == '-') {
string key;
cin >> key;
item.setKey(key);
}
switch (cmd) {
case 'H':
case 'h':
print_help();
break;
case '+':
table.insert(item);
cout << "Inserted data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
break;
case '-':
if (table.remove(item.getKey())) {
cout << "Removed data item with key ("
<< item.getKey() << ")" << endl;
}
else {
cout << "Could not remove data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case '?':
if (table.retrieve(item.getKey(), item)) {
cout << "Retrieved data item with key ("
<< item.getKey() << ") and value ("
<< item.getValue() << ")" << endl;
}
else {
cout << "Could not retrieve data item with key ("
<< item.getKey() << ")" << endl;
}
break;
case 'C':
case 'c':
cout << "Clear the hash table" << endl;
table.clear();
break;
case 'E':
case 'e':
cout << "Hash table is "
<< (table.isEmpty() ? "" : "NOT")
<< " empty" << endl;
break;
case 'Q':
case 'q':
return 0;
default:
cout << "Invalid command" << endl;
}
} while (1);
return 0;
}
--------------------------------------------------------------
test10std.cpp
--------------------------
#include <cmath>
#include <string>
#include <iostream>
#include <fstream>
#include "HashTable.cpp"
using namespace std;
struct Data {
public:
void setKey(string newKey) { key = newKey; }
string getKey() const { return key; }
static unsigned int hash(const string &str) {
// Uncomment each of these as you try them out.
// -----------------------
// Hash Algorithm 1
// -----------------------
// return 0;
// -----------------------
// Hash Algorithm 2
// -----------------------
return int(str[0])*10 + str.length();
// -----------------------
// Hash Algorithm 3
// -----------------------
// double val = 0;
// for (int i=0; i<str.length(); i++)
// val += (val*1.1)+str[i];
// return int (val);
// Add your two hash algorithms below
// -----------------------
// Hash Algorithm 4
// -----------------------
// -----------------------
// Hash Algorithm 5
// -----------------------
}
private:
string key;
};
int main() {
HashTable<Data, string> testTbl(64);
Data testData;
string key;
ifstream data("std-dev.dat");
if (!data) {
cerr << "Error opening 'std-dev.dat'" << endl;
}
else {
while (data >> key) {
testData.setKey(key);
testTbl.insert(testData);
}
testTbl.showStructure();
cout << endl << endl;
cout << "The standard deviation is "
<< testTbl.standardDeviation() << endl;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.