-2 
#include <iostream>
#include <cstring>
#include <vector>
#include "list.cpp"
#include <cmath>

using namespace std;

struct HashEntry{
   int key;
   List<string> list;
   HashEntry(int k)
   {        
         key=k;
   } 
}; 

class Hash{
  private:
         HashEntry *Table[100];
         int a;
  public:
         Hash(int A);
         void insert(string word);
         void Lookup(string word);
};    

Hash::Hash(int A)
{
    a=A;
}         

void Hash::insert(string word)
{
   int c=0;
   for (int i=0;i<word.size();i++)
   {                                 
       int b=(int)((a^i)*(word[i]));
       c+=b;
   }
   c%=100;
   List<string> list;
   if (Table[c-1]==NULL)     //if the respective bucket doesnot have any string
   Table[c-1]=new HashEntry(c-1);

   Table[c-1]->list.insertAtTail(word);
}                  


void Hash::Lookup(string word)
{
   int c=0;
   for (int i=0;i<word.size();i++)
   {                                 
     int b=(int)((a^i)*(word[i]));
     c+=b;
   }
   cout<<"one"<<endl;
   c%=100;
   Table[c-1]->list.searchFor(word);
   cout<<"two"<<endl;
}

我正在使用单独的链接制作一个哈希表。我的哈希函数正在使用一个常数“a”制作一个多项式方程，其功率随着单词中字母的索引而增加。（a^0xb+a^1xb+a^ 2xb+...) ，其中 b 是正在散列的单词中的一个字母，然后我取 mod(100) 的最终答案。我面临的问题是查找函数。当我测试查找函数时，searchFor () 作为部分链接列表类的一部分的函数不起作用，尽管它本身可以正常工作，并且在我用来调试的 cout<<"one" 之后出现分段错误。我很抱歉打扰，但我只是无法理解这里的问题。链表类文件在下面。我只是粘贴我遇到问题的函数

#ifndef __LIST_H
#define __LIST_H
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;
/* This class just holds a single data item. */
template <class T>
struct ListItem
{
   vector<string> words;
   T value;
   ListItem<T> *next;
   ListItem<T> *prev;

   ListItem(T theVal)
   {
       this->value = theVal;
       this->next = NULL;
       this->prev = NULL;
   }
};

/* This is the generic List class */
template <class T>
class List
 {
 ListItem<T> *head;

 public:
  // Constructor
  List();

  // Copy Constructor
  List(const List<T>& otherList);

  // Destructor
  ~List();

  // Insertion Functions
  void insertAtHead(T item);
  void insertAtTail(T item);
  void insertAfter(T toInsert, T afterWhat);
  void insertSorted(T item);
  void printList();
  // Lookup Functions
  ListItem<T> *getHead();
  ListItem<T> *getTail();
  void *searchFor(T item);

  // Deletion Functions
  void deleteElement(T item);
  void deleteHead();
  void deleteTail();

  // Utility Functions
  int length();
};

#endif

template <class T>
void List<T>::searchFor(T item)
{    
 ListItem<T> *temp=head;
 if (temp!=NULL)
 {
    while (temp->next!=NULL)
    {
         T sample=temp->value;
         if (sample==item)
         {      
             cout<<"String found";   
             return;
         }
         temp=temp->next;
    }
    T s=temp->value;
    if (s==item)
    {
       cout<<"String found";        
       return;
    }
  }                   
}
4

1 回答 1

0

除了我上面的评论，它导致您找到您遇到的错误之一，我将添加以下内容：

你崩溃的原因是你的Hash班级对哈希表管理不善。首先，分配一个包含 100 个HashEntry指针的数组：

HashEntry *Table[100];

请注意，您从未将这些指针设置为任何东西 - 所以它们指向谁知道什么。也许他们会靠运气指向 NULL，但这种可能性微乎其微——你赢得彩票的可能性要大得多。所以，你正在访问一些随机内存——这很糟糕。

解决方案是将每个条目设置为NULL在构造函数中显式使用循环。您还需要一个析构函数来释放任何已分配的条目，这样您就可以delete做到并且不会泄漏内存，因为泄漏是不好的。

但一个有趣的问题是，它为什么会这样呢？为什么不简单地声明这样的存储桶：

HashEntry Table[100];

这样，您的所有存储桶都被分配为Hash对象的一部分，您不必担心动态分配和释放存储桶、检查指针NULL等。

这样做的一个问题是您的HashEntry构造函数需要一个int参数。目前还不清楚为什么这个论点是必要的。我认为您不需要它，您可以将其删除。

这一更改将大大简化您的代码并消除三个错误和崩溃。

于 2013-04-02T16:28:08.583 回答