C++ finish code, must compile for thumbs up

Last 2 parts left to complete:

- Implement the Hash Table ADT (80 points)

- Programming Exercise 3 (20 points)

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;

}

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();

}

}

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

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

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