使用取巧的方式计算Huffman树的带权路径长度WPL
发布时间
阅读量：
阅读量
计算Huffman树的带权路径长度WPL
编程背景
该编码方案在通信系统中被广泛应用，并以其 unequal length codes著称。其显著特征在于能够在编码后显著缩短信息传递所需的空间。
- 输入：第一行为需要编码的符号个数n
- 第二行至第n+1行分别给出每个符号对应的频率值
- 输出：生成相应的哈夫曼树并计算其带权路径长度WPL
- 测试用例举例：
例如，在给定一组符号及其频率分布的情况下应用该算法可以得到具体的WPL结果
思路
为了实现相应的输入输出需求, 自然想到采用最简单的线性数据结构——一维数组来处理这些问题. 由于题目只要求计算WPL, 并通过对其输入输出特征的分析可知, 因此无需考虑使用链表结构.
借鉴
通过网络上查阅资料的过程中，我发现了一个非常实用的技巧：WPL表示的是所有叶节点的带权路径长度之和；同时它也等于所有非叶子结点的权值之和。如需更详细的解释，请参考哈夫曼树的WPL值的计算一文。
程序实现
m函数：返回一维数组S中最小的数，并将其从数组中剔出
int m(){
int min, position=0;
min = S[0];
int i=0;
for(i=0; i<len; i++){
if(min > S[i]){
min = S[i];
position = i;
}
}
for(i=position; i<len-1;i++) S[i] = S[i+1];
S[(len--)-1]=0;
return min;
}main函数
int main(){
int n; int i, temp;
scanf("%d", &n);
len = n;
for(i=0; i<n; i++) scanf("\n%d", &S[i]);
while(len>1){
temp = m() + m();
WPL += temp;
S[len++] = temp;
}
printf("WPL=%d\n",WPL);
return 0;
}后记
作为一个初学编程的新手，在上开始记录自己零散的学习收获。 precedent planting, 后人乘凉. 我也要努力成为一个前人! 不要做一个只会伸手的懒虫! 欢迎大家指出我的不足! 行礼.
全部评论 (0)
还没有任何评论哟~