时间戳

首页 > 解决方案 > C++ 自定义 HashTable 的使用给出了 SegFault

c++ - C++ 自定义 HashTable 的使用给出了 SegFault

问题描述

我必须为一个项目实现一个 Linked HashTable。现在我必须想出一个练习和一个使用我的哈希表的解决方案。一切正常，除了我得到随机的 Segfault 错误。

随机我的意思是：它是导致它的同一行代码，但总是在不同的时间，调用。 我在 Atom、Codeblocks 和 Visual Studio Code 中测试了我的代码。Atom 和 CB 都抛出了 SegFault 错误，但 VS Code 运行得很好，没有问题。

注意：这不是完整/真实的代码。它是包含在 main.cpp 文件中的头文件的一部分，然后编译并运行该文件。 编码：

#include <iostream>
#include <typeinfo>
#include <string>

using namespace std;

//List:
template<class T>
struct Node
{
  string data;
  Node *next;
};

class List
{
  private:
    Node *head, *tail;
    int length;
    friend class HashTable;
  public:
    List();
    List(const List &L);
    //~List() {delete this;};
    List& operator =(List L);
    int find(string);
    void insert(string value);
    void remove_head();
    void remove_poz(int);
    void remove_tail();
    void clear();
    void display();
};

List::List()
{
   head = NULL;
   tail = NULL;
   length = 0;
}

template<>
string List<string>::findByIndex(int ind)
{
    int i = 0;
    Node<string>* temp = new Node<string>;
    temp = head;
    while (temp != NULL)
    {
        i++;
        if (i == ind) return temp->data;
        temp = temp->next;
    }
    delete temp;
    return "-1";
}

template<class T>
void List<T>::remove_head()
{
  Node<T>* temp = new Node<T>;
  temp = head;
  head = head->next;
  delete temp;
  length--;
}

template<class T>
void List<T>::remove_pos(int pos)
{
  int i;
  Node<T>* curr = new Node<T>;
  Node<T>* prev = new Node<T>;
  curr = head;
  for (i = 1; i < pos; ++i)
  {
      prev = curr;
      curr = curr->next;
  }
  if (curr)
  {
    prev->next = curr->next;
    length--;
  }
  else cout << "Error" << endl;
}

template<class T>
void List<T>::remove_tail()
{
  Node<T>* curr = new Node<T>;
  Node<T>* prev = new Node<T>;
  curr = head;
  while (curr->next != NULL)
  {
      prev = curr;
      curr = curr->next;
  }
  tail = prev;
  prev->next = NULL;
  delete curr;
  length--;
}

//HashTable:
class HashTable
{
  private:
    List *table;
    float load, stored;
    int slots;
    friend class List;
  public:
    HashTable();
    HashTable(int);
    ~HashTable();
    int hashFunc(string key);
    int findTable(string);
    int findList(string);
    HashTable& operator =(const HashTable&);
    void resize();    //I need this one
    void insert(string);
    void remove(string);
    void clear(int);
    void clear();
    void display();
};

HashTable::HashTable()
{
  stored = 0;
  load = 0.00;
  slots = 15;
  table = new List[slots];
}

int HashTable::hashFunc(string key)
{
  int g, h = 0;
    unsigned int i;
    for (i = 0; i < key.size(); ++i)
    {
        h = (h << 4) + (int)(key[i]);
        g = h & 0xF0000000L;
        if (g != 0)
        {
            h = h ^ (g >> 24);
        }
        h = h & ~g;
    }
    return h % slots;
}

template<class T>
void HashTable<T>::remove(T value)
{
  int ind = hashFunc(value);
  int findInd = table[ind].findByValue(value);


  if (findInd == 0)
      table[ind].remove_head();

  else if (findInd < table[ind].length)
      table[ind].remove_pos(findInd);

  else table[ind].remove_tail();

  if (table[ind].isEmpty()) occupied--;
  stored--;
  load = stored / slots;
}

导致段错误的函数：（这将在循环中一遍又一遍地调用，直到我的表中没有更多元素）

string reakcio(HashTable<string>& HT, int tarolok)
{
    const int anyagszam = rand() % 4 + 2; //Min 2, Max 5 anyag hasznalodik
    int i = 0, j;
    string anyagok[5];
    string eredmeny;

    for(j = 0; j < tarolok && i < anyagszam; ++j) //elemek kivetele
    {
        while(!HT.table[j].isEmpty())
        {
            anyagok[i++] = HT.table[j].findByIndex(1); //This line right here is the culprit :(
            HT.remove(anyagok[i-1]);
        }
    }

    const int siker = rand() % 4 + 0; //75% esely a sikerre
    if (siker)
    {
        eredmeny = anyagok[0];
        for(i = 1; i < anyagszam; ++i)
            eredmeny += " + " + anyagok[i];
    }
    else
        eredmeny = "Sikertelen reakcio";
    return eredmeny;
}

（注意：这里只显示可能需要的功能）

我的哈希表或列表中的每个元素都是一个 10 个字符长的随机字符串值。srand(time(NULL)) 在 main.cpp 中的函数调用之前使用

任何帮助或建议将不胜感激，因为我坚持这一点，我真的需要继续进行下一部分练习，但我不能没有这个。

main.cpp 文件：

#include <iostream>
//#include "LinkedHash.h"
#include "functions.cpp"

int main()
{
  HashTable<string> Anyagok;
  int tarolok;

  tarol(Anyagok); //Stores the data from file, no problem here, functions.cpp
  tarolok = Anyagok.getSlots();

  srand(time(NULL));
  int i = 1;
  while (Anyagok.getStored() > 5 )
    cout<<reakcio(Anyagok, tarolok)<<" "<<i++<<endl;

  return 0;
}

LinkedHash.h 包含哈希表和列表，functions.cpp 包含有问题的函数。

编辑： 根据建议我改变了

Node<string>* temp = new Node<string>;
temp = head;

部分到

Node<string>* temp = head;

还删除了删除行。但我的问题还是一样的：/

标签： c++segmentation-faulthashtable

解决方案

一切正常，除了我得到随机的 Segfault 错误

然后根本没有任何作用。

第一次审查显示很少关心列表类中的角落案例。您需要为

  • 对空列表的操作
  • 对第一个和最后一个元素的操作
  • 搜索期间未找到密钥

发现明显错误：

  • remove_head、remove_tail 将在空列表中出现段错误。头为空。head->next 是无效的内存访问。类似的错误遍布整个实现。
  • HashTable<T>::remove(T value)总是会删除一些东西。即使 value 参数不在哈希表中。这是严重缺陷
  • findByIndex 返回“-1”没有意义。“-1”是一个有效的输入。
  • Node<T>* temp = new Node<T>;temp = head;. 你只是泄露了内存。您需要一个指针来操作节点地址。您不应该实例化节点来获取指针。这对于小型项目来说不是问题（即不明显），但对于实际实施来说是不可接受的。

推荐阅读