Help complete my C++ Lab and make it compile

to do:

- Implement the Hash Table ADT (80 points) (hashtable.cpp)

- Programming Exercise 3 (20 points)

(Photo below is Programming Exercise 3)

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

val += str[i];

}

return val;

}

void print_help() {

cout

cout

cout

cout

cout

cout

cout

cout

}

int main(int argc, char **argv) {

HashTable table(7);

print_help();

do {

table.showStructure();

cout

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

break;

case '-':

if (table.remove(item.getKey())) {

cout

} else {

cout

}

break;

case '?':

if (table.retrieve(item.getKey(), item)) {

cout

} else {

cout

}

break;

case 'C':

case 'c':

cout

table.clear();

break;

case 'E':

case 'e':

cout

break;

case 'Q':

case 'q':

return 0;

default:

cout

}

} while (1);

return 0;

}

show10.cpp:

#include "HashTable.h"

// show10.cpp: contains implementation of the HashTable showStructure function

template

void HashTable::showStructure() const {

for (int i = 0; i

cout

dataTable[i].writeKeys();

}

}

show9.cpp:

#include "BSTree.h"

//-------------------------------------------------------------------- // // Laboratory 9 show9.cpp // // Linked implementation of the showStructure operation for the // Binary Search Tree ADT // //--------------------------------------------------------------------

//--------------------------------------------------------------------

template 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

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template 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 dataItem.getKey(); // Output key if ( ( p->left != 0 ) && // Output "connector" ( p->right != 0 ) ) cout right != 0 ) cout left != 0 ) cout left,level+1); // Output left subtree } }

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)

{

}

BSTree.cpp:

#include "BSTree.h"

template

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

{

}

template

BSTree::BSTree ()

{

root = NULL;

}

template

BSTree::BSTree ( const BSTree& other )

{

}

template

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

{

}

template

BSTree::~BSTree ()

{

}

template

void BSTree::insert ( const DataType& newDataItem )

{

}

template

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

{

return false;

}

template

bool BSTree::remove ( const KeyType& deleteKey )

{

return false;

}

template

void BSTree::writeKeys () const

{

}

template

void BSTree::clear ()

{

}

template

bool BSTree::isEmpty () const

{

return false;

}

template

int BSTree::getHeight () const

{

return -1;

}

template

int BSTree::getCount () const

{

return -1;

}

template

void BSTree::writeLessThan ( const KeyType& searchKey ) const

{

}

#include "show9.cpp"

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

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

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

e distributed among the table ming Exercise 2-there is mal perfect hashes become items increases. In the worst ained off one hash table entry and y a binary search tree and the Performance of hash tables depends on how uniformly the keys are distributed among entries. In the ideal situation-a minimal perfect hash, see Programming Exercise exactly one data item per hash table entry. Unfortunately, minimal perfect hashes bi progressively more difficult to generate as the number of data items increases. In the possible key distribution scenario, all the data items would be chained off one hash ta all the other table entries would be empty. This is essentially a binary search tree performance benefits of the hash table are lost. Rather than trying to develop a perfect developers usually build a hash function that will attempt to distribute the keys uniformly all the table entries. Each table entry will have the same-or almost the same-number o associated with it. Suppose that you have developed a hash function that you believe does a satisfactory job of distributing keys over the table. A good question to ask is "How uniform a distribution is the hash function achieving?" The formal mathematical answers are beyond the scope of this lab text. However, one simple way of calculating this is to calculate the standard deviation of the number of data items associated with each table entry. The standard deviation number does not claim to answer whether or not a particular hash implementation is good or bad, but it can be used as a rough comparison among hash functions used with the same table size and set of keys. The smaller the number obtained, the closer the hash function comes to providing a uniform distribution. The formula to calculate the standard deviation, s, is e distributed among the table ming Exercise 2-there is mal perfect hashes become items increases. In the worst ained off one hash table entry and y a binary search tree and the Performance of hash tables depends on how uniformly the keys are distributed among entries. In the ideal situation-a minimal perfect hash, see Programming Exercise exactly one data item per hash table entry. Unfortunately, minimal perfect hashes bi progressively more difficult to generate as the number of data items increases. In the possible key distribution scenario, all the data items would be chained off one hash ta all the other table entries would be empty. This is essentially a binary search tree performance benefits of the hash table are lost. Rather than trying to develop a perfect developers usually build a hash function that will attempt to distribute the keys uniformly all the table entries. Each table entry will have the same-or almost the same-number o associated with it. Suppose that you have developed a hash function that you believe does a satisfactory job of distributing keys over the table. A good question to ask is "How uniform a distribution is the hash function achieving?" The formal mathematical answers are beyond the scope of this lab text. However, one simple way of calculating this is to calculate the standard deviation of the number of data items associated with each table entry. The standard deviation number does not claim to answer whether or not a particular hash implementation is good or bad, but it can be used as a rough comparison among hash functions used with the same table size and set of keys. The smaller the number obtained, the closer the hash function comes to providing a uniform distribution. The formula to calculate the standard deviation, s, is