快速序排+二分查找

#include
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;
        else
            high = mid - 1;
    }
    return -1;
}

int main()
{
    char str[25];
    int index = -1;
    while(gets(str))
    {
        if(str[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("ehn");
        else
            printf("%sn",entry[index].e);
    }
    return 0;
}


字符串哈希表，在《算法艺术与信息学竞赛》推荐使用ELFHash函数，哈希冲突的处理采用链表法

#include

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("%sn",entry[k].e);
            return;
        }
    }
    printf("ehn");
}

int main()
{
    char str[22];
    while(gets(str))
    {
        if(str[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;
}