ht.cpp

huffman编码规则演示

#include<iostream>
#include<malloc.h>
#include<string.h>
using namespace std;


typedef struct
{
	unsigned int weight;
	unsigned int parent,lchild,rchild;	
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{	
	if(n<=1) return;
	int i,m=2*n-1;
	HuffmanTree p;
	HT=(HuffmanTree)malloc((m)*sizeof(HTNode));
	for(i=1,p=HT;i<=n;++i,++p,++w) 
	{
		p->weight=*w;
		p->lchild=0;
		p->rchild=0;
		p->parent=0;
	}
	for(;i<=m;++i,++p) 
	{
		p->weight=0;
		p->lchild=0;
		p->rchild=0;
		p->parent=0;
	}
		
	int s1,s2;
	int flag1,flag2;
	int j;
	for(i=n;i<m;i++)
	{
		flag1=flag2=0;
		p=HT;
		for(j=0;j<=i-1;j++,p++)
		{			
			if((*p).parent==0)
			{
				if(flag1==0) 
				{
					s1=j;
					flag1=1;
					continue;
				}
				if((*p).weight<HT[s1].weight) s1=j;		
			}
		}
		p=HT;
		for(j=0;j<=i-1;j++,p++)
		{	
			if(j==s1) continue;
			if((*p).parent==0)
			{
				if(flag2==0) 
				{
					s2=j;
					flag2=1;
					continue;
				}
				if((*p).weight<HT[s2].weight) s2=j;		
			}
		}
		HT[s1].parent=i;
		HT[s2].parent=i;
		HT[i].lchild=s2;
		HT[i].rchild=s1;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	
	cout<<"================================="<<endl;
	for(int r=0;r<m;r++)
	cout<<HT[r].weight<<"---"<<HT[r].parent<<"---"<<HT[r].lchild<<"---"<<HT[r].rchild<<endl;
	cout<<"================================="<<endl;
	HC=(HuffmanCode)malloc(n*sizeof(char *));
	char *cd;
	int f,c,start;
	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]);
	}
	free(cd);
}

int main()
{
	int w[100],num,n=0;
	while(cin>>num)
	{
		if(num==0) break;
		else
			w[n++]=num;
	}
	HuffmanTree HT;
	HuffmanCode HC;
	HuffmanCoding(HT,HC,w,n);
	for(int i=0;i<n;i++)
		cout<<w[i]<<"---->"<<HC[i]<<endl;
	return 0;
}