数据结构实验题（整型关键字的散列映射）

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

输入格式:

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

输出格式:

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

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

 答案：

#include<stdio.h>
int main()
{
    int n,p,i,m,k;
    int a[500000]={0};//数组开大，防止p过大时数组空间不够
    scanf("%d%d",&n,&p);

    for(i=0; i<n; ++i)
    {
        scanf("%d",&k);
        m=k%p;//除留余数法
        while(a[m]!=0&&a[m]!=k)//线性探测法解决冲突且考虑重复关键字情况
        {
            m=(m+1)%p;//线性探测法，当空间被占时环形向后寻找空的
        }
        if(i!=0)
            printf(" ");//保证数字间以空格分隔，但行末尾无多余空格
        printf("%d",m);
        a[m]=k;//标记空间
    }
}