如何修复访问冲突读取位置错误？

Question

我目前正在开发一个使用哈希的程序 table。我在我自己的 Hash table class 上工作，程序可以运行，但在完成涉及 hash table 的工作后崩溃。我得到的错误是访问冲突读取位置错误。我花了几个小时检查我的代码，但仍然找不到我做错了什么或程序崩溃的原因。下面是我的问题 classes：

Hashtable.h:

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <string>
#include "LinkedList.h"
#include <iostream>

using namespace std;

class hashTable
{
    public:

        hashTable();
        virtual ~hashTable();
        void insertNode(string nodeData);
        bool removeNode(string nodeKey);
          Node * checkForDuplicate( string nodeData );

    private:
        LinkedList * tableArray;
        int length;
        int hash(string stateKey);

};

#endif // HASHTABLE_H

Hashtable.cpp:

#include "hashTable.h"


hashTable::hashTable()
{
   length = 181667;
   tableArray = new LinkedList[length];

}

int hashTable::hash(string stateKey) {

    int multiplier = 1;
    int total = 0;
    int l = stateKey.length();
    for(int i = l - 1; i > -1; --i) {
        int temp;
        temp = (stateKey[i] - '0') * multiplier;
        total += temp;
        multiplier = multiplier * 10;
    }
    return(total) % length;
}

void hashTable::insertNode(string stateData) {

    Node * newNode;
    newNode = new Node;

    newNode->data = stateData;

    int index = hash(newNode -> data);

    tableArray[index].insertNode(newNode);

    delete newNode;

}

bool hashTable::removeNode(string nodeKey) {

    int index = hash(nodeKey);
    return tableArray[index].removeNode(nodeKey);

}

Node * hashTable::checkForDuplicate( string nodeData )
{
    int index = hash( nodeData );

    return tableArray[ index ].getNode(nodeData);   
}


hashTable::~hashTable()
{
    delete [] tableArray;
    //dtor
}

LinkedList.h:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include<string>
#include<iostream>

using namespace std;

struct Node {
    string data;
    Node *next;

};

class LinkedList
{
    public:
        LinkedList();
        void insertNode(Node * newNode);
        bool removeNode(string stateData);
        Node * getNode(string stateData);
        int getLength();

        virtual ~LinkedList();

    private:
        Node * top;
        int length;
};

#endif // LINKEDLIST_H

LinkedList.cpp:

#include "LinkedList.h"

LinkedList::LinkedList()
{
    top = new Node;
    top->next = NULL;
    length = 0;

}

void LinkedList :: insertNode(Node * newNode) {

    Node * a = top;
    Node * b = top;

    while(b) {

        a = b;
        b = a -> next;

        if (a== NULL) { break; }
    }

    a -> next = newNode;
    newNode -> next = NULL;
    length++;
 }


bool LinkedList :: removeNode(string stateData) {

    if(!top -> next){
        return false;
    }
    Node * a = top;
    Node * b = top;

    while(b) {
        if(b->data == stateData) {
            a->next = b->next;
            delete b;
            length--;
            return true;
        }
        a = b;
        b = a ->next;
    }
    return false;
}

Node * LinkedList :: getNode(string stateData) {

    if(top == NULL) { return NULL ;}

    Node * current = top;

    while (current->next != NULL) {

        if((current->data == stateData)) {
            return current;
        }
        current = current -> next;
    }

    return NULL;
}

int LinkedList :: getLength() {

    return length;
}

LinkedList::~LinkedList()
{
    Node * a = top;
    Node * b = top;
    while (b) {
        a = b;
        b = a->next;
        if(b) delete a;
    }

}

Answer 1

您的 hashTable::insertNode() 方法正在分配一个新的 Node 对象，然后将其传递给 LinkedList::insertNode() 以 取得对象的所有权 ，但是然后 delete 之后就是它 ，从而使 LinkedList 带有一个指向无效内存的悬空指针。对该节点的任何访问都将导致未定义的行为。不要 delete LinkedList 之后的新节点拥有它。

如果 LinkedList::insertNode() 使用 string 而不是 Node* 指针作为输入会更好。让LinkedList在内部分配新节点。

此外，您的 LinkedList() 实现总体上还有一些其他小问题（比如没有遵循 Rule of Three，并且没有使用双链表来实现更高效的插入和删除）。

尝试更像这样的东西：

Hashtable.h:

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <string>
#include "LinkedList.h"

class hashTable
{
public:
    hashTable();
    hashTable(const hashTable &src);
    ~hashTable();

    void insertNode(const std::string &nodeData);
    bool removeNode(const std::string &nodeData);
    bool checkForDuplicate(const std::string &nodeData);

    hashTable& operator=(const hashTable &rhs);

private:
    std::vector<LinkedList> tableArray;
    int length;

    int hash(const std::string &nodeData);
};

#endif // HASHTABLE_H

Hashtable.cpp:

#include "hashTable.h"

hashTable::hashTable()
   : length(181667), tableArray(new LinkedList[length])
{
}

hashTable::hashTable(const hashTable &src)
    : length(src.length), tableArray(new LinkedList[length])
{
    for (int i = 0; i < length; ++i)
        tableArray[i] = src.tableArray[i];
}

hashTable::~hashTable()
{
    delete[] tableArray;
}

