huffman.cpp

自己做的数据结构实验题（合并链表

#include"huffman.h"
#include <math.h>

//初始化
huffman::huffman(string in_file_name,string out_file_name,Type T){
	(*this).in_file_name=in_file_name;
//in_file打开输入文件
	in_file.open(in_file_name.c_str(),ios::in);
//out_file打开输出文件
	out_file.open(out_file_name.c_str(),ios::out);
	if(!in_file)
		cout<<"no such a file"<<endl;
		else
//执行run函数 构造优先队列及构建Huffman树并进行编码

switch(T){
			case 1:
				RunHuffman();
				break;
			case 0:
				RunHuffmanReverse();
				break;
		}
	


}

//创建优先队列
void huffman::create_pq(){
	const string DEFAULT_TOTAL="使用二进制编码时编码长度为：";
//用于存放入队的node元素
	node_ptr entry;
	
	int sum=0,
	n_chars=0,
	n_bits_per_char=0;
	for(int i=0;i<MAX_SIZE;i++){
		node_array[i]=new huffman_node;
		(*node_array[i]).freq=0;
	}
//对文件1进行扫描，初始化各节点，计算出各字符出现的次数
create_node_array();
	for(i=0;i<MAX_SIZE;i++){//初始化一个有序队列
		
		entry=node_array[i];
		if((*entry).freq>0)
			//存在该字符
		{
			pq.push(entry);//入队列
			sum+=(*entry).freq;
			n_chars++;
		}
	}
	n_bits_per_char=ceil(log(n_chars)/log(2));//计算二进制编码的长度
	cout<<endl<<DEFAULT_TOTAL<<(sum*n_bits_per_char)<<endl;
}





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;
			}
		}
		entry=node_array[int('\n')];//记录每一行结尾处的回车符
		(*entry).freq++;
		(*entry).left=NULL;	
		(*entry).right=NULL;
		(*entry).parent=NULL;
	}
	
}

//根据优先队列构造huffman树
void huffman::create_huffman_tree(){
	node_ptr left,//暂存左儿子
		right,//暂存右儿子
		sum;//暂存两结点freq和的结点
	while(pq.size()>1){
		//取出两个freq最小的结点，构造树后将其和存在sum节点中,并将sum插回优先队列，直到优先队列只剩所有节点freq的和的节点
		//左儿子code为0，右为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).left=left;
		(*sum).right=right;
		(*sum).freq=(*left).freq+(*right).freq;
		(*right).parent=sum;
		(*left).parent=sum;
		pq.push(sum);
	}
}
//根据编码表构造Huffman树
void huffman::create_huffman_tree2(){
	string line;
	node_ptr current,left,right,Root;
	Root=new huffman_node;//建立根节点
	Root->left=NULL;
	Root->right=NULL;
	current=Root;
getline(in_file,line);//第一行为回车符
	while(getline(in_file,line)&&(line[0]!='*'||line[1]!='*'))
	{//读出文件一行
		for(unsigned j=1;j<line.length();j++){
			if (line[j]=='0')
			{
				if(!current->left){
					left=new huffman_node;
					left->code='0';
					left->left=NULL;
					left->right=NULL;
					left->parent=current;
					current->left=left;
				}
				current=current->left;
			}
			else	if (line[j]=='1')
			{
				if(!current->right){
					right=new huffman_node;
					right->code='1';
					right->left=NULL;
					right->right=NULL;
					right->parent=current;
					current->right=right;
				}
				current=current->right;
			}
			
		}//for
if(line[1]=='1'||line[1]=='0')//判断回车符编码的情况	
current->id=char(10);
else	
current->id=line[0];
current=Root;
	}//while
/*
current=Root;
current=current->right;
current=current->right;
current=current->left;
current=current->left;
current=current->right;
current=current->left;
	cout<<current->id;
*/
	while(getline(in_file,line)){
		for(unsigned j=0;j<line.length();){
				current=Root;
			while(current->left){
			
				if(line[j]=='0')
					current=current->left;		
				if(line[j]=='1')
					current=current->right;	
					j++;
			}
			cout<<current->id;
			out_file<<current->id;
		}
	}	
out_file.close();
}
//计算Huffman编码
void huffman::calculate_huffman_codes(){
const string HUFFMAN_CODES="Here are the huffman codes";
const string ENCODED_SIZE_MESSAGE="\n\n使用Huffman编码时编码长度为";

int total=0;
 string code;
 node_ptr entry;

 cout<<endl<<HUFFMAN_CODES<<endl;
 //对每个LEAF向ROOT遍历
 //根据得到的code计算出Huffman编码
 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;//对于每次遍历将新得到的code放在已得编码的前面,这样就相当于从根结点向下遍历
		 entry=(*entry).parent;
	 }
	 while((*entry).parent!=NULL);

		 cout<<code<<endl;
		 (*node_array[i]).code=code;
		 total+=code.length()*(*node_array[i]).freq;//计算出编码长度
 }
 }
cout<<ENCODED_SIZE_MESSAGE<<total<<endl;
}


void huffman::save_to_file(){
node_ptr entry;
string line;
in_file.close;
ifstream in_file2;
in_file2.open(in_file_name.c_str(),ios::in);//此处需修改 使得再次打开文件指向开头 将字符转换为huffman码输出

for(int i=0;i<MAX_SIZE;i++){
entry=node_array[i];
if((*entry).freq>0){

	out_file<<(char)i<<" "<<(*entry).code<<endl;
}
}
out_file<<"**"<<endl;
while(getline(in_file2,line)){
	for(unsigned j=0;j<line.length();j++){
		entry=node_array[(int)(line[j])];
		out_file<<(*entry).code;
	}
	entry=node_array[int('\n')];
	out_file<<(*entry).code;
}
out_file.close();
}


void huffman::RunHuffman(){
//保存编码

create_pq();
create_huffman_tree();
calculate_huffman_codes();
save_to_file();
}

void huffman::RunHuffmanReverse(){
//对文件遍历构建Huffman树，知道遇到**
//译码，从根节点向下遍历，到达树叶时输出字符，指针回到根节点重复之前过程，知道文件结束
create_huffman_tree2();
}

void main(){
	const string MESSAGE1="Please enter the in_file name";
	const string MESSAGE2="Please enter the out_file name";
string a1,a2,a3,a4;
cout<<MESSAGE1<<endl;
cin>>a1;
cout<<MESSAGE2<<endl;
cin>>a2;
huffman *H1=new huffman(a1,a2,1);

cout<<MESSAGE1<<endl;
cin>>a3;
cout<<MESSAGE2<<endl;
cin>>a4;
huffman *H2=new huffman(a3,a4,0);
}