第 2 章 第 1 题 同位词问题 下问 Multimap实现
2024-08-29 02:05:50
问题分析
输入:一个任意的单词和一个内含多个乱序单词的字典文件
输出:该单词在字典中的所有同位词
约束:允许事先对字典进行预处理
解决思路
上问的程序有个缺点 - 我们必须遍历完整个字典文件才能输出所有结果。现在下问允许我们事先对字典文件进行预处理,那么可以先对字典文件的单词按其标识符排序,这样相同标识符的单词都聚集在了一起,从而避免了对整个文件的检索。下面的代码用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容器不适合处理大批量的数据?原因仍在思考中 读者若有思路欢迎与我联系... ...
最新文章
- JavaScript权威指南 - 对象
- Mina、Netty、Twisted一起学(八):HTTP服务器
- 【转】Windows平台下的Subversion安装配置新手指南
- Redis 外部访问设置
- 【摘】使用tail、head命令过滤行
- The C Programming Language (second edition) 实践代码(置于此以作备份)
- 大数据量的csv文件如何导入到 sql 数据库
- 在linux下的firefox中安装flashplayer
- 黄聪:利用Aspose.Word控件实现Word文档的操作(转)
- js冒泡事件之之之
- POJ 1989
- Scala - 正则表达式匹配例子
- C语言字符串操作函数集
- javascript 用call来继承实例属性
- Java基础——关于访问权限的一道例题
- Git仓库创建和文件提交
- 【bzoj 4173】数学
- Spring boot配置logback
- 39.纯 CSS 创作一个表达怀念童年心情的条纹彩虹心特效
- mysql slave 主从 指定表 通配符