2.1.1 題目?jī)?nèi)容

2.1.1-A [問(wèn)題描述]

給定n個(gè)整數(shù)，請(qǐng)統(tǒng)計(jì)出每個(gè)整數(shù)出現(xiàn)的次數(shù)，按出現(xiàn)次數(shù)從多到少的順序輸出。

2.1.1-B [基本要求]

（1）輸入格式：

　輸入的第一行包含一個(gè)整數(shù)n，表示給定數(shù)字的個(gè)數(shù)。

　第二行包含n個(gè)整數(shù)，相鄰的整數(shù)之間用一個(gè)空格分隔，表示所給定的整數(shù)。

（2）輸出格式：

輸出多行，每行包含兩個(gè)整數(shù)，分別表示一個(gè)給定的整數(shù)和它出現(xiàn)的次數(shù)。按出現(xiàn)次數(shù)遞減的順序輸出。如果兩個(gè)整數(shù)出現(xiàn)的次數(shù)一樣多，則先輸出值較小的，然后輸出值較大的。

2.1.2 算法思想

使用計(jì)數(shù)排序的思想，創(chuàng)建一個(gè)輔助數(shù)組b，用于統(tǒng)計(jì)每個(gè)整數(shù)出現(xiàn)的次數(shù)。

遍歷整數(shù)數(shù)組a，將每個(gè)整數(shù)作為索引，將輔助數(shù)組b中相應(yīng)位置的值加1，表示該整數(shù)出現(xiàn)了一次。接著，通過(guò)排序算法（這里使用的是sort函數(shù)）對(duì)整數(shù)數(shù)組a進(jìn)行排序，以便后續(xù)按照出現(xiàn)次數(shù)從多到少輸出結(jié)果。最后，通過(guò)遍歷輔助數(shù)組b，從出現(xiàn)次數(shù)最多的整數(shù)開(kāi)始，逐個(gè)輸出整數(shù)及其出現(xiàn)次數(shù)。

2.1.3?源代碼 [共50行]

#include <iostream>
#include <algorithm>
using namespace std;
typedef struct T_Sort
{int cnt;int x;
}TS;bool sort_rule(TS A, TS B)
{if (A.cnt == B.cnt)return A.x < B.x;return A.cnt > B.cnt;
}
int main()
{int n;TS T[1005];cin >> n;for (int i = 0; i <= 1000; i++){T[i].cnt = 0;T[i].x = i;}while (n--){int x;cin >> x;T[x].cnt++;}sort(T, T + 1001, sort_rule);for (int i = 0; i <= 1000; i++){if (T[i].cnt)cout << T[i].x << " " << T[i].cnt << endl;}return 0;
}

2.1.4?CSP測(cè)評(píng)結(jié)果

正確-100分。

源碼地址：GeekclubC/Course-Design-of-Data-Structure: 用C++完成的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) (github.com)