Question

/*
* C++ Program to Implement Hash Tables with Quadratic Probing
*/

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;

//-----------------------------------------------------------------------
// Node Type Declaration
//-----------------------------------------------------------------------
enum EntryType
{
Legi, Emp, Del
};

//-----------------------------------------------------------------------
// Node Declaration
//-----------------------------------------------------------------------
struct HashTableEntry
{
int e;
enum EntryType info;
};

//-----------------------------------------------------------------------
// Table Declaration
//-----------------------------------------------------------------------
struct HashTable
{
int size;
HashTableEntry *t;
};

//-----------------------------------------------------------------------
// Function: isPrime Function
// Return whether n is prime or not
//-----------------------------------------------------------------------
bool isPrime (int n) //Complete the function stubs needed to implement the operations
{
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;
}

//-----------------------------------------------------------------------
// Function: nextPrime Function
// Finding next prime size of the table
//-----------------------------------------------------------------------
int nextPrime(int n)
{
if (n % 2 == 0)
++n;
while (!IsPrime(n)) n += 2;
return n;
}

//-----------------------------------------------------------------------
// Function: Hash Function
//-----------------------------------------------------------------------
int HashFunc(int key, int size) //Complete the function stubs needed to implement the operations
{

}

//-----------------------------------------------------------------------
// Function: initiateTable Function
// Initialize Table
//-----------------------------------------------------------------------
HashTable *initiateTable(int size)
{
HashTable *ht;
if (size < MIN_TABLE_SIZE)
{
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
ht= new HashTable;
  
if (ht == NULL)
{
cout<<"Out of Space"<<endl;
return NULL;
}
ht->size = nextPrime(size);
ht->t = new HashTableEntry [ht->size];
  
if (ht->t == NULL)
{
cout<<"Table Size is Too Small"<<endl;
return NULL;
}
  
for (int i = 0; i < ht->size; i++)
{
ht->t[i].info = Emp;
ht->t[i].e = 0;
}
return ht;
}

//-----------------------------------------------------------------------
// Function: Search Element at a key
//-----------------------------------------------------------------------
int SearchKey(int key, HashTable *ht) //Complete the function stubs needed to implement the operations
{

}

//-----------------------------------------------------------------------
// Function: Insert Element at a key
//-----------------------------------------------------------------------
void Insert(int key, HashTable *ht) //Complete the function stubs needed to implement the operations
{

}

//-----------------------------------------------------------------------
// Function: Rehash
//-----------------------------------------------------------------------
HashTable *Rehash(HashTable *ht) //Complete the function stubs needed to implement the operations
{

}

//-----------------------------------------------------------------------
// Function: Display Hash Table
//-----------------------------------------------------------------------
void display(HashTable *ht)
{
for (int i = 0; i < ht->size; i++)
{
int value = ht->t[i].e;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}
}

Answer 1

Sharing the code for Implementing Hash Tables with Quadratic Probing:

#include <iostream>
#include <cstdlib>
#define MIN_TABLE_SIZE 10
using namespace std;
/*
* Node Type Declaration
*/
enum EntryType {Legitimate, Empty, Deleted};
/*
* Node Declaration
*/
struct Node
{
int element;
enum EntryType info;
};
/*
* Table Declaration
*/
struct HashTable
{
int size;
Node *table;
};
/*
* Returns whether n is prime or not
*/
bool isPrime (int x)
{
if (x == 2 || x == 3)
return true;
if (x == 1 || x % 2 == 0)
return false;
for (int i = 3; i * i <= x; i += 2)
if (x % i == 0)
return false;
return true;
}
/*
* Finding next prime size of the table
*/
int nextPrime(int n)
{
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
/*
* Function To Generate Hash
*/
int HashFunc(int key, int size)
{
return key % size;
}
/*
* Function to Initialize Table
*/
HashTable *initializeTable(int size)
{
HashTable *htable;
if (size < MIN_TABLE_SIZE)
{
cout<<"Table Size Too Small"<<endl;
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Out of Space"<<endl;
return NULL;
}
htable->size = nextPrime(size);
htable->table = new Node [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;
}
/*
* Function to Find Element at a key
*/
int Find(int key, HashTable *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;
}
/*
* Function to Insert Element into a key
*/
void Insert(int key, HashTable *htable)
{
int pos = Find(key, htable);
if (htable->table[pos].info != Legitimate)
{
htable->table[pos].info = Legitimate;
htable->table[pos].element = key;
}
}
/*
* Function to Rehash the Table
*/
HashTable *Rehash(HashTable *htable)
{
int size = htable->size;
Node *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;
}
/*
* Function to Retrieve Hash Table
*/
void Retrieve(HashTable *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;
}

}
/*
* Main Contains Menu
*/
int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<"\n----------------------"<<endl;
cout<<"Operations on Quadratic Probing"<<endl;
cout<<"\n----------------------"<<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 Table"<<endl;
cout<<"5.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<" 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<<"\nEnter correct option\n";
}
}
return 0;
}