huffmancoding.cpp

霍夫曼编码

#include "StdAfx.h"

void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
{
	int m,i,c,s1,s2,start,f;
	char * cd;
	HuffmanTree p;

	if(n<2)
	{
		printf("字符只有一个,不用编码,按任意键退出");
		getch();
		exit(1);
	}
	m = 2 * n - 1;
	HT=(HuffmanTree)malloc((m+1) * sizeof(HTNode));

	//初始化
	for(p = HT+1,i = 1;i < n+1;++i,++p,++w)
	{
		p->weight = *w;
		p->lchild = 0;
		p->rchild = 0;
		p->parent = 0;
	}
	for(i = n+1;i <= m;++i,++p)
	{
		p->parent = 0;
		p->lchild = 0;
		p->rchild = 0;
		p->weight = 0;
	}

	//建霍夫曼树
	for (i= n+1;i <= m;++i)
	{
		Select(HT,i-1,s1,s2);
		
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight + HT[s2].weight;	
	}

	//从叶子到根逆向求各个字符的霍夫曼编码
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd=(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	
	for (i = 1;i < n+1;++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]);	
	}
	free(cd);	
}