我试图使用哈希图构建集合，但测试系统给我发送了错误的答案。我没有访问测试的权限，但在我的测试中，代码运行良好。我对新的测试没有任何想法，也许你会有一些？这是我的代码：
#include <iostream>
#include <fstream>
using namespace std;
int h1(int number) {
number %= 1000003;
return abs(number);
}
int h2(int number) {
number = number % 999991 + 12;
return abs(number);
}
int Insert(int * Hash_table,bool * Deleted,int& number) {
int x = h1(number);
int y = h2(number);
for(int i = 0; i < 1000003;i++) {
if(Hash_table[x] == NULL || Deleted[x]) {
Hash_table[x] = number;
Deleted[x] = false;
break;
}
x = (x + i * y) % 1000003;
}
}
string Exists(int * Hash_table,bool * Deleted,int& number) {
int x = h1(number);
int y = h2(number);
for(int i = 0; i < 1000003;i++) {
if(Hash_table[x] == 0 && number == 0 && !Deleted[x])
return "truen";
if(Hash_table[x] != NULL)
if(Hash_table[x] == number && !Deleted[x] ) {
return "truen";
}
if(Hash_table[x] == NULL || Deleted[x])
return "falsen";
x = (x + i * y) % 1000003;
}
}
int Delete(int * Hash_table,bool * Deleted,int& number){
int x = h1(number);
int y = h2(number);
for(int i = 0; i < 1000003;i++){
if(Hash_table[x] == 0 && number == 0){
Deleted[x] = true;
break;
}
if(Hash_table[x] != NULL) {
if(Hash_table[x] == number) {
Deleted[x] = true;
break;
}
x = (x + i * y) % 1000003;
}
else
return 0;
}
}
int main () {
int Hash_table[1000003];
bool Deleted[1000003];
ifstream input("set.in");
ofstream output("set.out");
string command;
int number;
while(true) {
input >> command;
if(input.eof())
break;
if(command == "insert") {
input >> number;
Insert(Hash_table,Deleted,number);
}
if(command == "delete") {
input >> number;
Delete(Hash_table,Deleted,number);
}
if(command == "exists") {
input >> number;
output << Exists(Hash_table,Deleted,number);
}
}
}
我必须实现诸如"输入"、"存在"one_answers"删除"之类的命令。我认为代码的逻辑很好，但我不确定散列函数。更新：添加0的if语句，现在h1和h2返回绝对值。但现在我在第四次考试中出现了问题。
int h1(int number) {
number %= 1000003;
return number;
}
int h2(int number) {
number = number % 99991 + 1;
return number;
}
Above函数将为负数提供负输出。这将导致Hash_table[x]的运行时错误。见下文：
int h1(int number) {
number = (number%1000003 + 1000003) % 1000003;
return number;
}
int h2(int number) {
number = (number % 99991 + 99991) % 99991 + 1;
return number;
}