huffmantree.cpp

Huffman算法的详细解析,包括建立Huffman树的方法,编码和解码

// HuffmanTree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "stdlib.h"
#include "iostream.h"
#include "string.h"
typedef struct{
              int weight;
              int parent,lchild,rchild;
}HTNode, *HuffmanTree;

typedef char **HuffmanCode;

void select(HuffmanTree &HT,int i,int *s1,int *s2)
{
	int j,wtemp,temp1,temp2;
	temp1=temp2=32676;
	for(j=1;j<=i;j++)
	{
		wtemp=HT[j].weight;
		if(HT[j].parent) continue;
		if(wtemp<temp1)
		{
			temp1=wtemp;
			*s1=j;
		}
		else
		{
		   if(wtemp<temp2)
		   {	
			    temp2=wtemp;
		        *s2=j;
		   }
		}
	}
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int* w,int n)
{
	int i,m,s1,s2,c,f,start;
	char *cd;
	HuffmanTree p;
	int *pp;
	pp=w;
	
	if(n<=1) return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	
	for(p=HT+1,i=1; i<=n; ++i,++p,pp++)   
	{	p->weight=*pp;
	    p->parent=0;
	    p->lchild=0;             
		p->rchild=0;
	}
    for(; i<=m; ++i,++p)                 
	{	 
		p->weight=0;
	    p->parent=0;
	    p->lchild=0;
	    p->rchild=0;   
	}
	
	//create huffman tree
	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;
	}	
//	for(i=1;i<=m;i++)
//		cout<<HT[i].weight<<endl;
	/*************从叶子到根逆向求每个字符的huffman码*********************/
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	cd=(char*)malloc(n*sizeof(char));
	cd[n-1]='\0';
    for(i=1;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 i,m,n;
	int weight[100];
	HuffmanTree HT;	
	HuffmanCode HC;
	cout<<"please input the number of HTNode"<<endl<<"n=";
	cin>>n;
	cout<<"please input the weight of HTNode"<<endl;
	for(i=0;i<n;i++)
		cin>>weight[i];
	m=2*n-1;
	HuffmanCoding(HT,HC,weight,n);
    cout<<"the weight of HuffmanTree"<<endl;
	for(i=1;i<=m;i++)
		cout<<HT[i].weight<<endl;
    cout<<"the huffmancode of HTNode"<<endl;
	for(i=1;i<=n;i++)
		cout<<weight[i-1]<<"->"<<HC[i]<<endl;


	return 0;
}