hafuman.cpp

哈夫曼编码 哈夫曼树 字符生成数 译码 由0和1组成的哈夫曼代码

#include <string>
#include <conio.h>//getche()函数
#include <fstream>
#include <iostream>
using namespace std;
#define MAXVALUE 10000

typedef struct
{
	char data;
	int weight,parent,lchild,rchild;
	string hcode;
}HuffNode;

int GetChar (HuffNode *&h)//输入字符函数
{
	char s,c;	int i=0;
	cout<<" 请输入要构造哈夫曼树的字符 或 输入空格载入已有的哈夫曼字符文本 \n";
	ifstream infile("已有哈夫曼字符文本.txt",ios::in);
	ofstream outfile("新的哈夫曼字符文本.txt",ios::out);
	if ((s=getche())==' ')		cout<<" 已有的哈夫曼字符文本为: ";
	for (;;)
	{
		if (s==' ')//如果输入空格则载入已有的哈夫曼字符文本
		{		if ((c=infile.get())==EOF)		{cout<<c;cout<<endl;break;}	cout<<c;}
		else
		{
			if (i==0)				c=s;
			else				cin.get(c);
			if (c=='\n')	break;
		}
		outfile<<c;//将字符写入文件
		for (int j=0;j<i;j++)//先查找是否已存在输入的字符
			if (h[j].data==c)	{	h[j].weight++;		break;	}//如果存在权值加1
		if (j!=i)			continue;//字符已存在
		else
		{
			h[i].data=c;	h[i].weight=1;	h[i].parent=-1;
			h[i].lchild=-1;		h[i].rchild=-1;
		}
		i++;//由于有continue;i++不可以放在for语句内
	}
	for (int j=i;j<2*i-1;j++)//将剩下的节点初始化
	{
		h[j].weight=1;		h[j].parent=-1;
		h[j].lchild=-1;		h[j].rchild=-1;
	}
	infile.close();	outfile.close();
	return i;//返回字符类型个数
}

void CreatHuffman (int n,HuffNode *&h)//创造哈夫曼树
{
	for (int i=0,j,m1,m2,x1,x2;i<n-1;i++)
	{
		for (m1=m2=MAXVALUE,x1=x2=0,j=0;j<n+i;j++)//查找哈夫曼树中的最小子树
		{
			if (h[j].parent==-1 && h[j].weight<m1)//与最小子树比较大小
			{
				m2=m1;				x2=x1;
				m1=h[j].weight;				x1=j;
			}
			else if (h[j].parent==-1 && h[j].weight<m2)//与次小子树比较
			{	m2=h[j].weight;	x2=j;	}
		}
		h[x1].parent=n+i;	h[x2].parent=n+i;//最小子树和次小子树合并成为一个较大子树
		h[n+i].weight=h[x1].weight+h[x2].weight;
		h[n+i].lchild=x1;	h[n+i].rchild=x2;
	}
}

void HuffmanCode (int n,HuffNode *&h)//对哈夫曼树编码
{
	string s;
	for (int i=0,c,p;i<n;i++)//求每个叶子节点的哈夫曼编码
	{
		for (c=i,p=h[c].parent,s="";p!=-1;)//由叶子节点向上直到树根
		{
			if (h[p].lchild==c)				s="0"+s;
			else				s="1"+s;
			c=p;			p=h[c].parent;
		}
		h[i].hcode=s;
		cout<<"  "<<h[i].data<<"的权值为: "<<h[i].weight
			<<" 编码为: "<<s<<endl;
	}
}

void OutChar (int n,HuffNode *&h)//输出编译好的编码
{
	char c;
	ifstream infile("新的哈夫曼字符文本.txt",ios::in);
	cout<<" 编译后的哈夫曼编码为: ";
	for (int i=0;infile;i++)//读取文本中的字符
	{
		if ((c=infile.get())==EOF)			break;
		for (int j=0;j<n;j++)//查找对应的哈夫曼码
			if (h[j].data==c)	{	cout<<h[j].hcode;break;	}
	}
	infile.close();
}

void Interpret (int n,HuffNode *&h)//译回字符
{
	char c;	string s;
	cout<<"\n 请输入由0和1组成的哈夫曼代码 ";	
	for (;;)
	{
		cin.get(c);		if (c=='\n')	break;
		s+=c;
		for (int j=0;j<n;j++)
			if (s==h[j].hcode)	{	cout<<h[j].data;s="";break;	}
	}
	cout<<" 为对应的代码 \n";
	if (s!="" && c=='\n')
		cout<<"\n 代码"<<s<<"不能编译为字符 \n";
}


int main ()
{
	HuffNode *huffchar=new HuffNode[511];
    int n=GetChar(huffchar);
	CreatHuffman(n,huffchar);
	HuffmanCode(n,huffchar);
	OutChar(n,huffchar);
	Interpret(n,huffchar);
	return 0;
}

//	aaaaaaabbbbbcccd