哈夫曼树.txt

哈夫曼树 源代码哈夫曼树哈夫曼树 源代码哈夫曼树哈夫曼树 源代码哈夫曼树

 哈夫曼树实现代码 
/***************************************************************
此程序根据用户输入的结点值和权重建立哈夫曼树，然后输出哈夫曼编
****************************************************************/
#include <stdio.h>
#define MAX 21
typedef struct 
{
    char data; /*结点值*/
    int weight; /*权值*/
    int parent; /*父结点*/
    int left; /*左结点*/
    int right;/*右结点*/
}huffnode;

typedef struct
{
    char cd[MAX];
    int start;
}huffcode;

main()
{
    huffnode ht[2*MAX];
    huffcode hcd[MAX],d;
    int i,k,f,l,r,n,c,m1,m2;

    printf("输入元素个数:");
    scanf("%d",&n);

    for (i=1;i<=n;i++)
    {
        getchar();
        printf("第%d个元素=>\n\t结点值:",i);
        scanf("%c",&ht[i].data);
        printf("\t权重:");
        scanf("%d",&ht[i].weight);
    }

    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;             /*l和r是最小权重的两个结点位置*/
        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++)    /*根据哈夫曼树求哈夫曼编码*/
    {
        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;
        }
        hcd[i]=d;
    }

    printf("输出哈夫曼编码: \n");
    for(i=1;i<=n;i++)
    {
        printf("%c: ",ht[i].data);
        for(k=hcd[i].start;k<=n;k++)
            printf("%c",hcd[i].cd[k]);
        printf("\n");
    }
}