huffmantree.cpp

是编译器我花了好几个礼拜才编好的确实难的这是个不错的编译器

// HuffmanTree.cpp: implementation of the CHuffmanTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "HuffmanTree.h"
#include "CMinHeap.h"

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

CHuffmanTree::CHuffmanTree()
{
	m_strConSent = "";
	m_strConReci = "";
	m_strConChar = "";
	m_nCharNum = 0;
}

CHuffmanTree::~CHuffmanTree()
{

}

/***********************************************************************
Void Analyze() 用于通过分析m_strConSent 来得到m_vecCharNum和m_strConChar
并建立字符相对应的权值节点，将相应指针赋值给m_vecPChar和m_vecForest
***********************************************************************/
void CHuffmanTree::Analyze(){

	int i=0,j=0;
	int conSentSize = m_strConSent.size();
	m_nCharNum = 0;

//	int conCharSize = 0;
//	int nTemCharNum = 0;
	m_strConChar = "";

	for(i=0;i<conSentSize;i++){							//用于判断每个字符
		//conCharSize = m_nCharNum;
		for(j=0;j<m_nCharNum;j++){						//和已记录的字符比较
			if(m_strConSent[i] == m_strConChar[j]){		//如果相等则该字符计数加1
				(m_arrCharProbability[j]) ++;
				break;
			}
		}
		if(j == m_nCharNum){							//如果该字符未记录
			m_strConChar += m_strConSent[i];			//则记录该字符
			m_arrCharProbability[m_nCharNum] = 1;		//并该字符计数加1
			m_nCharNum++;
		}
	}
	
	CBinTreNode<int> * pNodeTem = NULL;
	
	//m_vecPoiLeaf.clear();
	//m_vecForest.clear();
	//conCharSize = m_vecCharNum.size();

	for(i=0;i<m_nCharNum;i++){
		pNodeTem = new CBinTreNode<int>(m_arrCharProbability[i]);
		m_arrPoiLeaf[i] = pNodeTem;
		m_arrForest[i] = pNodeTem;
//		m_arrForest[i].m_nCharProbability = m_arrCharProbability[i];
	}

	
#if DEBUG == 1
	
	cout<<m_strConSent<<endl
		<<"m_nCharNum   "<<m_nCharNum<<endl;
	
	for(i = 0;i<m_nCharNum;i++){
		cout<<m_strConChar[i]<<"  "<<m_arrCharProbability[i]<<"  "
			<<m_arrPoiLeaf[i]->m_MData<<"  "
			<<m_arrPoiLeaf[i]->m_pParent<<"  "
			<<m_arrPoiLeaf[i]->m_pLefC<<"  "
			<<m_arrPoiLeaf[i]->m_pRigC<<"  "
			<<m_arrForest[i]->m_MData<<"  "
			<<m_arrForest[i]->m_pParent<<"  "
			<<m_arrForest[i]->m_pLefC<<"  "
			<<m_arrForest[i]->m_pRigC
			<<endl;
	}

#endif
}


void CHuffmanTree::HaffumEncode(){

	int i = 0,j = 0;
	
	for(i=0;i<m_nCharNum;i++){
		m_arrCharCode[i].clear();
	}

	if(m_nCharNum == 1) m_arrCharCode[0].push_front(0);

	CBinTreNode<int> * node1,*node2;
	CBinTreNode<int> * pForestNodePar = NULL;
	
	CMinHeap<CBinTreNode<int>*,Compare> theMinHeap(m_arrForest,m_nCharNum,MaxNum);

	for(i = 0;i<m_nCharNum - 1;i++){

		if(!theMinHeap.DelTop(node1) ) reportError("最小堆DelTop1错误",17);
		if(!theMinHeap.DelTop(node2) ) reportError("最小堆DelTop2错误",17);

		MergeTree(pForestNodePar,node1,node2);
		theMinHeap.Insert(pForestNodePar);
	}
	m_pRoot = m_arrForest[0];

	CBinTreNode<int> * pTem =NULL;

	for(i = 0;i<m_nCharNum;i++){
		pTem = m_arrPoiLeaf[i];
		while(pTem->m_pParent != NULL){
			if(pTem->m_pParent->m_pLefC == pTem)
				m_arrCharCode[i].push_front(0);
			else
				m_arrCharCode[i].push_front(1);
			pTem = pTem->m_pParent;
		}
	}

#if DEBUG == 1
	list<bool>::iterator myIter ;
	for(i = 0;i<m_nCharNum;i++){
		cout<<m_strConChar[i]<<":";
		myIter = m_arrCharCode[i].begin();
		while(myIter != m_arrCharCode[i].end()){
			cout<< *myIter;
			myIter++;
		}
		cout<<"    ";

	}
#endif

}

void CHuffmanTree::EncodeForm(){

	m_lisTranCode.clear();

	list<bool>::iterator myIter ;
	int i = 0,j = 0,k=0;
	for(i=0;i<m_strConSent.size();i++){
		for(j=0;j<m_nCharNum;j++){
			if(m_strConSent[i] == m_strConChar[j]){
				myIter = m_arrCharCode[j].begin();
				while(myIter != m_arrCharCode[j].end()){
					m_lisTranCode.push_back(*myIter);
					myIter++;
				}
				break;
			}
		}
	}

#if DEBUG == 1
	cout<<endl<<m_lisTranCode.size()<<endl;
	list<bool>::iterator myIter2 = m_lisTranCode.begin();
	cout<<endl;

	while(myIter2 !=  m_lisTranCode.end()){
			cout<< *myIter2;
			myIter2++;
	}
	cout<<"    ";

#endif

}


void CHuffmanTree::Encode(){
	Analyze();
	HaffumEncode();
	EncodeForm();

}

void CHuffmanTree::Decode(){

#if DEBUG == 1
	cout<<endl<<"原来的m_strConReci:"<<m_strConReci<<endl;
#endif

	
	int codeLenNow = 1;
	int i = 0,j = 0;
	m_strConReci = "";
	list<bool>::iterator myIterFront = m_lisTranCode.begin();	//未确定的编码的位置即回退位置
	list<bool>::iterator myIterCurrCode = myIterFront;			//当前比较的接收编码位置
	list<bool>::iterator myIterTem;								//字符表中的位置

	while(myIterFront != m_lisTranCode.end()){				//扫描收到的所有字符；
		for(i=0;i<m_nCharNum;i++){						//将现在的情况与第i个字符编码比较
			if(codeLenNow != m_arrCharCode[i].size()) continue;	//编码长度不同则不匹配
			myIterTem = m_arrCharCode[i].begin();
			for(j=0;j<codeLenNow;j++){					//比较接收码和字符编码
				if( *myIterCurrCode != *myIterTem) break;
				myIterCurrCode++;
				myIterTem++;
			}
			if(j == codeLenNow)	{						//如果匹配
				m_strConReci += m_strConChar[i];
				myIterFront = myIterCurrCode;
				codeLenNow = 1;
				break;
			}
			else{
				myIterCurrCode = myIterFront;
			}
		}
		codeLenNow++;
	}

#if DEBUG == 1
	cout<<endl<<"后来的m_strConReci: "<<m_strConReci<<endl;
#endif

}