给定一系列整型关键字和素数 p，用除留余数法定义的散列函数 H(key)=key%p 将关键字映射到长度为 p 的散列表中。用线性探测法解决冲突。

输入格式:

输入第一行首先给出两个正整数 n（≤1000）和 p（≥n 的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出 n 个整型关键字。数字间以空格分隔。

输出格式:

在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

#include <stdio.h>
#include <stdlib.h>
#include <string.h>int main()
{int i, n, p, x, k;scanf("%d %d", &n, &p);int *s = (int *)malloc(sizeof(int) * p);memset(s, 0, sizeof(int) * p); // 初始化动态数组s[]for (i = 0; i < n; i++){scanf("%d", &x);k = x % p;if (s[k] == 0){ // 如果此位置为空，直接存放s[k] = x;}else{ // 否则while (s[k] != 0 && s[k] != x){// 依次往后寻找，直到找到空位，或者找到具有相同的值的数字k = (k + 1) % p;}if (s[k] != x){ // 如果没有相等的，那么存储xs[k] = x;}// 否则，不用重复存储x}if (i == 0){printf("%d", k);}else{printf(" %d", k);}}return 0;
}