题目
你刚从你的家乡搬到上海。这里的人们说着一种难以理解的上海方言。幸运的是，你有一本字典来帮助你理解它们。
输入格式
输入最多由100000个字典条目组成，后面是一个空行，后面是一个最多100000个词语的消息。
空行前面的若干行，每个字典条目是一行，包含普通话词语、后面跟着一个空格、空格后面是一个方言。
每一个方言都有唯一确定的普通话与之对应，也就是说在字典里没有任何一个方言出现不止一次。
空行后面的若干行，表示你需要查询的词语。
每一行有一个词语。
题目中说的词语，都是最长10个小写字母的序列。
输出格式
输出方言对应的普通话词语。
如果方言在词典没有找到，你应该说“eh”。
思路
方法1
map<string,string>。空行处理有点麻烦，需要使用getline(cin,s)判断s.size()==0。
方法2
哈希+开放地址
方法3
哈希+链表
代码
方法1
#include<bits/stdc++.h>
using namespace std;map<string, string> m; // 上海话，普通话int main()
{
string s;while (getline(cin, s) && s.size()!=0){
int pos = s.find(' ');int len = s.length();string s1 = s.substr(0, pos); // mandarinstring s2 = s.substr(pos+1, len); // dialect// cout<<s1<<s1.size()<<endl;// cout<<s2<<s2.size()<<endl;m[s2] = s1;}string s_di; // dialectwhile (cin>>s_di){
if(m.count(s_di)==0) // 没出现过{
cout<<"eh"<<endl;}elsecout<<m[s_di]<<endl;}system("pause");return 0;
}
方法2
#include<bits/stdc++.h>
using namespace std;#define MOD 1000007
#define PRIME 37struct Entry
{
string key="";string val="";int flag = 0;
}ht[MOD+1]; // 不可以用typedefint Hash(string s) // 返回下标
{
int idx = 0;for (int i = 0; i < s.length(); i++){
idx = idx * PRIME + s[i]-'0';}//cout << idx << '&' << endl;return abs(idx)%MOD;
}void Insert(string key, string val) // 插入哈希表
{
int idx = Hash(key);while (ht[idx].key!="") // 出现冲突，找下一个位置idx = (idx + 1) % MOD;ht[idx].key = key;ht[idx].val = val;ht[idx].flag = 1;
}void Get(string s) // 获取key对应的value
{
int idx = Hash(s);//cout << idx << endl;while (idx<MOD && ht[idx].key.length()>0){
if (ht[idx].key == s){
cout << ht[idx].val << endl;return;}//cout << idx << endl;idx = (idx + 1) % MOD;}cout << "eh" << endl;
}int main()
{
string s;while (getline(cin, s) && s.size()){
int pos = s.find(' ');int len = s.length();string s1 = s.substr(0, pos);string s2 = s.substr(pos + 1, len);Insert(s2, s1);}string s_di;while (cin >> s_di){
Get(s_di);}return 0;
}方法3
#include<bits/stdc++.h>
using namespace std;#define MAXN 100007
#define PRIME 37struct Entry
{
string key;string val;int next;
}e[MAXN]; // 存放所有keyint head[MAXN] = {
0 }; // head[i]=j:哈希值为i的key在e中的位置为j
int num = 0; // key在e中的位置int Hash(string s)
{
int idx = 0;for (int i = 0; i < s.length(); i++){
idx = idx * PRIME + s[i] - '0';}return abs(idx) % MAXN;
}void Insert(string key, string val)
{
int idx = Hash(key);num++; // 更新e中的索引值e[num].key = key, e[num].val = val;e[num].next = head[idx]; // 上一个同idx的key在e中的位置head[idx] = num; // 更新该idx对应key在e中的位置
}void Get(string s)
{
int idx = Hash(s);for (int i = head[idx]; i; i = e[i].next){
if (e[i].key == s){
cout << e[i].val << endl;return;}}cout << "eh" << endl;
}int main()
{
string s;while (getline(cin, s) && s.size()){
int pos = s.find(' ');int len = s.length();string s1 = s.substr(0, pos);string s2 = s.substr(pos + 1, len);Insert(s2, s1);}string s_di;while (cin>>s_di){
Get(s_di);}return 0;
}