hufftree.cpp

哈夫曼编码、译码程序

#include <iostream.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#define MAXNUM 27

class HuffNode
{
public:
	char data;
	int weight;
	int father;
	int lc;
	int rc;
};
class HuffNodeCode
{
public:
	char data;
	char code[MAXNUM];
};
int Selete2Small(HuffNode *htree,int k,int *s1,int *s2);
int HufftreeCreate(HuffNode *htree,int n)
{
	int s1,s2,i;
	s1=s2=0;
	for(i=n+1;i<2*n;i++)
	{//选择两个父为0，权最小的树的下标
		Selete2Small(htree,i-1,&s1,&s2);
		htree[i].data=NULL;
	//置新父节点权值
		htree[i].weight=htree[s1].weight+htree[s2].weight;
	//置根无父
		htree[i].father=0;
	//置儿子指示	
		htree[i].lc=s1;
		htree[i].rc=s2;
		htree[s1].father=i;
		htree[s2].father=i;
	}
return 0;
};

int Selete2Small(HuffNode *htree,int k,int *s1,int *s2)
{
	int i,j;
	if (k<2) return -1;
	*s1=0;*s2=0;
	//令s1,s2分别指向htree中最前面的两个无父节点元素
	
	for (j=1;j<=k;j++)
	{
		if(htree[j].father!=0) continue;
		if(*s1==0) *s1=j;
		else {*s2=j;break;}
	}
	if(*s1==0||*s2==0) return -1;//表示htree中只有一棵树
	if(htree[*s1].weight>htree[*s2].weight)
	{
		i=*s1;*s1=*s2;*s2=i;}
	for(i=j+1;i<=k;i++) //j从上段程序的值开始
	{
		if(htree[i].father!=0) continue;
		if(htree[i].weight<htree[*s1].weight)
		{
			*s2=*s1;
			*s1=i;
		}
		else
			if(htree[i].weight<htree[*s2].weight) *s2=i;
	}
	return 0;
}
//列表输出哈夫曼树
void PrintHtree(HuffNode *htree,int n)
{
	cout<<"\n输出哈夫曼树结构："<<endl;
	cout<<"序号"<<"  "<<"节点数据"<<"  "<<"权重"<<"  "<<"父亲节点"<<"  "<<"左孩子"<<"  "<<"右孩子"<<endl;
	for(int i=1;i<=2*n-1;i++)
	{
		cout<<i<<"\t"<<htree[i].data<<"\t"<<htree[i].weight<<"\t"<<htree[i].father<<"\t"<<htree[i].lc<<"\t"<<htree[i].rc<<endl;
	}
}
//哈夫曼树编码
void HufftreeCode(HuffNode *htree,int n,HuffNodeCode *pcode)
{
	int i,j,k,m;
	HuffNode *curr;
	for(i=1;i<=n;i++)
	{
		curr=&htree[i];
		j=MAXNUM-1;
		k=i;
		pcode[i].data=htree[i].data;
		do 
		{
			if(n<=1) 
			{
				pcode[i].code[j]='0';
				return;
			}
			m=curr->father;
			curr=&htree[m];
			if(curr->lc==k) 
			{
				pcode[i].code[j]='0';
			}
			else
				if(curr->rc==k)
				{
					pcode[i].code[j]='1';
				}
				k=m;
				j=j-1;
		}while(curr->father!=0);
        if(curr->lc==k) pcode[i].code[j]='0';
		else
			if(curr->rc==k) pcode[i].code[j]='1';	
	}
}
//紧缩编码表
void HuffOrder(HuffNodeCode *htreecode,HuffNodeCode *htreecdout,int n)
{
	int i,j,k,kk;
	for(i=1;i<=n;i++)
	{
		htreecdout[i].data=htreecode[i].data;
	    j=0;
		while((htreecode[i].code[j]==NULL)&&(j<MAXNUM))	{j+=1;}
		kk=0;
		for(k=j;k<MAXNUM;k++)
		{
	    	htreecdout[i].code[kk]=htreecode[i].code[k];
		    kk+=1;
		}
		if(kk<MAXNUM)
		{
			for(k=kk;k<MAXNUM;k++) htreecdout[i].code[k]=NULL;
		}
	}
}
//对输入字符串编码
void StrCodeing(char *str,int n,HuffNodeCode *pcode)
{
	int i,j,k,m,flag;
	k=0;
	m=strlen(str);
	for(i=0;i<m;i++)
	{
		flag=0;
		for(j=1;j<=n;j++)
		{
			if(pcode[j].data==str[i]) 
			{
				cout<<pcode[j].code;
				flag=1;
				break;
			}
		}
		//控制输出
		k+=strlen(pcode[j].code);
		if(k>=50) {k=0;cout<<endl;}
				
	    if(flag==0) 
		{
			cout<<"字符串中含有不能编码的字符!"<<endl;
			exit(1);
		}
	}
}

