poj2503 Babelfish (hashmap)

题目链接：http://poj.org/problem?id=2503

该题用hashmap可以解决，我从中学到了以下几点：

1. 链表插入可以倒着来，省去搜索到链表末尾再进行插入的时间，代码如下

p->next = link[e]; //link[]一开始被赋予nullptr
link[e] = p;
           

2. gets_s函数当读到文件结束符时返回nullptr，可以在控制台使用ctrl-z验证。

3. gets_s读入一整行，但舍弃换行符。

4. BKDRHash效果最好

#include <iostream>
#include <cstring>
using namespace std;
#define M 100003
struct node
{
	int pos;
	node* next;
}*link[M] = { nullptr };

char word[100000][11], dialect[100000][11];
int ELFhash(char* key)
{
	unsigned long h = 0, g;
	while (*key)
	{
		h = ( h << 4 ) + *key++;
		g = h & 0xf0000000L;
		if (g)
			h ^= g >> 24;
		h &= ~g;
	}
	return h % M;
}
/*int insert(int e, int n)  //没有重复的，用不着在插入时判断
{
	node* p = link[e];
	while (p != nullptr)
	{
		if(==)
	}
}*/
int main()
{
	int i, e, n = 0;
	node* p;
	char str[50];
	gets_s(str);
	while (strcmp(str, "") != 0)
	{
		for (i = 0; str[i] != ' '; ++i)
		{
			word[n][i] = str[i];
		}
		word[n][i++] = '\0';
		strcpy(dialect[n], str + i);
		e = ELFhash(dialect[n]);
		p = new node;
		p->pos = n;
		p->next = link[e];
		link[e] = p;
		n++;
		gets_s(str);
	}
	while (gets_s(str) != nullptr)
	{
		e = ELFhash(str);
		p = link[e];
		while (p != nullptr)
		{
			if (strcmp(str, dialect[p->pos]) == 0)
				break;
			p = p->next;
		}
		if (p == nullptr)
		{
			printf("eh\n");
		}
		else printf("%s\n", word[p->pos]);
	}


	return 0;
}