#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct
{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}CTNode;
typedef char **HuffCrret;
void select(CTNode *HT,int *h1,int *h2,int n)
{
    int i,j;
    for(i = 1;i<=n;i++)
        if(!HT[i].parent)
        {
            *h1 = i;
            break;
        }
    for(j = i+1;j<=n;j++)
        if(!HT[j].parent)
        {
            *h2 = j;
            break;
        }
    for(i =1;i<=n;i++)
    {
        if(HT[*h1].weight > HT[i].weight &&!HT[i].parent && HT[i].weight != HT[*h2].weight )
            *h1 = i;
    }
    for(j = 1;j<=n;j++)
    {
        if(HT[*h2].weight > HT[j].weight &&!HT[j].parent && HT[j].weight != HT[*h1].weight)
            *h2 = j;
    }
    if(*h1 > *h2)
    {
        int temp;
        temp = *h1;
        *h1 = *h2;
        *h2 = temp;
    }
}
void Huffman(CTNode *HT,HuffCrret *HC,int *w,int n)
{
    int i,j,m;
    int s1,s2;
    char *cd ;
    CTNode *p;
    if(n<1)
        return ;
    m = 2 * n-1;
    HT = (CTNode *)malloc(sizeof(CTNode)*(m+1));
/*    for(i =1;i<=n;i++)
    {
        HT[i].weight = w[i-1];
        HT[i].parent = 0;
        HT[i].rchild = 0;
        HT[i].lchild = 0;
    }
    for(i = n+1;i<=m;i++)
    {
        HT[i].weight = 0;
        HT[i].parent = 0;
        HT[i].rchild = 0;
        HT[i].lchild = 0;
    }   */
    for(p = HT,i =1;i<=m; p++,w++,i++)  //
        *p = {*w,0,0,0};                // 这一句为什么会报语法错误，是我的编译器问题还是电脑问题，或者语法错误。 可我曾经就是这样赋过值。


    printf("赫夫曼初态：\n");
    printf(" 节点 weight parent lchild rchild\n");
    for(i = 1;i<=m;i++)
        printf("%4d%6d%6d%6d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    for(i = n+1;i<=m;i++)
    {
        select(HT,&s1,&s2,i-1);
        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(" 节点 weight parent lchild rchild\n");
        for(j = 1;j<=i;j++)
            printf("%4d%6d%6d%6d\n",j,HT[j].weight,HT[j].parent,HT[j].lchild,HT[j].rchild);
    }
    puts("");
    int start ,f;
    unsigned int c = 0;
    *HC = (HuffCrret)malloc(sizeof(char*) * (n+1));
    cd = (char *)malloc(sizeof(char) * n);
    if(!cd)
        exit(1) ;
    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(sizeof(char)*(n-start));
        strcpy((*HC)[i],&cd[start]);
    }
    free(cd);
}
void main(void)
{
    CTNode *HT = NULL;
    HuffCrret HC;
//    int (*Q)[4];
//    Q[4][4]
    int *w = NULL;
    int n = 0;
    int i = 0;
    printf("程序开始~~~!!\n");
    printf("请输入赫夫曼树的节点个数:");
    scanf("%d",&n);
    printf("\n请输入%d的权值:",n);
    w = (int *)malloc(sizeof(int)*n);
    for(i =0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    Huffman(HT,&HC,w,n);
    printf("\n 编号 权值 编码");
    for(i =1;i<=n;i++)
    {
        printf("\n%2d%6d%6s",i,w[i-1],HC[i]);
    }
    puts("");
    free(HC);
    free(HT);
}