******C++****** can you help me out with whats wrong with this hash table. It do
ID: 3918245 • Letter: #
Question
******C++****** can you help me out with whats wrong with this hash table. It does execute but adding node it goes to segmentation fault.
#include <vector>
#include <string>
#include <stdlib.h>
#include <iostream>
#include <climits>
#include "HashTable.hpp"
#include <stack>
using namespace std;
template <int ARRAY_LEN>
HashTable<ARRAY_LEN>::HashTable() {
tableSize = ARRAY_LEN;
for(int j = 0; j < tableSize; j++){
lookupTable[j] = NULL;
}
}
template <int ARRAY_LEN>
HashTable<ARRAY_LEN>::~HashTable() {
stack <ZippedBookNode*> wordItemStack;
for(int i = 0; i<ARRAY_LEN; i++){
ZippedBookNode* c;
for(ZippedBookNode*c=lookupTable[i]; c; c=c->next) wordItemStack.push(c);
while(!wordItemStack.empty()){
c=wordItemStack.top();
delete c;
wordItemStack.pop();
}
}
// delete[] wordItemStack;
// TODO: delete all the nodes. No need to delete the lookupTable because
// it's created on the stack (thanks to our friend template we were able to
// pass at initialization the size of the table)
}
template <int ARRAY_LEN>
int HashTable<ARRAY_LEN>::getTableSize() {
if(ARRAY_LEN <= 0){
return -1;
}
else{
tableSize = ARRAY_LEN;
return tableSize;
}
}
template <int ARRAY_LEN>
int HashTable<ARRAY_LEN>::hashSum(string bookTitle){
int sum = 0;
char letter;
if(bookTitle!="empty"){
for(int i = 0;i<bookTitle.length();i++){
letter = bookTitle[i];
sum = sum + (int)letter; //ASCII value of ith character in the string
}
sum = sum % ARRAY_LEN ;
return sum;
}
// TODO: create the hash function that will sum the ASCII values of the title
return -1;
}
template <int ARRAY_LEN>
void HashTable<ARRAY_LEN>::insertNode(ZippedBookNode* node) {
cout<<node->title<<endl;
int sum = hashSum(node->title);
cout<<sum<<endl;
if(!lookupTable[sum]){
lookupTable[sum]=node;
}
else{
ZippedBookNode* tmp=lookupTable[sum];
while(tmp->next){
tmp=tmp->next;
}
tmp->next=node;
}
}
// while(tmp){
// TODO: insert the new node in the linkedlist.
// Where will you insert the new node? How do you know that?
//We will insert it in lookupTable node which is inside HashTable class, It is know because lookupTable act as universal node which can be access by other function
// What cases should you consider?
//wheather node exist or not
// list[HashFunction(node->key)].insert(newNode);
// What should you do in case of collision?
template <int ARRAY_LEN>
void HashTable<ARRAY_LEN>::printTitles() {
ZippedBookNode *current = new ZippedBookNode;
for (int i = 0; i < ARRAY_LEN; i++) {
if (lookupTable[i] != NULL){
current = lookupTable[i];
cout <<"#"<<current->title;
while(current -> next != NULL) {
current = current -> next;
cout<<"->"<<current->title;
}
cout<<endl;
}
}
}
Explanation / Answer
Dear student,
As per my knowledge in cpp am answering this question. And here i can provide u code for hashtable implementation which will be executed and gives you result.
In this program given by you hashtable.hpp is a file thas had already been developed by you.
1. This file you included in this program means u r program using code of hashtable.hpp.
2. First check hashtable.hpp for errors.
3. If no errors then use it in this program. If at all any erros check for memory requirements such as node creation.
4. you mentioned that segmentation fault. This error is due to memory limitations or accessing out of scope variable.
The following code works and helps you.
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int TABLE_SIZE = 5;
// HashNode Class
class HashNode
{
public:
int key;
int value;
HashNode(int key, int value)
{
this->key = key;
this->value = value;
}
};
// DeletedNode Class
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
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;
}
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();
}
}
};
// 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
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.