以下是全部代码
#include<iostream>
#include<string>
#include<cstdio>
#include<cstdlib>
using namespace std;
#define LEN 8
typedef double DataType;
typedef struct
{
char ch;
int parent;
int LChild;
int RChild;
DataType weight;
}HNode,*Huffman;
typedef struct
{
int start; //存放编码的起始位置（从高位向低位，从右向左）
int bit[LEN]; //存放huffman编码
}HCode,*HuffCode;
void createHuffmanTree(Huffman &h,int leaves,DataType *weight,char *ch)
{
int i,j;
int l=2*leaves-1;
h=(Huffman)malloc((l+1)*sizeof(HNode));
for(i=0;i<leaves;i++) //初始化
{
h[i].parent=-1;
h[i].LChild=-1;
h[i].RChild=-1;
h[i].weight=0;
h[i].ch=0;
}
for(i=0;i<leaves;i++) //给叶子赋权重
{
h[i].weight=*(weight+i);
h[i].ch=*(ch+i);
}
for(i=0;i<leaves-1;i++)
{
DataType m1,m2;
int m1_pos,m2_pos;
m1=m2=65536;
m1_pos=m2_pos=0;
for(j=0;j<leaves+i;j++)
{
if(h[j].weight<m1&&h[j].parent==-1)
{
m2=m1;
m1=h[j].weight;
m2_pos=m1_pos;
m1_pos=j;
}
else if(h[j].weight<m2&&h[j].parent==-1)
{
m2=h[j].weight;
m2_pos=j;
}
}
h[leaves+i].parent=-1;
h[leaves+i].LChild=m1_pos;
h[leaves+i].RChild=m2_pos;
h[m1_pos].parent=leaves+i;
h[m2_pos].parent=leaves+i;
h[leaves+i].weight=m2+m1;
}
}
void huffmancode(Huffman &h,HuffCode &code,int leaves)
{
int i,j,p,c;
HCode hf;
char x[leaves][LEN];
code=(HuffCode)malloc((leaves)*sizeof (HCode));
for(i=0;i<leaves;i++)
{
c=i;
p=h[i].parent;
hf.start=LEN-1;
while(p!=-1){
if(h[p].LChild==c){
hf.bit[hf.start]=0;
}
else
{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
cout<<h[i].ch<<"("<<h[i].weight<<"):";
for(j=hf.start+1;j<LEN;j++){
code[i].bit[j]=hf.bit[j];
cout<<code[i].bit[j];
x[i][j]=code[i].bit[j]+'0';
cout<<x[i][j];
}
cout<<"\t";
code[i].start=hf.start+1;
}
for(int m=0;m<leaves;m++)
for(int n=0;n<LEN;n++)
cout<<x[m][n];
for(int k=0;k<leaves;k++)
puts(x[k]);
}
void main(){
Huffman h;
HuffCode code;
int leaves;
cout<<"请输入结点数leaves："<<endl;
cin>>leaves;
char ch[leaves];
cout<<"请输入字符"<<endl;
for(int i=0;i<leaves;i++){
cin>>ch[i];
}
DataType weight[leaves];
cout<<"请输入每个字符对应的权值"<<endl;
for(int i=0;i<leaves;i++){
cin>>weight[i];
}
createHuffmanTree(h,leaves,weight,ch);
cout<<"输出各个权值的编码:"<<endl;
huffmancode(h,code,leaves);
}
