Hi everyone.
We were given a homework to code a hash table. The objects and their members were given by our professor and we were only supposed to implement the functions (Add, Remove, Contains and Print), so I shouldn't change the objects. I should also do a copy constructor and a assignment operator (but that's another story i don't think I'll have any problems with that after I solve my current problem). The code compiles just fine but at first I got a segmentation fault on the line 158:
HashTable[HashCode(key)].Add(key). In debug mode HashCode(key) = 5 which is OK (5%10 = 5) so I tried to print every element of the array in the constructor itself. HashTable[0] works fine but HashTable[1] gives the segmentation fault so I guess the allocation fails or there's a logical error as I'm pretty new to OOP (although I thought that I pretty much get it).
I'd be thankful for any help.
#include <iostream>
#include <new>
using namespace std;
class Set
{
public:
typedef string T;
virtual void Add(const T& key) = 0;
virtual bool Contains(const T& key) = 0;
virtual void Print() = 0;
virtual void Remove(const T& key) = 0;
};
class ListSet: public Set
{
private:
struct Node
{
T value;
Node* next;
};
Node* first;
public:
ListSet()
{
first = NULL;
};
~ListSet()
{
Node* next = NULL;
while (first != NULL)
{
next = first->next;
delete first;
first = next;
}
};
void Add(const T& key)
{
Node* handle = first;
Node* prev = NULL;
if (Contains(key) == true)
{
return;
}
while (handle != NULL)
{
prev = handle;
handle = handle->next;
}
handle = new (nothrow) Node;
handle->value = key;
if (first == NULL)
{
first = handle;
}
if (prev != NULL)
{
prev->next = handle;
}
};
bool Contains(const T& key)
{
Node* handle = first;
while (handle != NULL)
{
if (key.compare(handle->value) == 0)
{
return true;
}
handle = handle->next;
}
return false;
};
void Print()
{
Node* handle = first;
if (handle == NULL)
{
cout << "Som prazdny...\n";
}
while (handle != NULL)
{
cout << (handle->value).c_str() << " ";
handle = handle->next;
}
};
void Remove(const T& key)
{
Node* handle = first;
Node* prev = NULL;
if (Contains(key) == false)
{
return;
}
while (key.compare(handle->value) != 0)
{
prev = handle;
handle = handle->next;
}
if (prev != NULL)
{
prev->next = handle->next;
}
else
{
first = handle->next;
}
delete handle;
};
};
class HashSet: public Set
{
private:
Set* HashTable;
short size;
short HashCode(const T& key)
{
return (key.length())%size;
};
public:
HashSet(short size = 10)
{
this->size = size;
HashTable = new (nothrow) ListSet [size];
int i;
for (i=0; i<size; i++)
{
HashTable[i].Print();
}
};
~HashSet()
{
delete[] HashTable;
};
void Add(const T& key)
{
HashTable[HashCode(key)].Add(key);
};
bool Contains(const T& key)
{
return HashTable[HashCode(key)].Contains(key);
};
void Print()
{
int i;
for (i=0; i<size; i++)
{
HashTable[i].Print();
cout << "\n";
}
};
void Remove(const T& key)
{
HashTable[HashCode(key)].Remove(key);
};
};
int main()
{
Set* table = new (nothrow) HashSet();
table->Add("Peter");
table->Print();
cout << "Pre ukoncenie programu stlacte enter...";
cin.get();
delete table;
return 0;
}