I\'m working on this assigmnet, but I\'m not really sure what to do. Design a cl
ID: 665221 • Letter: I
Question
I'm working on this assigmnet, but I'm not really sure what to do.
Design a class template for the ADT HashTable, using the implementation described in this section.The basic operations should include (at least) constructors, a destructor, a copy constructor, inserting an item into a hash table, searching for an item in the hash table, and deleting an item from the hash table. Use random hashing for the hash function and chaining to resolve collisions. You should also write a driver program to test your class template.
Explanation / Answer
BSTree.h
// HEADER FILES
#include "BSTree.h"
#include "show9.cpp"
//using namespace std;
// Binary Search Tree Function Implementations
// The default constructor that creates an empty binary search tree.
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTree()
{
root = NULL;
}
// The copy constructor that initializes BSTree
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTree(const BSTree<DataType,KeyType>& other)
{
*this = other;
}
//The overloaded assignment operator returrns a reference to this object.
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>& BSTree<DataType,KeyType>::operator=(
const BSTree<DataType,KeyType>& other)
{
if(*this == &other)
return *this;
clear();
copyHelper(root, other.root);
return *this;
}
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::copyHelper(BSTreeNode*& p, BSTreeNode* other)
{
if(other != NULL)
{
BSTreeNode *left = NULL;
BSTreeNode *right = NULL;
copyHelper(left, other->left); //Copy left branch
copyHelper(right, other-right); //Copy right branch
p = new BSTreeNode(other->dataItem, left, right); //Reached leaf
}
}
//The destructor deallocates the memory used to store this BSTree.
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::~BSTree()
{
clear();
}
//Inserts newDataItem into this BSTree.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::insert(const DataType& newDataItem)
{
insertHelper(newDataItem, root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::insertHelper(const DataType& newDataItem,
BSTreeNode*& p)
{
//Base case, p is NULL so there is room to insert
if(p == NULL)
{
p = new BSTreeNode(newDataItem, NULL, NULL);
}
else
{
//new data is equal to, so update
if((p->dataItem).getKey() == newDataItem.getKey())
p->dataItem = newDataItem;
//new data is greater than, so insert left
else if((p->dataItem).getKey() > newDataItem.getKey())
insertHelper(newDataItem, p->left);
//new data is less than, so insert right
else
insertHelper(newDataItem, p->right);
}
}
//Searches this BSTree for the data item with key searchKey.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::retrieve(const KeyType& searchKey,
DataType& searchDataItem) const
{
return retrieveHelper(searchKey, searchDataItem, root);
}
// Recursive helper function.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::retrieveHelper(const KeyType& searchKey,
DataType& searchDataItem, BSTreeNode* p) const
{
if(p != NULL)
{
//Base case, key has been found in tree
if(searchKey == (p->dataItem).getKey())
{
//Update the search data item
searchDataItem = p->dataItem;
return true;
}
//Key is less than, so check left
else if (searchKey < (p->dataItem).getKey())
return retrieveHelper(searchKey, searchDataItem, p->left);
//Key is greater than so check right
else
return retrieveHelper(searchKey, searchDataItem, p->right);
}
//Base case, key not found
else
return false;
}
//Deletes the data item with key deleteKey from this BSTree.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::remove(const KeyType& deleteKey)
{
return removeHelper(deleteKey, root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::removeHelper(const KeyType& deleteKey,
BSTreeNode*& p)
{
if(p != NULL)
{
//Delete key found
if(deleteKey == (p->dataItem).getKey())
{
//Node has no children, simply delete
if(p->left == NULL && p->right == NULL)
{
delete p;
p = NULL;
}
//Node only has right child, swap child with parent
else if(p->left == NULL)
{
BSTreeNode* temp = p;
p = p->right;
delete temp;
}
//Node only has left child, swap child with parent
else if(p->right == NULL)
{
BSTreeNode* temp = p;
p = p->left;
delete temp;
}
//Node has both children, find the node that is directly before the
//node in sorted order, delete that one from the tree, and place
//its data into the original node
else
{
//Go left one node
BSTreeNode* temp = p->left;
//Go right as far as you can
while(temp->right != NULL)
temp = temp->right;
//Temp should now be the node before it in sorted orrder
//Swap the data items
p->dataItem = temp->dataItem;
//Remove the temp node in the tree
removeHelper((temp->dataItem).getKey(), p->left);
}
return true;
}
//Delete key is less than the current node, go left
else if(deleteKey < (p->dataItem).getKey())
return removeHelper(deleteKey, p->left);
//Delete key is greater than the current node, go right
else
return removeHelper(deleteKey, p->right);
}
//Node is null
else
return false;
}
//Outputs the keys of the data items
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeKeys() const
{
writeKeysHelper(root);
cout << endl;
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeKeysHelper(BSTreeNode* p) const
{
if(p != NULL)
{
//To write in ascending order, go left, print, then go right
writeKeysHelper(p->left);
cout << (p->dataItem).getKey() << " ";
writeKeysHelper(p->right);
}
}
//Removes all data items
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::clear()
{
clearHelper(root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::clearHelper(BSTreeNode*& p)
{
if(p != NULL)
{
//Clear left branch
clearHelper(p->left);
//Clear right branch
clearHelper(p->right);
//Can't go left or right, so delete self
delete p;
//Set all to NULL
if(p->left != NULL)
p->left = NULL;
if(p->right != NULL)
p->right = NULL;
p = NULL;
}
}
//Returns true if this BSTree is empty. Otherwise, returns false.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::isEmpty() const
{
//If the root is NULL, then obviously the tree doesn't have anything in it
return (root == NULL);
}
//Returns the height of this BSTree.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getHeight() const
{
return getHeightHelper(root, 0);
}
//Recursive helper function.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getHeightHelper(BSTreeNode* p,
int currentLevel) const
{
static int maxLevel = 0;
//If the node is null, then check the current level with the max level
if(p == NULL)
{
if(currentLevel > maxLevel)
maxLevel = currentLevel;
}
//Continue left and right
else
{
getHeightHelper(p->left, currentLevel + 1);
getHeightHelper(p->right, currentLevel + 1);
}
return maxLevel;
}
//Returns the count of the number of data items in this BSTree.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getCount() const
{
return getCountHelper(root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getCountHelper(BSTreeNode* p) const
{
//Base case, no node so don't add
if(p == NULL)
return 0;
//Add 1 and go left and go right
else
return 1 + getCountHelper(p->left) + getCountHelper(p->right);
}
//Outputs all keys in this BSTree that are less than searchKey.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeLessThan(const KeyType& searchKey) const
{
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeLessThanHelper(const KeyType& searchKey,
BSTreeNode* p) const
{
}
//Binary Search Tree Node Function Implmentations
//The parameterized constructor
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTreeNode::BSTreeNode(const DataType& nodeDataItem,
BSTreeNode* leftPtr, BSTreeNode* rightPtr) : dataItem(nodeDataItem),
left(leftPtr), right(rightPtr)
{
}
Hash.cpp
// HEADER FILES
#include "HashTable.h"
#include "show10.cpp"
//using namespace std;
// Hash Table Function Implmentations
//The parameterized constructor
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>::HashTable(int initTableSize)
{
tableSize = initTableSize;
dataTable = new BSTree<DataType, KeyType>[initTableSize];
}
// The copy constructor
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>::HashTable(const HashTable& other)
{
*this = other;
}
//The overloaded assignment operator
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>& HashTable<DataType,KeyType>::operator=(
const HashTable& other)
{
if(this = &other)
return *this;
if(!isEmpty())
clear();
copyTable(other);
return *this;
}
//The destructor
template <typename DataType, typename KeyType>
HashTable<DataType,KeyType>::~HashTable()
{
clear();
}
//Inserts newDataItem
template <typename DataType, typename KeyType>
void HashTable<DataType,KeyType>::insert(const DataType& newDataItem)
{
//The index is based on the modulus operation
int index = newDataItem.hash(newDataItem.getKey()) % tableSize;
//Insert into the BST
dataTable[index].insert(newDataItem);
}
//Removes the data item
template <typename DataType, typename KeyType>
bool HashTable<DataType,KeyType>::remove(const KeyType& deleteKey)
{
DataType temp;
//The index is based on the modulus operation
int index = temp.hash(deleteKey) % tableSize;
//Remove from BST
return dataTable[index].remove(deleteKey);
}
//Searches for the data item
template <typename DataType, typename KeyType>
bool HashTable<DataType,KeyType>::retrieve(const KeyType& searchKey,
DataType& returnItem) const
{
//The index is based on the modulus operation
int index = returnItem.hash(searchKey) % tableSize;
//Retrieve from BST
return dataTable[index].retrieve(searchKey,returnItem);
}
//Removes all data items
template <typename DataType, typename KeyType>
void HashTable<DataType,KeyType>::clear()
{
//Iterate all BSTs and clear them
for(int i = 0; i < tableSize; i++)
dataTable[i].clear();
}
//Returns true if this HashTable is empty.
template <typename DataType, typename KeyType>
bool HashTable<DataType,KeyType>::isEmpty() const
{
//Iterate all BSTs and check if empty
for(int i = 0; i < tableSize; i++)
if(dataTable[i].isEmpty() == false)
return false;
return true;
}
template <typename DataType, typename KeyType>
double HashTable<DataType,KeyType>::standardDeviation() const
{
return -1.0;
}
//Recursive helper function.
template <typename DataType, typename KeyType>
void HashTable<DataType,KeyType>::copyTable(const HashTable& source)
{
//delete the previous dataTable
delete dataTable;
//set the new data table size
dataTable = new BSTree<DataType, KeyType>[source.tableSize];
//copy each element over
for(int i = 0; i < source.tableSize; i++)
dataTable[i] = source.dataTable[i];
}
HashTable.h
#ifndef HASHTABLE_H
#define HASHTABLE_H
//#include <stdexcept.h>
#include <iostream.h>
//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
// HEADER FILES
#include "BSTree.h"
#include "show9.cpp"
//using namespace std;
// Binary Search Tree Function Implementations
//The default constructor
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTree()
{
root = NULL;
}
//The copy constructor
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTree(const BSTree<DataType,KeyType>& other)
{
*this = other;
}
//The overloaded assignment operator
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>& BSTree<DataType,KeyType>::operator=(
const BSTree<DataType,KeyType>& other)
{
if(*this == &other)
return *this;
clear();
copyHelper(root, other.root);
return *this;
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::copyHelper(BSTreeNode*& p, BSTreeNode* other)
{
if(other != NULL)
{
BSTreeNode *left = NULL;
BSTreeNode *right = NULL;
copyHelper(left, other->left); //Copy left branch
copyHelper(right, other-right); //Copy right branch
p = new BSTreeNode(other->dataItem, left, right); //Reached leaf
}
}
//The destructor
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::~BSTree()
{
clear();
}
//Inserts newDataItem into this BSTree.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::insert(const DataType& newDataItem)
{
insertHelper(newDataItem, root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::insertHelper(const DataType& newDataItem,
BSTreeNode*& p)
{
//Base case, p is NULL so there is room to insert
if(p == NULL)
{
p = new BSTreeNode(newDataItem, NULL, NULL);
}
else
{
//new data is equal to, so update
if((p->dataItem).getKey() == newDataItem.getKey())
p->dataItem = newDataItem;
//new data is greater than, so insert left
else if((p->dataItem).getKey() > newDataItem.getKey())
insertHelper(newDataItem, p->left);
//new data is less than, so insert right
else
insertHelper(newDataItem, p->right);
}
}
//Searches this BSTree for the data item with key searchKey.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::retrieve(const KeyType& searchKey,
DataType& searchDataItem) const
{
return retrieveHelper(searchKey, searchDataItem, root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::retrieveHelper(const KeyType& searchKey,
DataType& searchDataItem, BSTreeNode* p) const
{
if(p != NULL)
{
//Base case, key has been found in tree
if(searchKey == (p->dataItem).getKey())
{
//Update the search data item
searchDataItem = p->dataItem;
return true;
}
//Key is less than, so check left
else if (searchKey < (p->dataItem).getKey())
return retrieveHelper(searchKey, searchDataItem, p->left);
//Key is greater than so check right
else
return retrieveHelper(searchKey, searchDataItem, p->right);
}
//Base case, key not found
else
return false;
}
//Deletes the data item with key deleteKey
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::remove(const KeyType& deleteKey)
{
return removeHelper(deleteKey, root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::removeHelper(const KeyType& deleteKey,
BSTreeNode*& p)
{
if(p != NULL)
{
//Delete key found
if(deleteKey == (p->dataItem).getKey())
{
//Node has no children, simply delete
if(p->left == NULL && p->right == NULL)
{
delete p;
p = NULL;
}
//Node only has right child, swap child with parent
else if(p->left == NULL)
{
BSTreeNode* temp = p;
p = p->right;
delete temp;
}
//Node only has left child, swap child with parent
else if(p->right == NULL)
{
BSTreeNode* temp = p;
p = p->left;
delete temp;
}
else
{
//Go left one node
BSTreeNode* temp = p->left;
//Go right as far as you can
while(temp->right != NULL)
temp = temp->right;
//Temp should now be the node before it in sorted orrder
//Swap the data items
p->dataItem = temp->dataItem;
//Remove the temp node in the tree
removeHelper((temp->dataItem).getKey(), p->left);
}
return true;
}
//Delete key is less than the current node, go left
else if(deleteKey < (p->dataItem).getKey())
return removeHelper(deleteKey, p->left);
//Delete key is greater than the current node, go right
else
return removeHelper(deleteKey, p->right);
}
//Node is null
else
return false;
}
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeKeys() const
{
writeKeysHelper(root);
cout << endl;
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeKeysHelper(BSTreeNode* p) const
{
if(p != NULL)
{
//To write in ascending order, go left, print, then go right
writeKeysHelper(p->left);
cout << (p->dataItem).getKey() << " ";
writeKeysHelper(p->right);
}
}
//Removes all data items
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::clear()
{
clearHelper(root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::clearHelper(BSTreeNode*& p)
{
if(p != NULL)
{
//Clear left branch
clearHelper(p->left);
//Clear right branch
clearHelper(p->right);
//Can't go left or right, so delete self
delete p;
//Set all to NULL
if(p->left != NULL)
p->left = NULL;
if(p->right != NULL)
p->right = NULL;
p = NULL;
}
}
//Returns true if this BSTree is empty.
template<typename DataType, class KeyType>
bool BSTree<DataType,KeyType>::isEmpty() const
{
//If the root is NULL, then obviously the tree doesn't have anything in it
return (root == NULL);
}
//Returns the height of this BSTree.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getHeight() const
{
return getHeightHelper(root, 0);
}
//Recursive helper function.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getHeightHelper(BSTreeNode* p,
int currentLevel) const
{
static int maxLevel = 0;
//If the node is null, then check the current level with the max level
if(p == NULL)
{
if(currentLevel > maxLevel)
maxLevel = currentLevel;
}
//Continue left and right
else
{
getHeightHelper(p->left, currentLevel + 1);
getHeightHelper(p->right, currentLevel + 1);
}
return maxLevel;
}
//Returns the count of the number of data items in this BSTree.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getCount() const
{
return getCountHelper(root);
}
//Recursive helper function.
template<typename DataType, class KeyType>
int BSTree<DataType,KeyType>::getCountHelper(BSTreeNode* p) const
{
//Base case, no node so don't add
if(p == NULL)
return 0;
//Add 1 and go left and go right
else
return 1 + getCountHelper(p->left) + getCountHelper(p->right);
}
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeLessThan(const KeyType& searchKey) const
{
}
//Recursive helper function.
template<typename DataType, class KeyType>
void BSTree<DataType,KeyType>::writeLessThanHelper(const KeyType& searchKey,
BSTreeNode* p) const
{
}
// Binary Search Tree Node Function Implmentations
//The parameterized constructor
template<typename DataType, class KeyType>
BSTree<DataType,KeyType>::BSTreeNode::BSTreeNode(const DataType& nodeDataItem,
BSTreeNode* leftPtr, BSTreeNode* rightPtr) : dataItem(nodeDataItem),
left(leftPtr), right(rightPtr)
{
}
show10.cpp
template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::showStructure() const {
for (int i = 0; i < tableSize; ++i) {
cout << i << ": ";
dataTable[i].writeKeys();
}
}