huffmantree.c

Huffman 构造和编码。 使用Borland C++ 调试成功。 其中包含4个主要的函数。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define true 1
#define false 0
typedef struct{
	int weight,parent,lc,rc;
}HNode,*HTree;
typedef char **HCode;
void select(HTree *tree,int i,int *s1,int *s2)
{
	int k,w1,w2;//w1,w2权重,k:循环变量
	w1=w2=INT_MAX;
	for(k=0;k<i;k++)
	{
		if(tree[0][k].parent==0)//parent为0的说明没有被选过
		{
			if(w1<=w2)
			{
				if(tree[0][k].weight<w2)
				{
					w2=tree[0][k].weight;
					*s2=k;
				}
			}
			else
			{
				if(tree[0][k].weight<w1)
				{
					w1=tree[0][k].weight;
					*s1=k;
				}
			}
			printf("a:%d,b:%d\t",*s1,*s2);
		}//end if
	}//end for
	if(*s1>*s2)//调整s1,s2,使s1<=s2,不然的话就不能保证左0右1
	{
		int temp=*s2;
		*s2=*s1;
		*s1=temp;
	}
}
void HCoding(HTree *aTree,HCode *aCode,int *w,int n)
{
	HTree pT;
	char *cd=(char*)malloc(n*sizeof(char));
	int m=2*n-1,i,start,c,f;
	if(n<=1)return;
	*aTree=pT=(HTree)malloc(sizeof(HNode)*m);
	*aCode=(HCode)malloc(sizeof(char*)*n);
	for(i=0;i<n;i++)
	{
		aTree[0][i].lc=aTree[0][i].rc=aTree[0][i].parent=0;
		aTree[0][i].weight=w[i];
	}
	for(;i<m;i++)
	{
		aTree[0][i].lc=aTree[0][i].rc=aTree[0][i].parent=aTree[0][i].weight=0;
	}
	for(i=n;i<m;i++)
	{
		int s1=0;
		int s2=0;
		select(aTree,i,&s1,&s2);
		printf("\n最小的两个:(%d,%d)\n",s1,s2);
		pT[s1].parent=pT[s2].parent=i;
		pT[i].lc=s1;
		pT[i].rc=s2;
		pT[i].weight=pT[s1].weight+pT[s2].weight;
	}
	if(!cd||!(*aCode))exit(-1);//没有申请到空间
	cd[n-1]=0;
	for(i=0;i<n;i++)
	{
		start=n-1;
		for(c=i,f=pT[i].parent;f;c=f,f=pT[f].parent)
		{
			cd[--start]=(pT[f].lc==c ? '0' : '1');//从根开始求编码，左零右壹
		}
		(*aCode)[i]=(char*)malloc(sizeof(char)*(n-start));
		strcpy((*aCode)[i],&cd[start]);
	}
	free(cd);
}
int main()
{
	int w1[8]={5,29,7,8,14,23,3,11};
	int i;
	HTree tree;
	HCode code;
	HCoding(&tree,&code,w1,8);
	for(i=0;i<15;i++)
	{
		printf("i:%2d %2d,%2d,%2d,%2d\n",i,tree[i].weight,tree[i].parent,tree[i].lc,tree[i].rc );
	}
	for(i=0;i<8;i++)
	{
		printf("Num %2d：Weight %3d：%s\n",i,w1[i],code[i]);
	}
	system("pause");
	return 0;
}