哈希表（搜索功能）

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更改將大大簡化您的代碼並消除三個錯誤和崩潰。