【题目链接】
ybt 1185：单词排序
OpenJudge NOI 1.10 10:单词排序
【题目考点】
1. 排序
【君义精讲】排序算法
2. 字符串比较
字符数组比较：char s1[N], s2[N];
strcmp(s1, s2)
返回正数：s1大于s2
返回负数：s1小于s2
返回0：s1等于s2。
s1小于s2指的是按字典序排序，s1在s2前。string类对象比较
string s1, s2;
可以直接用>, <, >=, <=, !=, ==来比较两个字符串
3. 读入多个由空格分隔的字符串
写while(cin >> s)或while(scanf("%s", s)!=EOF)，可以读入由多个空格分隔的字符串。本机调试时要想结束程序，需要输入Ctrl+z，再按回车，即可结束。
【解题思路】
输入过程可以通过while(cin>>s)来输入由空格分开的多个字符串，或读入整个字符串后解析出各个单词。字符串的存储结构可以选择二维字符数组、指针数组，或string类。排序方法随意选择。输出时有三种方法可以避免输出相同的元素： 可以先输出第一个字符串，后面的要输出的字符串如果与前一个相同，则不输出。与前一个不同则输出。这样如果有连续相同的多个字符串，只会输出第一个。如果当前字符串与后一个相同则不输出，不同则输出。最后一个字符串单独输出。这样可以输出连续相同的字符串中的最后一个。用一个变量记录先前输出的字符串，当前要输出的如果与先前输出的相同，则不输出。否则输出，并记录。【题解代码】
解法1：读入多个字符串，string类数组保存，STL sort排序，输出与前一个不同的元素
#include<bits/stdc++.h>using namespace std;#define N 105int main(){string s[N];int n = 1;while(cin >> s[n])n++;n--;//最后一次输入的值是EOF，不是有效的值，n应该减1 sort(s+1, s+1+n); cout << s[1] << endl;for(int i = 2; i <= n; ++i)if(s[i] != s[i-1])cout << s[i] << endl; return 0;}
解法2：读入多个字符串，string类数组保存，选择排序，输出与后一个不同的元素
#include<bits/stdc++.h>using namespace std;#define N 105int main(){string s[N];int n = 1;while(cin >> s[n])n++;n--;//最后一次输入的值是EOF，不是有效的值，n应该减1 for(int i = 1; i <= n-1; ++i)//选择排序 for(int j = i+1; j <= n; ++j)if(s[j] < s[i])swap(s[j], s[i]);for(int i = 1; i < n; ++i)if(s[i] != s[i+1])cout << s[i] << endl;cout << s[n] << endl; return 0;}
解法3：读入整句后解析，二维字符数组保存，插入排序，用字符数组记录上一次输出的字符串
#include<bits/stdc++.h>using namespace std;int main(){char words[105][55], tword[55], temp[55];//二维数组保存多个单词 int ti = 0, wi = 0;//t_i:tword中的下标 w_i:words中的下标 char s[10005];cin.getline(s, 10005);int len = strlen(s);for(int i = 0; i <= len; ++i)//解析整个字符串 {if(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z')//如果是字母 words[wi][ti++] = s[i];//wi单词添加字母s[i] else//如果是空格或'\0' {if(ti == 0)//如果没有添加字母，那么可能是遇到连续的空格，不添加单词 continue;words[wi++][ti] = '\0';//把words[wi]构成一个字符串ti = 0;for(int j = wi-1; j >= 1; --j)//插入排序 {if(strcmp(words[j], words[j-1]) < 0)//如果右面单词的比左面的小 {//交换两个字符串 strcpy(temp, words[j]);strcpy(words[j], words[j-1]);strcpy(words[j-1], temp);}elsebreak;}}}strcpy(temp, "");//用temp保存上一个取到的单词 for(int i = 0; i < wi; ++i){if(strcmp(words[i], temp) != 0){cout << words[i] << endl;strcpy(temp, words[i]);}}return 0;}
