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;
}