C++ Programming. Please only answer if you can do the ENTIRE problem. DO NOT MAK
ID: 3857824 • Letter: C
Question
C++ Programming. 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.
Parts to complete:
- Implement the Hash Table ADT (80 points)
- Programming Exercise 3 (20 points)
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
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
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"
example1:
// 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)
{
}
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.cp
---------------------
#include "BSTree.h"
template<typename T, class KeyType>
BSTree<T, KeyType>::BSTreeNode::BSTreeNode(const T &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr) {
dataItem = nodeDataItem;
left = leftPtr;
right = rightPtr;
}
template<typename T, class KeyType>
BSTree<T, KeyType>::BSTree() {
root = NULL;
}
template<typename T, class KeyType>
BSTree<T, KeyType>::BSTree(const BSTree<T, KeyType> &other) {
root = NULL;
copyTreeHelper(root, other.root);
}
template<typename T, class KeyType>
BSTree<T, KeyType>::~BSTree() {
clearHelper(root);
}
template<typename T, class KeyType>
BSTree<T, KeyType>&BSTree<T, KeyType>::operator=(const BSTree<T, KeyType> &other) {
clearHelper(root);
copyTreeHelper(root, other.root);
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::insert(const T &newDataItem) {
insertHelper(root, newDataItem);
}
template<typename T, class KeyType>
bool BSTree<T, KeyType>::retrieve(const KeyType &searchKey, T &searchDataItem) const {
return retrieveHelper(root, searchKey, searchDataItem);
}
template<typename T, class KeyType>
bool BSTree<T, KeyType>::remove(const KeyType &deleteKey) {
return removeHelper(root, deleteKey);
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::writeKeys() const {
writeKeysHelper(root);
cout << endl;
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::clear() {
clearHelper(root);
root = NULL;
}
template<typename T, class KeyType>
bool BSTree<T, KeyType>::isEmpty() const {
return root == NULL;
}
template<typename T, class KeyType>
int BSTree<T, KeyType>::getHeight() const {
return getHeightHelper(root) - 1;
}
template<typename T, class KeyType>
int BSTree<T, KeyType>::getCount() const {
return getCountHelper(root);
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::writeLessThan(const KeyType &searchKey) const {
writeLTHelper(root, searchKey);
}
// Helpers
template<typename T, class KeyType>
void BSTree<T, KeyType>::clearHelper(BSTreeNode *p) {
if (p->left != NULL) {
clearHelper(p->left);
}
if (p->right != NULL) {
clearHelper(p->right);
}
delete p;
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::copyTreeHelper(BSTreeNode* &p, const BSTreeNode *otherPtr) {
if (otherPtr == NULL) { return; }
p = new BSTreeNode(otherPtr->nodeDataItem, NULL, NULL);
copyTreeHelper(p->left, otherPtr->left);
copyTreeHelper(p->right, otherPtr->right);
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::insertHelper(BSTreeNode* &p, const T &newDataItem) {
if (p == NULL) {
p = new BSTreeNode(newDataItem, NULL, NULL);
return;
}
KeyType key = newDataItem.getKey();
KeyType currentKey = p->dataItem.getKey();
if (key > currentKey) {
insertHelper(p->right, newDataItem);
}
else if (key < currentKey) {
insertHelper(p->left, newDataItem);
}
else {
p->dataItem = newDataItem;
}
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::cutRightmost(BSTreeNode* &r, BSTreeNode* &delPtr) {
if (r->right != NULL) {
cutRightmost(r->right, delPtr);
}
else {
delPtr->dataItem = r->dataItem;
delPtr = r;
r = r->left;
}
}
template<typename T, class KeyType>
bool BSTree<T, KeyType>::removeHelper(BSTreeNode* &p, const KeyType &deleteKey) {
if (p == NULL) { return false; }
KeyType key = p->dataItem.getKey();
if (deleteKey < key) {
return removeHelper(p->left, deleteKey);
}
if (deleteKey > key) {
return removeHelper(p->right, deleteKey);
}
BSTreeNode *delPtr = p;
if (p->left == NULL) {
p = p->right;
}
else if (p->right == NULL) {
p = p->left;
}
else {
cutRightmost(p->left, delPtr);
}
delete delPtr;
return true;
}
template<typename T, class KeyType>
bool BSTree<T, KeyType>::retrieveHelper(BSTreeNode *p, const KeyType &searchKey, T &searchDataItem) const {
if (p == NULL) { return false; }
KeyType key = p->dataItem.getKey();
if (searchKey > key) {
return retrieveHelper(p->right, searchKey, searchDataItem);
}
if (searchKey < key) {
return retrieveHelper(p->left, searchKey, searchDataItem);
}
searchDataItem = p->dataItem;
return true;
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::writeKeysHelper(BSTreeNode *p) const {
if (p == NULL) { return; }
writeKeysHelper(p->left);
cout << p->dataItem.getKey() << " ";
writeKeysHelper(p->right);
}
template<typename T, class KeyType>
int BSTree<T, KeyType>::getCountHelper(BSTreeNode *p) const {
if (p == NULL) { return 0; }
return getCountHelper(p->left) + getCountHelper(p->right) + 1;
}
template<typename T, class KeyType>
int BSTree<T, KeyType>::getHeightHelper(BSTreeNode *p) const {
if (p == NULL) { return 0; }
return max(getHeightHelper(p->left), getHeightHelper(p->right)) + 1;
}
template<typename T, class KeyType>
void BSTree<T, KeyType>::writeLTHelper(BSTreeNode *p, const KeyType &searchKey) const {
if (p == NULL) { return; }
KeyType key = p->dataItem.getKey();
writeLTHelper(p->left, searchKey);
if (key < searchKey) {
cout << key << " ";
writeLTHelper(p->right, searchKey);
}
}
#include "show9.cpp"
-----------------------------------------------------
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
------------------------
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include <stdexcept>
#include <iostream>
#include <cmath>
using namespace std;
#include "BSTree.cpp"
template<typename T, typename KeyType>
class HashTable {
public:
HashTable(int initTableSize);
HashTable(const HashTable &other);
HashTable& operator=(const HashTable &other);
~HashTable();
void insert(const T &newDataItem);
bool remove(const KeyType &deleteKey);
bool retrieve(const KeyType &searchKey, T &returnItem) const;
void clear();
bool isEmpty() const;
void showStructure() const;
double standardDeviation() const;
private:
void copyTable(const HashTable &source);
int tableSize;
BSTree<T, KeyType> *dataTable;
};
#endif // ifndef HASHTABLE_H
-----------------------------------------------------
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;
}
-----------------------------------------------------
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();
}
}
-----------------------------------------------------
show9.cpp
------------------------
#include "BSTree.h"
// 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.
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
}
}
-----------------------------------------------------
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.