PAT1145 Hashing - Average Search Time-蒲公英云

PAT1145 Hashing - Average Search Time

在这里插入图片描述
本题是 pat1078hashing的变种题，题目意思很绕，而且描述的不是很清楚，做的时候遇到了很多的问题
解题步骤：
1.对于输入的msize（hashtable表长），如果不是素数的话，需要求出比msize大的最小的素数，令msize等于该素数值
2.平方探查法将temp插入hashtable，如果k在【0，msize）区间内都没有找到合适的位置的话视为无法插入
3.探测次数采用和上面插入同样的方法，每次查找到当前位置后判断该位置的值是否等于temp或者-1（-1意味的当前位置还是空，可以插入），如果是则累加到cnt,一直累加k判断，如果当k=msize-1时还是没有找到的话，cnt累加msize+1，并且输出未找到
4.最后输出cnt/m,取小数点后一位
代码：

//除留余数然后平方探查建hashtable
//quadratic是平方的意思
//tsize应为素数，如果题目给的不是需要自行求出比tsize大的最小的素数
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
bool isprime[10999];
void getprime()//标记isprime数组中素数为true
{ 
    for(int i=0;i<10999;i++)isprime[i]=true;
    isprime[1]=false;
    for(int i=2;i*i<10999;i++)
    { 
        if(isprime[i]==true)
        { 
            for(int j=2*i;j<10999;j+=i)isprime[j]=false;
        }
    }
}
int main()
{ 
    int msize,n,m;
    getprime();
    scanf("%d%d%d",&msize,&n,&m);
    while(isprime[msize]!=true)msize++;
    int hashtable[msize];
    memset(hashtable,-1,sizeof(hashtable));
    for(int i=0;i<n;i++)
    { 
        int temp,k=0;
        bool flag=false;
        scanf("%d",&temp);
        while(k<msize)
        { 
            int index=(temp+k*k)%msize;
            if(hashtable[index]==-1)//当前位置可以插入
            { 
                hashtable[index]=temp;
                flag=true;
                break;
            }
            else k++;
        }
    }
    int cnt=0;//总查询次数
    for(int i=0;i<m;i++)
    { 
        int temp,k=0;
        scanf("%d",&temp);
        bool flag=false;
        while(k<msize)
        { 
            if(hashtable[(temp+k*k)%msize]==temp||hashtable[(temp+k*k)%msize]==-1)
            { 
                cnt+=k+1;
                flag=true;
                break;
            }
            else k++; 
        }
        if(!flag)
        { 
            cnt+=msize+1;
            printf("%d cannot be inserted.\n",temp);
        }
    }
    printf("%.1f",cnt*1.0/m);
    return 0;
}