当前位置：首页 > news >正文

词典

news 来源：原创 2024/5/20 21:42:51

总时间限制: 3000ms 内存限制: 65536kB
描述
你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运
的是，你有一本词典可以帮助你。

输入
首先输入一个词典，词典中包含不超过100000个词条，每个词条占据一行。
每一个词条包括一个英文单词和一个外语单词，两个单词之间用一个空格隔
开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行，
然后给出一个由外语单词组成的文档，文档不超过100000行，而且每行只包
括一个外语单词。输入中出现单词只包括小写字母，而且长度不会超过10。

输出
在输出中，你需要把输入文档翻译成英文，每行输出一个英文单词。如果某个
外语单词不在词典中，就把这个单词翻译成“eh”。

样例输入
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

样例输出
cat
eh
loops

比较简单的检索题,主要建立一个词典的结构体,然后建立完毕后用sort对外文进行升序排序,查找时直接进行二分查找,速度很快.值得注意的是构造词典时,词典的输入是以一个回车结束,所以可以使用 getchar() 函数来获取输入的第一个字符,如果是'\n',说明词典的输入停止.然后再输入待查找的外文.

看起来挺简单的题目：

#include <iostream>
#include <cstring>
#include <string>
#include <stdio.h>
#include <algorithm>
using namespace std;

int d_num, flag, res;
char temp;
char _find[12];

struct dictionary
{
    char Eng[12];
    char For[12];
}dic[100100];

bool cmp(dictionary a,dictionary b)
{
    return strcmp(a.For,b.For)<0;
}

void dfs(int left,int right,char *des)
{
    int mid = (left+right)/2;
    if(left <= right)
    {
        if(strcmp(dic[mid].For,des) < 0)//在右侧区域
        {
            return dfs(mid+1,right,des);
        }
        else if(strcmp(dic[mid].For,des) > 0)
        {
            return dfs(left,mid-1,des);
        }
        else
        {
            flag = 1;
            res = mid;
            return;
        }
    }
    return;
}

int main()
{
    while((temp=getchar()) != '\n')
    {
        dic[d_num].Eng[0] = temp;
        scanf("%s%s",dic[d_num].Eng+1,dic[d_num].For);
        d_num++;
        getchar();//行尾回车
    }
    sort(dic,dic+d_num,cmp);//词典按外文排序
    while(scanf("%s",&_find) != EOF)
    {
        flag = 0;
        dfs(0,d_num-1,_find);
        if(flag == 0)
            printf("eh\n");
        else
        {
            printf("%s\n",dic[res].Eng);
        }
    }
    return 0;
}

这是通过自己手写的检索算法来实现的，其实并不需要自己手写，因为C++的STL库函数里面提供了一个map的容器，用来存储若干元素，这些元素都是由关键值 (Key Value，以下称为 Key 值) 和映射值 (Mapped Value，以下依旧称为映射值) 配对组成的，具体说明如下：
在一个 map 中， Key 值通常用来排序或特指元素，映射值用来存储与该 Key 值绑定的内容。 Key 值与映射值的数据类型可以不同，而且可以一起被放进成员类型 value_type 中，value_type 是一种配对类型，定义如下：

typedef pair<const Key, T> value_type;

在 map 内部的元素通常按照其 Key 值排序，且排序方式是根据某种明确、严格的弱排序标准进行的，这种排序标准是由 map 内部的比较对象（即 map::key_comp）指定的。
map 容器通过 Key 值访问特定元素的速度，相较于 unordered_map 容器通常较慢，但 map 容器允许基于它们的顺序对子集进行直接迭代。
map 中的映射值可以使用括号运算符 (operator[]) 通过其关联的 Key 值直接访问。
map 通常使用二叉搜索树实现。

因为map是根据二叉搜索树来实现，所以检索函数速度也还可以，这道题就是需要在两个字符串中建立一个映射，然后度字符串，判断如果是换行就退出，然后将读入的字符串存到map里面，之后继续while循环，只需要用map的查找函数count查找输入的字符串就行了，找到了就将其输出，没找到就输出eh。

这里先介绍一个东东：
istringstream

#include<bits/stdc++.h>
using namespace std;
int main()
{
	map<string,string>u;
	string s,k,g;
	int y;	
    while(1)
	{
        getline(cin,s);
        y=s.find(' ');
        if(y!=s.npos)
		{
            k=s.substr(0,y+1);
            g=s.substr(y+1);
            u.insert(make_pair(g,k));
        }
        else 
		  break;
    }
    while(cin>>s)
	{
        if(u.count(s))
		  cout<<u[s]<<endl;
        else 
		  cout<<"eh"<<endl;
    }
    return 0;
}

今天的数据结构题就讲到这里了，再见！