问题分析

  输入:一个任意的单词和一个内含多个乱序单词的字典文件

  输出:该单词在字典中的所有同位词

  约束:允许事先对字典进行预处理

解决思路

  上问的程序有个缺点 - 我们必须遍历完整个字典文件才能输出所有结果。现在下问允许我们事先对字典文件进行预处理,那么可以先对字典文件的单词按其标识符排序,这样相同标识符的单词都聚集在了一起,从而避免了对整个文件的检索。下面的代码用C++中的关联容器Multimap实现了这个思想。

代码实现

 #include <iostream>
#include <fstream>
#include <map>
#include <string> using namespace std; #define MAX 26 /*
* 获取单词word的标识符并返回
*/
string getID(string word)
{
string id(, '');
for (string::size_type i=; i<word.length(); i++) {
id[word[i]-]++;
} return id;
} int main()
{
/*
* 打开字典文件
*/
string filename;
cout << "请输入字典文件名( 当前目录下 ): ";
cin >> filename; fstream io;
io.open(filename.c_str());
if (!io) {
cout << "打开文件失败" << endl;
return ;
} /*
* 获取查询单词及其标识符
*/
string word;
cout << "请输入查询单词: ";
cin >> word;
string wordID = getID(word); /*
* 将字典文件存放进关联容器
*/
multimap<string, string> m;
string first, second;
while (io >> second) {
first = getID(second);
m.insert(make_pair(first, second));
}
io.close(); /*
* 检索关联容器并打印检索结果
*/
multimap<string, string> :: iterator it1, it2;
it1 = m.lower_bound(wordID);
it2 = m.upper_bound(wordID);
while (it1->first != it2->first) {
cout << it1->second << endl;
it1++;
} // 关闭文件指针
io.close(); return ;
}

运行测试

测试所用字典文件:

运行结果:

说明

  当字典文件中单词数量达到千万级别的时候,程序运行异常(很占CPU和内存且耗时巨大,而上问用的程序依然运行良好)。难道multimap容器不适合处理大批量的数据?原因仍在思考中 读者若有思路欢迎与我联系... ...

最新文章

  1. JavaScript权威指南 - 对象
  2. Mina、Netty、Twisted一起学(八):HTTP服务器
  3. 【转】Windows平台下的Subversion安装配置新手指南
  4. Redis 外部访问设置
  5. 【摘】使用tail、head命令过滤行
  6. The C Programming Language (second edition) 实践代码(置于此以作备份)
  7. 大数据量的csv文件如何导入到 sql 数据库
  8. 在linux下的firefox中安装flashplayer
  9. 黄聪:利用Aspose.Word控件实现Word文档的操作(转)
  10. js冒泡事件之之之
  11. POJ 1989
  12. Scala - 正则表达式匹配例子
  13. C语言字符串操作函数集
  14. javascript 用call来继承实例属性
  15. Java基础——关于访问权限的一道例题
  16. Git仓库创建和文件提交
  17. 【bzoj 4173】数学
  18. Spring boot配置logback
  19. 39.纯 CSS 创作一个表达怀念童年心情的条纹彩虹心特效
  20. mysql slave 主从 指定表 通配符

热门文章

  1. js方法encodeURI后,关于get请求url长度的限制测试与总结
  2. 按 Tab 在多个 InputField 间切换
  3. SpringBoot使用Junit4单元测试
  4. linux 时间模块 二
  5. https的简单学习
  6. hdu 1250(大整数)
  7. java 8 LocalDateTime 20 例
  8. 洛谷——P1508 Likecloud-吃、吃、吃
  9. deferred 对象
  10. AndroidStudio怎样导入jar包