poj2503 Babelfish–hash解决实现快速匹配
http://acm.pku.edu.cn/JudgeOnline/problem?id=2503
其实这个题目，使用qsort+二分查找应该是比较简单可以实现的，使用trie应该也可以，但是不晓得速度怎么样，另外不晓得有没有人直接用STL中的map做了没有，呵呵，那个一定很水。
我使用hash来做的目的是想熟悉一下指针以及hash的操作。这个题目我想到了使用ELFHash，并且使用拉链法处理冲突问题。
但是在POJ上运行的时间并不是很理想，后来我查看了一下，才晓得。为了节省空间，每个单词，每次去malloc空间，其实这样不太好，每次都去浪费时间去malloc，既然题目中明显说出仅有10000条数据，且每个单词不超过10个字节，那么完全可以用数组固定大小，或者用malloc一次分配完成，这样不会每次都浪费时间。不过，我还是觉得不浪费空间适应性更强，更适合工程上的项目。
所以就不再改了，代码贴出来讨论，呵呵
另外，其中，在调试的时候，一直WA，调试好久，在我电脑上运行结果正常，而到POJ上确实WA，郁闷至极的时候突然发现：查不到单词输出 “eh” 而我输出的是”en”，真是悲剧，en 和 eh差别那么小，呵呵。低级错误！
BabelfishTime Limit: 3000MS Memory Limit: 65536KTotal Submissions: 15393 Accepted: 6765DescriptionYou have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them.InputInput consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters.OutputOutput is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as “eh”.Sample Inputdog ogdaycat atcaypig igpayfroot ootfrayloops oopslayatcayittenkayoopslaySample Outputcatehloops
/* author:yqshare */
#include<stdio.h> #include<string.h> #include <stdlib.h> #define M 30000 struct word_entry{ char * word; char * foreign_word; struct word_entry * next; }; typedef struct word_entry WORD_ENTRY; ELFHash(char * str) { unsigned int hash = 0; unsigned int x = 0; while (*str) { hash = (hash << 4) + (*str++); if ((x = hash & 0xF0000000L) != 0) { hash ^= (x >> 24); hash &= ~x; } } return (hash & 0x7FFFFFFF); } WORD_ENTRY * alloc_entry(char * word , char * foreign) { WORD_ENTRY * word_entry =NULL; word_entry = (WORD_ENTRY *)malloc(sizeof(WORD_ENTRY)); word_entry->foreign_word = ( char * )malloc(strlen(foreign)+1); strcpy(word_entry->foreign_word,foreign); word_entry->word = ( char * )malloc(strlen(word)+1); strcpy(word_entry->word,word); word_entry->next = NULL; return word_entry ; } int main() { char word[11],foreign_word[11],buff[50]; int hash_size=0,i; WORD_ENTRY ** hash_base = (WORD_ENTRY *)calloc(M,sizeof(WORD_ENTRY *)); WORD_ENTRY * hash_tmp=NULL, * word_tmp = NULL; memset(word,0,10); memset(foreign_word,0,10); while(gets(buff) && strcmp (buff,"")!= 0) { for (i=0;buff[i]!=' ';i++) word[i]=buff[i]; word[i++]='\0'; strcpy(foreign_word,buff+i); hash_size = ELFHash(foreign_word)%M; hash_tmp = *(hash_base+hash_size); word_tmp = hash_tmp; hash_tmp = alloc_entry(word,foreign_word); hash_tmp->next = word_tmp; *(hash_base+hash_size) = hash_tmp; memset(word,0,10); memset(foreign_word,0,10); memset(buff,0,50); } while(gets(foreign_word)&& strcmp (foreign_word,"")!= 0) { hash_size = ELFHash(foreign_word)%M; hash_tmp = *(hash_base+hash_size); while(hash_tmp) { if(strcmp(hash_tmp->foreign_word,foreign_word)==0) break; hash_tmp = hash_tmp->next; } if(hash_tmp != NULL) printf("%s\n",hash_tmp->word); else printf("eh\n"); } }
学习了