-3

So as the title says I'm trying to implement a hash table that uses a hash function to map strings into an array. The hash table uses separate chaining method to handle collisions and thus requires linked list (the hash table is implemented as an array of linked lists). I keep getting that "Debug Assertion Failed" error and I can't seem to find the problem. I tried lots of things with my code, especially on the constructors and destructors and still no result. Here are all of my codes. Please help I am still a newbie in programming. I am using Microsoft Visual Studio 2010 Ultimate.

FILE: main.cpp

#include <iostream>
#include "HashTable.h"
using namespace std;

void simpleTest();

int main()
{
    simpleTest();
    system("pause");
    return 0;
}

void simpleTest()
{
    HashTable ht1(9);
    ht1.insert("bat");
    ht1.insert("lion");
    ht1.insert("panther");
    ht1.insert("cat");
    ht1.insert("michael");
    ht1.insert("rhinoceros");
    ht1.insert("duck");
    ht1.insert("bear");
    ht1.insert("shark");
    ht1.insert("elephant");
    ht1.insert("hippopotamus");
    ht1.insert("john");
}

FILE: HashTable.h

#pragma once

#include "LinkedList.h"

class HashTable
{
public:
    HashTable(); //default constructor
    HashTable(int); //one parameter constructor
    HashTable(const HashTable&); //copy constructor
    ~HashTable(); //destructor
    HashTable& operator=(const HashTable&); //assignment operator
    bool insert(const string&);
    bool remove(const string&);
    bool search(const string&) const;
    int size() const; //return numOfItems
    int maxSize() const; //return arrSize
    int loadFactor() const;
    vector<string> intersection(const HashTable&) const;
    vector<string> unions(const HashTable&) const;
    vector<string> difference(const HashTable&) const;
private:
    LinkedList* arr;
    int arrSize;
    int numOfItems;
    int hashFunc(const string&) const;
    int getPrime(int) const;
    bool isPrime(int) const;
    void deepCopy(const HashTable& h);
    vector<string> get() const; //returns a vector of all the strings in the HashTable
};

FILE: HashTable.cpp

#include "HashTable.h"

#include <iostream>
using namespace std;

//PRIVATE MEMBER FUNCTIONS

int HashTable::hashFunc(const string& s) const //hash function
{
    int hashVal=0,asc;
    for(int i=0;i<s.size();i++)
    {
        asc=s[i]>96?s[i]-96:s[i]-64;
        hashVal=(hashVal*32+asc)%arrSize;
    }
    cout<<hashVal<<endl;
    return hashVal;
}

int HashTable::getPrime(int n) const
{
    int i=2*n;
    while(!isPrime(i))
        i++;
    return i;
}

bool HashTable::isPrime(int n) const
{
    bool isPrime=true;
        for(int count=2;count<n && isPrime; count++)
            if(n%count==0)
                isPrime=false;
    return isPrime;
}

void HashTable::deepCopy(const HashTable& h)
{
    if(arr!=NULL)
        delete arr;
    numOfItems=h.size();
    arrSize=h.maxSize();
    arr=new LinkedList[arrSize];
    for(int i=0;i<arrSize;i++)
        arr[i]=h.arr[i];
}

vector<string> HashTable::get() const //returns a vector of all the strings in the hash table
{
    vector<string> v,tmp_v;
    for(int i=0;i<maxSize();i++)
    {
        tmp_v=arr[i].get();
        for(int j=0;j<tmp_v.size();j++)
            v.push_back(tmp_v[j]);
    }
    return v;
}

/*END OF PRIVATE MEMBER FUNCTIONS*/

/*==========================================================================*/

//PUBLIC MEMBER FUNCTIONS

HashTable::HashTable() //default constructor
{
    arrSize=101;
    arr=new LinkedList[arrSize];
    numOfItems=0;
}

HashTable::HashTable(int n) //creates a hash table to store n items where the size of the array is the smallest prime number >= 2*n
{
    arrSize=getPrime(n);
    arr=new LinkedList[arrSize];
    numOfItems=0;
}

HashTable::HashTable(const HashTable& h) //copy constructor
{
    deepCopy(h);
}

HashTable::~HashTable() //destructor
{
    for(int i=0;i<arrSize;i++)
        arr[i].deleteList();
    delete arr;
}

HashTable& HashTable::operator=(const HashTable& h) //assignment operator
{
    if(this!=&h)
    {
        if(h.arr!=NULL)
            delete arr;
        deepCopy(h);
    }
    return *this;
}

bool HashTable::insert(const string& s) //inserts string s if it doesn't exist in the hash table and returns 1 if insertion successful, 0 otherwise
{
    int hash=hashFunc(s);
    bool successOrFail=arr[hash].insert(s);
    numOfItems++;
    return successOrFail;
}

bool HashTable::remove(const string& s) //removes string s if s exist in the hash table and returns 1 if removal successful, 0 otherwise
{
    int hash=hashFunc(s);
    bool successOrFail=arr[hash].remove(s);
    numOfItems--;
    return successOrFail;
}

bool HashTable::search(const string& s) const //returns 1 if s exist in the hash table, 0 otherwise
{
    int hash=hashFunc(s);
    bool found=arr[hash].search(s);
    return found;
}

