【1145】Hashing - Average Search Time (25分)【hash 平方探测法】

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //插入时pos = (a + j * j) % tsize，j是从0～tsize-1的数字
     
    
   

    

     

    
    

     

      //查询时pos = (a + j * j) % tsize，其中j <= tsize
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool isprime(int n){//判断是否是素数
     
    
   

    

     

    
    

     
	for(int i=2;i*i<=n;i++){
     
    
   

    

     

    
    

     
		if(n%i==0)  return false;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return true;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
   
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
		int tsize,n,m,a;//表长，要插入个数，查询个数
     
    
   

    

     

    
    

     
		scanf("%d %d %d",&tsize,&n,&m);
     
    
   

    

     

    
    

     
		while(!isprime(tsize))  tsize++;//大于表长的最大素数
     
    
   

    

     

    
    

     

      		vector<int>v(tsize);
     
    
   

    

     

    
    

     
		for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
			scanf("%d",&a);
     
    
   

    

     

    
    

     
			int flag=0;
     
    
   

    

     

    
    

     
			for(int j=0;j<tsize;j++){
     
    
   

    

     

    
    

     
				int pos=(a+j*j)%tsize;
     
    
   

    

     

    
    

     
				if(v[pos]==0){
     
    
   

    

     

    
    

     

      					v[pos]=a;
     
    
   

    

     

    
    

     

      					flag=1;
     
    
   

    

     

    
    

     
					break;
     
    
   

    

     

    
    

     

      				}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			if(!flag) printf("%d cannot be inserted.\n",a);
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		int ans=0;
     
    
   

    

     

    
    

     
		for(int i=0;i<m;i++){
     
    
   

    

     

    
    

     
			scanf("%d",&a);
     
    
   

    

     

    
    

     
			for(int j=0;j<=tsize;j++){
     
    
   

    

     

    
    

     

      				ans++;
     
    
   

    

     

    
    

     
				int pos=(a+j*j)%tsize;
     
    
   

    

     

    
    

     
				if(v[pos]==a||v[pos]==0) break;
     
    
   

    

     

    
    

     
				//找到或者没找到(不存在)都退出
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("%.1lf\n",ans*1.0/m);
     
    
   

    

     

    
    

     
		system("pause");
     
    
   

    

     

    
    

     
		return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/103917181