( PLease Give me answer in JUST C++ launguage , this is very important final pro

Question

( PLease Give me answer in JUST C++ launguage , this is very important final project question , please give me FULL answer)

Write a complete program to hash a list of 200 words to a hash table using linear probing and a 70% load factor. Print the table. Give the number of probes for each word and the average number of probes to search for each word. The program should allow the user to interact with the program until the user wishes to stop. The user should be allowed to delete a word, search for a word and give the number of probes to find that word. The program shou1d rehash all words if 10% (20) of the words are deleted. The program should print the table every time it hashes/rehashes the words.

You are to create a Word Dictionary that contains 200 words – You can read from any document to get the words (cannot contain: common words, contain numbers, duplicate words) Your input file (a separate program) is the following - You are to create NumberWord list that takes the words in the Word Dictionary and converts them to numbers using ascii values. Each letter of the word is given a numeric value from the asci table (all letter should be converted to lowercase).

Hash each word to a hash table using linear probing and a 70% load factor for full credit, you must

Use functions

Use header files to hold all function definitions

The program will rehash if 10% or more of the words are deleted

Should catch the following errors:

Word not in the list

A word that is supposed to be in the list but was deleted and there is no holding spot to designate that the word has been deleted

Try/catch for input and output files

Should give the number of probes to search and locate all the words in the Word List

The end user should be able to

to delete word(s)

search for a word

Explanation / Answer

ANSWER::

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};
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;
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;
}
int HashFunc(int key)
{
return key % TABLE_SIZE;
}
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);
}
}
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;
}
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();
}
}
};
int main()
{
HashMap hash;
int key, value;
int choice;
while(1)
{
cout<<"Operations on Hash Table"<<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 #
• Subjects

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