4034 - 哈夫曼编码
时间限制 : 1 秒
内存限制 : 128 MB
给定一个文本中n个字符的出现频率。设计n个字符的哈夫曼编码。
题目输入
输入包括多组数据。每组数据的第一行是一个整数n(1 <= n <= 100)，代表不同字符的总数，n = 0意味着输入结束；接下来有n行，其中的每一行包含一个字符及其出现频率。
题目输出
对每组数据，输出哈夫曼编码的平均位数，即l1 * f1 + l2 * f2 + ... + ln * fn，其中li是第i个字符的哈夫曼编码的位数，fi是第i个字符出现的频率。
输入/输出样例
输入格式
5 A 35 B 10 C 20 D 20 _ 15 3 x 20 Y 50 Z 5 0
输出格式
225 100
C语言解答
#include <stdio.h> #include <stdlib.h> typedef struct node { char symbol; int freq; int parent; int tag; }NODE; int main() { NODE* tree; int i,j; int n; int min; int index1,index2; int depth; char ch; int sum; scanf("%d",&n); while(n>=1) { tree=(NODE*)malloc((2*n-1)*sizeof(NODE)); for(i=0;i<n;i++) { scanf("%c%c%d",&ch,&tree[i].symbol,&tree[i].freq); tree[i].parent=-1; tree[i].tag=0; } for(i=n;i<2*n-1;i++) { min=RAND_MAX; for(j=0;j<i;j++) { if(tree[j].tag==0&&tree[j].freq<min) { min=tree[j].freq; index1=j; } } tree[index1].tag=1; min=RAND_MAX; for(j=0;j<i;j++) { if(tree[j].tag==0&&tree[j].freq<min) { min=tree[j].freq; index2=j; } } tree[index2].tag=1; tree[i].freq=tree[index1].freq+tree[index2].freq; tree[i].parent=-1; tree[i].tag=0; tree[index1].parent=i; tree[index2].parent=i; } sum=0; for(i=0;i<n;i++) { depth=0; j=i; while(tree[j].parent!=-1) { j=tree[j].parent; depth++; } sum+=depth*tree[i].freq; } printf("%d\n",sum); scanf("%d",&n); } }
C++解答
#include <stdio.h> #include <stdlib.h> typedef struct node { char symbol; int freq; int parent; int tag; }NODE; int main() { NODE* tree; int i,j; int n; int min; int index1,index2; int depth; char ch; int sum; scanf("%d",&n); while(n>=1) { tree=(NODE*)malloc((2*n-1)*sizeof(NODE)); for(i=0;i<n;i++) { scanf("%c%c%d",&ch,&tree[i].symbol,&tree[i].freq); tree[i].parent=-1; tree[i].tag=0; } for(i=n;i<2*n-1;i++) { min=RAND_MAX; for(j=0;j<i;j++) { if(tree[j].tag==0&&tree[j].freq<min) { min=tree[j].freq; index1=j; } } tree[index1].tag=1; min=RAND_MAX; for(j=0;j<i;j++) { if(tree[j].tag==0&&tree[j].freq<min) { min=tree[j].freq; index2=j; } } tree[index2].tag=1; tree[i].freq=tree[index1].freq+tree[index2].freq; tree[i].parent=-1; tree[i].tag=0; tree[index1].parent=i; tree[index2].parent=i; } sum=0; for(i=0;i<n;i++) { depth=0; j=i; while(tree[j].parent!=-1) { j=tree[j].parent; depth++; } sum+=depth*tree[i].freq; } printf("%d\n",sum); scanf("%d",&n); } }