Help complete my C++ Lab and make it compile to do: - Implement the Hash Table A
ID: 3865389 • Letter: H
Question
Help complete my C++ Lab and make it compile
to do:
- Implement the Hash Table ADT (80 points)
- Programming Exercise 3 (20 points)
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;
}
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();
}
}
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
}
}
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)
{
}
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"
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.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
Explanation / Answer
Please find your answer as below and sorry i got the answer for only 1st part I din't get what exactly you were asking in 2nd part. anyway I'm coding for your 1st part.
---------------------------------------------------------------------------------------------------------------------------------------------------------
Code:
/*
* C++ Program for Hash Tables
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
/*
* HashNode Class Declaration
*/
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};
/*
* DeletedNode Class Declaration
*/
class DeletedNode:public HashNode
{
private:
static DeletedNode *entry;
DeletedNode():HashNode(-1, -1)
{}
public:
static DeletedNode *getNode()
{
if (entry == NULL)
entry = new DeletedNode();
return entry;
}
};
DeletedNode *DeletedNode::entry = NULL;
/*
* HashMap Class Declaration
*/
class HashMap
{
private:
HashNode **htable;
public:
HashMap()
{
htable = new HashNode* [TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
{
htable[i] = NULL;
}
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (htable[i] != NULL && htable[i] != DeletedNode::getNode())
delete htable[i];
}
delete[] htable;
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (htable[hash_val] == DeletedNode::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
htable[deletedindex] = new HashNode(key, value);
else
htable[hash_val] = new HashNode(key, value);
}
if(init != hash_val)
{
if (htable[hash_val] != DeletedNode::getNode())
{
if (htable[hash_val] != NULL)
{
if (htable[hash_val]->key == key)
htable[hash_val]->value = value;
}
}
else
htable[hash_val] = new HashNode(key, value);
}
}
/*
* Search Element at a key
*/
int Search(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
return -1;
else
return htable[hash_val]->value;
}
/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && htable[hash_val] != NULL)
{
delete htable[hash_val];
htable[hash_val] = DeletedNode::getNode();
}
}
};
/*
* Main Contains Menu
*/
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<" ----------------------"<<endl;
cout<<"1.Insert element"<<endl;
cout<<"2.Search element"<<endl;
cout<<"3.Delete element"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Please Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.Search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}
---------------------------------------------------------------------------------------------------------------------------------------------------------
Please feel free to comment if you have any doubts.
Happy Chegging !!!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.