huffmancode.cpp

对符号进行huffman编码和解码的程序

// HuffmanCode.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanCode.h"

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

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

Huffman::Huffman()   
{   
char   name;   
int   i=0;   
cout<<endl<<"Please   input   the   number   of   codes(if   M<=0   to   use   defualt):";   
cin>>M;   
if(M>0)   
{   
index=2*M-2;   
tree=new   node[2*M-1];   
code=new   int[2*M];   
nodes=new   elem[M];   
for(i=0;i<M;i++)   
{   
cout<<endl<<"Please   input   name:";   
cin>>nodes[i].name;   
cout<<"Please   input   weight:";   
cin>>nodes[i].weight;   
}   
}   
else   
{   
M=5;   
index=2*M-2;   
tree=new   node[2*M-1];   
code=new   int[2*M];   
nodes=new   elem[M];   
nodes[0].name='a';   
nodes[0].weight=2;   
nodes[1].name='b';   
nodes[1].weight=54;   
nodes[2].name='c';   
nodes[2].weight=16;   
nodes[3].name='d';   
nodes[3].weight=9;   
nodes[4].name='e';   
nodes[4].weight=34;   
}   
//initialize   nodes[i].codes   
for(i=0;i<M;i++)   
{   
nodes[i].code=new   int[2*M];   
}   
//initialize   code     
for   (i=0;i<2*M;i++)   
code[i]=-1;   
//sort   
for(i=0;i<M-1;i++)   
{   
for(int   j=i+1;j<M;j++)   
{   
if(nodes[j-1].weight>nodes[j].weight)   
{   
nodes[j-1].weight=nodes[j-1].weight+nodes[j].weight;   
nodes[j].weight=nodes[j-1].weight-nodes[j].weight;   
nodes[j-1].weight=nodes[j-1].weight-nodes[j].weight;   
name=nodes[j-1].name;   
nodes[j-1].name=nodes[j].name;   
nodes[j].name=name;   
}   
}   
}   
for(i=0;i<M;i++)   
{   
tree[i].elementary=nodes[i];   
tree[i].weight=nodes[i].weight;   
tree[i].leftson=NULL;   
tree[i].rightson=NULL;   
}   

}   

Huffman::~Huffman()   
{   
//free   the   recource     
delete   []tree;   
delete   []code;   
for(int   i=0;i<M;i++)   
{   
delete   []nodes[i].code;   
}   
delete   []nodes;   
} 

void   Huffman::MakeupTree()   
{
node   node0,node1,node2;   

if(index==2*M-2)flag=M;   
if(index>0)   
{   
node0.weight=tree[0].weight+tree[1].weight;   
node1=tree[0];   
node2=tree[1];   
tree[index]=node1;   
node0.leftson=&tree[index--];   
tree[index]=node2;   
node0.rightson=&tree[index--];   
for(int   i=0;i<flag-2;i++)   
{   
tree[i]=tree[i+2];   
}   
flag--;   
for(i=0;i<flag-1;i++)   
{   
if(node0.weight<tree[i].weight)   
break;   
}   
for(int   j=flag-1;i<j;j--)   
{   
tree[j]=tree[j-1];   
}   
tree[i]=node0;   
MakeupTree();   
}   
return;   
}   

void   Huffman::coding(int   sign,node   *head)   
{   
if(head!=NULL)   
{   
code[sign]=0;   
coding(sign+1,head->leftson);   
code[sign]=1;   
coding(sign+1,head->rightson);   
}   
else   
{   

return;   
}   
if(head->rightson==NULL)   
{   
for(int   i=0;i<=sign;i++)   
head->elementary.code[i]=code[i];   
head->elementary.code[sign]=-1;   
code[sign]=-1;   
for(int   j=0;head->elementary.name!=nodes[j].name;j++);   
for(i=0;code[i]>=0;i++)   
{   
nodes[j].code[i]=code[i];   
}   
nodes[j].code[i]=-1;   
//cout   
cout<<endl<<head->elementary.name<<":";   
//cout   
for(i=0;head->elementary.code[i]!=-1;i++)   
cout<<head->elementary.code[i];   
return;   
}   
}   

void   Huffman::doCode()   
{   
MakeupTree();   
coding(0,&tree[0]);   
}   

elem*   Huffman::deCode(int*matchingCode)//the   end   of   matchingCode   is   integer   -1     
{   
bool   judge=false;   
for(int   i=0;i<M&&judge==false;i++)   
{   
for(int   j=0;matchingCode[j]==nodes[i].code[j]&&matchingCode[j]>=0;j++);   
if(matchingCode<0)judge=true;   
}   
if(judge)return   &nodes[i];   
else   return   NULL;   
}