haffcode.cpp

本程序用于解决数据信息（主要是字符串信息）的哈夫曼编码

// HaffCode.cpp: implementation of the CHaffCode class.
//////////////////////////////////////////////////////////////////////

#include "HaffCode.h"
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <iomanip>

using namespace std;

CHaffCode::CHaffCode()                  //编码
{
	num = 0;
	for(int i=0;i<100;i++)
	{
		ht[i].weight = 0;               //初始化权值
		ht[i].ch = 0;
		ht[i].lch = -1;                 //初始化左孩子
		ht[i].rch = -1;                 //初始化右孩子
		ht[i].pa = -1;                  //初始化双亲
	}
	
	for(i=0;i<256;i++)
		weight[i] = 0;
	
	for(i=0;i<50;i++)
	{
		hc[i].weight = 0;
	}
	
	cout<<"Please input the source file name:"; 
	gets(ifname); 
	ifstream infile(ifname); 
	if(infile.eof()) 
	{ 
		cout<<"Source file open error!"<<endl;; 
		throw 1;                      //异常处理
	}
	infile.close();                   //输入文件结束
	
	cout<<"Please input the destination file name:"; 
	gets(ofname);                     //得到编码地址
	
	cout<<"Please input the Haffman code file name:"; 
	gets(buf);                        //得到Haffman编码地址
	
	cout<<"Please input the decode file name:"; 
	gets(dfname);                     //得到解码文件地址
}

CHaffCode::~CHaffCode()               //析构函数
{
}

void CHaffCode::encode()
{
	count();                           //计算每个字符的个数
	hafftree();                        //根据权值构造哈夫曼树
	compile();                         //将Haffman树转化成Haffman编码
	
	ifstream infile(ifname);
	ofstream outfile(ofname);
	
	char ch;
	int i;
	
	while(!infile.eof())
	{
		ch=infile.get();
		for(i=0;i<num;i++)
		{
			if(ch == hc[i].ch)
			{
				for(int j=hc[i].start+1;j<maxbit;j++)
					outfile<<hc[i].bit[j];
			}
		}
	}
	infile.close();
	outfile.close();
}

void CHaffCode::decode()               //解码
{
	ofstream outfile(dfname);
	char ch;
	
	int t = 0;

	//找出根节点
	while (-1 != ht[t].pa) 
	{
		t++;
	}
	
	int i = t;
	
	ifstream infile(ofname);
	while(infile.get(ch))
	{
		if(ch == '1')
		{
			i=ht[i].rch;
		}
		else if(ch == '0')
		{
			i=ht[i].lch;
		}
		if(ht[i].rch == -1)                     //输出每个叶子节点的字符
		{
			cout<<ht[i].ch;
			outfile<<ht[i].ch;
			i = t;                              //继续从根节点处开始
		}
	}
	cout<<endl;
	infile.close();
	outfile.close();	
}

void CHaffCode::printHafftree()
{
	cout<<"HaffmanTree:"<<endl;
	cout<<setw(3)<<"num"<<" "<<setw(5)<<"value"<<"  "<<setw(6)<<"weight"<<"  "<<setw(6)<<"parent"<<"  "
		<<setw(6)<<"lchild"<<"  "<<setw(6)<<"rchild"<<endl;
	int i = 0;
	while(ht[i].weight)
	{
		cout<<setw(3)<<i<<" "<<setw(5)<<ht[i].ch<<"  "<<setw(6)<<ht[i].weight<<"  "<<setw(6)<<ht[i].pa<<"  "
			<<setw(6)<<ht[i].lch<<"  "<<setw(6)<<ht[i].rch<<endl;
		i++;
	}
}

void CHaffCode::hafftree()
{
	int k = 0;
	for(int i=0;i<256;i++)
	{
		if (weight[i]) 
		{
			ht[k].ch = char(i);
			ht[k].weight = weight[i];
			k++;
			num++;            //存储编码数
		}
	}
	
	int flag = 0;             //找到次小的标志
	int j,m1,m2,x1,x2;
	int t = 0;
	for(i=0;i<num;i++)
	{
		flag = 0;             //标记
		m1 = m2 = 1000;
		x1 = x2 = 0;
		for(j=0;j<num+i;j++)                //找到权值最小的2个结点x1,x2
		{
			if (ht[j].weight<m1&&-1 == ht[j].pa) 
			{
				m2 = m1;
				x2 = x1;
				m1 = ht[j].weight;          //将其权值赋给m1
				x1 = j;
				flag++;
			}
			else if (ht[j].weight<m2&&-1 == ht[j].pa)
			{
				m2 = ht[j].weight;
				x2 = j;
				flag++;
			}
		}
		if(flag>1)
		{
			ht[x1].pa = num+t;              //将x1和x2合并，则x1和x2的双亲是num+t
			ht[x2].pa = num+t;
			ht[num+t].weight = ht[x1].weight+ht[x2].weight;//num+t的权值是x1的权值加上x2的权值
			ht[num+t].lch = x1;             //num+t的左孩子是x1
			ht[num+t].rch = x2;             //num+t的右孩子是x2
			ht[num+t].pa = -1;                        
			t++;
		}
	}
}

void CHaffCode::compile()                   //将Haffman树转化成Haffman编码
{
	ofstream outfile(buf);
	
	code *cd = new code;                   //新建立栈顶指针
	int child,parent;
	int t = 0;
	
	for(int i=0;i<num;i++)
	{
		cd->ch = ht[i].ch;
		cd->start = maxbit-1;             //maxbit是要编码的数据内码的最大长度
		cd->weight = ht[i].weight;
		child = i;
		parent = ht[child].pa;
		
		while (-1 != parent)
		{
			if(ht[parent].lch == child)  //如果双亲结点的左孩子等于child
				cd->bit[cd->start] = 0;  
			else
				cd->bit[cd->start] = 1;
			cd->start--;                 //栈顶指针减1
			child = parent;
			parent = ht[child].pa;
		}
		
		hc[t].start = cd->start;         //输出
		hc[t].weight = cd->weight;
		hc[t].ch = cd->ch;
		
		outfile<<char(hc[t].ch)<<" ";
		
		for(int j = cd->start+1;j<maxbit;j++)//输出编码
		{
			hc[t].bit[j] = cd->bit[j];
			outfile<<hc[t].bit[j];
		}
		outfile<<endl;
		
		t++;
	}
	
	outfile.close();
	delete[] cd;
}

void CHaffCode::count()             //计算每个字符的个数
{
	ifstream infile(ifname);
	char ch;
	while(infile.get(ch))
		weight[ch]++;               //字符的个数加1
	infile.close();
}

void CHaffCode::printHaffCode()
{
	cout<<"HaffmanCode:"<<endl;
	cout<<setw(5)<<"value"<<"  "<<setw(6)<<"weight"<<"  "<<setw(6)<<"code"<<endl;
	int i = 0;
	while(hc[i].weight)
	{
		cout<<setw(5)<<hc[i].ch<<"  "<<setw(6)<<hc[i].weight<<" ";
		for(int j=hc[i].start+1;j<maxbit;j++)
			cout<<hc[i].bit[j];
		cout<<endl;
		
		i++;
	}
}