huffmancoding.cpp

实现用huffman编码的编码译码器

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
typedef struct{
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;    //动态分配数组存储哈夫曼树
HuffmanTree HT;
typedef char** HuffmanCode;
HuffmanCode HC;         //动态分配数组存储哈夫曼编码表

int m=53,n=27,*w;//分别为树的节点个数，叶子结点个数，以及对应的权值
string c;//用来保存字符集

void Select(int a,int &s1,int &s2)
{
	int i,j,jj;unsigned int min1=32767;
	for(i=1;i<=a;i++)
	{
		if(HT[i].weight<min1&&HT[i].parent ==0)
		{
			j=i;
			min1=HT[i].weight ;
		}
	}
		s1=j;
		min1=32767;
	for(int n0=1;n0<=a;n0++)
	{
			if(HT[n0].weight<min1&&HT[n0].parent ==0&&n0!=s1)
			{
				jj=n0;
				min1=HT[n0].weight ;
			}
	}
			s2=jj;
}
void HuffmanCoding(){
	if(n<=1) return;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	int i=1;
	HuffmanTree p=HT+1;
	for(;i<=n;i++,p++,w++){
		p->weight =*w;
		p->lchild =0;
		p->rchild =0;
		p->parent=0;
	}
	for(;i<=m;++i,++p){
		p->lchild =0;
		p->rchild =0;
		p->parent =0;
		p->weight =0;
	}
	int s1,s2;
	for(i=n+1;i<=m;++i){
		Select(i-1,s1,s2);   //在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为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;
	}
    //以上建立哈夫曼树
	ofstream hfm("hfmTree.txt");
	for(i=1;i<=m;i++){
		hfm<<i<<' '<<HT[i].weight<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
	}     //将哈夫曼树输出

	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));   //分配n个字符编码的头指针向量
	char *cd;
	cd=(char *)malloc(n*sizeof(char));   //分配求编码的工作空间
	for(i=1;i<=n;++i){
		int start=n-1;
		for(int 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));
		for(int a=0;a<n-start-1;a++)
			HC[i][a]=cd[start+1+a];
		HC[i][n-start-1]='\0';
	}
	free(cd);
}
void Initialization(){
	ifstream in("chars.txt");
	ifstream putin("weight.txt");
	putin>>n;
	getline(in,c);
	w=(int *)malloc(n*sizeof(int));
	for(int a=0;a<n;a++){
		putin>>w[a];
	}
	HuffmanCoding();
	in.close ();
	putin.close ();
}

void Encoding(){
	cout<<"use the default file or not? y/n"<<endl;
	char yn;
	cin>>yn;
	while(yn!='y'&&yn!='Y'&&yn!='n'&&yn!='N')
	{
			cout<<endl<<"the command is wrong ,please try again：";
			cin>>yn;
	}
	ifstream input;
	if(yn=='n'||yn=='N')
	{
		cout<<"input the tobetraned filename:(filetotran.txt)"<<endl;
		string fch;
		cin>>fch;
		input.open (fch.c_str ());
		//ifstream input(fch.c_str ());
	}
	else
	{
		input.open ("ToBeTran.txt");
		//ifstream input("ToBeTran.txt");
	}
	ofstream encode("CodeFile.txt");
	string a;
	getline(input,a);
	int p=0;
	for(;a[p]!='\0';p++){
		int i=0;
		for(;i<n;i++){
			if(c[i]==a[p])
				break;}
		encode<<HC[i+1];
	}
	input.close ();
	encode.close ();
}
/******译码过程从根结点扫描，遇到叶子节点则打印相应的字符********/
void Decoding(){
	cout<<"use the default file or not? y/n"<<endl;
	char yon;
	cin>>yon;
	while(yon!='y'&&yon!='Y'&&yon!='n'&&yon!='N')
	{
			cout<<endl<<"the command is wrong ,please try again：";
			cin>>yon;
	}
	ifstream inp;
	if(yon=='n'||yon=='N')
	{
		cout<<"input the 0-1 filename :(cdfile.txt)";
		string cd;
		cin>>cd;
		 inp.open(cd.c_str ());
	}
	else
	{
		 inp.open ("CodeFile.txt");
	}
	ofstream decode("TextFile.txt");
	char a;int b=m;//头结点在ht【m】中保存
	cout<<"the context of the file is :"<<endl;
	while(inp>>a){
		if(a=='0') b=HT[b].lchild;
		else b=HT[b].rchild;
		if(HT[b].lchild==0){
			cout<<c[b-1];//在屏幕上输出
			decode<<c[b-1];//保存至文件
			b=m;//结束一个字符的译码后，再次回到头结点
		}
	}
	cout<<endl;
	inp.close ();
	decode.close ();
}
void Print()
{
	ifstream cfile1("CodeFile.txt");
	ofstream cpfile("CodePrin.txt");
	int e=0;
	char ca;
	cout<<"the following is the codefile:"<<endl;
	while(cfile1>>ca)
	{
		if(e%50==0)
			cout<<endl;
		cout<<ca;
		cpfile<<ca;
		e++;
	}
	cfile1.close ();
	cpfile.close ();
	cout<<endl;
}
//打印树形，即为遍历树,此处采用先序遍历
void TreePrinting(int i,int m)
{
	ofstream tpt("TreePrint.txt" ,ios::app);
	tpt.unsetf (ios::skipws );
	if(i==0) return;
	for(int p=0;p<m;p++){
		cout<<"    ";
		tpt<<"    ";
	}
	cout<<HT[i].weight;
	tpt<<HT[i].weight;
	for(int q=15-m;q>0;q--)
	{
		cout<<"<<<";
		tpt<<"<<<";
	}
	cout<<endl;
	tpt<<endl;
	TreePrinting(HT[i].lchild,m+1);
	TreePrinting(HT[i].rchild,m+1);
}
void Menu()
{
	cout<<"Command:"<<endl;
	cout<<"Encoding--e Decoding--d "<<endl;
	cout<<"TreePrinting--t  Quit--q Print--p"<<endl;
}
void ReadCommand(char &cmd){
	cout<<"please enter the command：";
	cin>>cmd;
	while(cmd!='e'&&cmd!='E'
		&&cmd!='q'&&cmd!='Q'&&cmd!='d'&&cmd!='D'&&cmd!='t'&&cmd!='T'&&cmd!='p'&&cmd!='P'){
			cout<<endl<<"the command is wrong ,please try again：";
			cin>>cmd;
	}
}

void Interpret(char cmd){
	switch(cmd){
		case 'e': case 'E':
			Encoding();
			break;
		case 'd': case 'D':
			Decoding();
			break;
		case 't': case 'T':
			TreePrinting(2*n-1,1);
			break;
		case 'p': case'P':
			Print();
			break;

	}
}

int  main()
{
	char cmd;
	 Initialization();
	do{		Menu();
		ReadCommand(cmd);
		Interpret(cmd);

	}while(cmd!='q'&&cmd!='Q');
	return 0;
}