Write the definitions of the functions search, isItemAtEqual, retrieve, remove,
ID: 3683974 • Letter: W
Question
Write the definitions of the functions search, isItemAtEqual, retrieve, remove, and print, the constructor, and the destructor for the class hashT, as described in the section, ‘‘Hashing: Implementation Using Quadratic Probing,’’ of this week's reading.
Here is the starting class header file for hashT:
//Use these data sets to test the program
//78 45 67 22 11 110 300 292 65 89 98 66 109 27 61 71
//10 20 30 35 77 68 15 87 54 57 195 78 25 111 37 83
//10 20 30 35 77 68 110 87 54 57 195 292 65 89 98 300
//(indexStatusList[hashIndex] != 0 && indexStatusList[hashIndex] != -1)
#include <iostream>
#include "hashT.h"
using namespace std;
int hashFunc(int num);
int main()
{
hashT<int> intHashTable(19);
int num;
int key;
bool found;
cout << "Enter 16 integers." << endl;
for (int i = 0; i < 16; i++)
{
cin >> num;
key = hashFunc(num);
intHashTable.insert(key, num);
}
intHashTable.print();
cout << "Enter item to be deleted: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.remove(key, num);
intHashTable.print();
cout << "Enter item to be searched: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.search(key, num, found);
if (found)
cout << "Item found in the list" << endl;
else
cout << "Item not in the list." << endl;
cout << "Enter item to be inserted: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.insert(key, num);
intHashTable.print();
return 0;
}
int hashFunc(int num)
{
return num % 19;
}
Here are the main driver:
#ifndef H_Htable
#define H_Htable
//****************************************************************
// Designed by Malik of Cengage Publishing
//
// This class specifies the members to implement a hash table as
// an ADT. It uses quadratic probing to resolve collisions.
//****************************************************************
#include <iostream>
#include <cassert>
using namespace std;
template <class elemType>
class hashT
{
public:
void insert(int hashIndex, const elemType& rec);
//Function to insert an item in the hash table. The first
//parameter specifies the initial hash index of the item to
//be inserted. The item to be inserted is specified by the
//parameter rec.
//Postcondition: If an empty position is found in the hash
// table, rec is inserted and the length is incremented by
// one; otherwise, an appropriate error message is
// displayed.
void search(int& hashIndex, const elemType& rec, bool& found) const;
//Function to determine whether the item specified by the
//parameter rec is in the hash table. The parameter hashIndex
//specifies the initial hash index of rec.
//Postcondition: If rec is found, found is set to true and
// hashIndex specifies the position where rec is found;
// otherwise, found is set to false.
bool isItemAtEqual(int hashIndex, const elemType& rec) const;
//Function to determine whether the item specified by the
//parameter rec is the same as the item in the hash table
//at position hashIndex.
//Postcondition: Returns true if HTable[hashIndex] == rec;
// otherwise, returns false.
void retrieve(int hashIndex, elemType& rec) const;
//Function to retrieve the item at position hashIndex.
//Postcondition: If the table has an item at position
// hashIndex, it is copied into rec.
void remove(int hashIndex, const elemType& rec);
//Function to remove an item from the hash table.
//Postcondition: Given the initial hashIndex, if rec is found
// in the table it is removed; otherwise, an appropriate
// error message is displayed.
void print() const;
//Function to output the data.
hashT(int size = 101);
//constructor
//Postcondition: Create the arrays HTTable and indexStatusList;
// initialize the array indexStatusList to 0; length = 0;
// HTSize = size; and the default array size is 101.
~hashT();
//destructor
//Postcondition: Array HTable and indexStatusList are deleted.
private:
elemType *HTable; //pointer to the hash table
int *indexStatusList; //pointer to the array indicating the
//status of a position in the hash table
int length; //number of items in the hash table
int HTSize; //maximum size of the hash table
};
template <class elemType>
void hashT<elemType>::insert(int hashIndex, const elemType& rec)
{
int pCount;
int inc;
pCount = 0;
inc = 1;
while (indexStatusList[hashIndex] == 1
&& HTable[hashIndex] != rec
&& pCount < HTSize / 2)
{
pCount++;
hashIndex = (hashIndex + inc ) % HTSize;
inc = inc + 2;
}
if (indexStatusList[hashIndex] != 1)
{
HTable[hashIndex] = rec;
indexStatusList[hashIndex] = 1;
length++;
}
else if (HTable[hashIndex] == rec)
cerr << "Error: No duplicates are allowed" << endl;
else
cerr << "Error: The table is full. "
<<"Unable to resolve the collision" << endl;
}
template <class elemType>
void hashT<elemType>::search(int& hashIndex, const elemType& rec,
bool& found) const
{
//Place your search code here
}
template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
//Place your retrieve code here
}
template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
//Place your retrieve code here
}
template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
//Place your remove code here
}
template <class elemType>
void hashT<elemType>::print() const
{
for (int i = 0; i < HTSize; i++)
if (indexStatusList[i] != 0)
cout << i << " " << indexStatusList[i]
<< " " << HTable[i] << endl;
}
template <class elemType>
hashT<elemType>::hashT(int size)
{
assert(size > 0);
HTable = new elemType[size];
indexStatusList = new int[size];
length = 0;
HTSize = size;
for (int i = 0; i < size; i++)
indexStatusList[i] = 0;
}
template <class elemType>
hashT<elemType>::~hashT()
{
delete [] HTable;
delete [] indexStatusList;
}
#endif
Explanation / Answer
#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
using namespace std;
const int TABLE_SIZE = 128;
/*
* HashNode Class Declaration
*/
class HashNode
{
public:
int key;
int value;
HashNode* next;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
this->next = NULL;
}
};
/*
* HashMap Class Declaration
*/
class hashT
{
private:
HashNode** htable;
public:
hashT()
{
htable = new HashNode*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
htable[i] = NULL;
}
~hashT()
{
for (int i = 0; i < TABLE_SIZE; ++i)
{
HashNode* entry = htable[i];
while (entry != NULL)
{
HashNode* prev = entry;
entry = entry->next;
delete prev;
}
}
delete[] htable;
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
void insert(int key, int num)
{
int hash_val = HashFunc(key);
HashNode* prev = NULL;
HashNode* entry = htable[hash_val];
while (entry != NULL)
{
prev = entry;
entry = entry->next;
}
if (entry == NULL)
{
entry = new HashNode(key, value);
if (prev == NULL)
{
htable[hash_val] = entry;
}
else
{
prev->next = entry;
}
}
else
{
entry->value = value;
}
}
/*
* Remove Element at a key
*/
void remove(int key, int num)
{
int hash_val = HashFunc(key);
HashNode* entry = htable[num];
HashNode* prev = NULL;
if (entry == NULL || entry->key != key)
cout<<"No Element found at key "<<key<<endl;
return;
}
while (entry->next != NULL)
{
prev = entry;
entry = entry->next;
}
if (prev != NULL)
{
prev->next = entry->next;
}
delete entry;
cout<<"Element Deleted"<<endl;
}
/*
* Search Element at a key
*/
bool search(int key,int num,bool& found)
{
found = false;
int hash_val = HashFunc(key);
HashNode* entry = htable[num];
while (entry != NULL)
{
if (entry->key == key)
{
cout<<entry->value<<" ";
found = true;
}
entry = entry->next;
}
return found;
}
};
/*
* Main Contains Menu
*/
int main()
{
hashT<int> intHashTable(19);
int key, num;
bool found;
cout << "Enter 16 integers." << endl;
for (int i = 0; i < 16; i++)
{
cin >> num;
key = hashFunc(num);
intHashTable.insert(key, num);
}
intHashTable.print();
cout << "Enter item to be deleted: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.remove(key, num);
intHashTable.print();
cout << "Enter item to be searched: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.search(key, num, found);
if (found == true)
cout << "Item found in the list" << endl;
else
cout << "Item not in the list." << endl;
cout << "Enter item to be inserted: ";
cin >> num;
cout << endl;
key = hashFunc(num);
intHashTable.insert(key, num);
intHashTable.print();
return 0;
}
int hashFunc(int num)
{
return num % 19;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.