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技術方案你知多少？