#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<conio.h>
typedef struct
{
    unsigned int weight;//用来存放各个结点的权值
    unsigned int parent,lchild,rchild;//指向双亲、孩子结点的指针
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表
//1.选择权值最小的两个结点
void Select(HuffmanTree &HT,int m,int *s1,int *s2)
{
    int i,min;
    for(i=1;i<=m;i++)
    {
        if(HT[i].parent==0)
        {
            min=i;i=m+1;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(HT[i].parent==0)
        {
            if(HT[i].weight<HT[min].weight)
                min=i;
        }
    }
    *s1=min;
    for(i=1;i<=m;i++)
    {
        if(HT[i].parent==0&&i!=(*s1))
        {
            min=i;i=m+1;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(HT[i].parent==0 && i!=(*s1))
        {
            if(HT[i].weight<HT[min].weight)
                min=i;
        }
    }
    *s2 = min;
}//select
//2.构造哈夫曼编码
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w,int n)
{//根据赫夫曼树HT求赫夫曼编码表HC
    int i,j,m,s1,s2,start;
    char *cd;
    unsigned int c,f;
    if(n<=1) return;
    m=2*n-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    for(i=1;i<=n;i++)
    {
        HT[i].weight=w[i];
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(i=n+1;i<=m;i++)
    {
        HT[i].weight=0;
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    printf("\n哈夫曼树的构造过程如下图所示:\n");
    printf("HT初态:\n 结点 weight parent lchild rchild");
    for(i=1;i<=m;i++)
        printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,    HT[i].lchild,HT[i].rchild);
    printf("   按任意键，继续……");
    getch();
    //建造哈夫曼HT
    for(i=n+1;i<=m;i++)
    {
        Select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;HT[s2].parent=i;
        HT[i].lchild=s1;HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
        printf("\nselect:s1=%d s2=%d\n",s1,s2);
        printf("结点 weight parent lchild rchild");
        for(j=1;j<=i;j++)
            printf("\n%4d%8d%8d%8d%8d",j,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
        printf("   按任意键，继续……");
        getch();
    }
    printf("\n%d个字符的哈夫曼编码如下:\n",n);
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    cd=(char*)malloc(n*sizeof(char));
    cd[n-1]='\0';
    for(i=1;i<=n;++i)
    {
        start=n-1;
        for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
            if(HT[f].lchild==c)cd[--start]='0';
            else cd[--start]='1';
            HC[i]=(char*)malloc((n-start)*sizeof(char));
            strcpy(HC[i],&cd[start]);
    }
    free(cd);
    for(i=1;i<=n;i++)
        printf("<%2d>编码:%s\n",HT[i].weight,HC[i]);
}//HuffmanCoding
//3.主函数
void main()
{
    HuffmanTree myHuffmanTree;
    HuffmanCode myHuffmanCode;
    int *w,i;
    int n,wei;
    printf("请输入需要哈夫曼编码的字符个数:");
    scanf("%d",&n);
    w=(int*)malloc((n+1)*sizeof(int));
    for(i=1;i<=n;i++)
    {
        printf("请输入第%d字符的权值:",i);
        fflush(stdin);
        scanf("%d",&wei);
        w[i]=wei;
    }
    HuffmanCoding(myHuffmanTree,myHuffmanCode,w,n);
}