题目描述
分析
霍夫曼编码的应用。
本题没有必要构造一棵完整的霍夫曼树。只需利用霍夫曼编码的原理，每次挑选频率最低的两个元素进行合并。（显然，可以利用优先级队列，这里用数组来模拟）
源码
//每次挑出现频率最小的两个元素，应该用优先级队列！！！！！！！！！！ #include <stdio.h>
#include <limits.h>
#include <string.h>
int unionFre(int fre[26]); int main()
{
int frequency[26]; //记录每个字母出现的频率
int n;
int m;
char input[10000];
int letterNum; //出现的小写字母的个数
int len;
int result;
int i, j; scanf("%d", &n);
while (n --)
{
scanf("%d", &m);
scanf("%s", &input);
//初始化
memset(frequency, 0, sizeof(frequency)); //统计每个字母出现的次数
len = strlen(input);
for (i = 0; i < len; i ++)
{
frequency[input[i]-'a'] ++;
}
//没出现的字母频率均设为最大值
letterNum = 26;
for (i = 0; i < 26; i ++)
{
if (frequency[i] == 0)
{
letterNum --;
frequency[i] = INT_MAX;
}
} //如果字符串只由一个字母组成
if (letterNum == 1)
{
result = frequency[input[0]-97];
if (result <= m)
printf("yes\n");
else
printf("no\n"); continue;
} //循环(letterNum-1)次，每次挑选出现频率最低的两个元素进行合并
//并更新result值，加上被合并的两个元素的频率和
result = 0;
for (i = 0; i < letterNum-1; i ++)
{
result = result + unionFre(frequency);
} if (result <= m)
printf("yes\n");
else
printf("no\n");
} return 0;
} //合并函数
int unionFre(int fre[26])
{
int min, secondMin;
int minIndex, secondMinIndex;
int temp;
int i; min = fre[0];
minIndex = 0;
secondMin = fre[1];
secondMinIndex = 1; if (min > secondMin)
{
temp = min;
min = secondMin;
secondMin = temp; temp = minIndex;
minIndex = secondMinIndex;
secondMinIndex = temp;
} //找出频率最低的两个元素
for (i = 2; i < 26; i ++)
{
if (fre[i] < min)
{
secondMin = min;
secondMinIndex = minIndex; min = fre[i];
minIndex = i;
}
else if (fre[i] < secondMin)
{
secondMin = fre[i];
secondMinIndex = i;
}
} //合并两个元素
fre[minIndex] = min + secondMin;
fre[secondMinIndex] = INT_MAX; return (min + secondMin);
}