haffman.cpp

haffman的编码和译码 haffman的编码和译码

#include <iostream.h>
#include <string.h>
#define MAX 99   //定义MAX为99
char cha[MAX];   //定义字符串变量
char hc[MAX-1][MAX];   //定义编码数组变量
void menu();     //用户进入huffman树编码与译码菜单的函数
void huffman();  //构造huffman树的函数
void encoder();  //编码huffman树的函数
void decode();   //译码huffman树的函数
void end();      //结束译码提示用户是否继续的函数
void huff();     //用户输入huffman树有关数据的函数

//定义huffman树的存储结构
typedef struct 
{
	int tag;           //标记此结点是否有父结点
	int weight;        //存放结点的权值
	int parent;        //记录结点父亲位置,
	int lchild,rchild; //存放该结点的左、右孩子的所在单元的编号
}hufftree;

//用户进入huffman树编码与译码菜单的函数
void menu()
{
	int num;
    cout  <<"请选择操作类型(1/2):";
loop:	          //进入loop循环
	cin >>num;
	switch(num)   //通过swich语句进行选择
	{
 	case 1: 
		huff();   //调用huff()函数进行用户输入huffman树有关数据
		break;
	case 2: 
		break;    //退出huffman树编码与译码系统
	default: 
		cout <<endl<<"选择错误!!!"<<endl<<"请重新选择(1/2):";
		goto
			loop; //返回loop循环
	}
}

//构造huffman树的函数
void huffman(hufftree tree[],int *w,int n)//w表示存放n个字符的权值
{
	int i,j,m1,m2,x1,x2,m;
	
	m=2*n-1;       //计算huffman树所有结点的个数
	//初始化huffman树的外部结点
	for(i=1;i<=n;i++)
	{
		tree[i].tag=0;
		tree[i].weight=w[i];  //外部结点赋权值
 		tree[i].parent=0;
		tree[i].lchild=0;
		tree[i].rchild=0;
		
	}
	//初始化huffman树的内部结点
	for(i=n+1;i<=m;i++)
	{
		tree[i].tag=0;
		tree[i].weight=0;
        tree[i].parent=0;
		tree[i].lchild=0;
        tree[i].rchild=0;
	}
	//逐步构造huffman树
	for(i=1;i<=n-1;i++)
	{
		m1=m2=32767;//m1,m2是比任何权都大的整数
		x1=x2=-1;
		//找两个最小的权
		for(j=1;j<n+i;j++)
		{
			if(tree[j].weight<m1&&tree[j].tag==0)
			{
				m2=m1;
				x2=x1;
				m1=tree[j].weight;
				x1=j;
			}
			else if(tree[j].weight<m2&&tree[j].tag==0)
			{
				m2=tree[j].weight;
				x2=j;
			}
		}
		//标记
		tree[x1].tag=1;
		tree[x2].tag=1;
		//为最小的权所在结点的父结点赋值
        tree[x1].parent=n+i;
        tree[x2].parent=n+i;
		//构造子树
		tree[n+i].lchild=x1;
		tree[n+i].rchild=x2;
		tree[n+i].weight=tree[x1].weight+tree[x2].weight;
	}
}

//编码huffman树的函数
void encoder(hufftree tree[],char code[],int n)//code[]存储huffman树的编码
{
	int start,c,i,j,f;
	char anychar[MAX];  //定义所要编码的字符
	code[n-1]='\0';     //标志编码的结束符
	cout <<"Huffman编码:"<<endl;
	//对用户要求的字符进行编码
	for(i=1;i<=n;i++)
	{
		start=n-1;
		for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
		{
			if(tree[f].lchild==c)      
				code[--start]='0';   
			else           
				code[--start]='1';
		}
		strcpy(hc[i],&code[start]);   //将编码赋给hc[]，用hc[]实现所对字符编码的输出
		cout <<cha[i] <<"-->"<<hc[i] <<endl;
	}
	cout <<"请输入一段任意长字符，结束时请按下回车:" <<endl;
	cin >>anychar;    //用户输入想要编码的字符
	cout <<"进行Huffman编码后的结果为:" <<endl;
	//对字符编码的输出
	for (i=0;anychar[i]!='\0';i++)
	{
		for(j=0;anychar[i]!=cha[j]&&j<=n;)
			j++;
		if (j<=n)
			cout <<hc[j];
	}
	cout <<endl;
}

//译码huffman树的函数
void decode(char ch[],hufftree tree[],int n)
{
	int i,j,m;
	char b;
	m=2*n-1;     //计算huffman树所有结点的个数
	i=m;
	cout <<"请输入你要译码的编码:" <<endl;
	cin >>b;     //输入要译码的编码
	cout <<"译码结果为(输入*结束):" <<endl;
	//对编码进行译码
	while(b!='*')   
	{
		if(b=='0')
			i=tree[i].lchild;
		else
			i=tree[i].rchild;
		if(tree[i].lchild==0)
		{
			cout<<ch[i];
			j=i;i=m;
		}
		cin>>b;
	}
	if(tree[j].lchild!=0)
		cout <<"发生错误!!";
}

//结束译码提示用户是否继续的函数
void end()
{	
	int s;
	cout<<"\n*******************************\n";
	cout<<"**请选择操作：1、继续 2、退出  **";
	cout<<"\n*******************************\n";
	cin>>s;
	if(s==1)
		huff();   //进入huffman树编码与译码系统
	else
		return;   //退出系统
}

//用户输入huffman树有关数据的函数
void huff()
{
	int i=0,n=0;
	int *w,weight[MAX];  //定义权值变量
	char code[MAX];      //定义编码变量
	hufftree tree[MAX];  //定义huffman树的存储结构数组
	w=weight;            //权值赋给变量w
	cout <<"请输入N(N为你要建树的字符个数):\n";
	cin >>n;
	cout <<"请输入字符和它的权值(例如:a12):" <<endl;
	//输入huffman树的有关数据
	for(i=1;i<=n;i++)
	{
		cin >>cha[i] >>weight[i];
	}
	huffman(tree,w,n);     //调用构造huffman树的函数
	encoder(tree,code,n);  //调用编码huffman树的函数
	decode(cha,tree,n);    //调用译码huffman树的函数
	end();
}

//主函数
void main()
{
	cout  <<"*****************欢迎使用哈夫曼编码与译码系统*******************"<<endl;
	cout  <<"*                                                              *"<<endl;
	cout  <<"*                                                              *"<<endl;
	cout  <<"*                制作人：黄高锦 杨靖飞 史保瑞                  *"<<endl;
    cout  <<"*                                                              *"<<endl; 
	cout  <<"*                                                              *"<<endl;
	cout  <<"*                    1.Huffman编码与译码                       *"<<endl;
    cout  <<"*                    2.退出                                    *"<<endl;
    cout  <<"*                                                              *"<<endl;
    cout  <<"*                                                              *"<<endl;
	cout  <<"****************************************************************"<<endl;
	menu();
}