题解 Andy s First Dictionary(UVa10815)紫书P112set的应用

紫书P112；set的应用；Andy’s First Dictionary(UVa10815)；

Vjudge题目地址请移步此处

题目大意：

输入一个文本（最多500行，每行最多200个字符，以EOF结尾），找出所有不同的单词，按照字典序从小到大输出以小写输出（一行一单词）。

Sample Input

Adventures in Disneyland

Two blondes were going to Disneyland when they came to a fork in the

road. The sign read: “Disneyland Left.”

So they went home.

Sample Output
a
adventures
blondes
came
disneyland
fork
going
home
in
left
read
road
sign
so
the
they
to
two
went
were
when

题目分析：

数据结构选择：统计出现过的单词，理所当然想到set；

算法设计：暴力模拟，时间O(n)最大100000；每次读入一串字符，for循环判断单个字符是否为字母，若是转换为小写，若不是，则存入已读入的字母构成的单词，重新开始读入下一个单词；

//dict为set集合,s为当前读入的字符串,now为当前已经存入的字母构成的单词
if(isalpha(s[i])){
    
		  	 	 now+=tolower(s[i]);
			 }else{
    
			 	 if(!now.empty()) dict.insert(now);
			 	 now.clear();
			 }

模块设计：定义与预处理–读入与初始化–处理字符串–输出–return 0;

代码：

#include<iostream>
#include<set>
#include<cctype>
#include<string>
using namespace std;

struct rule{
    
	 bool operator()(const string &a,const string &b){
    
	 	 return a<b;
	 }
};

set<string,rule> dict;
string s;

int main()
{
    
	 while(cin>>s)
	 {
    
	 	 string now;
	 	 now.clear();
	 	 for(int i=0;i<s.length();i++)
		 {
    
		  	 if(isalpha(s[i])){
    
		  	 	 now+=tolower(s[i]);
			 }else{
    
			 	 if(!now.empty()) dict.insert(now);
			 	 now.clear();
			 }
		 }
		 if(!now.empty()) dict.insert(now);
	 }
	 for(set<string>::iterator i=dict.begin();i!=dict.end();i++)//auto i=dict.begin();
	 	 cout<<*i<<endl;
	 return 0;
}

要点与细节总结：

1. 代码中使用了字符串处理函数isalpha()与tolower();
   isalpha()：判断是否为字母；
   islower()：判断是否为小写字母；
   isupper()：判断是否为大写字母；
   tolower()：转换为小写字母；
   toupper()：转换为大写字母；
2. set的插入insert()若遇到重复值则无效；
3. 代码中对于now的处理可以用输入流替代：遇到非字母转换为空格，之后对s进行流输入处理，需要加头文件#include<sstream>；

for(int i=0;i<s.length();i++)
	 if(isalpha(s[i])) s[i]=tolower(s[i]); else s[i]=' ';
stringstream ss(s);
while(ss>>buf) dict.insert(buf);

4. 代码中定义迭代器set<string>::iterator i=dict.begin();可以用更为简洁的auto i=dict.begin()替换。

更新与2020.6.23