Wie behebt man Zugriffsverletzungs-Lesefehler?

Question

Ich arbeite derzeit an einem Programm, das eine Hash-Tabelle verwendet. Ich habe an meiner eigenen Hash-Tabellenklasse gearbeitet und das Programm funktioniert, stürzt aber ab, nachdem es die Arbeit mit der Hash-Tabelle bereits erledigt hat. Der Fehler, den ich erhalte, ist ein Fehler beim Lesen der Zugriffsverletzung. Ich habe Stunden damit verbracht, meinen Code durchzugehen und kann immer noch nicht herausfinden, was ich falsch mache oder warum das Programm abstürzt. Hier sind meine Problemklassen unter:

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

Ihre hashTable::insertNode() Methode wird ein neues Objekt Node Zuweisung, dann ist es zu LinkedList::insertNode() zu Besitz übernehmen des Objekts vorbei, aber dann delete ist es danach, so die LinkedList mit einem baumelnden Zeiger verlassen Speicher auf ungültig. Jeder Zugriff auf diesen Knoten führt zu undefiniertem Verhalten. NICHT delete der neue Knoten nach LinkedList übernimmt Besitz davon.

Es wäre besser, wenn LinkedList::insertNode() einen string als Eingabe anstelle eines Node* Zeigers nahm. Lassen Sie LinkedList den neuen Knoten intern zuweisen.

Außerdem gibt es einige andere kleinere Probleme mit Ihrer LinkedList() Implementierung im Allgemeinen (wie nicht nach der Rule of Three, und nicht mit einer doppelt verketteten Liste für effizientere Einsätze und Entfernungen).

etwas mehr wie diese stattdessen versuchen:

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; 
} 

das gesagt ist, können Sie dann von LinkedList insgesamt durch std::list statt mit loszuwerden, und hashTable ‚s Speicherverwaltung vereinfachen std::vector unter Verwendung:

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