1679: 树-哈夫曼编码
金币值：2
定数：10
时间限制：1.000 s
内存限制：128 M
正确：5
提交：5
正确率：100.00% 命题人：
题目描述
某通信系统传输的信息由若干字符组成，为了达到传输时间最短的要求，需要根据每一个字符出现的频率进行编码，然后进行传输。根据该通信系统的要求，依据哈夫曼树构造算法设计对应的哈夫曼编码（提示：构造哈夫曼树时从上到下找到两个最小的权值，权值小的存放在左子树，权值大的存放在右子树，如果出现权值相等的两个数则下标小的存放在左子树，否则存放在右子树；编码约定向左为0向右为1）。参考代码中的select函数功能为在哈夫曼树T的1-end位置之间找到权值最小的位置s1，权值次小的位置s2；Huffman函数功能为由n个给定的频率值构造哈夫曼树T；HuffmanCoding函数的功能为依据构造的哈夫曼树T设计对应的哈夫曼编码。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
double weight; //频率值
int parent,lchild,rchild;
} node,*Huffmantree;
typedef char** Huffmancode;//动态分配数组存储哈夫曼编码表
void select(Huffmantree T, int end, int &s1, int &s2); //在哈夫曼树T的顺序存储结构中，在1-end位置之间，找到权值最小的位置s1，权值次小的位置s2
void Huffman(Huffmantree &T,int n); //由n个频率值构造哈夫曼树T ，T存储结构中的0号单元不使用
void HuffmanCoding(Huffmantree T,Huffmancode &HC,int n); //对n个频率值（对应的字符）进行编码，存储在哈夫曼编码表HC中，HC的0号单元不使用
int main() {
int n,i;
Huffmantree T;
Huffmancode HC;
scanf("%d",&n);
Huffman(T,n);
HuffmanCoding(T,HC,n);
for(i=1; i<=n; i++)
printf("%s\n",HC[i]);
return 0;
}
void select(Huffmantree T, int end, int &s1, int &s2) {
double min1=1.0, min2=1.0;//min1为最小值，min2为次小值。任何字符的频率均小于1.0，min1,min2初值设定为1.0
int i ;
for(i=1; i<=end; i++)
if(T[i].weight<min1 && T[i].parent==0) {
min2 = min1;
min1 = T[i].weight;
s2 = s1;
s1 = i;
} else if(T[i].weight<min2 && T[i].parent==0) {
min2 = T[i].weight;
s2 = i;
}
}
/*仅提交以下代码*/
void Huffman(Huffmantree &T,int n) {
}
void HuffmanCoding(Huffmantree T,Huffmancode &HC,int n) {
} 输入格式
第 1 行输入一个整数表示通信系统中出现的字符个数n(n<=20)
第 2 行输入n个实数，表示各个字符出现的概率（要求这些实数之和为1）
输出格式
输出每个字符的编号，共n行
输入样例 复制
4
0.1 0.21 0.33 0.36输出样例 复制
100
101
11
0提示
1. 构造哈夫曼树采用的是贪心算法，即每次从集合中选择没有双亲的两个最小值的权重并以此构造一个新的二叉树并插入到集合中。
2. 构造哈夫曼树中每个叶子结点的编码方法是分别从叶子结点开始向上查找根结点，得到的分支结点上值的序列正好与所求的对应编号相反。
样例中构造出来的哈夫曼表如下：
void Huffman(Huffmantree &T,int n) {
int i,m;
m=2*n-1;
T=new node[m+1]; //0号单元不用
for(i=1; i<=m; i++) {
__________________
}
for(i=1; i<=n; i++) {
__________________
}
for(i=n+1; i<=m; i++) {
_________________________
}
}
void HuffmanCoding(Huffmantree T,Huffmancode &HC,int n) {
HC=new char*[n+1]; //0号单元不用
char *cd=new char[n];
for(int i=1; i<=n; i++) {
____________________
while(f!=0) {
_____________________
}
_____________________
}
}
求每个叶子结点的编码，需要从叶子结点开始向上找到根结点。如果是双亲结点的左孩子，则为0，否则为1。样例中构造出来的哈夫曼表如下：
0.10 0 0 5 0.21 0 0 5 0.33 0 0 6 0.36 0 0 7 0.31 1 2 6 0.64 5 3 7 1.00 4 6 0