huffman.cpp

用优先队列实现霍夫曼编码

#include<string.h>
#include<string>
#include<queue>

#include<fstream>
#include<vector>
#include<iostream>
#include<iomanip>
using namespace std;
using std::string;
static const int MAX_SIZE=256;
struct huffman_node;
typedef huffman_node* node_ptr;//huffman结点指针
struct huffman_node{
	char id;
	int freq;
	string code;
	node_ptr left,right,parent;
};
//类huffman
class compare;
class huffman{
      private:
		  class compare{
		  public:
			  bool operator ()(const node_ptr&c1,const node_ptr&c2){
				  return (*c1).freq>(*c2).freq;
			  }//重载运算符（）
		  };//类compare
          node_ptr node_array[MAX_SIZE];//指针型结点的数组
	      priority_queue<node_ptr,vector<node_ptr>,compare> pq;
		  fstream in_file,out_file;
	      string in_file_name;
		  string out_file_name;
	  public:
		  huffman(string in_file_name,string out_file_name);
		  void create_pq();
		  void create_node_array();
		  void create_huffman_tree();
		  void calculate_huffman_codes();
		  void save_to_file();
		 
			  
			 
};
 
huffman::huffman(string in_file_name,string out_file_name){
	(*this).in_file_name=in_file_name;
	(*this).out_file_name=out_file_name;
	in_file.open(in_file_name.c_str (),ios::in);

    out_file.open(out_file_name.c_str(),ios::out);
	
}//构造器
//创建huffman结点数组,根据读入的每一行的字符，存入下标是自身Asc码数字的指针数组
void huffman::create_node_array(){
	node_ptr entry;
	string line;
	while(getline(in_file,line)){
		for(unsigned j=0;j<line.length();j++){
			entry=node_array[(int)(line[j])];
			(*entry).freq++;
			if((*entry).freq==1){
				(*entry).left=NULL;
				(*entry).right=NULL;
				(*entry).parent=NULL;
			}//if
		}//for
		entry=node_array[(int)'\n'];
		(*entry).freq++;
		(*entry).left=NULL;
		(*entry).right=NULL;
		(*entry).parent=NULL;
	}//while
	
}//create_node_array
//将所有huffman结点插入优先队列
void huffman::create_pq(){
     node_ptr entry;
	 int sum=0,n_chars=0;
	 for(int i=0;i<MAX_SIZE;i++){  //定义单个结点
		 node_array[i]=new huffman_node;
         (*node_array[i]).freq=0;
	 }//初始化数组
	 create_node_array();
	 for(int j=0;j<MAX_SIZE;j++){
		 entry=node_array[j];
		 if((*entry).freq>0){
			 pq.push(entry);
			 sum+=(*entry).freq;
			 n_chars++;

		 }
	 }
}
void huffman::create_huffman_tree(){
	node_ptr left;
	node_ptr right;
	node_ptr sum;
	while(pq.size()>1){
		left=pq.top();
		pq.pop();
		(*left).code=string ("0");

		right=pq.top();
		pq.pop();
		(*right).code=string ("1");

		sum=new huffman_node;
		(*sum).parent=NULL;
		(*sum).freq=(*left).freq+(*right).freq;
		(*sum).left=left;
		(*sum).right=right;
		(*left).parent=sum;
		(*right).parent=sum;

		pq.push(sum);
	}
}
//对各个字符进行编码
void huffman::calculate_huffman_codes(){
	const string HUFFMAN_CODES="Here are the huffman codes: ";
	const string ENCODED_SIZE_MESSAGE="\n\nThe size of the encoded message, in bits,is ";
	int total=0;//记录编码后的总位数
	string code;
	node_ptr entry;
	cout<<endl<<HUFFMAN_CODES<<endl;
	for(int i=0;i<MAX_SIZE;i++){
		code=" ";    
		entry=node_array[i];
		if((*entry).freq>0){
			cout<<char(i)<<" "; //注意，空格和回车非打印字符，所以是空格，但有编码
			do{
				code=(*entry).code+code;//将叶子代码和上层的父节点连接，迭代到根结点
				entry=(*entry).parent;
			}while((*entry).parent!=NULL);
			
				cout<<code<<endl;
			(*node_array[i]).code=code;
			total+=code.length()*(*node_array[i]).freq;//每个字符编码*每个字符频率
		}//if
	}//for
	cout<<ENCODED_SIZE_MESSAGE<<total<<endl;
}//
//输出每个字符和其huffman编码和编码后的文件
void huffman::save_to_file(){
	node_ptr entry;
	string line;
	(*this).in_file.close();
	(*this).in_file.open(in_file_name.c_str(),ios::in);
	for(int i=0;i<MAX_SIZE;i++){
		entry=node_array[i];//指针数组中如果频率大于0表示存在编码信息
		if((*entry).freq>0)
			out_file<<(char)i<<" "<<(*entry).code<<endl;
	}//for
	out_file<<"----"<<endl;
	while(getline(in_file,line)){//这里问题出现，调试时根本进入不了，所以文件编码不能写进h2.txt
	
		for(unsigned j=0;j<line.length();j++){
			entry=node_array[(int)(line[j])];//给定字符，寻找指针数组中下标对应的编码信息
			out_file<<(*entry).code;//写出编码
		}//for
		entry=node_array[(int)'\n'];
		out_file<<(*entry).code;//写出换行符编码
	}//while
	out_file.close();
	in_file.close();
}//save_to_file
void main(){

        
		huffman h("h1.txt","h2.txt");
		h.create_pq();
		h.create_huffman_tree();
		h.calculate_huffman_codes();
		h.save_to_file();
}