在 C++ 中实现将字符串映射到数组的散列 table。我一直收到 "Debug Assertion Failed"，我不知道为什么

Question

正如标题所说，我正在尝试实现一个散列 table，它使用散列函数将字符串映射到数组中。散列table使用单独的链接方法来处理冲突，因此需要链表（散列table实现为链表数组）。我一直收到 "Debug Assertion Failed" 错误，但我似乎找不到问题所在。我用我的代码尝试了很多东西，尤其是在构造函数和析构函数上，但仍然没有结果。这是我所有的代码。请帮助我仍然是编程的新手。我正在使用 Microsoft Visual Studio 2010 Ultimate。

文件：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");
}

文件：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
};

文件：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;
}

文件：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();
};

文件：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;
    }
}

Answer 1

您的问题在这里：

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

    delete arr;
}

您正在调用 delete arr，但您将 arr 分配给了 new[]。您需要致电：

delete[] arr;

在 C++ 中实现将字符串映射到数组的散列 table。我一直收到 "Debug Assertion Failed"，我不知道为什么

Implementing a hash table that maps strings to an array in C++. I keep getting "Debug Assertion Failed" and I don't know why

c++

hash

hashmap

hashtable

hash-function