int HashTable::size() const //returns numOfItems
{
    return numOfItems;
}

int HashTable::maxSize() const //returns arrSize
{
    return arrSize;
}

int HashTable::loadFactor() const //returns the load factor of the hash table
{
    return numOfItems/arrSize;
}

vector<string> HashTable::intersection(const HashTable& h) const //returns a vector of string containing intersection of calling object's data and h's data
{
    vector<string> ret_v;
    vector<string> v=this->get();
    for(int i=0;i<v.size();i++)
        if(h.search(v[i]))
            ret_v.push_back(v[i]);
    return ret_v;
}

vector<string> HashTable::unions(const HashTable& h) const //returns a vector of string containing union of calling object's data and h's data
{
    vector<string> ret_v;
    vector<string> v1=this->get();
    vector<string> v2=h.get();
    for(int i=0;i<v2.size();i++) //push_back all h elements
        ret_v.push_back(v2[i]);
    for(int i=0;i<v1.size();i++) //push_back caller elements that are not found in h
        if(!h.search(v1[i]))
            ret_v.push_back(v1[i]);
    return ret_v;
}

vector<string> HashTable::difference(const HashTable& h) const //returns a vector of string containing set difference of calling object's data and h's data
{
    vector<string> ret_v;
    vector<string> v1=this->get();
    vector<string> v2=h.get();
    for(int i=0;i<v1.size();i++) //push_back caller elements that are not found in h
        if(!h.search(v1[i]))
            ret_v.push_back(v1[i]);
    for(int i=0;i<v2.size();i++) //push_back h elements that are not found in caller
        if(!this->search(v1[i]))
            ret_v.push_back(v2[i]);
    return ret_v;
}

FILE: LinkedList.h

#pragma once

#include <cstdlib>
#include <vector>
#include <string>

using namespace std;

class LinkedList
{
public:
    class Node
    {
    public:
        string data;
        Node* next;
        Node(string s):data(s),next(NULL) {};
        Node(string s,Node* nd):data(s),next(nd) {};
    };
    Node* front;
    //member functions
    LinkedList(); //default constructor
    LinkedList(const LinkedList& ls);//copy constructor
    ~LinkedList(); //destructor
    LinkedList& operator=(const LinkedList&); //assignment operator
    bool insert(const string&);
    bool remove(const string&);
    bool search(const string&) const;
    vector<string> get() const;
    void deepCopy(const LinkedList& ls);
    void deleteList();
};

FILE: LinkedList.cpp

#include "LinkedList.h"

LinkedList::LinkedList() //default constructor
{
    front=NULL;
}

LinkedList::LinkedList(const LinkedList& ls) //copy constructor
{
    deepCopy(ls);
}

LinkedList::~LinkedList() //destructor
{
    deleteList();
}

LinkedList& LinkedList::operator=(const LinkedList& ls) //assignment operator
{
    if(this!=&ls)
    {
        deleteList();
        deepCopy(ls);
    }
    return *this;
}

bool LinkedList::insert(const string& s)
{
    if(search(s))
        return false;
    front=new Node(s,front);
    return true;
}

bool LinkedList::remove(const string& s)
{
    Node* temp=front;
    if(temp==NULL) //list is empty
        return false;
    if(temp->data==s) //s is first string in list
    {
        front=temp->next;
        delete temp;
        return true;
    }
    else
    {
        while(temp->next!=NULL){
            if(temp->next->data==s)
            {
                Node* deletedNode=temp->next;
                temp->next=temp->next->next;
                delete deletedNode;
                return true;
            }
            temp=temp->next;
        }
        return false;
    }
}

bool LinkedList::search(const string& s) const
{
    Node* temp=front;
    while(temp!=NULL) //Traverse list
    {
        if(temp->data==s)
            return true;
        temp = temp->next;
    }
    return false;
}

vector<string> LinkedList::get() const
{
    vector<string> str_vec;
    for(Node* temp=front;temp!=NULL;temp=temp->next)
        str_vec.push_back(temp->data);
    return str_vec;
}

void LinkedList::deepCopy(const LinkedList& ls)
{
    front=NULL;
    if(ls.front!=NULL) //Only copy if ls is non-empty
    {
        Node* original=ls.front;
        Node* copy;
        copy=new Node(original->data, NULL);
        front=copy;
        original=original->next;
        while(original!=NULL) //Traverse the original copying each node
        {
            copy->next=new Node(original->data, NULL);
            copy=copy->next;
            original=original->next;
        }
    }
}

void LinkedList::deleteList()
{
    Node* tmp;
    while(front!=NULL){
        tmp=front->next;
        delete front;
        front=tmp;
    }
}
3
  • If this is Visual Studio you can go to the line that the assertion fails on then walk up the callstack to the exact line of your code that caused the assertion to fail.
    – drescherjm
    Apr 30, 2015 at 16:18
  • std::map<std::string, std::vector<std::string>> is much shorter and more versatile. Apr 30, 2015 at 16:25

1 Answer 1

3

Your problem is here:

HashTable::~HashTable() //destructor
{
    for(unsigned int i=0;i<arrSize;i++)
        arr[i].deleteList();

    delete arr;
}

you are calling delete arr, but you allocated arr with new[]. You need to call:

delete[] arr;
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.