7-8 整型关键字的散列映射

给定一系列整型关键字和素数 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)
            { // 如果没有相等的，那么存储x
                s[k] = x;
            }
            // 否则，不用重复存储x
        }
        if (i == 0)
        {
            printf("%d", k);
        }
        else
        {
            printf(" %d", k);
        }
    }

    return 0;
}