uva10008tutor_3.c

uva10008tutor_3.c

/*
這題還得用到排序，是可以不用，我會把那個方法寫在最後，但不建議用這種方法，可能會 TLE（我沒測試過），而且泛用性（適用性）很小。
不使用排序，還可以使用像 priority_queue 這種東西，但 C 的標準函式庫沒有，那是 C++ 的東西。
這題的排序還得使用到 struct 跟指標這兩個東西，所以你們看看就好，看不懂我也不知道要怎麼辦……（這是基本的東西啊，雖然還沒教到……）
*/

/*
題目要求的是
出現次數越多的英文字母要越先輸出，次數相同時，字典順序較小的英文字母先輸出。

C 中的排序函式是 stdlib.h 下的 qsort，時間複雜度是似乎是 Unspecified。
http://www.cplusplus.com/reference/cstdlib/qsort/
（這點讓人很不爽，沒給出 Worst-case 的 Time complexity，我怎麼保證我的程式不會 TLE。）
（所以寫 online judge 題目，大部分人都使用 C++，C++ 的函式庫比 C 的好太多了。C++ 的 sort 是 O(nlgn)。）
（不用 C++，又要保險的話，就只能自己寫 mergesort 了。）
在這題我們用 qsort，因為 n 才 26 而已。
*/

/*
qsort 對一個陣列排序，例如
int a[5] = {2, 4, 5, 3, 1};
qsort 之後（我們讓小的在前面，qsort 可以自訂「比較規則」），a[] 變成
{1, 2, 3, 4, 5};

但在這題，我們沒辦法直接對 cnt 排序，因為我們用 cnt 的 index 來作為英文字母的資訊，一排序完，這些資訊就會丟失。
例如：
int cnt[26] = {2, 1, 3, 0, 0, 0, ... , 0};
這代表 'A' 有 2 個； 'B' 有 1 個； 'C' 有 3 個。
排序後，cnt [] =
{0, 0, 0, ... , 0, 1, 2, 3};
變成 'X' 有 1 個，'Y' 有 2 個，'Z' 有 3 個 ？這當然是錯誤的，所以我們知道，排序時不能用 index 來紀錄英文字母的資訊。
所以我們引入 struct：
*/

struct Node_
{
    char c;
    int cnt;
};

typedef struct Node_ Node;
/*我一般喜歡這麼寫，這樣以後用到 Node 就不用打 struct Node 了。*/

int main() {
    ...
    Node data[26];
    /* 初使化 */
    for (int i=0; i<26; i++) {
        data[i].c = i + 'A';
        data[i].cnt = 0;
    }
    ...    
    while (N--) {
        ...
        /*統計出現次數：*/
        for (i=0; i<strlen(input); i++)
            if (isalpha(input[i]))
                data[input[i] - 'A'].cnt++;
    }
    ...
    return 0;
}

/*這樣我們在未排序前仍可以使用 index 作為英文字母的資訊，排序後，可以使用 c 這個 struct Node 的成員（field）來得到這個資訊。
統計完後，我們就可以來排序了，qsort 接受一個函式作為參數，這個函式的作用是自訂比較規則。
這個函式接受兩個參數，若前一個參數在排序後的結果後應該在後一個參數的前面，這個函式應該要回傳 <0 的值。
若後一個應該前一個前面，則回傳 > 0 的值。
若相等，回傳 0。
所以這個函式可以這麼寫：*/
int compare_node(const void * a, const void * b)
{
    Node* na = (Node*) a; /*強制轉型*/
    Node* nb = (Node*) b; /*強制轉型*/
    if (na->cnt > nb->cnt) /*先比出現次數*/
        return -1;
    if (na->cnt < nb->cnt)
        return +1;
    if (na->c < nb->c) /*若到這裡程式都還沒 return，代表 na->cnt = nb->cnt，所以再來比字母的字典順序。*/
        return -1;
    if (na->c > nb->c)
        return +1;
    return 0;
}

/*排序時就可以使用：*/
qsort(data, 26, sizeof(Node), compare_node);

/*之後只要輸出 data 裡 cnt 不為零的項就可以了。uva10008 就這麼簡單（這題就只是基本的 struct, sort 應用）。*/

/*補充，不用排序，也不用 struct 的方法：窮舉，
我們先得到最大的出現次數，之後我們就讓 i 從最大出現次數一個一個掃下來，掃到 1 為止，
看 A ~ Z 哪個英文字母的出現次數等於 i ，我們就輸出該英文字母及次數。這樣輸出的順序就是題目要求的順序。*/
/* 在統計完所有輸入後，並紀錄在 cnt 陣列裡 */
int max_cnt = -1;
for (i=0; i<26; i++)
    if (cnt[i] > max_cnt)
        max_cnt = cnt[i];

for (i=max; i>=1; i--)
    for (int j=0; j<26; j++)
        if (cnt[j] == i) 
            printf("%c %d\n", (j+'A'), i);

/*這種寫法，只要出題者狠一點，造出這種測資，然後時間卡緊一點（0.5秒），通常都會 TLE。
但用排序來處理這個，執行時間（扣除讀入的時間）會跟小測資時一模一樣，因為都是在對一個長度為 26 的陣列排序。
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa（10^6 個 a）
當然，這種情況也沒辦法用前面教的整行讀入來處理輸入，記憶體跟 input 陣列的長度都不夠。
得用
while (scanf("%c", &somechar) != EOF) {
    ...
}
來讀入輸入。
*/