pat 数据结构与算法题目集

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

输入格式:

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

输出格式:

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

输入样例:

4 5
24 15 61 88

输出样例:

4 0 1 3

题目看起来很简单，却有两个坑点，
1.线性探测小心一直加会超出数组的长度
2.如果要填入的数字已经出现过了，则直接输出第一次的散列位置
ac代码

/*
   Name:
   Copyright:
   Author:  流照君
   Date: data
   Description:
*/
#include <iostream>
#include<string>
#include <algorithm>
#include <vector>
#define inf 100005
using namespace std;
typedef long long ll;
int arr[inf]; 
int main(int argc, char** argv)
{
#ifdef ONLINE_JUDGE//条件编译，如果有oj则忽略文件读取
#else
   //freopen("in.txt", "r", stdin);//输入输出文件重定向
   //freopen("out.txt", "w", stdout);
#endif  //#if, #ifdef, #ifndef这些条件命令的结束标志.
//代码位置
   int n,p,temp,flag=0;
   cin>>n>>p;
   fill(arr,arr+inf,0);
   while(n--)
   {
       int flag1=0;
         cin>>temp;
         int pos=temp%p;
           for(int i=0;i<p;i++)
           {
               if(arr[i]==temp)
               {
                   flag1=1;
                   cout<<" "<<i;
                    break;
               }
           }
           if(flag1)
           continue;
           while(arr[pos]!=0)
           {
               pos=(pos+1)%p;
           }
           if(!flag)
           cout<<pos;
           else
           cout<<" "<<pos;
           arr[pos]=temp;
           flag=1;
   }
   return 0;
}