huffman.h

实现huffman编码和译码一条龙算法。可以自己输入编码长度与内容

#include<iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<iomanip.h>
#include<string.h>
#include<ctype.h>
typedef struct
{
	unsigned int weight;//权值
	unsigned int parent, lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储Huffmantree
typedef char**HuffmanCode;//动态分配数组存储huffman存储表
typedef struct
{
	char letter;
	unsigned int value;
}*wElem;
void Select(HuffmanTree ht,int i,int &a1,int &a2)
{
	unsigned int sm1 , sm2;   // 用于权值的比较
	a1 = 1;  
	a2 = 1;
	int m=0;  
	for( m = 1 ; m <= i ; m++ ) // 第一遍中第一个 parent 为 0 的结点
	{
		if( ht[ m ].parent != 0 ) continue;
		else 
		{
			sm1 = ht[ m ].weight;
			a1=m;
			break;
		}
	}
	for( int j = m+1 ; j <= i ; j++ ) // 第一遍选第一个最小的
	{
		if( ht[ j ].parent != 0 ) continue;
		else
		{
			if( sm1 > ht[ j ].weight ) 
			{
				sm1 = ht[ j ].weight;
				a1 = j;
			}
		}
	}
	for( m = 1 ; m <= i ; m++ ) // 第二遍中第一个 parent 为 0 的结点
	{
		if( ht[ m ].parent != 0 ) continue;
		else 
		{
			sm2 = ht[ m ].weight;
			a2=m;
			if( a2 == a1 ) continue;
			else break;
		}
	}
	for( int k = m+1 ; k <= i ; k++ ) // 第二遍选第二个最小的
	{
		if( ht[ k ].parent != 0 ) continue;
		else
		{
			if( (ht[ k ].weight < sm2) && ( k != a1 ) ) // 
			{
				sm2 = ht[ k ].weight;
				a2 = k;
			}
		}
	}
} 

//求Huffman编码的算法
void HuffmanCoding(HuffmanTree &ht,HuffmanCode &hc,wElem &w,int n)//求n个字符的huffman编码
{
	if(n<=1)exit(-1);
	int m=2*n-1;
	int i=0;
	 w=(wElem)malloc(n*sizeof(wElem));
	cout<<"请输入字符和权值"<<endl;
	for(i=0;i<n;i++)
	{
		cin>>w[i].letter>>w[i].value;
	}
	 ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(i=1;i<=n;i++)
	{
		ht[i].weight=w[i-1].value;	
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(;i<=m;++i)
	{
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(i=n+1;i<=m;++i)//建huffman树
	{
		int s1,s2;
		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;
	}
	//从叶子到根逆向求每个字符的huffman编码
	 hc=(HuffmanCode)malloc((n+1)*sizeof(char*));
	char* cd=new char[n*sizeof(char)];
	cd[n-1]='\0';
	for(i=1;i<=n;++i)
	{
		int start=n-1;		
		for(int c=i,int 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]);			
	}	
	delete[]cd;

}
void transform(HuffmanTree ht,HuffmanCode& hc,int n)//译码
{
     char* cd=new char[n*sizeof(char)];
	int m=2*n-1;
	int p=m;
	int cdlen=0;
	for(int i=1;i<=m;++i)
		ht[i].weight=0;
	while(p)
	{
		if(ht[p].weight==0)
		{
			ht[p].weight=1;
			if(ht[p].lchild!=0)
			{
				p=ht[p].lchild;
				cd[cdlen++]='0';
			}
			else if(ht[p].rchild==0)
			{
				hc[p]=(char*)malloc((cdlen+1)*sizeof(char));
				cd[cdlen]='\0';
				strcpy(hc[p],cd);
			}
		}
		else if(ht[p].weight==1)
		{
			ht[p].weight=2;
			if(ht[p].rchild!=0)
			{
				p=ht[p].rchild;
				cd[cdlen++]='1';
			}
		}
		else
			{
				ht[p].weight=0;
				p=ht[p].parent;
				--cdlen;
			}
		}
	
}