问题：事情总是这样，当你明白时，很简单，但当你不会时，又好像觉得自己怎么那么笨。。。
huffman算法关键是选择两个最小的数时不要弄错了。
刚开始看时，真的很吃力，都不敢相信自己居然把huffman译码也做出来了。
代码：
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
int s1,s2;
typedef struct huffmanNode
{
int weight;
int parent;
int lchild;
int rchild;
}*HuffmanTree;
typedef struct weight
{
char c;
int wt;
}*wt;
typedef char** HuffmanCode;
void select(HuffmanTree ht,int i);
void CreateHT(HuffmanTree &ht,HuffmanCode &code,wt w,int n) //编码
{
int m,i,j,start;
char *cd;
if(n<1)
return;
m=2*n-1;
ht=(HuffmanTree)malloc((m)*sizeof(struct huffmanNode));
for(i=0;i<n;i++)
{
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].parent=0;
ht[i].weight=w[i].wt;
}
for(j=i;j<m;j++)
{
ht[j].lchild=0;
ht[j].rchild=0;
ht[j].parent=0;
ht[j].weight=0;
}
for(i=n;i<m;i++) //构造哈夫曼树
{
select(ht,i-1);
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;
}
code=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
for(int k=0;k<n;k++)
{
start=0;
for(int p=k,f=ht[k].parent;f!=0;p=f,f=ht[f].parent)
{
if(ht[f].lchild==p)cd[start++]='0';
else cd[start++]='1';
}
cd[start]='\0';
code[k]=(char*)malloc((start)*sizeof(char));
strcpy(code[k],cd);
}
free(cd);
}
void select(HuffmanTree ht,int i)
{
int j,t,k;
for(j=0;j<=i;j++)
{
if(ht[j].parent==0)
{
s1=j;
break;
}
}
for(t=j+1;t<=i;t++)
{
if(ht[t].parent==0)
{
s2=t;
break;
}
}
for(k=0;k<=i;k++)
{
if((ht[k].weight<ht[s1].weight)&&(k!=t)&&(ht[k].parent==0))
{
s1=k;
}
}
for(k=0;k<=i;k++)
{
if((ht[k].weight<ht[s2].weight)&&(k!=s1)&&(ht[k].parent==0)) //容易出错，看出来了吗？
{
s2=k;
}
}
}
void TransHT(HuffmanTree ht,HuffmanCode code,int n,wt w) //译码
{
int temp;
int len;
int f;
int j,m;
for(int t=0;t<(2*n-1);t++)
{
if(ht[t].parent==0)
{
temp=t;
break;
}
}
for(j=0;j<n;j++)
{
len=strlen(code[j]);
f=temp;
for(int k=len-1;k>=0;k--)
{
if(code[j][k]=='0')
f=ht[f].lchild;
else
f=ht[f].rchild;
}
for(m=0;m<n;m++)
{
if(ht[f].weight==w[m].wt)
{
cout<<code[j]<<": "<<w[m].c<<endl;
break;
}
}
}
}
int main()
{
HuffmanTree ht;
HuffmanCode code;
wt w;
int n;
cout<<"请输入字符个数：";
cin>>n;
w=(wt)malloc(n*sizeof(struct weight));
cout<<"请输入各字符的权重："<<endl;
for(int i=0;i<n;i++)
{
cin>>w[i].c>>w[i].wt;
}
cout<<"创建哈夫曼树:"<<endl;
CreateHT(ht,code,w,n);
cout<<"输出哈夫曼编码:"<<endl;
for(int i=0;i<n;i++)
{
cout<<w[i].c<<" ";
cout<<code[i];
cout<<endl;
}
cout<<"译码结果为："<<endl;
TransHT(ht,code,n,w);
return 0;
}
运行结果：
