湖南生第八届大学生程序设计大赛原题 C-Updating a Dictionary(UVA12504 - Updating a Dictionary）
UVA12504 - Updating a Dictionary
给出两个字符串，以相同的格式表示原字典和更新后的字典。要求找出新字典和旧字典的不同，以规定的格式输出。
算法操作：
（1）处理旧字典，将旧字典中的每对关键字及其价值从字典串中截取出来，压入容器中。用做新旧字典对比检索。
（2）处理新字典，将新字典中的每对关键字及其价值从字典串中截取出来。对于每个关键字，在容器中检索相同的关键字。若检索不成功，该关键字是新字典新增的，处理存储到相关的串数组中。若检索成功，提取容器中该关键字的价值与新字典中该关键字的价值对比，若值相同，该关键之没有改变，不予处理；若价值不同，处理存储到相关的串数组中。对于检索成功的关键字，处理完后立即将其从容器中删除，以免影响后续操作。
（3）处理容器中剩下的关键字及其价值。新字典处理完后，容器中剩余的都是旧字典更新后删除的关键字。提取容器中所有剩余关键字，并将其处理存储到相关串数组中。
（4）对处理所得结果【关键字及其价值变化后存储的数组】进行判断输出。完全没有变化，输出“No changes”；否则，按照题目要求的格式输出相关变化值。
难点：
（1）截取关键字及其价值的操作，字符串综合应用（*****）
（2）处理新字典中关键字和旧字典中关键字的操作【关键删除和价值不同的变化】,容器的基本应用（**）
（3）处理旧字典中删除的关键字的操作【map容器方法的应用】，容器的高级应用（***）
（4）输出格式，逗号隔开（*）
易错点：
（1）关键字及其价值截取长度，截取的起始位置和终止位置
（2）关键字的价值的长度可能大于20，__int64存储可能会溢出，要用字符串存储
（3）空字典—>非空字典，非空字典—>空字典 的转换，不予处理会出错
（4）输出格式，中间有逗号，最后有空行
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<map> using namespace std; int main()
{
//freopen("in.txt","r",stdin); string str1,str2;
int add1,d,m; // <增加的，减少的，价值变化的>关键字的个数
string ad[102],decr[102],mul[102]; // 存储<增加的，减少的，价值变化的>关键字 int t;
cin>>t; //t组数据
while(t--)
{
map<string,string> ma; //主要查找索引的容器 cin>>str1>>str2; //输入两个“字典” add1=0; //初始化为0，表示都还没有
d=0;
m=0; int a=0; //截取检索的起始位置为0 while(str1.find(',',a+1)<str1.size()) //当串中没有逗号的时候结束【截取关键字和其价值】
{
string s(str1,a+1,str1.find(',',a+1)-a-1); //截取到一组关键字及其价值【上一个逗号到下一个逗号之间】 string x(s,0,s.find(':',0));
string y(s,s.find(':',0)+1,s.size()-s.find(':',0)); //分离一组关键字及其价值【分号为分割符】 ma.insert(pair<string,string>(x,y)); //把关键字及其价值作为一组索引，插入到容器map中 a=str1.find(',',a+1); //下组关键字截取的起始位置，从本组关键字截取的末尾位置后面的逗号的下一个字符开始
} string s(str1,a+1,str1.find('}',a+1)-a-1); //逗号为界的已经截取完，最后一组数据，截取标志是【右大括号】 string x(s,0,s.find(':',0));
string y(s,s.find(':',0)+1,s.size()-s.find(':',0)); if(x.size()!=0) ma.insert(pair<string,string>(x,y)); //若最后一组是【空】，该字典为空字典，截取的空字符串不予处理 a=0;
while(str2.find(',',a+1)<str2.size())
{
string s(str2,a+1,str2.find(',',a+1)-a-1); string x(s,0,s.find(':',0));
string y(s,s.find(':',0)+1,s.size()-s.find(':',0)); if(ma.find(x)==ma.end())ad[add1++]=x; //在容器map中检索不到关键字x，x是新加进来的，更新【增加的关键字的串数组（添加）】
else //在map中检索到该关键字
{
string temp=ma.find(x)->second; //取出容器中该关键字对应的价值
if(temp!=y)mul[m++]=x; //价值不同，改变【价值变化关键字的串数组（增加）】
ma.erase(x); //检索应用过的，直接删除，免得影响后面的操作
}
a=str2.find(',',a+1);
} string s1(str2,a+1,str2.find('}',a+1)-a-1); string x1(s1,0,s1.find(':',0));
string y1(s1,s1.find(':',0)+1,s1.size()-s1.find(':',0)); if(x1.size()!=0) //【第二个字典是空字典】
{
if(ma.find(x1)==ma.end())ad[add1++]=x1;
else
{
string temp=ma.find(x1)->second;
if(temp!=y1)mul[m++]=x1;
ma.erase(x1);
} } while(ma.begin()!=ma.end()) //处理两个字典对照后，容器中的关键字【第一个字典更新后，删掉的关键字】
{
string temp=ma.begin()->first;
decr[d++]=temp;
ma.erase(temp);//处理过的就删除，知道容器为空，处理结束
} if(add1==0&&d==0&&m==0)cout<<"No changes"<<endl; //关键字变化的总个数为0【字典更新后没有变化】 else
{
if(add1!=0) //字典跟新后，关键字有增加
{
sort(ad,ad+add1);
cout<<"+";
for(int i=0;i<add1;i++)
{
if(i!=0)cout<<",";
cout<<ad[i];
}
cout<<endl;
} if(d!=0) //字典更新后，关键字减少
{
sort(decr,decr+d);
cout<<"-";
for(int i=0;i<d;i++)
{
if(i!=0)cout<<",";
cout<<decr[i];
}
cout<<endl;
} if(m!=0) //字典更新后，有关键字的价值变化
{
sort(mul,mul+m);
cout<<"*";
for(int i=0;i<m;i++)
{
if(i!=0)cout<<",";
cout<<mul[i];
}
cout<<endl;
}
} cout<<endl;
}
return 0;
}
最新文章
- 【原创】threejs实现一个全景地球
- Mac上安装 mySql
- HDU 5534 Partial Tree (完全背包变形)
- 一个js排序
- JAVA设置环境变量和在DOS下运行java程序
- MYSQL 删除二进制日志的 3 个方法
- mysql union ,UNION RESULT
- Windows API 之 ReadProcessMemory
- 【Jquery】prop与attr的差别
- 1. CMake 系列 - 从零构建动态库和静态库
- PyCharm(python的开发工具)的安装与破解
- Hadoop之HDFS概述
- [转]Kaldi语音识别
- 理解Java注解类型
- PHP FastCGI进程管理器PHP-FPM的架构
- codeforces 797B
- PHP学习 例外和错误处理
- JavaScript进阶系列02,函数作为参数以及在数组中的应用
- 课堂练习Complex类
- Java基础学习—思维导图