7-43 字符串关键字的散列映射 (25 分)
给定一系列由大写英文字母组成的字符串关键字和素数$P$，用移位法定义的散列函数$H$($K$$e$$y$)将关键字$K$$e$$y$中的最后3个字符映射为整数，每个字符占5位；再用除留余数法将整数映射到长度为$P$的散列表中。例如将字符串AZDEG插入长度为1009的散列表中，我们首先将26个大写英文字母顺序映射到整数0~25；再通过移位将其映射为$3×32^2+4×32+6=3206$；然后根据表长得到，即是该字符串的散列映射位置。
发生冲突时请用平方探测法解决。
输入格式:
输入第一行首先给出两个正整数$N$（≤500）和$P$（≥2$N$的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出$N$个字符串关键字，每个长度不超过8位，其间以空格分隔。
输出格式:
在一行内输出每个字符串关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。
输入样例1:
1
2
| 4 11
HELLO ANNK ZOE LOLI
|
输出样例1:
输入样例2:
1
2
| 6 11
LLO ANNA NNK ZOJ INNK AAA
|
输出样例2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include<iostream>
#include<cstring>
using namespace std;
int changeToInt(char* str);
int main() {
int N, P;
scanf("%d %d", &N, &P);
char strs[P][9];
bool filled[P];
fill(filled, filled + P, false);
for(int i = 0; i < N; i++){
char input[9];
scanf("%s", input);
int num = changeToInt(input);
for(int j = 0; j < P; j++){
int index1 = (num + j * j) % P;
if(!filled[index1] || strcmp(strs[index1], input) == 0){
filled[index1] = true;
strcpy(strs[index1], input);
printf("%d", index1);
break;
}
int index2 = (num - j * j) % P;
while(index2 < 0){
index2 += P;
}
if(!filled[index2] || strcmp(strs[index2], input) == 0){
filled[index2] = true;
strcpy(strs[index2], input);
printf("%d", index2);
break;
}
}
if(i == N - 1){
printf("\n");
}else{
printf(" ");
}
}
return 0;
}
int changeToInt(char* str) {
int result = 0;
int len = strlen(str);
for(int i = max(len - 3, 0); i < len; i++) {
result = result * 32 + str[i] - 'A';
}
return result;
}
|
