12.3 字典序比较

“在计算机科学中，我们经常需要比较字符串的大小，”我说道，”字典序就像查字典一样，按字母顺序比较字符串的大小关系。”

12.3.1 寻找字典序最小的字符串

题目描述： 编写程序，针对输入的N个不同的字符串（长度不超过30），输出其中字典码最小的字符串。

输入格式： 输入第一行给出正整数N；随后N行，每行给出一个长度小于80的非空字符串，其中不会出现换行符，空格，制表符。

输出格式： 输出字典码最小的字符串。

样例输入：

5
Li
Wang
Zha
Jin
Xian

样例输出：

Jin

代码实现（方法一：手动比较）：

#include<bits/stdc++.h>
using namespace std;

int main(){
    char a[35], mi[35];    // a存储当前字符串，mi存储最小字符串
    int n;
    cin >> n;
    cin >> mi;             // 读入第一个字符串作为初始最小值
    n--;                   // 还需要读入n-1个字符串
    
    while(n--){
        cin >> a;          // 读入下一个字符串
        bool f = false;    // 标记是否需要更新最小字符串
        
        // 逐字符比较两个字符串
        for(int i = 0; i < min(strlen(a), strlen(mi)); i++){
            if(a[i] != mi[i]){          // 找到第一个不同的字符
                if(a[i] < mi[i]){       // 如果a的字符更小
                    f = true;           // 需要更新最小字符串
                }
                break;                  // 跳出比较循环
            }
            // 如果比较到了较短字符串的末尾
            if(i == min(strlen(a), strlen(mi)) - 1){
                if(strlen(a) < strlen(mi)){  // 较短的字符串字典序更小
                    f = true;
                }
            }
        }
        
        // 如果需要更新，复制新的最小字符串
        if(f == true){
            for(int i = 0; i < strlen(a); i++){
                mi[i] = a[i];
            }
            mi[strlen(a)] = '';       // 添加字符串结束符
        }
    }
    
    cout << mi;            // 输出字典序最小的字符串
    return 0;
}

代码实现（方法二：使用strcmp函数）：

#include<bits/stdc++.h>
using namespace std;

int main(){
    char a[35], mi[35];    // a存储当前字符串，mi存储最小字符串
    int n;
    cin >> n;
    cin >> mi;             // 读入第一个字符串作为初始最小值
    n--;                   // 还需要读入n-1个字符串
    
    while(n--){
        cin >> a;          // 读入下一个字符串
        int k = strcmp(a, mi);    // 比较两个字符串
        if(k < 0){         // 如果a字典序更小
            strcpy(mi, a); // 复制a到mi
        }
    }
    
    cout << mi;            // 输出字典序最小的字符串
    return 0;
}

算法解析：

方法一手动实现字典序比较：逐字符比较，遇到不同字符时判断大小；如果前缀相同，较短的字符串字典序更小。

方法二使用C++标准库函数strcmp()：返回值小于0表示第一个字符串字典序更小。