2625: 贪心算法-哈夫曼树
金币值：3
定数：8
时间限制：1.000 s
内存限制：128 M
正确：3
提交：5
正确率：60.00% 命题人：
题目描述
某通信系统传输的信息由若干字符组成，为了达到传输时间最短的要求，需要根据每一个字符出现的频率进行编码，然后进行传输。根据该通信系统的要求，依据哈夫曼树构造算法设计对应的哈夫曼编码（提示：构造哈夫曼树时从上到下找到两个最小的权值，权值小的存放在左子树，权值大的存放在右子树，如果出现权值相等的两个数则下标小的存放在左子树，否则存放在右子树）。参考代码中的select函数功能为在哈夫曼树T的1-end位置之间找到权值最小的位置s1，权值次小的位置s2；Huffman函数功能为由n个给定的频率值构造哈夫曼树T。
测试代码 复制
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct {
double weight; //频率值
int parent,lchild,rchild;
} Node,*Huffmantree;
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 output(Huffmantree &T,int n);
int main(void) {
int n,i;
Huffmantree T;
scanf("%d",&n);
Huffman(T,n);
output(T,n);
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) {
int i,m=2*n-1;
T=new Node[m+1];
for(i=1; i<=m; i++) {
T[i].parent=T[i].lchild=T[i].rchild=0; //初始化
}
for(i=1; i<=n; i++) {
————————————————————————————————————
}
for(i=n+1; i<=m; i++) {
————————————————————————————————————
}
}
void output(Huffmantree &T,int n){
int i;
for(i=1; i<=2*n-1; i++){
printf("%.2lf %4d %4d %4d\n",T[i].weight,T[i].lchild,T[i].rchild,T[i].parent);
}
}输入格式
第 1 行输入一个整数表示通信系统中出现的字符个数n(n<=20)
第 2 行输入n个实数，表示各个字符出现的概率（要求这些实数之和为1）
第 2 行输入n个实数，表示各个字符出现的概率（要求这些实数之和为1）
输出格式
从编号1开始依次输出哈夫曼树中每个结点的信息（权值，左孩子编号，右孩子编号，双亲编号），共2n-1行。假设根结点的双亲编号为0。
输入样例 复制
4
0.1 0.21 0.33 0.36输出样例 复制
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