poj2503哈希表实现字符串查找

题目链接

Babelfish

题目描述(Description)

给定一些字符串以及它在一种外星语言中的对应解释，现在有若干外星语言中的串，要求把它们翻译成英语。

分析(Analysis)

直接用字典树存外星语，维护一个长度为11的字符数组，用来存对应的英语。

代码(Code)

#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int M=100003;
struct Node{
    int hash;
    struct Node *next;
}*link[M]={NULL};

char word[100000][11],dialect[100000][11];

/*Unix系统ELF字符串散列函数*/
int ELFhash(char *key)
{
    unsigned long h=0,g;
    while(*key){
        h=(h<<4)+*key++;
        g=h&0x0000000L;
        if(g)
            h^=g>>24;
        h&=~g;
    }
    return h%M;
} 

int main()
{
    int i,j,e,n=0;
    struct Node *p;
    char str[100];
    gets(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=(struct Node *)malloc(sizeof(struct Node));
        p->hash=n;
        p->next=link[e];
        link[e]=p;
        n++;
        gets(str);
    }
    while(gets(str)!=NULL){
        e=ELFhash(str);
        p=link[e];
        while(p!=NULL){//哈希冲突处理
            if(strcmp(str,dialect[p->hash])==0)
                break;
            else
                p=p->next;    
        }
        if(!p)
            printf("eh\n");
        else
            printf("%s\n",word[p->hash]);
    }
    return 0;
}