POJ 2503 hash函数

只涉及插入和查找运算，用HASH函数，ELFHash的插入和元素按的时间复杂度均为O(1)

#include<iostream>

#include<string>

using namespace std;

const int MAX_LEN=12;

const int MAX_HASH=21169;

struct Dict

{

char english[MAX_LEN];

char foreign[MAX_LEN];

}dict[100000];

struct LNode

{

int ind;

LNode *Next;

};

LNode *HashLish[MAX_HASH];

int Hash(char *str)

{

__int64 h=0;

while(*str!='\0')

{

h=(h<<4)+*str;

str++;

__int64 g=h&0xf0000000L;

if(g!=0)

{

h^=g>>24;

}

h&=~g;

}

return h%MAX_HASH;

}

int main()

{

char buffer[512];

LNode *p;

int i=0;

while(gets(buffer))

{

if(sscanf(buffer,"%s%s",dict[i].english,dict[i].foreign)!=2)

{

break;

}

else

{

int key=Hash(dict[i].foreign);

p=new LNode();

p->ind=i;

p->Next=HashLish[key];

HashLish[key]=p;

i++;

}

while(gets(buffer)!=NULL)

{

int key=Hash(buffer);

p=HashLish[key];

while(p!=NULL)

{

if(strcmp(buffer,dict[p->ind].foreign)==0)

break;

p=p->Next;

}

if(p==NULL)

printf("eh\n");

else printf("%s\n",dict[p->ind].english);

}

return 0;

}

posted on 2011-04-18 18:49 Myth. 阅读(129) 评论(0) 编辑收藏引用

常用链接

留言簿

文章档案

搜索

最新评论

只有注册用户登录后才能发表评论。




网站导航: 博客园博客园最新博文博问管理