哈夫曼树和哈夫曼编码

【实例简介】

简单的哈夫曼树和哈夫曼编码

【核心代码】

#include <stdio.h>
#define MAXVALUE 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2-1
#define MAXBIT 10
typedef struct
{
    int bit[MAXBIT];
    int start;
} HCodeType;
typedef struct
{
    char data;
    int weight;
    int parent;
    int lchild;
    int rchild;
} HNodeType;
//哈夫曼树的构造方法
void HuffmanTree(HNodeType HuffNode[],int *hn)
{
    int i,j,m1,m2,x1,x2,n;
    scanf("%d",&n);
    getchar();
    for(i=0; i<2*n-1; i )
    {
        HuffNode[i].data='0';
        HuffNode[i].weight=0;
        HuffNode[i].parent=-1;
        HuffNode[i].lchild=-1;
        HuffNode[i].rchild=-1;
    }
    //printf("HuffNode:\n");
    for(i=0; i<n; i )
    {
        scanf("%c,%d",&HuffNode[i].data,&HuffNode[i].weight);
        getchar();
    }
    for(i=0; i<n-1; i )
    {
        m1=m2=MAXVALUE;
        x1=x2=0;
        for(j=0; j<n i; j )
        {
            if(HuffNode[j].weight<m1&&HuffNode[j].parent==-1)
            {
                m2=m1;
                x2=x1;
                m1=HuffNode[j].weight;
                x1=j;
            }
            else if(HuffNode[j].weight<m2&&HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        }
        HuffNode[x1].parent=n i;
        HuffNode[x2].parent=n i;
        HuffNode[n i].weight=HuffNode[x1].weight HuffNode[x2].weight;
        HuffNode[n i].lchild=x1;
        HuffNode[n i].rchild=x2;

    }
    *hn=n;
}
//生成哈夫曼编码
void HuffmanCode(HNodeType HuffNode[],HCodeType HuffCode[],int n)
{
    HCodeType cd;
    int i,j,c,p;
    for(i=0;i<n;i )
    {
        cd.start=n-1;
        c=i;
        p=HuffNode[c].parent;
        while(p!=-1)
        {
            if(HuffNode[p].lchild==c)
                cd.bit[cd.start]=0;
            else
                cd.bit[cd.start]=1;
            cd.start--;
            c=p;
            p=HuffNode[c].parent;
        }
        for(j=cd.start 1;j<n;j )
            HuffCode[i].bit[j]=cd.bit[j];
        HuffCode[i].start=cd.start;

    }
    printf("HuffCode:\n");
    for(i=0;i<n;i )
    {
        printf("%c:",HuffNode[i].data);
        for(j=HuffCode[i].start 1;j<n;j )
            printf("%d",HuffCode[i].bit[j]);
        printf("\n");
    }
}
int main()
{
    HNodeType HuffNode[MAXNODE];
    HCodeType HuffCode[MAXLEAF];
    int n,i;
    HuffmanTree(HuffNode,&n);
    printf("HuffTable:\n");
    for(i=0;i<2*n-1;i )
    {
        putchar(HuffNode[i].data);
        printf(" %d ",HuffNode[i].weight);
        printf("%d ",HuffNode[i].parent);
        printf("%d ",HuffNode[i].lchild);
        printf("%d ",HuffNode[i].rchild);
        printf("\n");
        }
        printf("\n");
        HuffmanCode(HuffNode,HuffCode,n);
        return 0;
}