POJ2503两种解法：快速排序+二分查找与哈希表

??? poj2503题目意思很简单：就像查找一本字典，根据输入的条目和要查询的单词，给出查询结果（每个单词长度不超过10）。这题有很多实现方式，最容易想到的就是map，但这是acm训练且stl里面的map速度不够快，那就要另谋出路。

??? 数据量为100,000。可以想到的是快排+二分，复杂度是O(nlog2n)。还有就是哈希，哈希查询时间是O(1)，当然，还要考虑哈希冲突，设计合理的字符串哈希函数。

??? 首先是快排+二分，比较简单。

#include <iostream>const int MAX = 100001;typedef struct{char e[11];char f[11];}Entry;Entry entry[MAX];int i = 0;//词典总条数int cmp(const void *a, const void *b){return strcmp((*(Entry *)a).f, (*(Entry *)b).f);}int BinSearch(char c[]){int low = 0, high = i - 1;int mid, t;while(low <= high){mid = (low + high) / 2;t = strcmp(entry[mid].f, c);if(t == 0)return mid;else if(t == -1)low = mid + 1;elsehigh = mid - 1;}return -1;}int main(){char str[25];int index = -1;while(gets(str)){if(str[0] == '\0')break;sscanf(str,"%s%s",entry[i].e,entry[i].f);i++;}qsort(entry,i,sizeof(Entry),cmp);  while(gets(str)){        index = BinSearch(str);if(index == -1)printf("eh\n");elseprintf("%s\n",entry[index].e);}return 0;}

?

??? 对于字符串的哈希，在《算法艺术与信息学竞赛》推荐使用ELFHash函数。对于哈希冲突的处理，采用的是链表法（个人认为线性探测等效率不是很高）。

#include <iostream>const int M = 149993;typedef struct{char e[11];char f[11];int next;}Entry;Entry entry[M];int i = 1;//词典总条数int hashIndex[M];int ELFHash(char *key){    unsigned long h=0;    while(*key)    {        h=(h<<4)+(*key++);        unsigned long g=h&0Xf0000000L;        if(g) h^=g>>24;        h&=~g;    }    return h%M;}void find(char f[]){int hash = ELFHash(f);for(int k = hashIndex[hash]; k; k = entry[k].next){if(strcmp(f, entry[k].f) == 0){printf("%s\n",entry[k].e);return;}}printf("eh\n");}int main(){char str[22];while(gets(str)){if(str[0] == '\0')break;sscanf(str,"%s %s",entry[i].e,entry[i].f);int hash = ELFHash(entry[i].f);entry[i].next = hashIndex[hash];hashIndex[hash] = i;i++;}while(gets(str))find(str);return 0;}

?

?