这是一道字符串处理的题。有点写字典，查字典的意思，首先要解决的是输入字典和查字典时输入单词中间的那

一个空行，我是用gets输入前面的东西，所以只需一个判断就可以跳出输入字典的循环。然后是输入单词翻译，

因为字典当中的单词比较多，我又不会hash，所以用了二分查找。

#include
     
       #include
      
        #include
       
         #define M 100003 typedef struct dictionary {
   char f[15]; char n[15]; }D; D dic[M]; /* 按照后一个单词的字典序升序排序 */ int cmp( const void *_p, const void *_q) {
       D *q = (D *)_q;     D *p = (D *)_p; return strcmp( p->n, q->n); } int main() {
   char s[30]; int i = 0; while( gets(s) != NULL)     {
   if( s[0] == '\0') break; //结束字典的输入         sscanf( s, "%s%s", dic[i].f, dic[i].n);         i ++;     }     qsort( dic, i, sizeof( dic[0]), cmp); int x, y; while( gets(s) != NULL)     {
           x = 0, y = i; //让x，y分别等于第一个和最后一个下标         while( x < y) //二分查找         {
   int m = x + (y - x) / 2; if( strcmp( dic[m].n, s) == 0) {
                   printf( "%s\n", dic[m].f); break;             } else if( strcmp( dic[m].n, s) > 0)                 y = m; else x = m + 1;         } if( x >= y) printf( "eh\n");     } return 0; }
       
      
     

 

今天看了字典树原理，顺便将这道题再写了一遍。

（字典树）

字典树的基本功能是用来查询某个单词（前缀）在所有单词中出现次数的一种数据结构，

它的插入和查询复杂度都为O(len),Len为单词（前缀）长度，但是它的空间复杂度却非

常高，如果字符集是26个字母，那每个节点的度就有26个，典型的以空间换时间结构。

/*Accepted    13604K    235MS    C++    904B    2012-08-02 10:33:31*/#include
     
      #include
      
       #include
       
        typedef struct{    int next[26];    char eng[11];}Trie;Trie t[200000];char en[11], fr[11];int tp;void insert(char *x, int site){    if(*x)    {        if(!t[site].next[*x - 'a'])            t[site].next[*x - 'a'] = ++ tp;        insert(x + 1, t[site].next[*x - 'a']);    }    else        strcpy(t[site].eng, en);}void search(char *x, int site){    if(*x)    {        if(!t[site].next[*x - 'a'])        {            printf("eh\n");            return;        }        search(x + 1, t[site].next[*x - 'a']);    }    else        printf("%s\n", t[site].eng);}int main(){    char s[25];    while(gets(s) && s[0] != '\0')    {        sscanf(s, "%s%s", en, fr);        insert(fr, 0);    }    while(scanf("%s", fr) == 1)        search(fr, 0);    return 0;}