7-42 整型关键字的散列映射 (25 分)
给定一系列整型关键字和素数$P$，用除留余数法定义的散列函数将关键字映射到长度为$P$的散列表中。用线性探测法解决冲突。
输入格式:
输入第一行首先给出两个正整数$N$（≤1000）和$P$（≥$N$的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出$N$个整型关键字。数字间以空格分隔。
输出格式:
在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。
输入样例:
输出样例:
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
| 思路：用一个bool类型的数组filled标记某个位置是否有值，用一个int型数组nums标记存储数字
#include<iostream>
using namespace std;
int main(){
int N, P;
scanf("%d %d", &N, &P);
bool filled[P];
fill(filled, filled + P, false);
int nums[P];
for(int i = 0; i < N; i++){
int num;
scanf("%d", &num);
for(int j = 0; j < P; j++){
if(!filled[(num + j) % P] || nums[(num + j) % P] == num){
filled[(num + j) % P] = true;
nums[(num + j) % P] = num
printf("%d", (num + j) % P);
break;
}
}
if(i == N - 1){
printf("\n");
}else{
printf(" ");
}
}
return 0;
}
|
