AaBbC AaBbCel AaBb .:a.. Emphasis Heading 111 Normal! Subtitle Title 1N0 Spac He

Question

AaBbC AaBbCel AaBb .:a.. Emphasis Heading 111 Normal! Subtitle Title 1N0 Spac Heading 2 Subtle Ern Intense E., St. raph Styles Write C++ Program to implement the Hash Table Your program should be able storing and searching items from Hash tables. Hash Table The hash table data structure is based on the idea of using table lookup to speed up an arbitrary mapping. For our purposes, we are interested in mapping strings into integers We cannot use strings directly as indices into an array. However, we can define an auxiliary function that converts strings into such indices. Such a function is called a hash function. Thus we could imagine a two-step process to map a string into an integer: for a given string calculate the hash function and then use the result to access an array that contains the pre-computed value of the mapping at that offset Key-value pairs records) Keys Indexes A small phone book as a hash table Hash Tables anana apple kiwi mango pear cantaloupe uncti Submit Mar 22, 2018, upload your solutions to Moodle. You should upload a single zip file that contains a CSC254 Hash epp, CSC254 Hash.h, and main.cpp, the files containing the C++ source code D o Do not put any unnecessary files such as the files generated from your favorite IDE, and name your zip file as follows. "Project,NAMES URNAME.zip"

Explanation / Answer

/*
* C++ Program to Implement Hash Tables with Linear Probing
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;

/*
* HashNode Class Declaration
*/
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};

/*
* DeletedNode Class Declaration
*/
class DeletedNode:public HashNode
{
private:
static DeletedNode *entry;
DeletedNode():HashNode(-1, -1)
{}
public:
static DeletedNode *getNode()
{
if (entry == NULL)
entry = new DeletedNode();
return entry;
}
};
DeletedNode *DeletedNode::entry = NULL;
/*
* HashMap Class Declaration
*/
class HashMap
{
private:
HashNode **htable;
public:
HashMap()
{
htable = new HashNode* [TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
{
htable[i] = NULL;
}
}

~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
{
if (htable[i] != NULL && htable[i] != DeletedNode::getNode())
delete htable[i];
}
delete[] htable;
}
/*
* Hash Function
*/
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
/*
* Insert Element at a key
*/
void Insert(int key, int value)
{
int hash_val = HashFunc(key);
int init = -1;
int deletedindex = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
if (htable[hash_val] == DeletedNode::getNode())
deletedindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
{
if(deletedindex != -1)
htable[deletedindex] = new HashNode(key, value);
else
htable[hash_val] = new HashNode(key, value);
}
if(init != hash_val)
{
if (htable[hash_val] != DeletedNode::getNode())
{
if (htable[hash_val] != NULL)
{
if (htable[hash_val]->key == key)
htable[hash_val]->value = value;
}
}
else
htable[hash_val] = new HashNode(key, value);
}
}
/*
* Search Element at a key
*/
int Search(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (htable[hash_val] == NULL || hash_val == init)
return -1;
else
return htable[hash_val]->value;
}
/*
* Remove Element at a key
*/
void Remove(int key)
{
int hash_val = HashFunc(key);
int init = -1;
while (hash_val != init && (htable[hash_val]
== DeletedNode::getNode() || htable[hash_val]
!= NULL && htable[hash_val]->key != key))
{
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && htable[hash_val] != NULL)
{
delete htable[hash_val];
htable[hash_val] = DeletedNode::getNode();
}
}
};

/*
* Main Contains Menu
*/
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<" ----------------------"<<endl;
cout<<"Operations on Hash Table"<<endl;
cout<<" ----------------------"<<endl;
cout<<"1.Insert element into the table"<<endl;
cout<<"2.Search element from the key"<<endl;
cout<<"3.Delete element at a key"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter your choice: ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter element to be inserted: ";
cin>>value;
cout<<"Enter key at which element to be inserted: ";
cin>>key;
hash.Insert(key, value);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
cin>>key;
if(hash.Search(key) == -1)
{
cout<<"No element found at key "<<key<<endl;
continue;
}
else
{
cout<<"Element at key "<<key<<" : ";
cout<<hash.Search(key)<<endl;
}
break;
case 3:
cout<<"Enter key of the element to be deleted: ";
cin>>key;
hash.Remove(key);
break;
case 4:
exit(1);
default:
cout<<" Enter correct option ";
}
}
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.