void PrintCode(HuffNodeCode *htreecdout,int n)
{
	cout<<"输出哈夫曼树编码； "<<endl;
	for(int i=1;i<=n;i++)
	{
		cout<<htreecdout[i].data<<"  :   "<<htreecdout[i].code<<endl;
	}
}

//二进制译码
void StrConcodeing(char *chr,int n,HuffNode *htree)
{
	int i=0,m;
	m=2*n-1;
	while(chr[i]!='\0')
	{
		
		if (chr[i]=='0')
		{
			m=htree[m].lc;
		}
		else if(chr[i]=='1')
		{
			m=htree[m].rc;
		}
	    if(htree[m].lc==0) 
		{
			cout<<htree[m].data;
			m=2*n-1;
		}
		i+=1;
	}
}

//主程序
void main()
{
	int n,i,sele;
    char str1[100];
	char str2[1000];
    char chr[1];
    cout<<"输入字符集大小：";
	cin>>n;
	HuffNode *htree=(HuffNode *) malloc(2*n*sizeof(HuffNode));
	HuffNodeCode *htreecode=(HuffNodeCode *) malloc((n+1)*sizeof(HuffNodeCode));
	HuffNodeCode *htreecdout=(HuffNodeCode *) malloc((n+1)*sizeof(HuffNodeCode));
	//对第htree[0]单元置初值
	htree[0].data=NULL;
	htree[0].father=htree[0].lc=htree[0].rc=htree[0].weight=0;
	for(i=1;i<=n;i++)
	{
		cout<<"\n输入第"<<i<<"个字符:"<<endl;
		gets(chr);
		htree[i].data=chr[0];
		//cin>>htree[i].data;
		cout<<"\n输入字符\""<<chr[0]<<"\"的权值:";
		cin>>htree[i].weight;
		htree[i].father=htree[i].lc=htree[i].rc=0;
	}
	//编码数组初始化
	for(i=1;i<=n;i++)
	{
		for(int j=0;j<MAXNUM;j++)
		{
			htreecode[i].code[j]=NULL;
		}
	}
	//构造哈夫曼树
	HufftreeCreate(htree,n);
	//列表输出哈夫曼树结构
	PrintHtree(htree,n);		
	//哈夫曼树编码
	HufftreeCode(htree,n,htreecode);
	//将编码正序紧缩存入htreecdout中
	HuffOrder(htreecode,htreecdout,n);
	//输出字符编码	
	PrintCode(htreecdout,n);
	while(1)
	{
        cout<<"\n------操作表------"<<endl;	
		cout<<"1   输入字符串，编写二进制码； "<<endl;
		cout<<"2   输入二进制数据，译码输出； "<<endl;
		cout<<"3   退出； "<<endl;		 
		cout<<"请选择操作："<<endl;
	    cin>>sele;
		switch(sele)
		{
		case 1:
			{
				cout<<"请输入要编码的字符串:"<<endl;
			    gets(str1);
				cout<<"输入的字符串为:"<<str1<<endl;
				//编码
				cout<<"字符串的二进制编码为:"<<endl;
                StrCodeing(str1,n,htreecdout);
				break;
			}
		case 2:
			{	
    			cout<<"请输入要译码的二进制编码:"<<endl;
			    gets(str2);
				cout<<"输入的字符串为:"<<str2<<endl;
				//译码
				cout<<"二进制字符串的原码为:"<<endl;
				StrConcodeing(str2,n,htree);
				break;			
			}
		case 3: exit(1);
		}
	}
}