PTA:哈夫曼编码
题干
只有一行,是一个字符串,由长度不超过255个字符的小写英文字母组成。
输出格式:
有若干行,每行由两部分组成:一个字母和该字母出现的频率,中间用一个空格分隔,并按频率高低排列,频率相同时则按字母的ASCII码的先后顺序排列。
输入样例:
soon
输出样例:
o 2
n 1
s 1
解题过程
#include <stdio.h>
#include <string.h>
struct CharFreq {char letter;int frequency;
};
int compare(const void *a, const void *b) {struct CharFreq *charFreqA = (struct CharFreq *)a;struct CharFreq *charFreqB = (struct CharFreq *)b;if (charFreqA->frequency != charFreqB->frequency) {return charFreqB->frequency - charFreqA->frequency;} else {return charFreqA->letter - charFreqB->letter;}
}
int main() {char input[256];scanf("%s", input);int freq[26] = {0};int len = strlen(input);for (int i = 0; i < len; ++i) {if (input[i] >= 'a' && input[i] <= 'z') {freq[input[i] - 'a']++;}}struct CharFreq charFreqs[26];for (int i = 0; i < 26; ++i) {charFreqs[i].letter = 'a' + i;charFreqs[i].frequency = freq[i];}qsort(charFreqs, 26, sizeof(struct CharFreq), compare);for (int i = 0; i < 26; ++i) {if (charFreqs[i].frequency > 0) {printf("%c %d\n", charFreqs[i].letter, charFreqs[i].frequency);}}return 0;
}