爱华网Code:
#include<iostream>
#include<string>
using namespace std;
typedef struct{
int weight;
int parent,lchild,rchild;
}HFNode;
void Select(HFNode *HT,int n,int &s1,int&s2){//在前n个数组中，选择parent为-1且weight最小的两个结点
int temp=100;
for(int i=0;i<n;i++)
if(temp>HT[i].weight&&HT[i].parent==-1){
s1=i;
temp=HT[i].weight;
}
temp=100;
for(int i=0;i<n;i++)
if(i!=s1&&temp>HT[i].weight&&HT[i].parent==-1){
s2=i;
temp=HT[i].weight;
}
}
void HuffmanCode(HFNode *&HT,int *w,intn){ //霍夫曼编码
int m=2*n-1,i,s1,s2;
HT=(HFNode *)malloc(m*sizeof(HFNode));
for(i=0;i<n;i++){//初始化前n个霍夫曼结点
HT[i].weight=w[i];
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
for(i;i<m;i++){//初始化后n-1个霍夫曼结点
HT[i].weight=0;
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}
for(i=n;i<m;i++){//建立霍夫曼树
Select(HT,i,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
for(intj=0;j<n;j++){//从叶子结点到根逆向求每个根节点的霍夫曼编码
char *cd=(char*)malloc(n*sizeof(n));
int k=0,c=j;
while(HT[c].parent!=-1){
if(HT[HT[c].parent].lchild==c)cd[k]='0';
if(HT[HT[c].parent].rchild==c)cd[k]='1';
k++;
c=HT[c].parent;
}
cout<<"第"<<j+1<<"个元素的霍夫曼编码为：";
for(intl=k-1;l>=0;l--)
cout<<cd[l];
cout<<endl;
free(cd);
}
}
void HuffmanEncode(HFNode *HT,int n,string s){//霍夫曼解码
int m=2*n-2;
for(inti=0;i<s.length();i++){
if(s[i]=='0'){
m=HT[m].lchild;
}
else
m=HT[m].rchild;
if(HT[m].lchild==-1&&HT[m].rchild==-1){
cout<<HT[m].weight<<endl;
m=2*n-2;
}
}
}
int main(){ //测试
int n;
string s;
cout<<"请输入待编码元素的个数：";
cin>>n;
int *w=(int *)malloc(n*sizeof(int));
cout<<"请输入待编码元素的权值：";
for(int i=0;i<n;i++)
cin>>w[i];
HFNode *HT;
HuffmanCode(HT,w,n);
cout<<"请输入待解码：";
cin>>s;
cout<<"解码结果为："<<endl;
HuffmanEncode(HT,n,s);
system("pause");
return 0;
}
