【題目鏈接】

ybt 2048：【例5.18】串排序

【題目考點】

1. 多字符串處理

• 方法1：string類對象數組
  設string類對象數組s，s[i]保存第i個字符串。s[i]是string類對象。

string s[105];//s[i]保存第i個字符串 int n; cin >> n; for(int i = 1; i <= n; ++i)cin >> s[i];

• 方法2：二維數組
  設二維數組s，s[i]保存第i個字符串。s[i]是char*類型指針常量，是一維字符數組。缺點是指針不可改變。
  例：輸入n，輸入n個字符串

char s[105][105];//s[i]保存第i個字符串 int n; cin >> n; for(int i = 1; i <= n; ++i)cin >> s[i];

• 方法3：指針數組
  設指針數組s，s[i]保存第i個字符串。s[i]是char*類型指針變量，指向一維字符數組。
  使用前需要動態申請內存空間。優點是指針值可以改變。

char *s[105];//s[i]保存第i個字符串 int n; cin >> n; for(int i = 1; i <= n; ++i) {s[i] = new int[105];//申請完記得釋放cin >> s[i]; }

2. 排序

本題考查重點不是排序，隨便選一種基本排序方法就好，或者用sort函數進行排序。
sort函數使用可以讀者自行搜索。這里不做過多介紹。

3. 字符串比較

基于字典序比較：遍歷兩個字符串，對應位置字符進行比較

• 如果發現字符不同，哪個字符的ASCII碼大，那個字符所在的字符串就更大
• 如果字符相同，看下一個字符
• 如果一個字符串遍歷完了，另一個字符串沒遍歷完，那么更長的字符串更大。
• 如果兩個字符串同時遍歷完，那么兩字符串相同

字符數組比較：strcmp(s1, s2)，其中s1， s2是字符數組

• 如果s1比s2小，即s1字典序在s2前，返回 -1
• 如果s1比s2大，即s1字典序在s2后面，返回1
• 如果s1與s2相同，返回0

string類對象比較：>, <, >=, <=, ==, !=
string類對象重載了各種關系運算符，可以用關系運算符直接比較

【解題思路】

存儲結構可以選擇：string類數組，指針數組，二維數組
排序方法可以有多種選擇，大體分為：手寫排序、調用stl排序函數（如sort函數）
以下給出幾種方法示例

【題解代碼】

解法1：string類+sort函數

#include<bits/stdc++.h> using namespace std; int main() {string s[25];//string類數組 int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> s[i];sort(s+1, s+1+n);//默認升序 比較時使用string類重載的<運算符 for(int i = 1; i <= n; ++i)cout << s[i] << endl;return 0; }

解法2：string類數組+選擇排序

#include<bits/stdc++.h> using namespace std; int main() {string s[25];int n;cin >> n;for(int i = 1; i <= n; ++i)cin >> s[i];for(int i = 1; i <= n - 1; ++i)//選擇排序{int m = i;//找從i+1~n最小值下標 for(int j = i + 1; j <= n; ++j){if(s[j] < s[m])m = j;}swap(s[m], s[i]);}for(int i = 1; i <= n; ++i)cout << s[i] << endl;return 0; }

解法3：指針數組+冒泡排序

#include<bits/stdc++.h> using namespace std; int main() {char *s[25];//指針數組 int n;cin >> n;for(int i = 1; i <= n; ++i){s[i] = new char[25];//動態內存申請 cin >> s[i];}for(int i = 1; i <= n-1; ++i)for(int j = 1; j <= n-i; ++j){if(strcmp(s[j], s[j+1]) > 0)//或寫為==1 swap(s[j], s[j+1]);//s[j]和s[j+1]是char*類型指針變量，可以交換 }for(int i = 1; i <= n; ++i){cout << s[i] << endl; delete s[i];//動態申請的內存要釋放，雖然程序運行完了也能釋放，但要養成這種手動釋放的習慣。以防工作后寫出使內存泄露的程序。 }return 0; }

解法4：二維數組+索引數組+插入排序

#include<bits/stdc++.h> using namespace std; int main() {char s[25][25]; int n, ind[25];//s[ind[i]]：索引數組，排序后第i個元素 cin >> n;for(int i = 1; i <= n; ++i){cin >> s[i];ind[i] = i;}for(int i = 2; i <= n; ++i)//把第幾個元素插入有序序列 for(int j = i; j >= 2; --j){if(strcmp(s[ind[j]], s[ind[j-1]]) < 0)//排序后數組第j元素小于排序后第j-1元素 swap(ind[j], ind[j-1]);elsebreak;}for(int i = 1; i <= n; ++i)cout << s[ind[i]] << endl;return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 2048：【例5.18】串排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。