題目描述

給定的一組無重復數據的正整數，根據給定的哈希函數建立其對應hash表，哈希函數是H(Key)=Key%P，P是哈希表表長，P是素數，處理沖突的方法采用平方探測方法，增量di=±i^2,i=1,2,3,...,m-1

輸入

輸入一組測試數據，數據的第1行給出兩個正整數N(N <= 500)和P(P >= 2N的最小素數)，N是要插入到哈希表的元素個數，P是哈希表表長；第2行給出N個無重復元素的正整數，數據之間用空格間隔。

輸出

按輸入數據的順序輸出各數在哈希表中的存儲位置 (hash表下標從0開始)，數據之間以空格間隔，以平方探測方法處理沖突。

示例輸入

4 11 10 6 4 15 9 11 47 7 29 11 9 84 54 20 30

示例輸出

10 6 4 5 3 7 8 0 9 6 10 2 1

提示

#include <bits/stdc++.h>


using namespace std;


int main()
{
? ? int a[500];//存儲下標；
? ? int n,p,i,j,num,h;
? ? int Hash[500];//哈希表；
? ? while(~scanf("%d%d",&n,&p))
? ? {
? ? ? ? memset(Hash,-1,sizeof(Hash));//初始化哈希表；
? ? ? ? int sum=0;//統計數組元素個數；
? ? ? ? for(i=0;i<n;i++)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&num);
? ? ? ? ? ? h=num%p;//取余數；
? ? ? ? ? ? if(Hash[h]==-1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Hash[h]=num;
? ? ? ? ? ? ? ? a[sum++]=h;//記錄余數下標；
? ? ? ? ? ? }
? ? ? ? ? ? else
? ? ? ? ? ? {
? ? ? ? ? ? ? ? g=h;
? ? ? ? ? ? ? ? for(j=1;j<=sqrt(p);j++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? h=(g+j*j)%p;//向表的后面找；
? ? ? ? ? ? ? ? ? ? if(Hash[h]==-1)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? Hash[h]=num;
? ? ? ? ? ? ? ? ? ? ? ? a[sum++]=h;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? ? h=(g-j*j)%p;//向表的前面找；
? ? ? ? ? ? ? ? ? ? if(Hash[h]==-1)
? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? Hash[h]=num;
? ? ? ? ? ? ? ? ? ? ? ? a[sum++]=h;
? ? ? ? ? ? ? ? ? ? ? ? break;
? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? for(i=0;i<sum;i++)
? ? ? ? ? ? if(i!=sum-1)
? ? ? ? ? ? printf("%d ",a[i]);
? ? ? ? else
? ? ? ? ? ? printf("%d\n",a[i]);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的数据结构实验之查找五：平方之哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。