【解題】Tell me the frequencies!

ACM Volume C 10062 - Tell me the frequencies!


The Problem

Given a line of text you will have to find out the frequencies of the ASCII characters present in it. The given lines will contain none of the first 32 or last 128 ASCII characters. Of course lines may end with ‘\n’ and ‘\r’ but always keep those out of consideration.


The Input

Several lines of text are given as input. Each line of text is considered as a single input. Maximum length of each line is 1000.


The Output

Print the ASCII value of the ASCII characters which are present and their frequency according to the given format below. A blank line should separate each set of output. Print the ASCII characters in the ascending order of their frequencies. If two characters are present the same time print the information of the ASCII character with higher ASCII value first. Input is terminated by end of file.


Sample Input

AAABBC
122333


Sample Output

67 1
66 2
65 3

49 1
50 2
51 3


解題思考

　　在這一題中，為了方便起見，我定義了一個「紀錄字元」的結構。結構成員包含了字元的 ASCII 碼，以及字元出現的次數。

　　接著根據題意，一次讀取整行資料之後，使用 for 迴圈依序抓出每一個字元。然後使用搜尋，判斷這個字元是否(在這一行資料中)曾經出現。若是曾經出現過，則將對應此字元結構的出現次數遞增加一；若是未曾出現過，則將此字元的 ASCII 碼存入未使用的結構中，並將出現次數設定為 1。

　　在讀入所有字元之後，根據題目要求的方式作排序(下面我使用的是 C 內建函式的快速排序 qsort())，再依序將結果輸出結果，這一題就解好了。


參考解答(C++)

#include <iostream>
#include <string>

using namespace std;

// 一個紀錄字元的結構
struct character
{
    int ascii, time;
};

int compare(const void *, const void *);

int main(void)
{
    bool first = true;
    string str;

    while (getline(cin, str))
    {
        // 只有第一次進入迴圈不換行
        if (!first) { cout << endl; }
        else        { first = false; }

        int n = 0;
        character c[1000];

        for (int i = 0; i < str.size(); i++)
        {
            // 尋找這個字元是否出現過了
            bool find = false;
            for (int j = 0; j < n; j++)
            {
                if (c[j].ascii == str[i])
                {
                    // 出現累計次數 + 1
                    c[j].time++;

                    find = true;
                    break;
                }
            }

            // 仍未出現過, 新增一個結構
            if (!find)
            {
                c[n].ascii = str[i];
                c[n].time = 1;
                n++;
            }
        }

        // 使用快速排序法做優先排序
        qsort(c, n, sizeof(character), compare);

        for (int i = 0; i < n; i++)
        {
            cout << c[i].ascii << " " << c[i].time << endl;
        }
    }

#ifndef ONLINE_JUDGE
    system("pause");
#endif
}

int compare(const void *a, const void *b)
{
    int arg1 = ((character *)a)->time;
    int arg2 = ((character *)b)->time;

    // 先比對出現次數
    if (arg1 < arg2)        { return -1; }
    else if (arg1 > arg2)   { return 1; }
    else
    {
        // 再比對 ASCII 碼
        arg1 = ((character *)a)->ascii;
        arg2 = ((character *)b)->ascii;

        if (arg1 > arg2)        { return -1; }
        else if (arg1 < arg2)   { return 1; }
    }
}