哈希表（搜索功能）

Question

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

我使用单独的链接taking.my散列函数进行哈希表正在使用恒定的多项式方程“一”，其功率与在一个字信的指数增长。 （a^0xb + a^1xb + a^2xb + ...），其中b是正被哈希的单词中的一个字母，然后我将mod（100）作为最终答案。我面临的问题是查找函数。当我测试查找函数时，部分链接列表类中的searchFor（）函数不起作用，尽管它自己可以正常工作，并且在我使用了“1”之后出现了分段错误调试。我很抱歉打扰，但我只是无法理解这里的问题。链表的类文件如下。我只是粘贴我哈维的功能NG问题

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

Answer 1

除了上面我的意见，这导致你找到你的错误之一，我会补充一点：

你之所以崩溃是你Hash类mismanages哈希表。首先，你分配的100个HashEntry指针数组：你从来没有设置这些指针到什么

HashEntry *Table[100]; 

通知 - 所以他们指着谁知道什么。也许他们凭借纯粹的运气，会指向NULL，但这样做的可能性很小 - 您在赢取彩票方面的可能性更大。所以，你正在访问一些随机存储器 - 这是不好的。

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

但一个有趣的问题是为什么这样做呢？为什么不直接宣布桶这样的：

HashEntry Table[100]; 

这样，所有的桶被分配为Hash对象的一部分，你不必对动态担心分配和回收桶，检查指针NULL等。

这样做的一个问题是您的HashEntry构造函数需要参数int。目前还不清楚为什么这种说法是必要的。我不认为你需要它，并且你可以删除它。

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