hufuman.cpp

霍夫曼编码与解码

// Hufuman.cpp: implementation of the Hufuman class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Code.h"
#include "Hufuman.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Hufuman::Hufuman()
{

}

Hufuman::~Hufuman()
{

}

//在ht[1...k]中选择权值最小且parent为0的根节点，其序号用是s1，s2返回
void Hufuman::select(HuffmanTree ht, int k, int &s1, int &s2)
{
	int i,j;
	int minw = 32767;
	for (i=1; i<=k; i++)
	{
		if (ht[i].weight<minw && ht[i].parent==0)
		{
			j = i;
			minw = ht[i].weight;
		}
	}
	s1 = j;
	minw = 32767;
	for (i=1; i<=k; i++)
	{
		if (ht[i].weight<minw && ht[i].parent==0 && i!=s1)
		{
			j = i;
			minw = ht[i].weight;
		}
	}
	s2 = j;
}

int Hufuman::scan(char *s)
{
	int m = 1;
	int i = 0;
	while(s[i]!='\0')             //求叶节点的个数及相对应的权值
	{
		int flag=0;
		for(int j=0;j<m;j++)
			if(s[i]==m_char[j])
			{
				m_weight[j]++;
				flag=1;
				break;
			}
			else
				flag=0;
		if(flag==0)
		{
			m_char[m]=s[i];
			m_weight[m]=1;
			m++;
		}
		i++;
	}
	m_num = m-1;
	return m;  //返回叶节点数
}



void Hufuman::creatHuffmanTree(HuffmanTree ht, HuffmanCode hc, int weight[MAX], int str[MAX])
{
	int i,s1,s2;
	for (i=1;i<=2*m_num-1;i++)
	{
		ht[i].lchild = 0;
		ht[i].rchild = 0;
		ht[i].parent = 0;
		ht[i].weight = 0;
	}

	for (i=1;i<=m_num;i++)
	{
		ht[i].weight = m_weight[i];
	}

	for (i=m_num+1;i<=2*m_num-1;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;
	}

	for (i=0;i<=m_num;i++)
		hc[i].ch = str[i];
	//
}

void Hufuman::HuffmanEncoding(HuffmanTree ht, HuffmanCode hc)
{
	//根据霍夫曼树求霍夫曼编码表hc
	int c,p,i; //c,p分别指示ht中孩子和双亲的位置
	char cd[MAX]; //临时存放编码串
	int start; //指示编码在cd中的位置
	cd[m_num] = '\0'; //最后一位存结束符
	for (i=1;i<=m_num;i++)
	{
		start = m_num; //初始位置
		c = i; //从叶子节点ht[i]开始上溯
		while ((p = ht[c].parent)>0)
		{//ht[c]是ht[p]的左孩子，则生成0，否则1
			cd[--start] = (ht[p].lchild == c) ? '0' : '1' ;
			c = p;
		}
		strcpy(hc[i].bits, &cd[start]);
		hc[i].len = m_num - start;
	}

	
}

void Hufuman::Coding(HuffmanCode hc, char *str)
{
	//对str所代表的字符串编码并写入磁盘文件
	int i,j;
	FILE *fp;
	fp = fopen("codefile.txt","w");
//	ofstream fout;
//	fout.open("codefile.txt",ios::app);

	while (*str)
	{
		for (i=1;i<=m_num;i++)
		{
			if(hc[i].ch == *str)
			{
				for(j=0;j<hc[i].len;j++)
					fputc(hc[i].bits[j],fp);
				//	fout<<hc[i].bits[j];
					break;
			}
		}
		str++;
	}
	fclose(fp);
//	fout.close();
}

void Hufuman::TxtToCode(char *s)
{
	HuffmanTree ht;
//	HuffmanCode hc;
	scan(s);
	creatHuffmanTree(ht,m_hc,m_weight,m_char);
	HuffmanEncoding(ht,m_hc);
	Coding(m_hc,s);
}

char* Hufuman::decode(HuffmanCode hc)
{
	FILE *fp;
	char str[254];
//	char *p;
	static char cd[MAX+1];
	int i,j,cjs;
	int k = 0;
	fp = fopen("codefile.txt","r");
	while (!feof(fp))
	{
		cjs=0;
		for (i=0;i<=m_num && cjs==0 && !feof(fp); i++)
		{
			cd[i] =' ';
			cd[i+1] = '\0';
			cd[i] = fgetc(fp);
			for (j=0;j<=m_num;j++)
			{
				if (strcmp(hc[j].bits,cd)==0)
				{
					str[k] = hc[j].ch;
					k++;
					cjs = 1;
					break;
				}
			}
		}
	}
	str[k] = '\0';
//	p = str;
	return str;
}

char* Hufuman::CodeToTxt()
{
	char *s;
	s = decode(m_hc);
	return s;
}

CString Hufuman::getScan(int i)
{
	CString str;
	CString temp;
	temp.Format("%d",m_weight[i]);
	str = (CString)m_hc[i].ch + "       " + temp;
	return str;
}

int Hufuman::getNum()
{
	return m_num;
}

CString Hufuman::getHc(int i)
{
	CString str;
	str = (CString)m_hc[i].ch + "       " ;
	for (int j=0;j<=m_hc[i].len;j++)
	{
		str += (CString)m_hc[i].bits[j];
	}
	return str;
}

void Hufuman::creatHCfile()
{
	int i,j;
/*	CString temp;
	CStdioFile mFile(_T("hc.txt"), CFile::modeWrite|CFile::modeCreate);
	for (i=0;i<=m_num;i++)
	{
		mFile.Write(&m_hc[i].ch,2);
		for (j=0;j<=m_hc[i].len;j++)
		{
			mFile.Write(&m_hc[i].bits[j],2);
		}
		temp.Format("%d %d",m_hc[i].len,m_hc[i].start);
		mFile.WriteString(temp);	
	}
	*/
	CFile mFile; 
	mFile.Open("hc.txt", CFile::modeCreate|CFile::modeNoTruncate|CFile::modeWrite);
	CArchive ar(&mFile, CArchive::store);
	ar<<m_num;
	for (i=0;i<=m_num;i++)
	{
		ar<<m_hc[i].ch;
		ar<<m_hc[i].len;
		ar<<m_hc[i].start;
		for (j=0;j<=m_hc[i].len;j++)
		{
			ar<<m_hc[i].bits[j];
		}
	}
	ar.Close();
	mFile.Close();

}

void Hufuman::readHCFile(CString filename)
{
	int i,j;
	CFile mFile; 
	if(mFile.Open(filename,CFile::modeRead)==0)
		return;
	CArchive ar(&mFile,CArchive::load);
	ar>>m_num;
	for (i=0;i<=m_num;i++)
	{
		ar>>m_hc[i].ch;
		ar>>m_hc[i].len;
		ar>>m_hc[i].start;
		for (j=0;j<=m_hc[i].len;j++)
		{
			ar>>m_hc[i].bits[j];
		}
	}
	ar.Close();
	mFile.Close(); 
}


bool Hufuman::compareFile(CString file1, CString file2)
{
	FILE *fp1,*fp2;
	fp1 = fopen(file1,"r");
	fp2 = fopen(file2,"r");
	while (!feof(fp1)||!feof(fp2))
	{
		if (fgetc(fp1) != fgetc(fp2))
		{
			return false;
		}
	}
	return true;
}