[编程题]字串的连接最长路径查找

矫情吗；* 2022-07-14 12:28 63阅读 0赞

> Talk is cheap, show me the code.

### 一、问题描述 ###

给定n个字符串，请对n个字符串按照字典序排列。

**输入描述：**

> 输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长度≤100),字符串中只含有大小写字母。

**输出描述：**

> 数据输出n行，输出结果为按照字典序排列的字符串。

**输入例子：**

9
    cap
    to
    cat
    card
    two
    too
    up
    boat
    boot

**输出例子：**

boat
    boot
    cap
    card
    cat
    to
    too
    two
    up

### 二、问题分析 ###

按照字典序排序，set默认是按字典序排列的，但是set中不允许重复，所以不能采用set来处理，那么可以用vector、list或者deque来存放string，排序可以自定义方法，也可以采用标准库中的方法。

**解题方式1：**

采用标准库算法中的sort来进行排序。

#include <iostream>
    #include <vector>
    #include <iterator>
    #include <string>
    #include <algorithm>
    using namespace std;
    
    int main()
    {
        int num;
        while (cin >> num)
        {
            vector<string> vect;
            string s;
            while (num--)
            {
                cin >> s;
                vect.push_back(s);
            }
            sort(vect.begin(),vect.end());
            for (vector<string>::iterator it = vect.begin(); it != vect.end(); ++it)
            {
                cout << *it << endl;
            }
        }
        return 0;
    }

**解题方式2：**

自定义排序方法。

#include <iostream>
    #include <vector>
    #include <string>
    #include <iterator>
    using namespace std;
    
    typedef vector<string>::iterator strIterator;
    
    void bubbleSort(strIterator beg, strIterator end)
    {
        for (vector<string>::size_type i = 0; i < end - beg - 1; i++)
        {
            for (strIterator it = beg; it != end - i - 1; ++it)
            {
                if ( *it > *(it + 1))
                {
                    string temp = *it;
                    *it = *(it + 1);
                    *(it + 1) = temp;
                }
            }
        }
    }
    
    int main()
    {
        int num;
        while (cin >> num)
        {
            string s;
            vector<string> vect;
            while (num--)
            {
                cin >> s;
                vect.push_back(s);
            }
            bubbleSort(vect.begin(), vect.end());
            for (strIterator it = vect.begin(); it != vect.end(); ++it)
            {
                cout << *it << endl;
            }
        }
    
        return 0;
    }