线性探测（一步降低） [英] Linear probing(one step down)

问题描述

我的问题是：

在你的主要文件中打开一个文件。您的文件在每行中都有一个单词。我应该读取一个文件总结每个单词的ascii值，总和mod的散列大小将是我的关键，我应该用线性探测来处理碰撞。对于线性探测，我需要创建一个线性探测类。我有两个问题：



a）我不明白这个错误信息。

未定义引用`LinearProbing :: HashFunction（std :: string，int，int）

我不明白为什么会这么说。



b）我是否完成了Insert方法？我的逻辑是，如果给定键的位置为空，则在该键或索引中插入该单词。如果不是空的，请向下一步并在那里插入单词。



任何有关此事的输入都会对我有所帮助！请不要讽刺言论！谢谢!!!



我尝试过：



< pre lang =C＃> #include< iostream>
#include< fstream>
#include< sstream>

使用 命名空间标准;
// 全局变量
int HASHSIZE = 100 ;
string HashTable [ 100 ];

class LinearProbing {

int HashFunction（ string ， int ， int ）;
void InsertWord（ string ）;
int SearchWord（ string ）;
};


int main（）{
string 字;
string 行;
fstream文件;
int index;

// 用户输入
cout<< 输入您要搜索的单词：;
cin>> word;

// 阅读文件
file.open（ text.txt）;
while （file）{ // http ：//www.cplusplus.com/forum/beginner/146982/
getline（文件，行）;
}
file.close（）;

}

int HashFunction（ string 键， int index， int HASHSIZE）{
int sum = 0 ;
for （ int i = 0 ; i< index; i ++）{
sum = sum + key [i];
}
return sum％HASHSIZE;
}

void LinearProbing :: InsertWord（ string 字） {
int key = LinearProbing :: HashFunction（word，word.length（），HASHSIZE）;
for （ int i = 0 ; i < HASHSIZE; i ++）{
if （HashTable [key]。 empty（）== true ）{ // 如果spot是空的，用空格填充空格
HashTable [key] = word;
return ;
}
else {
HashTable [key + 1] = word;
}
}
}

int LinearProbing :: SearchWord（ string word）{
int key = LinearProbing :: HashFunction（word，word.length（），HASHSIZE）;
for （ int i = 0 ; i < HASHSIZE; i ++）{
if （HashTable [（key +） i）％HASHSIZE] == word）{
cout<< 您正在寻找的单词在<< key + i<< position;
}
}
cout<< 表中未包含的值;
return 0 ;
}

解决方案

可能像这样：

  int  LinearProbing :: SearchWord（string word）{
 LinearProbing lp; 
  int  key = lp.HashFunction（word，word.length（），HASHSIZE）; 
  for （ int  i =  0 ; i< HASHSIZE; i ++）{
  if （HashTable [（key + i）％HASHSIZE] == word）{
 cout<<  您要查找的单词位于<< key + i& ; lt;& lt;   position;& lt;！ -  newline =    -  =  > } 
} 
 cout<<  表中未包含的值; 
  return   0 ; 
} 

使用对象。

My question is:
Open a file in your main. Your file has one word in each line. I'm supposed to read a file sum up the ascii values of each word, the sum mod the hash size will be my key and i'm supposed to take care of the collisions with linear probing. for linear probing I need to create a linear probing class. I have two questions:

a) I do not understand this error message.
"undefined reference to `LinearProbing::HashFunction(std::string, int, int)"
I do not understand why it says that.

b) Have I done the Insert method right? My logic is that if the spot of a given key is empty, insert the word in that key or index. If not empty, go one step down and insert the word there.

Any input on this matter would help me greatly!! and Please no sarcastic remarks! Thank you!!!

What I have tried:

#include <iostream>
#include <fstream>
#include <sstream>

using namespace std;
//Global variables
int HASHSIZE=100;
string HashTable[100];

class LinearProbing{

int HashFunction(string,int,int);
void InsertWord(string);
int SearchWord(string);
};


int main(){
string word;
string line;
fstream file;
int index;

//User Input
cout<<"Enter a word you would like to search: ";
cin>>word;

//Reading File
file.open("text.txt");
while(file){                      //http://www.cplusplus.com/forum/beginner/146982/
 getline(file,line);
 }
file.close();

}

int HashFunction(string key, int index,int HASHSIZE){
int sum=0;
for(int i=0;i<index;i++){
    sum=sum+key[i];
}
return sum%HASHSIZE;
}

void LinearProbing::InsertWord(string word){
int key= LinearProbing::HashFunction(word,word.length(),HASHSIZE);
for (int i = 0; i < HASHSIZE; i++){
        if (HashTable[key].empty()==true){//if the spot is empty, fill the space with the word
            HashTable[key] = word;
            return;
        }
        else{
            HashTable[key+1] = word;
        }
    }
}

int LinearProbing::SearchWord(string word){
int key=LinearProbing::HashFunction(word,word.length(),HASHSIZE);
for (int i = 0; i < HASHSIZE; i++){
        if (HashTable[(key + i)%HASHSIZE] == word){
            cout<<"The word you're looking for is in "<<key+i<<"position";
        }
    }
    cout << "Value not contained in table";
    return 0;
}

解决方案

Probably, like this:

int LinearProbing::SearchWord(string word){
LinearProbing lp;
int key=lp.HashFunction(word,word.length(),HASHSIZE);
for (int i = 0; i < HASHSIZE; i++){
        if (HashTable[(key + i)%HASHSIZE] == word){
            cout<<"The word you're looking for is in "<<key+i&lt;&lt;"position";&lt;!-- newline="" --="">        }
    }
    cout << "Value not contained in table";
    return 0;
}

Use objects.

这篇关于线性探测（一步降低）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！