此题的思路和代码都是别人的，我觉得写得比较清晰，就直接复制过来吧。
代码如下：
#include <stdio.h> #include <string.h> #define N 128 #define inf 0x7fffffff struct node { int val; //权值 int left, right, parent; }p[1000]; int f[N]; //存放每个字母权值 int len[N]; //统计编码的长度 void hufuman(int n) { int i, min1, min2, pos1, pos2, flag; for(i =0; i < n; i++) { p[i].val = f[i]; p[i].parent =-1; p[i].left =-1; p[i].right =-1; } while(1) //构建Hufuman树 { int mark1 =0, mark2 =0; min1 = min2 = inf; for(i =0; i < n; i++) //每次取最小和第二小的元素 { if(p[i].parent ==-1&& p[i].val < min1) { if(min1 != min2) { min2 = min1; pos2 = pos1; mark2 =1; } min1 = p[i].val; pos1 = i; mark1 =1; } else if(p[i].parent ==-1&& p[i].val < min2) { min2 = p[i].val; pos2 = i; mark2 =1; } } if(mark1 ==0|| mark2 ==0) //如果没有则跳出，表示已经建好Hufuman树 break; p[n].val = min1 + min2; p[pos1].parent = n; p[pos2].parent = n; p[n].left = pos1; p[n].right = pos2; p[n].parent =-1; n++; } for(i =0; i < n; i++) { if(p[i].right !=-1|| p[i].left !=-1) //如果不是原有的元素，而是后来构建出来的，则说明编码长度已经统计完 break; flag = i; len[i] =1; while(p[flag].parent !=-1) { len[i]++; //统计编码长度（这地方没有必要得出Hufuman编码，这道题用不到） flag = p[flag].parent; //跳到i的父节点，继续查找 } } return; } int main() { char str[N]; int data[N], i; while(gets(str) != NULL) { if(!strcmp(str, "END")) break; memset(data, 0, sizeof(data)); memset(f, 0, sizeof(f)); for(i =0; i < strlen(str); i++) data[(int)str[i]]++; //求出每个字母的权值 int num =0; for(i =0; i <128; i++) { if(data[i] !=0) { f[num++] = data[i]; //给每个字母编号num，并将权值存到f[] } } if(num ==1) { printf("%d %d 8.0\n",strlen(str)*8, f[0]); continue; } hufuman(num); int sum =0; for(i =0; i < num; i++) { if(len[i] !=1) sum += (len[i]-1)*f[i]; //编码总长度 = sum（每个字母所对应的编码长度 * 字母出现的次数） } printf("%d %d %.1f\n", strlen(str)*8,sum, strlen(str)*8/(float)sum); } return 0; }