PAT1145 Hashing - Average Search Time

旧城等待， 2023-07-24 15:59 45阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
本题是 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;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230528/fe481ce6b57d4bf4ade16b9f82524e9d.png