给定一系列整型关键字和素数P，用除留余数法定义的散列函数将关键字映射到长度为P的散列表中。用线性探测法解决冲突。
输入格式: 输入第一行首先给出两个正整数N（≤1000）和P（≥N的最小素数），分别为待插入的关键字总数、以及散列表的长度。第二行给出N个整型关键字。数字间以空格分隔。
输出格式: 在一行内输出每个整型关键字在散列表中的位置。数字间以空格分隔，但行末尾不得有多余空格。
输入样例: 4 5 24 15 61 88 输出样例: 4 0 1 3
#include <stdio.h> #include <string.h> #define N 2000 typedef struct HashMap{ int loc; int value; } Hash; int hash( int x, int p ) // 计算哈希值 { return (x%p); } int main() { int n, p; scanf("%d %d", &n, &p); // flag[]用于标记地址是否已用，index[]用于按输入顺序记录地址 int flag[N], index[N]; int i, j; /* 初始化两个数组的值为 0 */ memset(flag, 0, sizeof(flag)); memset(index, 0, sizeof(index)); int x; Hash h[N]; for( i=0; i<n; i++) { scanf("%d", &x); for( j=0; j<i; j++) { if( x == h[j].value ) // 查询是否重复 { index[i] = h[j].loc; break; } } if( j==i ) // 查找存入的地址值 { int h0 = hash(x, p); int cnt = 0; int hi = hash(h0, p); while( cnt != p && flag[hi] ) // 冲突，寻找新的地址 { h0 ++; cnt ++; // 由于答案中的地址区间是在 [0, p]，所以超过 p时要回到头部 hi = hash(h0, p); // 寻找新的地址 } flag[hi] = 1; // 标记该地址已使用 index[i] = hi; // 记录地址值 h[i].value = x; h[i].loc = hi; } } for(i=0; i<n; i++) { // 遍历输出地址值 if(i != (n-1)) printf("%d ", index[i]); else printf("%d", index[i]); } return 0; }