Code:
#include iostream
#include cstdlib
#define MIN_TABLE_SIZE 10
using namespace std;
/*
* Node Type Declaration
*/
enum EntryType {Legitimate, Empty, Deleted};
/*
* Node Declaration
*/
struct HashNode
{
int element;
enum EntryType info;
};
/*
* Table Declaration
*/
struct HashTable
{
int size;
HashNode *table;
};
/*
* Returns whether n is prime or not
*/
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;
}
/*
* 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"<
return NULL;
}
htable = new HashTable;
if (htable == NULL)
{
cout<<"Out of Space"<
return NULL;
}
htable->size = nextPrime(size);
htable->table = new HashNode [htable->size];
if (htable->table == NULL)
{
cout<<"Table Size Too Small"<
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;
HashNode *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: "<
else
cout<<"Position: "<
}
}
/*
* Main Contains Menu
*/
int main()
{
int value, size, pos, i = 1;
int choice;
HashTable *htable;
while(1)
{
cout<<"\n----------------------"<
cout<<"Operations on Quadratic Probing"<
cout<<"\n----------------------"<
cout<<"1.Initialize size of the table"<
cout<<"2.Insert element into the table"<
cout<<"3.Display Hash Table"<
cout<<"4.Rehash The Table"<
cout<<"5.Exit"<
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: "<
break;
case 2:
if (i > htable->size)
{
cout<<"Table is Full, Rehash the table"<
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;
}
Output:
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 5
Table Size Too Small
Size of Hash Table: 5
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 10
Size of Hash Table: 11
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 100
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 200
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 300
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 400
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 500
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 600
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 700
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 800
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 900
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1000
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1100
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: 1100
Position: 2 Element: 100
Position: 3 Element: 200
Position: 4 Element: 300
Position: 5 Element: 400
Position: 6 Element: 500
Position: 7 Element: 600
Position: 8 Element: 700
Position: 9 Element: 800
Position: 10 Element: 900
Position: 11 Element: 1000
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 4
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: Null
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 2200
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3300
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4400
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5500
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6600
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: 5500
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: 4400
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: 3300
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: 2200
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: 6600
----------------------
Operations on Quadratic Probing
----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter your choice: 5
------------------
(program exited with code: 1)
Press return to continue
More C++ Programs:
