In this programming assignment, you will design and implement a (n) algorithm to use a hash table to determine the most frequently occurring integer in an array of 'n' integers as well as print the associated largest frequency. You are given a singly Linked List-based implementation of a Hash table. You could augment this code to do the assignment. The main function is setup to generate an array of random integers (of size numElements) in the range [1...maxValue]; the hash function is given by K mod hashTableSize where K is an integer data in the array. C++

#include #include //srand, rand #include //clock_t, clock, CLOCKS_PER_SEC using namespace std;

// implementing hash tables as an array of linked lists

class Node{ private: int data; Node* nextNodePtr; public: Node(){} void setData(int d){ data = d; }

int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePtr(){ return nextNodePtr; } };

class List{

private: Node *headPtr; public: List(){ headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr(){ return headPtr; } bool isEmpty(){ if (headPtr->getNextNodePtr() == 0) return true; return false; } void insert(int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; while (currentNodePtr != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodePtr); }

void IterativePrint(){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << ", "; currentNodePtr = currentNodePtr->getNextNodePtr(); } cout << endl; } bool containsElement(int searchData){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ if (currentNodePtr->getData() == searchData) return true; currentNodePtr = currentNodePtr->getNextNodePtr(); } return false; } };

class Hashtable{ private: List* listArray; int tableSize; public: Hashtable(int size){ tableSize = size; listArray = new List[size]; } int getTableSize(){ return tableSize; } void insert(int data){ int hashIndex = data % tableSize; listArray[hashIndex].insert(data); } bool hasElement(int data){ int hashIndex = data % tableSize; return listArray[hashIndex].containsElement(data); } void printHashTable(){ for (int hashIndex = 0; hashIndex < tableSize; hashIndex++){ cout << "Hash Index: " << hashIndex << " : " ; listArray[hashIndex].IterativePrint(); } } List getListAtIndex(int index){ return listArray[index]; } };

int main(){

int numElements; cout << "Enter the number of elements you want to store in the array: "; cin >> numElements; int maxValue; cout << "Enter the maximum value for an element: "; cin >> maxValue;

int hashTableSize; cout << "Enter the size of the hash table: "; cin >> hashTableSize; Hashtable hashTable(hashTableSize); srand(time(NULL)); int array[numElements]; cout << "Elements generated: "; for (int index = 0; index < numElements; index++){ array[index] = 1 + (rand() % maxValue); cout << array[index] << " "; hashTable.insert(array[index]); } cout << endl; cout << " Contents of the Hash Table " << endl; hashTable.printHashTable();

// Implement here the code to determine and print the most frequently occuring data/integer // in the array and its frequency system("pause"); return 0; }