哈夫曼编码译码系统的实现，主要包含三部分：
1、创建哈夫曼树
2、编码函数
3、译码函数
编写代码时为了方便，在这里混用了c++的输入输出流。主体用c语言实现。
下面时代码部分：
1、头文件，以及储存结构：
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAX 2000
typedef char ElemType;
typedef struct{
ElemType data;
int w;
int parent,lchild,rchild;
}HFMTNode;
2、哈夫曼树的创建，Ht储存全部节点的权值，n代表叶子节点数量。
void menu(HFMTNode Ht [],int n);//原型声明
void CreatHFMTree(HFMTNode Ht[],int n)//创建哈夫曼树
{
int i,j,k,lmin,rmin;
int min1,min2,m1;
for(i=;i<*n;i++)
{
Ht[i].parent=Ht[i].lchild=Ht[i].rchild=-;
}
for(i=n+;i<*n;i++)
{
min1=min2=MAX;
lmin=rmin=-;
for(k=;k<i;k++)
{
if(Ht[k].parent==-)//只在尚未构造的二叉树节点中运行
{
if(Ht[k].w<min1)
{
min2=min1;
rmin=lmin;
min1=Ht[k].w;
lmin=k;
}
else
{
if(Ht[k].w<min2)
{
min2=Ht[k].w;
rmin=k;
}
}
}
else{
if(Ht[k].w<min2&&k>m1)//与创建好的二叉树节点比较，选取w小的一个
{
min2=Ht[k].w;
rmin=k;
m1=k;
}
}
}
Ht[lmin].parent=i;//对选择出的结点进行连接
Ht[rmin].parent=i;
Ht[i].w=Ht[lmin].w+Ht[rmin].w;
Ht[i].lchild=lmin;
Ht[i].rchild=rmin;
}
printf("HFMTree have been created\n");
}
3、编码译码函数、主函数：
void encoding(HFMTNode Ht [],int n)//编码
{
int k;
fflush(stdin);
printf("Please input what you want to encode with the ending of'#' :\n");
char ch;
ch=getchar(); //读取字符
while (ch!='#')
{
for(k=;k<=n;k++)
{
if(Ht[k].data==ch)
{
break;
}
} //找到字符位置
HFMTNode temp1,temp=Ht[k];
int flag=;
int a[n];
while(temp.w!=Ht[*n-].w)
{
temp1=temp;
temp=Ht[temp.parent];
if(Ht[temp.lchild].w==temp1.w )
{
a[flag]=;
flag++;
}
else if(Ht[temp.rchild].w==temp1.w )
{
a[flag]=;
flag++;
}
} //用数组记录路径
for(int f=flag-;f>=;f--)
{
printf("%d",a[f]);
} //编码输出
ch=getchar();
}
printf("\nencoding have finished\n");
system("pause");
system("cls");
menu(Ht,n);
}
void decoding(HFMTNode Ht [],int n)//译码
{
int k=*n-;
fflush(stdin);
printf("Please input what you want to decode with the ending of'#' :\n");
char ch;
ch=getchar(); //依次读取01字符
HFMTNode temp=Ht[*n-];
while (ch!='#')
{
if(ch=='')
{
if(temp.rchild==-)
{
printf("%c",temp.data); //根据01向左右寻找，到达叶子节点时输出
temp=Ht[*n-];
continue;
}
else
{
temp=Ht[temp.rchild ];
ch=getchar();
}
}
else if(ch=='')
{
if(temp.lchild==-)
{
printf("%c",temp.data);
temp=Ht[*n-];
continue;
}
else
{
temp=Ht[temp.lchild ];
ch=getchar();
}
}
}
printf("%c",temp.data); //输出要译码的最后一个字符
printf("\ndecoding have finished\n");
system("pause");
system("cls");
menu(Ht,n);
}
void menu(HFMTNode Ht [],int n)
{
int j;
printf("Input your choice:\n");
printf("1.encoding 2.decoding 0.exit\n");
cin>>j;
switch (j)
{
case :encoding(Ht,n);break;
case :decoding(Ht,n);break;
case :break;
}
}
int main()
{
printf("Please input the amount of the node:\n");
int i;
scanf("%d",&i);
HFMTNode Ht[*i];//储存各个节点的数据
for(int k=;k<=i;k++)
{
printf("Ht[%d]:Please input data :",k);
cin>>Ht[k].data;
printf("Ht[%d]:Please input w :",k);
cin>>Ht[k].w;
}
CreatHFMTree(Ht,i);
menu(Ht,i);
return ;
}
上面代码放在一起即可直接运行，本人水平有限，如有错误，欢迎大神指正。