248      阿里云  技术社区[云栖]

uva 10282 - Babelfish

     这题可以用map直接水过，但是那样就没有什么意思了。

     所以还是用hash表写了下，学习了一下hash链表的方法，其实就是做一个邻接表，但是这样在判断时还要比较生成hash值的string，而且如果hash函数没构造好，复杂度会大大增加，不过是一个解决冲突的好办法。

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stdlib.h>
#define INF 1E9
using namespace std;
int head[1000000],next[100010];
string s[100010],f[100010];
int get_hash(string s)
{
    long long ans=0;
    for(int i=0;i<s.size();i++)
      ans=ans*33+s[i];
    return ans%999991;
}
int main()
{
    memset(head,-1,sizeof(head));
    string a,t;
    char ss;
    int cnt=1,now,u;
    s[0]="eh";
    while(cin>>a>>t)
    {
        s[cnt]=a;
        f[cnt]=t;
        now=get_hash(t);
        next[cnt]=head[now];//因为数据保证唯一，所以直接插入即可
        head[now]=cnt;
        cnt++;
        getchar();
        if((ss=getchar())=='\n')break;//判断有无遇到空行
        else ungetc(ss,stdin);
    }
    while(cin>>a)
    {
        now=get_hash(a);
        bool flag=1;
        for(u=head[now];u!=-1;u=next[u])
        {
            if(f[u]!=a)continue;
            cout<<s[u]<<endl;
            flag=0;
        }
        if(flag)cout<<s[0]<<endl;
    }
}

最后更新：2017-04-02 22:15:46

  上一篇： 我项目中使用到的以object作为参数的简单整理

  下一篇： 服务器RAID技术方案你知多少？