C++ (Only need the new Hash Table ADT operation -standardDeviation- part impleme

Question

C++   (Only need the new Hash Table ADT operation -standardDeviation- part implemented. )

Please implement the following function using the information below. Thank you!

Standard deviation is calculated as follows:

1.) calculate and save the average or mean number of data items per table entry.

2.) For each table entry , calculate and save (numbers of data items per table entry.

3.) Compute the sum of all the values calculated in step 2.

4.) Divide the result from step 3 by n-1, where n is the number of hash tables entries.

5.) Calculate the square root of the result obtained in Step 4. This is the standard deviation.

----------------------------------------------------------------------------------------------------------------------------

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

template <typename DataType, typename KeyType>
double HashTable<DataType, KeyType>::standardDeviation() const
{
}

template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::copyTable(const HashTable& source)
{
}

Explanation / Answer

HashTable.cpp

#include <iostream>

#include "HashTable.h"

template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(int initTableSize): tableSize(initTableSize)
{
   dataTable = new BSTree<DataType, KeyType>[tableSize];
}

template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::HashTable(const HashTable& source) {
   if (this != &source) {
       *this = source;
   }
}

template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>&
HashTable<DataType, KeyType>::operator=(const HashTable& source) {
   copyTable(source);
   return *this;
}

template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::copyTable(const HashTable& source) {
   unsigned int count = 0;
   tableSize = source.tableSize;
   dataTable(tableSize);
   for (count; count < tableSize; count++) {
       dataTable[count] = source.dataTable[count];
   }
}

template <typename DataType, typename KeyType>
HashTable<DataType, KeyType>::~HashTable() {
   clear();
}

template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::insert(const DataType& newDataItem) {
   int index = newDataItem.hash(newDataItem.getKey()) % tableSize;
   dataTable[index].insert(newDataItem);
}

template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::remove(const KeyType& deleteKey) {
   DataType temp;
   int index = temp.hash(deleteKey) % tableSize;
   return dataTable[index].remove(deleteKey);
}

template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::retrieve(const KeyType& searchKey,
   DataType& returnItem) const{
   int index = returnItem.hash(searchKey) % tableSize;
   return dataTable[index].retrieve(searchKey, returnItem);
}

template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::clear() {
   for (int i = 0; i < tableSize; i++)
       dataTable[i].clear();
}

template <typename DataType, typename KeyType>
bool HashTable<DataType, KeyType>::isEmpty() const {
   for (int i = 0; i < tableSize; i++)
       if (dataTable[i].isEmpty() == false)
           return false;
   return true;
}

#include <cmath>

template <typename DataType, typename KeyType>
double HashTable<DataType, KeyType>::standardDeviation() const {
   int total = 0;

   for (int i = 0; i < tableSize; ++i) {
       total += dataTable[i].getCount();
   }

   double average = total / tableSize;
   double sum = 0.0;

   for (int i = 0; i < tableSize; ++i) {
       int size = dataTable[i].getCount();
       sum += (size - average) * (size - average);
   }

   return sqrt(sum / (tableSize - 1));
}

template <typename DataType, typename KeyType>
void HashTable<DataType, KeyType>::showStructure() const {
   for (int i = 0; i < tableSize; ++i) {
       cout << i << ": ";
       dataTable[i].writeKeys();
   }
}

HashTable.h

// HashTable.h

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <stdexcept>
#include <iostream>

using namespace std;

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

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.