时间戳

首页 > 解决方案 > HashTable 不断产生 segFault。如何使用析构函数正确删除？

c++ - HashTable 不断产生 segFault。如何使用析构函数正确删除？

问题描述

我有一个 HashTable 类。这样做的目的是练习如何生成哈希表。我目前的问题是析构函数。我应该在控制台上看到，这个： 在此处输入图像描述

但相反，我看到了这个：

在此处输入图像描述

我跑了gdb ./app，这给了我这个： 在此处输入图像描述

#include <iostream>
#include "HashTable.h"

using namespace std;

int main(){
 HashTable table;
 table.initTable();
 table.addNode("Software");
 table.addNode("Engineering");
 table.addNode("Art");
 table.addNode("Programming");
 table.addNode("Miscellanous");
 table.displayByIndex();
 return 0;
}

哈希表头：

#ifndef _HASHTABLE_H_
#define _HASHTABLE_H_

#include <iostream>
#include "Hash.h"

class HashTable{
private:
    static const int TABLESIZE = 5;
    Hash* head;
public:
    HashTable();
    ~HashTable();

    void initTable();
    int hashKey(char*);
    int quadProbing(int,int);
    int hashKeyWithProbing(char*);
    bool isEmpty();
    void addNode(char*);
    void displayByIndex();
    void searchByKey(char*);

};#endif

这是我的哈希表 CPP，我包括了构造函数/析构函数和初始化函数。由于我不使用“新”关键字，因此不包括其他功能。如果需要，我将包括它[希望使这个线程变小]

#include "HashTable.h"
#include <cstring>

HashTable::HashTable(){
  head = new Hash[TABLESIZE];
}
HashTable::~HashTable(){
  Hash* destList = NULL;
   for(int i = 0; i< TABLESIZE; i++){
     destList = &head[i];
     while(destList != NULL){
        head = head->getNext();
        delete destList;
        destList = head;
     }
   }
   head = NULL;
   delete [] head;
}
void HashTable::initTable(){
  for(int i = 0; i < TABLESIZE; i++){
    Hash *traverseHeadArray = &head[i];
    traverseHeadArray->setKey("EMPTY");
    traverseHeadArray->setNext(NULL);
    traverseHeadArray = NULL;
  }
} 

int HashTable::hashKey(char *tempKey){
 //Find the asc value for the string
//add them together
//modules by the total table size
//then return the index (remainder using modules)
//Index is were that key will be stored
 int index = 0;
 for(int i = 0; i < strlen(tempKey); i++){
    index += tempKey[i];
 }
  return index % TABLESIZE;
 }//DONE
int HashTable::quadProbing(int index, int counter){
  return (index + counter*counter) % TABLESIZE;
}//DONE
int HashTable::hashKeyWithProbing(char* key){
 int index = hashKey(key);
 int count = 1;

 while(head[index].getKey() != key && head[index].getKey() != "EMPTY"){
    index = quadProbing(index, count);
    count++;
 }
 return index;
}//DONE

void HashTable::addNode(char* tempValue){
 Hash* newNode = new Hash;
 newNode->setKey(tempValue);
 newNode->setNext(NULL);
 int index = hashKey(tempValue);
 int counter = 1;

 while(head[index].getKey() != tempValue && head[index].getKey() !="EMPTY")
  {
    index = quadProbing(index, counter);
    counter++;
  }

  Hash* traverse = &head[index];
 if(isEmpty() || traverse->getKey() == "EMPTY"){
    traverse->setKey(newNode->getKey());
    traverse->setNext(newNode->getNext());
 }else{
    while(traverse->getNext() != NULL)
        traverse = traverse->getNext();
    traverse->setNext(newNode);
 }
 traverse = NULL;  
 delete newNode;
}
void HashTable::displayByIndex(){
 for(int i = 0; i < TABLESIZE; i++){
    Hash *traverse = &head[i];
    std::cout << "----------------------------------------" << std::endl;
    std::cout << "INDEX: " << i << std::endl; 
    while(traverse != NULL){
        std::cout << "Key: " << traverse->getKey() << std::endl;
        traverse = traverse->getNext();
    }
    std::cout << "----------------------------------------" << std::endl;
    traverse = NULL;
  }
 }
 bool HashTable::isEmpty(){
  return (head == NULL);
 }
 void HashTable::searchByKey(char* key){
   int index = hashKeyWithProbing(key);

   if(isEmpty())
    std::cout << "Empty Bucket\n";
   else{
    Hash* traverse = &head[index];
    while(traverse != NULL && traverse->getKey() != "EMPTY"){
        std::cout << "TOPIC KEY: " << traverse->getKey() << std::endl;
        traverse = traverse->getNext();
    }
     traverse = NULL;
   }
  }

这是我的哈希类标头和 CPP 文件：

#ifndef _HASH_H_
#define _HASH_H_

class Hash{
 private:
    char* key;
    Hash* next;

 public:
    Hash();
    ~Hash();

    void setKey(char*);
    void setNext(Hash* const);
    char* getKey();
    Hash* getNext();

  };#endif



#include "Hash.h"
#include <iostream>

Hash::Hash(){
 key = NULL;
 next = NULL;
}
Hash::~Hash(){
// TODO Destructor
}

void Hash::setKey(char* tempKey){
 this->key = tempKey;
}
void Hash::setNext(Hash* const tempNext){
 this->next = tempNext;
}
char* Hash::getKey(){
 return key;
}
Hash* Hash::getNext(){
  return next;
}

标签： c++hashtable

解决方案

在您的代码中，您只分配getNext()节点，因此您应该只删除它们（您试图删除&head[i]根本没有分配的节点）。双重释放某些节点仍然存在异常，您应该调试并按照堆栈进行计算。

HashTable::~HashTable(){
    for(int i = 0; i< TABLE_SIZE; i++){
        Hash* node = head[i].getNext();
        while(node != nullptr){
            Hash* temp = nullptr;
            if (node -> getNext()) {
                temp = node->getNext();
            }
            delete node;
            node= temp;
        }
    }
    delete[] head;
}

输出：

----------------------------------------
INDEX: 0
Key: Art
----------------------------------------
----------------------------------------
INDEX: 1
Key: Engineering
----------------------------------------
----------------------------------------
INDEX: 2
Key: Miscellanous
----------------------------------------
----------------------------------------
INDEX: 3
Key: Software
----------------------------------------
----------------------------------------
INDEX: 4
Key: Programming
----------------------------------------
double free or corruption (fasttop)

Process finished with exit code 134 (interrupted by signal 6: SIGABRT)

推荐阅读