filetohuffmancode.cpp

数据结构中最优二叉树Huffman编码的实现

#include<iostream>
#include<fstream>
#include<malloc.h>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<string>
using namespace std;

class HuffmanTree
{
public:
	int weight;
	int parent,lchild,rchild;

};

typedef char **HuffmanCode;

int w[256];
HuffmanTree *HT;
HuffmanCode HC;
int n=256;
int m=2*n-1;
int root=0;


void printTree(fstream &TreePrint);
void wordStatistics(fstream &file);
void Encoding(fstream &startTran,fstream &CodeFile);
void Decoding(fstream &CodeFile,fstream &TextFile);
void Print(fstream &CodeFile,fstream &CodePrin);
void HuffmanCoding();


void main()
{
	fstream startTran;
	fstream CodeFile;
	fstream TextFile;
	fstream CodePrin;
	fstream TreePrint;
	fstream f1("test1.txt");
	fstream f2("test2.txt");
	fstream f3("test3.txt");
    fstream f4("test4.txt");
	cout<<"哈夫曼编码是通过统计1,2,3,4,5文件得到的";
	memset(w,0,sizeof(w));
	wordStatistics(f1);
	wordStatistics(f2);
	wordStatistics(f3);
	wordStatistics(f4);
	HuffmanCoding();

	Encoding(startTran,CodeFile);

	Decoding(CodeFile,TextFile);
	Print(CodeFile,CodePrin);

	printTree(TreePrint);
}

void wordStatistics(fstream &file)
{
	char ch;
	while(file.get(ch))
		w[int(ch)]++;
}

void HuffmanCoding()
{
	 if(n<1)
		 return;
	 int no=0;
	 for(int i=0;i<n;i++)
		if(w[i]!=0)
			no++;
	 HT=(HuffmanTree*)malloc(m*sizeof(HuffmanTree));
	 HuffmanTree* p;
	 p=HT;
	 for(i=0;i<m;i++,p++)
		 p->weight=p->lchild=p->rchild=p->parent=0;
	 for(i=0,p=HT;i<n;i++,p++)
		 p->weight=w[i]; 
	 int k=1;
	 for(root=n;root<m&&k<no;root++,k++)
	 {
		 int s1,s2,flag=0;
		 for(int j=0;j<root;j++)
		 {
			 int flag2=0;
			 if(HT[j].parent==0&&HT[j].weight!=0)
			 {
				 flag++;
				 if(flag==1)
					 s1=j;
				 else if(flag==2)
					 s2=j;
				 else 
				 {
					 if(HT[j].weight<s1)
					 {
						 flag2=1;
						 s2=s1;
						 s1=j;
					 }
					 if(HT[j].weight<s2&&flag2==0)
						 s2=j;
				 }
			 }
		 }
		 HT[root].lchild=s1;
		 HT[root].rchild=s2;
		 HT[s1].parent=root;
		 HT[s2].parent=root;
		 HT[root].weight=HT[s1].weight+HT[s2].weight;
	 }
	 HC=(HuffmanCode)malloc(n*sizeof(char*));
	 char *cd=new char[n];
	 cd[n-1]='\0';
	 for(i=0;i<n;i++)
	 {
		 if(w[i]!=0)
		 {
		
			 int temp=n-1,c=i,f=HT[c].parent;
			 for(;f!=0;c=f,f=HT[c].parent)
			 {
				 if(HT[f].lchild==c)
					 cd[--temp]='0';
				 else  cd[--temp]='1';
			 }
			 HC[i]=(char*)malloc((n-temp)*sizeof(char));
			 strcpy(HC[i],&cd[temp]);
		 }else
			 HC[i]=NULL;
	 }
}

void Encoding(fstream &startTran,fstream &CodeFile)
{
	startTran.open("startTran.txt",ios::in);
	CodeFile.open("CodeFile.txt",ios::out);
	char ch;
	while(startTran.get(ch))
	{
		if(int(ch)<0)
			return;
		int c=int(ch);
		CodeFile.write(HC[c],strlen(HC[c]));
	}
	startTran.close();
	CodeFile.close();
	CodeFile.clear();
	startTran.clear();
}

void Decoding(fstream &CodeFile,fstream &TextFile)
{
	TextFile.open("TextFile.txt",ios::out);
	CodeFile.open("CodeFile.txt",ios::in);
	char ch;
	char buf[20];
	int k=0;
	if(!CodeFile.is_open())
	{
		cout<<"File not open"<<endl;
		exit(0);
	}
	cout<<endl<<"The startTran file to HuffmanCode:"<<endl;
	while(CodeFile.get(ch))
	{
		buf[k++]=ch;
		buf[k]='\0';
		for(int i=0;i<256;i++)
			if(w[i]!=0)
				if(strcmp(buf,HC[i])==0)
				{
					char a=char(i);
					TextFile.put(a);
					k=0;
					break;
				}
	}
	TextFile.close();
	CodeFile.close();
	CodeFile.clear();
	TextFile.clear();
}

void Print(fstream &CodeFile,fstream &CodePrin)
{
	CodeFile.open("CodeFile.txt",ios::in);
	CodePrin.open("CodePrin.txt",ios::out);	
	if(!CodeFile.is_open())
	{
		cout<<"File not open"<<endl;
		exit(0);
	}
	char ch;
	int k=0;
	while(CodeFile.get(ch))
	{
		k++;
		cout<<ch;
		CodePrin.put(ch);
		if(k==50)
		{
			cout<<endl;
			CodePrin<<'\n';
			k=0;
		}
	}	
	cout<<endl;
	CodePrin.close();
	CodeFile.close();
	CodePrin.clear();
	CodeFile.clear();
}

void preorder(int k,int acc)
{
	if(k<256)
	{
		if(k==32)
			cout<<"空格";
		else if(k==10)
			cout<<"回车";
		else if(char(k)=='\0' || char(k)=='0')
			cout<<"    ";
		else
			cout<<char(k)<<"   ";
		cout<<"   ";
		for(int i=0;i<70-acc;i++)
			cout<<"#";
		for( i=0;i<acc;i++)
			cout<<" ";
		cout<<endl;
	}
	acc+=3;
	if(HT[k].lchild!=0)
		preorder(HT[k].lchild,acc);
	if(HT[k].rchild!=0)
		preorder(HT[k].rchild,acc);
	return;
}

void printTree(fstream &TreePrint)
{
	TreePrint.open("printTree.txt");
	TreePrint.write("The HuffmanCode(all the ASCII codes included) :",60);
	for(int i=0;i<256;i++)
	{
		char ch;
		if(w[i]!=0)
		{
			ch=char(i);
			TreePrint.put(ch);
			TreePrint.write(HC[i],strlen(HC[i]));
			TreePrint.write("  ",2);
			TreePrint.put('\n');
		}
	}
	TreePrint.close();
	TreePrint.clear();

	cout<<"用凹入表示哈夫曼树：(略去了那些创建哈夫曼树过程产生的父节点)"<<endl;
	int acc=0;
	preorder(--root,acc);

}