huffmancoding.c

哈夫曼编码解码以及文档资料和Makefile文件。

#include "head.h"
#include "struct.h"
#include "declare.h"

HuffmanTree HuffmanCoding(HuffmanTree HT,HuffmanCode HC,CharArr *ch)//编码
{
	int m,n,i;
	HuffmanTree p;
	int s1=0,s2=0;
	char *cd;
	int start,c,f;

#if M
	int j;
#endif	

	if(ch->size<1)
		return NULL;
	n=ch->size;
	m = 2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(p=HT+1,i=1;i<=n;++i,++p)//初始化前n个空间
	{
		p->s=ch->e[i-1].c;
		p->weight=ch->e[i-1].w;
		//printf("p->weight=%d\tch->e[i].w=%d\n",p->weight,ch->e[i].w);
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}
	for(;i<=m;++i,++p)//初始化m-n的空间
	{
		p->s='\0';
		p->weight=0;
		p->parent=0;
		p->lchild=0;
		p->rchild=0;
	}

#if M
	printf("\n\tweight\tparent\tlchild\trchild\n");
	for(j=1,p=HT+1;j<=m;j++,p++)
	{
		printf("\t%d\t%d\t%d\t%d\n",p->weight,p->parent,p->lchild,p->rchild);
	}
#endif

	for(i=n+1;i<=m;++i)//构建哈夫曼树
	{
		SelectMin(HT,i-1,&s1,&s2);

#if M
		printf("s1=%d\ts2=%d\n",s1,s2);
#endif

		HT[s1].parent=i;
		HT[s2].parent=i;
		if(s1<=s2)
		{
			HT[i].lchild=s1;
			HT[i].rchild=s2;
		}
		else
		{
			HT[i].lchild=s2;
			HT[i].rchild=s1;
		}
		HT[i].weight = HT[s1].weight+HT[s2].weight;
	}

#if M
	printf("\n\tweight\tparent\tlchild\trchild\n");
	for(j=1,p=HT;j<=m+1;j++,p++)
	{
		printf("\t%d\t%d\t%d\t%d\n",p->weight,p->parent,p->lchild,p->rchild);
	}
#endif

	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	cd = (char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(i=0;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((n-start)*sizeof(char));
		strcpy(HC[i],&cd[start]);
		strcpy(ch->e[i].code,HC[i]);//将编码存入数组
		if(i!=0)
		printf("ch->e[%d].code=\t%s\n",i,ch->e[i].code);
		free(HC[i]);
	}
	free(cd);
	free(HC);
	printHuffmantree(HT,m,5);
	return HT;
}