#include <stdio.h>

#define max 500//定义存储的最大结点数

typedef struct //定义结点

{

               char data;//结点值

               int weight;//权重

               int parent;//父结点

               int left;//左孩子结点

               int right;//右孩子结点

}huffnode;

typedef struct

{

               char cd[max];

               int start;

}huffcode;

char elem[1000];

char input[1000];

int weight[1000]={0};

int m=0;

int find_char(char a[],char c,int n)//在数组中查找某一个元素，返回其位置

{

               int i;

               for(i=0;i<=n;i++)

               {

                               if(a[i]==c) return i;

               }

               return -1;

}

int get_elem_weight()

//从输入中得到除空格和回车之外的所有字符类型及其权值

{

               int i,n=-1;

               for(i=0;i<100;i++)

    elem[i]=' ';

               char c;

               while(1)

               {

                               c=getchar();

                               input[m++]=c;

                               if(c==10) break;

                               else if(c!=' ')

                               {

                                              if(find_char(elem,c,n)==-1)

                                              {   n++;

                                                             elem[n]=c;

                                                             weight[n]=1;

                                              }

                                              else weight[find_char(elem,c,n)]+=1;

                               }

               }

               printf("除空格和回车之外各字符的出现频率如下：\n");

//打印字符极其权值

               for(i=0;i<=n;i++)

               {

                               printf("%c %d",elem[i],weight[i]);

                               printf("\n");

               }

               return n+1;

}

main()

{

               huffnode ht[2*max];

               huffcode htd[max],d;

               int i,k,f,l,r,n,c,m1,m2,j;

               printf("请输入一个字符串，以回车结束\n");

               n=get_elem_weight();

               for(i=1;i<=n;i++)

               {

                               ht[i].data =elem[i-1];

                               ht[i].weight =weight[i-1];

               }

               for(i=1;i<=2*n-1;i++)

                               ht[i].parent =ht[i].left =ht[i].right =0;//叶结点初始化

               for(i=n+1;i<=2*n-1;i++)

               {

                               m1=m2=32767;

                               l=r=0;

                               for(k=1;k<=i-1;k++)

                                              if(ht[k].parent ==0)

                                              //寻找当前结点中权值最小的两个结点

                                                             if(ht[k].weight <m1)

                                                             {

                                                                            m2=m1;

                                                                            r=l;

                                                                             m1=ht[k].weight ;

                                                                            l=k;

                                                             }

                                                             else if(ht[k].weight <m2)

                                                             {

                                                                            m2=ht[k].weight ;

                                                                            r=k;

                                                             }

                                                             ht[l].parent =i;//建立父结点信息

                                                             ht[r].parent =i;

                                                             ht[i].weight =ht[l].weight +ht[r].weight ;

                                                             ht[i].left =l;

                                                             ht[i].right =r;

               }

               for(i=1;i<=n;i++)//由建立的结点生成Huffman编码

               {

                               d.start =n+1;

                               c=i;

                               f=ht[i].parent ;

                               while(f!=0)

                               {

                                              if(ht[f].left ==c)

                                                             d.cd[--d.start ]='0';

                                              else

                                                             d.cd [--d.start ]='1';

                                              c=f;

                                              f=ht[f].parent ;

                               }

                               htd[i]=d;

               }

               printf("输出编码\n");

               for(i=1;i<=n;i++)

               {

                               printf("%c:",ht[i].data );

                               for(k=htd[i].start ;k<=n;k++)

                                              printf("%c",htd[i].cd[k]);

                               printf("\n");

               }

               printf("你所输入的字符串为\n");

               for(i=0;i<m-1;i++) printf("%c",input[i]);

               printf("\n");

               printf("经过编码之后\n");//打印编码后结果

               for(i=0;i<m-1;i++)

               {

                  if(input[i]!=' ')

                  {

                                 for(k=1;k<=n;k++)

                                                if(ht[k].data ==input[i]) break;

                                                for(j=htd[k].start ;j<=n;j++)

                                                                printf("%c",htd[k].cd [j]);

                  }

                  else printf("%c",input[i]);

               }

    printf("\n");

}