c++实现的哈夫曼编码和解码（源代码）

#include "HuffMan.h" string CHufffMan::HuffDeCode(const char *buffer,unsigned int ilen,int ipos) { memcpy(m_cFreq,buffer,CHAR_NUM*sizeof(unsigned int)); CreateQueue(); CreateHuffManTree(); return DeCode(buffer+=CHAR_NUM*sizeof(unsigned int),ilen-CHAR_NUM*sizeof(unsigned int),ipos); } void CHufffMan::StatisCharFreq(const char *buffer,unsigned int ilen) { memset(m_cFreq,0,CHAR_NUM*sizeof(unsigned int)); for (unsigned int i=0;i<ilen;++i) { m_cFreq[(unsigned char)buffer[i]]++; } } void CHufffMan::CreateQueue() { m_FreqQue.clear(); for (int i=0;i<CHAR_NUM;++i) { if (m_cFreq[i]) { m_FreqQue.insert(make_pair(i,m_cFreq[i])); } } } void CHufffMan::CreateHuffManTree() { int iNode=m_FreqQue.size(); //初始化哈夫曼树,共有2n-1个节点 delete[] m_HuffTree; m_HuffTree=new HuffNode[iNode*2-1]; m_vValueKey.clear(); //初始化叶子节点 map<char,unsigned int>::iterator iter=m_FreqQue.begin(); for (int i=0;iter!=m_FreqQue.end();++i,++iter) { m_HuffTree[i].weight=iter->second; m_HuffTree[i].value=iter->first; m_HuffTree[i].code=0; m_vValueKey[iter->first]=i; } //构造哈夫曼树haffTree的n-1个非叶结点 for(int i=0;i<iNode-1;i++) { int m1=100000,m2=100000; //Maxvalue=10000;(就是一个相当大的数) int x1=0,x2=0; //x1、x2是用来保存最小的两个值在数组对应的下标 //循环找出所有权重中，最小的二个值 for(int j=0;j<iNode+i;j++) { if(m_HuffTree[j].weight<m1&&!m_HuffTree[j].bflag) { m2=m1; x2=x1; m1=m_HuffTree[j].weight; x1=j; } else if(m_HuffTree[j].weight<m2&&!m_HuffTree[j].bflag) { m2=m_HuffTree[j].weight; x2=j; } } //将找出的两棵权值最小的子树合并为一棵子树 m_HuffTree[x1].bflag=true; m_HuffTree[x2].bflag=true; m_HuffTree[x1].code=0; m_HuffTree[x2].code=1; m_HuffTree[iNode+i].weight=m_HuffTree[x1].weight+m_HuffTree[x2].weight; m_HuffTree[iNode+i].lchild=x1; m_HuffTree[iNode+i].rchild=x2; m_HuffTree[x1].parent=iNode+i; m_HuffTree[x2].parent=iNode+i; } } string CHufffMan::Code(const char* buffer,unsigned int ilen,int &iout) { string strContent=GetHuffTree(); string str; for (unsigned int i=0;i<ilen;++i) { map<char,int>::iterator iter=m_vValueKey.find(buffer[i]); if (iter!=m_vValueKey.end()) { str+=GetCodeStr(iter->second); while (str.size()>7) { bitset<8> bit(str.substr(0,8)); strContent+=static_cast<char>(bit.to_ulong());; str.erase(0,8); } } } iout=0; if (!str.empty()) { iout=8-str.size(); str.insert(str.size(),iout,'0'); bitset<8> bit(str); strContent+=static_cast<char>(bit.to_ulong()); } return strContent; } string CHufffMan::GetCodeStr(int iNode) { string str=ToString(m_HuffTree[iNode].code); while (m_HuffTree[iNode].parent!=-1) { iNode=m_HuffTree[iNode].parent; if (m_HuffTree[iNode].code!=-1) { str+=ToString(m_HuffTree[iNode].code); } } reverse(str.begin(),str.end()); return str; } string CHufffMan::GetHuffTree() { char *buffer=new char[CHAR_NUM*sizeof(unsigned int)]; memset(buffer,0,CHAR_NUM*sizeof(unsigned int)); memcpy(buffer,m_cFreq,CHAR_NUM*sizeof(unsigned int)); string str; str.insert(0,buffer,CHAR_NUM*sizeof(unsigned int)); delete[] buffer; return str; } string CHufffMan::DeCode(const char *buffer,int ilen,int ipos) { string str=BufferToBinary(buffer,ilen); m_Check=&m_HuffTree[GetRoot()]; string stm; for (unsigned int i=0;i<str.size()-ipos;++i) { char cc; if(CheckChar(str[i],cc)) { stm+=cc; m_Check=&m_HuffTree[GetRoot()]; } } return stm; } bool CHufffMan::CheckChar(char ch,char &cc) { if (m_Check->lchild==-1&&m_Check->rchild==-1) { cc=m_Check->value; return true; } if (ch=='0') { m_Check=&m_HuffTree[m_Check->lchild]; } else { m_Check=&m_HuffTree[m_Check->rchild]; } if (m_Check->lchild==-1&&m_Check->rchild==-1) { cc=m_Check->value; return true; } return false; } int CHufffMan::GetRoot() { int iroot=0; int index=m_HuffTree[0].parent; while (index!=-1) { iroot=index; HuffNode *pNode=&m_HuffTree[index]; index=pNode->parent; } return iroot; }