Telephone Book Database Implementation using HashTable | Linear Probing with Replacement | Linear Probing without Replacement
Problem Statement: Consider telephone book database of N clients. Make use of a hash table implementation to quickly look up client‘s telephone number. Make use of two collision handling techniques and compare them using number of comparisons required to find a set of telephone numbers (use linear probing with replacement and without replacement)
Note:- Scroll horizontally to see the full line of code.
#include <iostream>
using namespace std;
class record
{
string name;
long long int number;
int link;
public:
record()
{
this->name = "";
this->number = 0;
link = -1;
}
record(string name, long long int number)
{
this->name = name;
this->number = number;
this->link = -1;
}
friend class hashTableWithoutReplacement;
friend class hashTableWithReplacement;
};
class hashTableWithoutReplacement
{
int n;
record *table = NULL;
public:
hashTableWithoutReplacement(int n)
{
this->n = n;
table = new record[this->n];
}
int hashFunction(long long int number);
void addRecord(string name, long long int number);
void showRecord();
void searchRecord(long long int number);
};
int hashTableWithoutReplacement::hashFunction(long long int number)
{
return number % n;
}
void hashTableWithoutReplacement::addRecord(string name, long long int number)
{
int address = hashFunction(number);
int prevAddress;
record temp(name, number);
if (table[address].number == 0)
{
table[address] = temp;
return;
}
else
{
prevAddress = address;
while (table[address].link != -1)
{
address = table[address].link;
prevAddress = address;
}
}
while (table[address].number != 0)
{
if (address == n - 1)
{
address = 0;
}
else
{
address++;
}
}
table[prevAddress].link = address;
table[address] = temp;
}
void hashTableWithoutReplacement::showRecord()
{
cout << "Name\t\tNumber\t\tLink" << endl;
for (int i = 0; i < n; i++)
{
if (table[i].number == 0)
{
cout << "----\t\t----\t\t" << table[i].link << endl;
}
else
{
cout << table[i].name << "\t\t" << table[i].number << "\t" << table[i].link << endl;
}
}
}
void hashTableWithoutReplacement::searchRecord(long long int number)
{
int count = 0;
int address = hashFunction(number);
while (true)
{
if (table[address].number == number)
{
count++;
cout << "Name: " << table[address].name << endl;
cout << "Number: " << table[address].number << endl;
cout << "No. of comparisons for the searching in without replacement are " << count << endl;
return;
}
else if (table[address].link == -1)
{
return;
}
else
{
count++;
address = table[address].link;
}
}
}
class hashTableWithReplacement
{
int n;
record *table = NULL;
public:
hashTableWithReplacement(int n)
{
this->n = n;
table = new record[this->n];
}
int hashFunction(long long int number);
void addRecord(string name, long long int number);
void showRecord();
void searchRecord(long long int number);
};
int hashTableWithReplacement::hashFunction(long long int number)
{
return number % n;
}
void hashTableWithReplacement::searchRecord(long long int number)
{
int count = 0;
int address = hashFunction(number);
while (true)
{
if (table[address].number == number)
{
count++;
cout << "Name: " << table[address].name << endl;
cout << "Number: " << table[address].number << endl;
cout << "No. of comparisons for the searching in with replacement are " << count << endl;
return;
}
else if (table[address].link == -1)
{
return;
}
else
{
count++;
address = table[address].link;
}
}
}
void hashTableWithReplacement::addRecord(string name, long long int number)
{
int address = hashFunction(number);
int prevAddress;
record temp(name, number);
if (table[address].number == 0)
{
table[address] = temp;
return;
}
else
{
if (address == hashFunction(table[address].number))
{
prevAddress = address;
while (table[address].link != -1)
{
address = table[address].link;
prevAddress = address;
}
}
else
{
record temp1 = table[address];
// hashfunction of non synonym collision element
int m = hashFunction(table[address].number);
int prevm;
while (table[m].number != temp1.number)
{
prevm = m;
m = table[m].link;
}
table[prevm].link = temp1.link;
table[address] = temp;
addRecord(temp1.name, temp1.number);
return;
}
}
while (table[address].number != 0)
{
if (address == n - 1)
{
address = 0;
}
else
{
address++;
}
}
table[prevAddress].link = address;
table[address] = temp;
}
void hashTableWithReplacement::showRecord()
{
cout << "Name\t\tNumber\t\tLink" << endl;
for (int i = 0; i < n; i++)
{
if (table[i].number == 0)
{
cout << "----\t\t----\t\t" << table[i].link << endl;
}
else
{
cout << table[i].name << "\t\t" << table[i].number << "\t" << table[i].link << endl;
}
}
}
int main()
{
int n;
cout << "Enter the no. of records: ";
cin >> n;
hashTableWithoutReplacement hashTable(n);
hashTableWithReplacement hashTable1(n);
int num;
string name;
long long int number;
cout << "No. of entries to be entered: ";
cin >> num;
for (int i = 0; i < num; i++)
{
cout << "Enter Name: ";
cin >> name;
cout << "Enter Number: ";
cin >> number;
hashTable.addRecord(name, number);
hashTable1.addRecord(name, number);
}
char cont = 'y';
while (cont == 'y')
{
cout << "<-----------Menu----------->" << endl;
cout << "1. Print the Records" << endl;
cout << "2. Search the Record" << endl;
int choice;
cout << "Enter the Choice: ";
cin >> choice;
switch (choice)
{
case 1:
cout << "Hashtable without Replacement" << endl;
hashTable.showRecord();
cout << "Hashtable with Replacement" << endl;
hashTable1.showRecord();
break;
case 2:
cout << "Enter the no. to be searched: ";
cin >> number;
hashTable.searchRecord(number);
cout << endl;
hashTable1.searchRecord(number);
break;
default:
cout << "INVALID Choice!!!" << endl;
break;
}
cout << "Do you want to continue? (y/n): ";
cin >> cont;
}
cout << "Program Ended Successfully!!!" << endl;
return 0;
}
Comments
Post a Comment