Question

霍夫曼编码C++语言显示编码和平均码长的.能执行的

Answer 1

#include<iostream>
using namespace std;
struct HaffNode
{
int weight;
int parent;
int lchild;
int rchild;
};
struct HaffCode
{
int bit[100];
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;
}
}
int main()
{
int w[]={4,2,6,8,3,2,1};
int n=7,i,j;
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;
}
system("pause");
return 0;
}