C++ problem Write the definitions of the functions search, isItemAtEqual, retrie
ID: 3571504 • Letter: C
Question
C++ problem
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 chapter. Also, write a program to test various hashing
operations.
Problem came from Data Structures using C++ by D.S. Malik
If you have any questions don't hesitate to ask.
Below is the class template provided if it helps.
#ifndef H_Htable
#define H_Htable
//****************************************************************
// Author: D.S. Malik
//
// 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
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
bool hashT<elemType>::isItemAtEqual(int hashIndex, const elemType& rec) const
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
void hashT<elemType>::retrieve(int hashIndex, elemType& rec) const
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
void hashT<elemType>::remove(int hashIndex, const elemType& rec)
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
void hashT<elemType>::print() const
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
hashT<elemType>::hashT(int size)
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
template <class elemType>
hashT<elemType>::~hashT()
{
cout<<"See Programming Exercise 7 at the end of Chapter 9."<<endl;
}
#endif
Explanation / Answer
#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
struct HashN
{
int element;
enum EntryType info;
};
struct HashT
{
int size;
HashN *table;
};
bool isPrime (int n)
{
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n)
{
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int key, int size)
{
return key % size;
}
HashT *initializeTable(int size)
{
HashT *htable;
if (size < MIN_TABLE_SIZE)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
htable = new HashT;
if (htable == NULL)
{
cout<<"Out of Space"<<endl;
return NULL;
}
htable->size = nextPrime(size);
htable->table = new HashN [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
for (int i = 0; i < htable->size; i++)
{
htable->table[i].info = Empty;
htable->table[i].element = NULL;
}
return htable;
}
int Find(int key, HashT *htable)
{
int pos = HashFunc(key, htable->size);
int collisions = 0;
while (htable->table[pos].info != Empty &&
htable->table[pos].element != key)
{
pos = pos + 2 * ++collisions -1;
if (pos >= htable->size)
pos = pos - htable->size;
}
return pos;
}
void Insert(int key, HashT *htable)
{
int pos = Find(key, htable);
if (htable->table[pos].info != Legitimate)
{
htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}
}
HashT *Rehash(HashT *htable)
{
int size = htable->size;
HashN *table = htable->table;
htable = initializeTable(2 * size);
for (int i = 0; i < size; i++)
{
if (table[i].info == Legitimate)
Insert(table[i].element, htable);
}
free(table);
return htable;
}
void Retrieve(HashT *htable)
{
for (int i = 0; i < htable->size; i++)
{
int value = htable->table[i].element;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}
}
int main()
{
int value, size, pos, i = 1;
int choice;
HashT *htable;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"Operations on Quadratic Probing"<<endl;
cout<<" ----------------------"<<endl;
cout<<"1.Initialize size of the table"<<endl;
cout<<"2.Insert element into the table"<<endl;
cout<<"3.Display Hash Table"<<endl;
cout<<"4.Rehash The Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter size of the Hash Table: ";
cin>>size;
htable = initializeTable(size);
cout<<"Size of Hash Table: "<<nextPrime(size);
break;
case 2:
if (i > htable->size)
{
cout<<"Table is Full, Rehash the table"<<endl;
continue;
}
cout<<"Enter element to be inserted: ";
cin>>value;
Insert(value, htable);
i++;
break;
case 3:
Retrieve(htable);
break;
case 4:
htable = Rehash(htable);
break;
case 5:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.