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

BSTree::BSTreeNode::BSTreeNode ( const DataType &nodeDataItem, BSTreeNode *leftPtr, BSTreeNode *rightPtr )

{

}

template < typename DataType, class KeyType >

BSTree::BSTree ()

{

root = NULL;

}

template < typename DataType, class KeyType >

BSTree::BSTree ( const BSTree& other )

{

}

template < typename DataType, class KeyType >

BSTree& BSTree:: operator= ( const BSTree& other )

{

}

template < typename DataType, class KeyType >

BSTree::~BSTree ()

{

}

template < typename DataType, class KeyType >

void BSTree::insert ( const DataType& newDataItem )

{

}

template < typename DataType, class KeyType >

bool BSTree::retrieve ( const KeyType& searchKey, DataType& searchDataItem ) const

{

return false;

}

template < typename DataType, class KeyType >

bool BSTree::remove ( const KeyType& deleteKey )

{

return false;

}

template < typename DataType, class KeyType >

void BSTree::writeKeys () const

{

}

template < typename DataType, class KeyType >

void BSTree::clear ()

{

}

template < typename DataType, class KeyType >

bool BSTree::isEmpty () const

{

return false;

}

template < typename DataType, class KeyType >

int BSTree::getHeight () const

{

return -1;

}

template < typename DataType, class KeyType >

int BSTree::getCount () const

{

return -1;

}

template < typename DataType, class KeyType >

void BSTree::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

#include

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& other ); // Copy constructor

BSTree& operator= ( const BSTree& 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 #include #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 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 ( 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

HashTable::HashTable(int initTableSize)

{

}

template

HashTable::HashTable(const HashTable& other)

{

}

template

HashTable& HashTable::operator=(const HashTable& other)

{

}

template

HashTable::~HashTable()

{

}

template

void HashTable::insert(const DataType& newDataItem)

{

}

template

bool HashTable::remove(const KeyType& deleteKey)

{

return false;

}

template

bool HashTable::retrieve(const KeyType& searchKey, DataType& returnItem) const

{

return false;

}

template

void HashTable::clear()

{

}

template

bool HashTable::isEmpty() const

{

return true;

}

#include "show10.cpp"

template

double HashTable::standardDeviation() const

{

}

template

void HashTable::copyTable(const HashTable& source)

{

}

HashTable.h

// HashTable.h

#ifndef HASHTABLE_H

#define HASHTABLE_H

#include

#include

using namespace std;

#include "BSTree.cpp"

template

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* 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:: 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:: 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 << "\t"; 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

void HashTable::showStructure() const {

for (int i = 0; i < tableSize; ++i) {

cout << i << ": ";

dataTable[i].writeKeys();

}

}

test10.cpp

#include

#include

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 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

#include

#include

#include

#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

// 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 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;

}

}