PAT 1145 C++ 版

PAT 1145 C++版

1.题意

• 哈希函数是：H(key)=key%TSize
• 给出一串数字，将这串数字按照上述的哈希函数插入到哈希表中，如果遇到哈希冲突，则使用平方探测法解决冲突。【如果对平方探测法不理解的，可以看我的博客】
• 在给出一串数字，计算查询这串数字的平均查询次数
• 给出的Msize，可能不是一个素数，所以需要table Size 设置成 >= Msize 的素数

2.分析

• 使用一个函数获取>=Msize 的第一个素数
• 将字符串插入到哈希表中【哈希表使用数组表示】
• 计算查询字符串需要的时间

3.代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>

using namespace std;

//获得一个 >=num 素数 
int getPrime(int num){
	int i; 
	while(true){//
		for( i = 2;i <= sqrt(num);i++ ){
			if(num % i == 0){
				num++;
				break;//说明不是素数 
			}
		}
		if(i > sqrt(num)){
			break;
		}
	}
	return num;
}

int main(){
	int mSize,N,M;//其中Msize 是table size； N是需要插入的数字总数；M是待查找数字的总数 
	cin >> mSize >> N >> M;
	int i ,j;
	int tSize;
	tSize = getPrime(mSize);
	//cout << "tSize = "<< tSize << "\n";	
	int array[N];
	int hashTable[tSize];//得到一个tSize 大小的hash 表 
	
	memset(hashTable,0,sizeof(hashTable)); 
	//输入待插入的n个数 
	for(i = 0;i< N;i++){
		cin >> array[i];
	}
			
	int query[M];
	for(i = 0;i< M ;i++){
		cin >> query[i];
	}
		
	//insert into table
	int index;//将元素放入hashTable 的下标 
	int flag = 0; 
	for(i = 0;i< N;i++){		
		for(j = 0;j < tSize ;j++){
			index = (array[i] + (j * j)) % tSize ;
			if(hashTable[index] == 0){
				hashTable[index] = array[i];
				break;
			}
		}
		if(j == tSize){
			flag = 1;
			cout << array[i]<<" ";
		}	
	}
	if(flag == 1)
		cout<<"cannot be inserted."<<"\n";
	
	
	//查询m个数
	double count = 0;//查找次数 	
	for(i = 0;i< M;i++){		 
		for(j = 0;j < tSize ;j++){
			count ++;//查找次数 
			index = (query[i] + (j * j)) % tSize ;		
			if(hashTable[index] == query[i] ){//说明找到了 		
				break;
			}
			if( hashTable[index] == 0 ){//说明query[i]这个元素不存在 
				break; 
			}
		}
		if(j == tSize){
			count++;
		}
	} 

	double aveNum = count / M;
	printf("%.1f\n",aveNum);
}

4.测试用例

4 5 4
10 6 4 15 11
11 4 15 2

5 5 2
10 6 4 15 11
15 2

5 5 2
10 6 4 15 11
15 6


4 5 4
10 6 4 13 11
11 4 15 2

5.执行结果

6.注意点

• 可能有不止一个的 不能插入元素，也有可能所有元素都能插入。在这两种的情况***意输出格式。
• 另外，就是在查询哈希表时，如果对于 j==size的元素，则表示已经查询到头了，【但是仍然需要将count+1，否则得不到正确答案。我对此做法的原因也不是很清楚。。。<(￣ ﹌ ￣)> 】
• 题目中的二次探测法【只取i^2】和 严奶奶书中的二次探测法【正负交叉】稍有不同。