题目描述 给定n个字符的权值(权值均是大于0的正整数)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。 注意：在构造赫夫曼树HT时，序号小的权值放在左边，不是权值小的放左边！（序号：与权值输入的顺序相对应，序号由小到大） 输入 先输入权值的个数n（n>1）。 然后依次输入n个权值（权值均是大于0的正整数） 输出 与输入的n个权值相对应，依次输出对应的编码。 编码时，左孩子分支编码为0，右孩子分支编码为1。 样例输入 Copy 8 5 29 7 8 14 23 3 11 样例输出 Copy 0110 10 1110 1111 110 00 0111 010
#include<stdio.h> #include<string.h> #define maxsize 100000 struct fff { int start; int len[maxsize]; int weight; }code[100],cd; struct tree { int weight; int parent; int lchild; int rchild; }T[100]; int a[300]; int main() { int n,k,i,j,m,m1,m2,x1,x2,pare,child; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&k); T[i].weight=k; T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; } m=2*n-1; for(i=n;i<m;i++) { T[i].lchild=-1; T[i].rchild=-1; T[i].parent=-1; T[i].weight=0; } for(i=0;i<n-1;i++) { m1=m2=1000000000;//记录权值 x1=x2=0;//记录 节点所在位置 for(j=0;j<n+i;j++) { if(T[j].weight<m1&&T[j].parent==-1) { m2=m1; x2=x1; m1=T[j].weight; x1=j; } else if(T[j].weight<m2&&T[j].parent==-1) { m2=T[j].weight; x2=j; } } T[x1].parent=n+i; T[x2].parent=n+i; T[n+i].weight=T[x1].weight+T[x2].weight; if(x1<x2) { T[n+i].lchild=x1; T[n+i].rchild=x2; } else { T[n+i].lchild=x2; T[n+i].rchild=x1; } } for(i=0;i<n;i++) { cd.start=n-1; child=i; pare=T[child].parent; while(pare!=-1) { if(T[pare].lchild==child) cd.len[cd.start]=0; else cd.len[cd.start]=1; cd.start--; child=pare; pare=T[child].parent; } for(j=cd.start+1;j<n;j++) { code[i].len[j]=cd.len[j]; } code[i].start=cd.start+1; code[i].weight=T[i].weight; } for(i=0;i<n;i++) { for (j=code[i].start; j < n; j++) { printf ("%d", code[i].len[j]); } printf("\n"); } return 0; }