c++ - 检查哈希表中的重复项
问题描述
我正在尝试读取一个文件,每个字符串将少于 30 个,并且在数千个中将有 20 个唯一序列。我们正在计算唯一性在哈希表中出现的次数。我在处理碰撞时遇到问题。我将所有 char[] 值初始化为“0”,但是 if(protiens[key].protien == "0") 无法检查结构中的该点是否具有“0”值或我的 protiens 之一总是“ABCDJ ...”超过 10 并且少于 30 个字符。所以我认为将所有初始化为“0”将是一种查看我是否已经在结构中放入蛋白质的方法。
这个逻辑错误出现在我的第二个 if 语句中。
这是我们应该使用的算法,然后是我的代码。
While(there are proteins)
Read in a protein
Hash the initial index into the proteins table
While(forever)
If(found key in table)
Increment count
Break;
If(found empty spot in table)
Copy key into table
Increment count
Break;
Increment index; // collision! Try the next spot!
#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;
//struct to hold data and count
struct arrayelement
{
char protien[30] {"0"};
int count;
};
arrayelement protiens[40];
//hash function A=65 ascii so 65-65=0 lookup table = A=0,B=1...
//h(key) = ( first_letter_of_key + (2 * last_letter_of_key) ) % 40
int getHashKey(char firstLetter, char lastLetter)
{
return ((int(firstLetter) - 65) + (2 * (int(lastLetter) - 65))) % 40;
}
int main()
{
fstream file;
string filename;
char word[30];
int key;
filename = "proteins.txt";
//open file
file.open(filename.c_str());
//while not eof
while (file >> word)
{
//get key
key = getHashKey(word[0], word[strlen(word)-1]);
//loop "forever" no difference if i use 1 or 10000000 besisdes run time????
for (int j = 0; j < 1; j++)
{
//if found key in table
if (protiens[key].protien == word)
{
protiens[key].count++;
break;
}
//if found empty spot in table
//if(protiens[key].protien == "0") i intialized all protiens to "0" why would this not work for
//checking if i put a protien there already or not
else
{
strcpy_s(protiens[key].protien, word);
protiens[key].count++;
break;
}
//collison incrment key
key = getHashKey(word[0], word[strlen(word) - 1]) + 1;
}
}
//print array of uniques with counts
for (int j = 0; j < 40; j++)
{
cout << j << "\t" << protiens[j].protien << "\t" << protiens[j].count << endl;
}
}
解决方案
//if(protiens[key].protien == "0") i intialized all protiens to "0" why would this not work for
//checking if i put a protien there already or not
由于"0"
是一个常量并且protiens[key].protien
是一个指向变量的指针,它们不可能相等。
想象一下,如果他们是平等的。那将意味着这protients[key].protien[0]='Q';
将与"0"[0]='Q';
. 但前者非常有意义,改变了一个变量。后者是疯狂的,修改一个常数。
我不知道当你有std::string
. 但是如果你坚持的话,strcmp
用来比较字符串。比较指向字符的指针是否相等会告诉您两个指针是否相等,而不是它们是否指向相同的字符串。
推荐阅读
- android - 我们可以为两个不同的 Android 应用程序使用相同的签名密钥吗?
- kubernetes - Minikube 错误 - 启动主机时出错:临时错误:在主机上配置身份验证时出错:操作系统类型无法识别
- laravel - 我收到对成员函数 diffForHumans 字符串错误的调用
- android - Dagger 2 错误:依赖“不能在没有 @Provides 注释的方法的情况下提供”
- ios - iOS 分发(UDID/Adhoc)pem 文件未发送通知
- ios - 我可以在同一个视图控制器中添加两个标签栏,一个标签栏在底部,一个标签栏在顶部
- javascript - 如何在 amCharts 中每 5 秒翻转一次切片?
- python - Python 3.7 Openpyxl 2.5.11 最大行和列的错误值
- mysql - 如何在mysql查询中引用日期作为列名
- java - 没有这样的元素:无法在硒中找到元素