poj 2503 Babelfish(查找)

Memory: 2504K

Time: 344MS

解题思路

题意：

    给出一些英文单词及其相应的外语单词，相当于一个词典。再给出一些外语单词，要根据字典输出相应的英文单词。

 

思路：

   用qsort+bearch。把英文单词和外语单词用一个结构体数组存起来，用qsort把它从小到大排序，因为bsearch用的时候查找的数组必须是升序的。再用bsearch查找输入的单词，并输出。Bsearch用的时候跟qsort差不多，就多了第一个参数&key，表示要找的目标单词。它的返回值是（void*）所以要转化为（word*）。

源程序

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>
#define N 100004

typedef struct
{
    char engl[12];  
    char fore[12];
}word;
word words[N];

int cmp(const void *p, const void *q)
{
    word *a = (word *)p;
    word *b = (word *)q;
    return strcmp(a->fore, b->fore);
}

int main()
{
    int i, j, re;
    char ch[30];   //这里本来数组开小了。搞出个破坏栈的错误，找好久。。
    char *p;
    word *q, key;

    freopen("in.txt", "r", stdin);
    i = 0;
    while(strcmp(gets(ch), "") != 0)
    {
        p = strtok(ch, " ");     //这里是把英文单词跟外语单词分开来
        strcpy(words[i].engl, p); 
        p = strtok(NULL, " ");
        strcpy(words[i].fore, p);
        i++;
    }
    qsort(words, i, sizeof(words[0]), cmp);
    while(scanf("%s", ch)!=EOF)
    {
        strcpy(key.fore, ch);
        q = (word*)bsearch(&key, words, i, sizeof(words[0]), cmp);
        if(q)
            printf("%s\n", q->engl);
        else printf("eh\n");
    }
    getch();
    return 0;
}