// huffman编码.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdio.h"
#define N 50             //叶子结点数
#define M 2*N-1            //树中结点总数

typedef struct
{
    char data;            //结点值
    double weight;       //权值
    int parent;            //双亲结点
    int lchild;            //左孩子结点
    int rchild;            //右孩子结点
} HTNode;
typedef struct
{
    char cd[N];            //存放哈夫曼码
    int start;
} HCode;

//建立Huffman树
void CreateHT(HTNode ht[],int n)
{
    int i,k,lnode,rnode;
    double min1,min2;
    for (i=0;i<2*n-1;i++)                 //所有结点的相关域置初值-1
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
    for (i=n;i<2*n-1;i++){                //构造哈夫曼树
        min1=min2=33267;                 //lnode和rnode为最小权重的两个结点位置
        lnode=rnode=-1;
        for (k=0;k<=i-1;k++)
            if (ht[k].parent==-1)       //只在尚未构造二叉树的结点中查找
            {
                if (ht[k].weight<min1){
                    min2=min1;
                    rnode=lnode;
                    min1=ht[k].weight;
                    lnode=k;
                }
                else if (ht[k].weight<min2){
                    min2=ht[k].weight;
                    rnode=k;
                }
            }
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;
        ht[i].lchild=lnode;
        ht[i].rchild=rnode;
        ht[lnode].parent=i;
        ht[rnode].parent=i;
    }
}


void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,f,c;
    HCode hc;
    for (i=0;i<n;i++){             //根据哈夫曼树求哈夫曼编码
        hc.start=n;c=i;
        f=ht[i].parent;
        while (f!=-1){           //循序直到树根结点
            if (ht[f].lchild==c)         //处理左孩子结点
                hc.cd[hc.start--]='0';
            else                        //处理右孩子结点
                hc.cd[hc.start--]='1';
            c=f;
            f=ht[f].parent;
        }
        hc.start++;                 //start指向哈夫曼编码最开始字符
        hcd[i]=hc;
    }
}

//输出哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,k;
    double sum=0,m=0;
    int j;
    printf("输出哈夫曼编码:\n");      
    for (i=0;i<n;i++){
        j=0;
        printf("   %c:",ht[i].data);
        for (k=hcd[i].start;k<=n;k++){
            printf("%c",hcd[i].cd[k]);
            j++;
        }
        m+=ht[i].weight;
        sum+=ht[i].weight*j;
        printf("\n");
    }
}

int main(int argc, char* argv[])
{
    int n=9,i;                     //n表示初始字符串的个数
    char str[]={'A','S','D','F','G','H','J','K','L'};      //数据
    double fnum[]={1,2,3,4,5,6,7,8,9};                 //权值
    HTNode ht[M];
    HCode hcd[N];
    for (i=0;i<n;i++)    {
        ht[i].data=str[i];
        ht[i].weight=fnum[i];
    }
    CreateHT(ht,n);
    CreateHCode(ht,hcd,n);
    DispHCode(ht,hcd,n);
    printf("\n");
}