Question

用C++实现哈夫曼编码译码

统计字符串长度和各字符频度，编码译码，打印哈夫曼树

Answer 1

#include <iostream>

using namespace std;

#define MAX_FILE 5000//假设的文件最大长度
#define MAXLIST 256//最大MAP值
#define MAX_HOFFMAN_LENGTH 50//哈夫曼编码长度
char dictionary[MAXLIST][2]={0};//Hash映射,[][0]为权值,[][1]为字符
char fileContent[MAX_FILE];//处理的字符串大小
int Hoffman[MAXLIST][MAX_HOFFMAN_LENGTH]={2};//哈夫曼编码序列
char HoffmanList[MAXLIST]={0};//哈夫曼编码对应的字符有序序列
char HoffFileCode[MAX_FILE]={0};//哈夫曼编码字符串序列
char HoffFile[MAX_FILE]={0};
//编码到假设的文件的哈夫曼压缩格式： 依次存储 原字符串长度(1字节存储:可扩展到2字节)、哈夫曼编码数(1字节)、每个哈夫曼编码的长度序列、每个哈夫曼编码对应的字符序列、编码过的哈夫曼字符串

char GetFile[MAX_FILE]={0};//解码序列

void ShellSort(char pData[MAXLIST][2],int Count)//Shell排序，用于准备有序化要构造的编码权值构造哈夫曼树做准备
{
int step[4]={9,5,3,1};//增量序列

int iTemp,cTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k=step[i];
s=-k;
for(int j=k;j<Count;j++)
{iTemp=pData[j][0];
cTemp=pData[j][1];
w=j-k;
if(s==0)
{
s=-k;
s++;
pData[s][0]=iTemp;
pData[s][1]=cTemp;
}
while((iTemp<pData[w][0])&&(w>=0)&&(w<=Count))
{
pData[w+k][0]=pData[w][0];//权值交换
pData[w+k][1]=pData[w][1];//字符交换
w=w-k;
}
pData[w+k][0]=iTemp;
pData[w+k][1]=cTemp;
}
}
}

struct TNode//哈夫曼树结点
{
TNode* pNode;
TNode* lNode;
TNode* rNode;
char dictionary;
char weight;
TNode(char dic,char wei)
{
pNode=0;
lNode=0;
rNode=0;
dictionary=dic;
weight=wei;
}
};

struct LNode//链表结点,用于存储哈夫曼树结点,进而构造哈夫曼树(保证每一步链表结点包含的哈夫曼结点都是有序的)
{
LNode* prev;
LNode* next;
TNode* tnode;
LNode()
{
prev=next=0;
tnode=0;
}
};

