哈弗曼编码.cpp

哈弗曼编/译码程序源代码,可以由用户读入哈弗曼树

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

typedef struct{
	char         ch;
	unsigned int weight;
	unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char **HuffmanCode;

void Select(HuffmanTree,int,int&,int&);

void InitHuffman(HuffmanTree &HT,HuffmanCode &HC,int n){
	int m,i,s1,s2,start;
	unsigned c,f;
	char *cd;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	HuffmanTree p;
	cout<<"请依次字符和权值的顺序各个输入！"<<endl;
	cout<<"字符如果是空格，请用#代替！"<<endl;
	for(p=HT+1,i=1;i<=n;i++,p++){
		cin>>p->ch;
		cin>>p->weight;
		p->parent=0; p->lchild=0; p->rchild=0;
	}
	
	for(;i<=m;++i,p++){
		p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; 
	}
	for(i=n+1;i<=m;++i){
		Select(HT,i-1,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;
	}
    
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
    // 分配n个字符编码的头指针向量([0]不用)
    cd=(char*)malloc(n*sizeof(char)); // 分配求编码的工作空间
    cd[n-1]='\0'; // 编码结束符
    for(i=1;i<=n;i++)
    { // 逐个字符求赫夫曼编码
        start=n-1; // 编码结束符位置
        for(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));
     // 为第i个字符编码分配空间	
        strcpy(HC[i],&cd[start]); // 从cd复制编码(串)到HC
    }
	//
	free(cd);
	ofstream fout("hfmTree.txt");
	fout<<n<<endl;
	i=1;
	while(i<=n){
	   fout<<HT[i].ch<<" "<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<" ";
	   fout<<HC[i]<<endl;
	   i++;
	}
	while(i<=m){
		fout<<HT[i].parent<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
		i++;
	}
	fout.close();
	cout<<"初始化成功！哈弗曼树已存入“hfmTree.txt”文件中！"<<endl;
}//end of InitHuffMan

void Select(HuffmanTree HT,int i,int &s1,int &s2){
	
	unsigned w=10000;
	for(int j=1;j<=i;j++){
		if(HT[j].weight<w&&HT[j].parent==0) {
           w=HT[j].weight; s1=j;
		}
	}
	HT[s1].parent=1;
	w=10000;
    for(j=1;j<=i;j++){
		if(HT[j].weight<w&&HT[j].parent==0){
           w=HT[j].weight; s2=j;
		}
	}
}//end of Select

void ReadHuffman(HuffmanTree &HT,HuffmanCode &HC,int &n){
	string code;
	int i=1;
	ifstream fin("hfmTree.txt");
	fin>>n;
	HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	while(i<=n){
		fin>>HT[i].ch>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
		fin>>code;
		//HT[i].ch=c;
		//.str()将字符串转化成const char*类型，为将const性质强制去掉
		HC[i]=(char*)malloc(30*sizeof(char));
		strcpy(HC[i],code.c_str());
		i++;
	}
	while(!fin.eof()){
		fin>>HT[i].parent>>HT[i].lchild>>HT[i].rchild;
		i++;
	}
	cout<<"已从文件获取哈弗曼树！"<<endl;
	fin.close();
}

void Encoding(HuffmanTree HT,HuffmanCode HC,int n){
	cout<<"正在从文件ToBeTran.txt读取要编码的数据..."<<endl;
	ifstream fin("ToBeTran.txt");
	ofstream fout("CodeFile.txt");
	if(!fin) {cout<<"文件读取失败！"<<endl; return; }
	char c;  int i=0;
	while(!fin.eof()){
		c=fin.get();
		for(int i=1;i<=n;++i){
			if(c==HT[i].ch) {fout<<HC[i]; cout<<HC[i]<<endl; break;}
		}//for
		if(i==n+2){
			cout<<"字符编码失败，编码表中不存在此字符，程序结束！"<<endl;
			return;
		}//if
	}//while
	cout<<"编码成功！结果已经存入CodeFile.txt文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Encoding

void Decoding(HuffmanTree HT,int n){
	ifstream fin("CodeFile.txt");
	ofstream fout("TextFile.txt");
    if(!fin) {cout<<"文件读取失败！"<<endl; return; }
	char c;
	int fen=2*n-1;   //flag始终跟在fen变量的后边第一个，用于输出
	while(!fin.eof()){
		c=fin.get();	
	    if(c=='0')
			fen=HT[fen].lchild;
	    else
			fen=HT[fen].rchild;
		if(!HT[fen].lchild){    //判断是否已经到叶子结点，是的话输出此叶子结点的字符
		    cout<<HT[fen].ch;
			fout<<HT[fen].ch;
			fen=2*n-1; //当译出一个字符时，fen回到树根，准备下一个译码
		}      
	}//while
	cout<<"\n译码成功！结果已经存入TextFile.txt文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Decoding 

void Print(){
	char c;
	int counter=1;
	ifstream fin("CodeFile.txt");
	ofstream fout("CodePrin.txt");
	while(!fin.eof()){
		c=fin.get();
		if(counter%50==1){ cout<<"\n";  fout<<"\n";}
        cout<<c;   fout<<c;
		counter++;
	}
	cout<<"\n编码成功保存在“CodePrin.txt”文件中！"<<endl;
	fin.close();
	fout.close();
}//end of Print

//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0
void Print_BiTree(HuffmanTree T,int m,int i)
{
	
    if(T[m].rchild){
        //m=T[m].rchild;
		Print_BiTree(T,T[m].rchild,i+1);
	}
    for(int j=1;j<=i;j++) cout<<" ";    //打印i个空格以表示出层次
    cout<<T[m].weight<<" "<<endl;  //打印T元素,换行
    if(T[m].lchild) {
		//m=T[m].lchild;
		Print_BiTree(T,T[m].lchild,i+1);}
}//Print_BiTree

void main(){
	HuffmanTree HT;
	HuffmanCode HC;
	int n,i=0;
	char choice;
	while(1){
	    cout<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl
            <<"☆     欢迎使用哈弗曼编/译器,请选择（I,E,D,P,T,Q ）:      ☆"<<endl
	        <<"☆           I.初始化                                     ☆"<<endl
		    <<"☆           E.编码                                       ☆"<<endl
		    <<"☆           D.译码                                       ☆"<<endl
		    <<"☆           P.印代码文件                                 ☆"<<endl
		    <<"☆           T.印哈弗曼树                                 ☆"<<endl
	        <<"☆           Q.退出系统                                   ☆"<<endl
		    <<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl;
	    cin>>choice;
		switch(choice){
		case 'i':
		case 'I':{
            cout<<"请输入您要建立的曼哈顿树的叶子个数n："<<endl;
			cin>>n;
			InitHuffman(HT,HC,n); 
			}break;
		case 'e':
		case 'E':{
			cout<<"哈弗曼树是否已在内存中?(y/n)"<<endl;
			char ans;
			cin>>ans;
			if(ans=='y'||ans=='Y')
                Encoding(HT,HC,n);
			else{
				cout<<"正在从文件读取哈弗曼树..."<<endl;
				ReadHuffman(HT,HC,n);
				Encoding(HT,HC,n);
				 }
				 }
			break;
		case 'd':
		case 'D':
			Decoding(HT,n);
			break;
		case 'p':
		case 'P':
			Print();
			break;
		case 't':
		case 'T':
			Print_BiTree(HT,2*n-1,i);
			break;
		case 'q':
		case 'Q':
			return;
			break;
		default: cout<<"选择错误！"<<endl;
		}
	}	
}