huffmantree.c

哈弗曼编码可以用来实现 哈弗曼编码的部分功能 运用基础知识

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct
{
	unsigned int Weight;
	unsigned int Parent;
	unsigned int lChild;
	unsigned int rChild;
}HTNode,*HuffmanTree;

/* (*s1) is smallest,(*s2) is smaller */
void select(HuffmanTree HT,int Count,int *s1,int *s2)
{
    int i;
    unsigned int temp1=0;
    unsigned int temp2=0;
    unsigned int temp3;
    for(i=1;i<=Count;i++)
    {
        if(HT[i].Parent==0)
        {
            if(temp1==0)
            {
                temp1=HT[i].Weight;
                (*s1)=i;
            }
            else
            {
                if(temp2==0)
                {
                    temp2=HT[i].Weight;
                    (*s2)=i;
                    if(temp2<temp1)
                    {
                        temp3=temp2;
                        temp2=temp1;
                        temp1=temp3;
                        temp3=(*s2);
                        (*s2)=(*s1);
                        (*s1)=temp3;
                    }
                }
                else
                {
                	/*本程序里的两个函数select和createHTree都是从网上借用过来的，
                	  但网上的select没有考虑到要比较的节点里有两个节点甚至是多个
                	  节点的weight出现相等的情况，所以会导致构建出来的霍夫曼树是
                	  错误的。本程序修正里这一点:将" HT[i].Weight < temp1 "改为
                	  "HT[i].Weight <= temp1"。读者可自行验证本人的想法。  */
                    if(HT[i].Weight <= temp1)
                    {
                        temp2=temp1;
                        temp1=HT[i].Weight;
                        (*s2)=(*s1);
                        (*s1)=i;
                    }
                    if(HT[i].Weight>temp1&&HT[i].Weight<temp2)
                    {
                        temp2=HT[i].Weight;
                        (*s2)=i;
                    }
                }
            }
        }
    }
}

void createHTree(HuffmanTree HT, int *w, int n)
{
    /*数组c[0..n-1]和w[0..n-1]存放了n个字符及其概率，构造霍夫树HT*/
    int i, s1, s2;
    if (n <= 1)
        return;

    /*根据n个权值构造n棵只有根结点的二叉树*/
    for (i=1; i<=n; i++)
    {
        HT[i].Weight = w[i-1];
        HT[i].Parent = HT[i].lChild = HT[i].rChild = 0;     
    }

    for (; i<2*n; ++i)
    {
        HT[i].Parent = 0;
        HT[i].lChild = 0;
        HT[i].rChild = 0;
    }

    /*构造霍夫曼树*/
    for (i=n+1; i<2*n; i++)
    {
        /*从HT[1..i-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2*/
        select(HT,i-1,&s1,&s2);
        HT[s1].Parent = i;    //将HT[i]作为新的二叉树的根节点
        HT[s2].Parent = i;
        HT[i].lChild = s1;
        HT[i].rChild = s2;
        HT[i].Weight = HT[s1].Weight + HT[s2].Weight;
    }
}

int main(void)
{
	int i;
	int leaf_num;
	int node_num;
	HuffmanTree HT;
	int pWeight[] = {45,13,12,16,9,5};

	leaf_num = sizeof(pWeight)/sizeof(int);
	node_num = leaf_num*2;
	HT = (HuffmanTree)malloc(node_num*sizeof(HTNode));
	createHTree(HT, pWeight, leaf_num);
	printf("node  weight  parent  lchild  rchild\n");
	for(i = 1;i<node_num;i++)
	{
		printf("%d %d %d %d %d\n",i,HT[i].Weight,HT[i].Parent,HT[i].lChild,HT[i].rChild);
	}
	HuffmanCode(HT, pWeight, node_num);
	free(HT);
	return 0;
}