hashTable& hashTable::operator=(const hashTable &rhs)
{
    hashTable tmp(rhs);
    std::swap(tableArray, tmp.tableArray);
    std::swap(length, tmp.length);
    return *this;
}

int hashTable::hash(const std::string &nodeData)
{
    int multiplier = 1;
    int total = 0;
    int l = nodeData.length();
    for(int i = l - 1; i > -1; --i)
    {
        int temp = (nodeData[i] - '0') * multiplier;
        total += temp;
        multiplier *= 10;
    }
    return total % length;
}

void hashTable::insertNode(const std::string &nodeData)
{
    int index = hash(nodeData);
    tableArray[index].insertNode(nodeData);
}

bool hashTable::removeNode(const std::string &nodeData)
{
    int index = hash(nodeData);
    return tableArray[index].removeNode(nodeData);
}

bool hashTable::checkForDuplicate(const std::string &nodeData)
{
    int index = hash(nodeData);
    return (tableArray[index].getNode(nodeData) != NULL);
}

LinkedList.h:

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <string>

struct Node
{
    std::string data;
    Node *previous;
    Node *next;
};

class LinkedList
{
public:
    LinkedList();
    LinkedList(const LinkedList &src);
    ~LinkedList();

    void insertNode(const std::string &nodeData);
    bool removeNode(const std::string &nodeData);
    Node* getNode(const std::string &nodeData);
    int getLength();

    LinkedList& operator=(const LinkedList &rhs);

private:
    Node *head;
    Node *tail;
    int length;
};

#endif // LINKEDLIST_H

LinkedList.cpp:

#include "LinkedList.h"
#inclue <algorithm>

LinkedList::LinkedList()
    : head(NULL), tail(NULL), length(0)
{
}

LinkedList::LinkedList(const LinkedList &src)
    : head(NULL), tail(NULL), length(0)
{
    Node *current = src.top;
    while (current != NULL)
    {
        insertNode(current->data);
        current = current->next;
    }
}

LinkedList::~LinkedList()
{
    Node *current = top;
    while (current != NULL)
    {
        Node *next = current->next;
        delete current;
        current = next;
    }
}

LinkedList& LinkedList::operator=(const LinkedList &rhs)
{
    LinkedList tmp;

    Node *current = rhs.top;
    while (current != NULL)
    {
        tmp.insertNode(current->data);
        current = current->next;
    }

    std::swap(top, tmp.top);
    std::swap(bottom, tmp.bottom);
    std::swap(length, tmp.length);

    return *this;
}

void LinkedList::insertNode(const string &nodeData)
{
    Node *newNode = new Node;    
    newNode->data = nodeData;
    newNode->previous = NULL;
    newNode->next = NULL;

    if (top == NULL) top = newNode;
    if (bottom != NULL)
    {
        newNode->previous = bottom;
        bottom->next = newNode;
    }
    bottom = newNode;

    length++;
 }

bool LinkedList::removeNode(const string &nodeData)
{
    Node* node = getNode(nodeData);
    if (node != NULL)
    {
        if (node->next != NULL)
            node->next->previous = node->previous;
        if (node->previous != NULL)
            node->previous->next = node->next;
        if (top == node)
            top = node->next;
        if (bottom == node)
            bottom = node->previous;

        delete node;
        length--;

        return true;
    }

    return false;
}

Node* LinkedList::getNode(const string &nodeData)
{
    Node *current = top;
    while (current != NULL)
    {
        if (current->data == nodeData)
            return current;
        current = current->next;
    }
    return NULL;
}

int LinkedList::getLength()
{
    return length;
}

话虽如此，您可以通过使用 std::list 来完全摆脱 LinkedList，并通过使用 std::vector 简化 hashTable 的内存管理：

Hashtable.h:

#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <string>
#include <list>
#include <vector>

class hashTable
{
public:
    hashTable();

    void insertNode(const std::string &nodeData);
    bool removeNode(const std::string &nodeData);
    bool checkForDuplicate(const std::string &nodeData);

private:
    std::vector< std::list<std::string> > tableArray;

    int hash(const std::string &stateKey);
};

#endif // HASHTABLE_H

Hashtable.cpp:

#include "hashTable.h"
#include <algorithm>

hashTable::hashTable()
   : tableArray(181667)
{
}

int hashTable::hash(const std::string &nodeData)
{
    int multiplier = 1;
    int total = 0;
    int l = nodeData.length();
    for(int i = l - 1; i > -1; --i)
    {
        int temp = (nodeData[i] - '0') * multiplier;
        total += temp;
        multiplier *= 10;
    }
    return total % length;
}

void hashTable::insertNode(const std::string &nodeData)
{
    int index = hash(nodeData);
    tableArray[index].push_back(nodeData);
}

bool hashTable::removeNode(const string &nodeData)
{
    int index = hash(nodeData);
    std::list<std::string>::iterator iter = std::find(tableArray[index].begin(), tableArray[index].end(), nodeData);
    if (iter != tableArray[index].end())
    {
        tableArray[index].erase(iter);
        return true;
    }
    return false;
}

bool hashTable::checkForDuplicate(const std::string &nodeData)
{
    int index = hash(nodeData);
    std::list<std::string>::iterator iter = std::find(tableArray[index].begin(), tableArray[index].end(), nodeData);
    return (iter != tableArray[index].end());
}

如何修复访问冲突读取位置错误？

How to fix Access Violation Reading location error?

c++

memory-leaks

hashtable