int len=0;//哈夫曼编码数
int deep=-1;//深度
void Preorder(TNode * p);//前序遍历
void byLeft(TNode*p)//经由左结点
{
deep++;
Hoffman[len][deep]=0;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void byRight(TNode*p)//经由右结点
{

deep++;
Hoffman[len][deep]=1;
Preorder(p);

Hoffman[len][deep]=2;
deep--;
}
void Preorder(TNode * p)
{

if(p->lNode!=0)//当左子结点非空则遍历
{

byLeft(p->lNode);
}
if(p->rNode!=0)//当右子结点非空则遍历
{
byRight(p->rNode);
}

if((p->lNode==0)&&(p->rNode==0))//当左右结点都为空，则增加哈夫曼编码数到另一个记录
{

Hoffman[len][deep+1]=2;
int i=0;
for(;Hoffman[len][i]!=2;i++)
{
Hoffman[len+1][i]=Hoffman[len][i];
}
Hoffman[len+1][i]=2;

HoffmanList[len]=p->dictionary;

len++;
}

}

char generateOne(int k)//产生k个连续1的二进制串,比如111,1111,111111,用于编码进假设的文件
{
char c=0;
for(;k!=0;k--)
{
c|=(1<<(k-1));

}
return c;
}

int compareBits(char b1,char b2,char c,int l,int d)//判断由 [b1,b2] 组成的16位二进制数以d为起点,是否是长度为l的c二进制串（哈夫曼编码）的前缀
{
unsigned __int8 t=(((((0x00ff&b1)<<8)|(0x00ff&b2))>>(8-d))&0x00ff);
return (((t)&((generateOne(l)<<(8-l))&0xff))==((c<<(8-l))&0xff));
}

int main()
{

/* 或许假定的文件字符串向量中的字符串 */
cout<<"请输入要压缩的字符串：";
cin>>fileContent;

cin.get();
unsigned short fileLen=0;

/* Hash进dictionary */
for(int i=0;fileContent[i]!='\0';i++,fileLen++)
{

++dictionary[fileContent[i]][0];
dictionary[fileContent[i]][1]=fileContent[i];
}
int len=0;

/* 把Hash了的dictionary向前靠拢 */

{
for(int i=0;i!=MAXLIST;i++)
{

if(dictionary[i][0]!=0)
{
dictionary[len][0]=dictionary[i][0];
dictionary[len][1]=dictionary[i][1];
len++;
}
}
}
cout<<"哈夫曼编码个数:"<<len<<endl;
/* 对dictionary按权值进行排序 */

ShellSort(dictionary,len);

/* 构造链表,链表中放有序dictionary权值的树结点 */
LNode* head=new LNode,*p=head;
head->next=new LNode;
TNode *tempTNode=new TNode(dictionary[0][1],dictionary[0][0]);
head->tnode=tempTNode;

{
for(int i=0;i!=len-1;i++)
{
p->next->prev=p->next;
p=p->next;

p->next=new LNode;
tempTNode=new TNode(dictionary[i+1][1],dictionary[i+1][0]);
p->tnode=tempTNode;
}
}
delete p->next;
p->next=0;

/* 每次最小权值的前面两个链表结点中的树结点组成一个子树,子树有合权值,子数的根按权值排序进链表*/

for(p=head;p->next!=0;)
{

p->tnode->pNode=new TNode('\0',(p->tnode->weight)+(p->next->tnode->weight));
p->next->tnode->pNode=p->tnode->pNode;
p->tnode->pNode->lNode=p->tnode;
p->tnode->pNode->rNode=p->next->tnode;
head=p->next;
delete p;
p=head;
p->tnode=p->tnode->pNode;
for(LNode* t=head;t->next!=0;t=t->next)
{
if(t->tnode->weight>t->next->tnode->weight)
{
TNode* k=t->tnode;
t->tnode=t->next->tnode;
t->next->tnode=k;
}
}

}

int code[500],h=0;

/* 前序遍历构造哈夫曼编码 */
Preorder(p->tnode);

{
for(int i=0;i!=len;i++)
dictionary[HoffmanList[i]][0]=i;
}
/* 存储字符串的哈夫曼压缩编码串,并且打包文件格式 */
int codeLen=0,total=0;
{
for(int i=0;i!=fileLen;i++)
{
int j=dictionary[fileContent[i]][0];
for(int k=0;Hoffman[j][k]!=2;k++)
{

HoffFileCode[codeLen]|=(Hoffman[j][k]<<(7-total%8));
code[h++]=Hoffman[j][k];

if(((total+1)%8)==0)
{
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
codeLen++;
}
total++;
}

}
}
HoffFile[1+len*3+1+codeLen]=HoffFileCode[codeLen];
HoffFile[0]=(fileLen);

/* 解压缩假定的文件HoffFile成为原字符串序列 */
cout<<"哈夫曼编码序列:\n";
HoffFile[1]=len;

{
for(int i=0,j=0;i!=len;i++,j=0)
{

for(;Hoffman[i][j]!=2;j++);

HoffFile[i+2]=j;
HoffFile[i+2+2*len]=HoffmanList[i];

for(int k=0;k!=j;k++)
{

cout<<Hoffman[i][k];
HoffFile[i+2+len]|=(Hoffman[i][k]<<(j-1-k));

}
cout<<":"<<HoffmanList[i]<<endl;

}
}

{
for(int i=0,j=0;i!=(HoffFile[0]&0xff);i++)
{
for(int k=0;k!=HoffFile[1];k++)
{

char l=HoffFile[2+k],d=j%8,b1=HoffFile[j/8+2+HoffFile[1]*3],b2=HoffFile[j/8+1+2+HoffFile[1]*3];

char c=HoffFile[HoffFile[1]+2+k];

if(compareBits(b1,b2,c,l,d))
{

j+=HoffFile[2+k];

GetFile[i]=HoffFile[2+HoffFile[1]*2+k];

break;

}
}

}
}
{
cout<<"哈夫曼压缩后二进制序列:"<<endl;
for(int i=0;i!=h;i++)
{
cout<<code[i];
if((i+1)%8==0)
cout<<" ";
}
}
cout<<endl;

{
cout<<"哈夫曼压缩打包假定文件格式二进制的文本体现:";
cout<<endl;
for(int i=0;i!=HoffFile[0]+HoffFile[1]*3;i++)
{
cout<<HoffFile[i];
}
cout<<endl;
}

cout<<"原字节数为:"<<fileLen<<endl;
cout<<"压缩后字节数为:"<<(h)/8+1<<endl;
cout<<"压缩率为"<<((h/8.0+1)/fileLen)*100<<"%"<<endl;

{

cout<<"字符串字节数为:"<<(HoffFile[0]&0xff)<<endl;
cout<<"字符串解压序列为:";
for(int i=0;i!=(HoffFile[0]&0xff);i++)
{
cout<<GetFile[i];
}

cout<<endl;
cin.get();
}
return 1;
}

Answer 2

#include<iostream.h>
struct HaffNode
{
int weight;
int parent;
int lchild;
int rchild;
};
struct HaffCode
{
int bit[10000];
int start;
int weight;
};
void Haffman(int w[],int n,HaffNode ht[],HaffCode hc[])
{
int i,j,m1,m2,x1,x2;
for(i=0;i<2*n-1;i++)
{
if(i<n)
ht[i].weight=w[i];
else
ht[i].weight=0;
ht[i].parent=0;
ht[i].lchild=-1;
ht[i].rchild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=1000;
x1=x2=0;
for(j=0;j<n+i;j++)
{
if(ht[j].weight<m1&&ht[j].parent==0)
{
m2=m1;
x2=x1;
m1=ht[j].weight;
x1=j;
}
else if(ht[j].weight<m2&&ht[j].parent==0)
{
m2=ht[j].weight;
x2=j;
}
}
ht[x1].parent=n+i;
ht[x2].parent=n+i;
ht[n+i].weight=ht[x1].weight+ht[x2].weight;
ht[n+i].lchild=x1;
ht[n+i].rchild=x2;
}
HaffCode cd;
int child,parent;
for(i=0;i<n;i++)
{
cd.start=n-1;
cd.weight=ht[i].weight;
child=i;
parent=ht[child].parent;
while(parent!=0)
{
if(ht[parent].lchild==child)
cd.bit[cd.start]=0;
else
cd.bit[cd.start]=1;
cd.start--;
child=parent;
parent=ht[child].parent;
}
for(j=cd.start+1;j<n;j++)
hc[i].bit[j]=cd.bit[j];
hc[i].start=cd.start;
hc[i].weight=cd.weight;
}
}
void main()
{
int w[1000];
int n,i,j,a;
cout<<"输入个数："<<endl;
cin>>n;
cout<<"输入数："<<endl;
for(a=0;a<n;a++)
cin>>w[a];

HaffNode* ht=new HaffNode[2*n-1];
HaffCode* hc=new HaffCode[n];
Haffman(w,n,ht,hc);
for(i=0;i<n;i++)
{
cout<<"weight="<<hc[i].weight<<"code=";
for(j=hc[i].start+1;j<n;j++)
cout<<hc[i].bit[j];
cout<<endl;
}
}
这个应该很容易理解的