//顺序探查法处理冲突，没有用二维数组，这点我觉得这样更好，数组可以更小，冲突也100%可以解决。用了300000除，没有用质数，可以改进吧……
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct aa
{
	char word[13];
	char foreign[13];
}dic[100010];
int hash[300000];
int main()
{
	int i,j,n;
	int getf;
	int rt;
	char line[30];
	gets(line);
	n=0;
	for(i=0;i<300000;i++)
		hash[i]=-1;
	while(line[0]!='\0')
	{
		for(i=0;line[i]!=' ';i++)
			dic[n].word[i]=line[i];
		dic[n].word[i++]='\0';
		for(i,j=0;line[i]!='\0';i++,j++)
			dic[n].foreign[j]=line[i];
		dic[n].foreign[j]='\0';
		getf=0;
		i=0;
		while(dic[n].foreign[i]!='\0')
		{
			getf=getf*26+dic[n].foreign[i++];
			getf%=300000;
		}
		while(hash[getf]!=-1)
			getf=(getf+1)%300000;
		hash[getf]=n;
		n++;
		gets(line);
	}
	while(gets(line))
	{
		getf=0;i=0;
		while(line[i]!='\0')
		{
			getf=getf*26+line[i++];
			getf%=300000;
		}
		while(hash[getf]!=-1 && strcmp(dic[hash[getf]].foreign,line)!=0)
			getf=(getf+1)%300000;
		if(hash[getf]!=-1)
			printf("%s\n",dic[hash[getf]].word);
		else
			printf("eh\n");
	}
	return 0;
}
		
			
			

• Re:不过也真奇怪，hash表初始-1 用memset 就瞬间超时…… (0) kimhmguen 2010-01-28 06:43:59