//first thing:thanks to my teacher---chenrong Dalian Maritime university
/*
构造Huffman Tree思路:
（1）根据给点的n个权值{w1,w2,w3.....wn}构成n棵二叉树的集合F={T1,T2,T3......Tn},其中每棵二叉树只有个带有权值Wi的根节点，其左右子树为空。
（2）在F中选取两棵根结点的权值最小的树作为左右子树构造一个新二叉树，新根权值为左右子树权值之和。
（3）在F中delete掉这两棵树，插入新二叉树到F中。
（4）重复（2）和（3），直到F中只含一棵树，此树为Huffman Tree。
网络查找到英文字母使用频率如下:
E是使用频率最高的，下面是英文字母使用频率表:(%)
A 8.19 B 1.47 C 3.83 D 3.91 E 12.25
F 2.26 G 1.71 H 4.57 I 7.10 J 0.14
K 0.41 L 3.77 M 3.34 N 7.06 O 7.26
P 2.89 Q 0.09 R 6.85 S 6.36 T 9.41
U 2.58 V 1.09 W 1.59 X 0.21 Y 1.58 Z 0.08
*/
#include
#define n 29 //叶子数目(设计为适用26个英文字母加空格逗号点号的叶子节点数)
#define m (2*n-1) //结点总数
#define maxval 10000.0 //maxval是float类型数据的最大值
#define maxsize 100 //哈夫曼编码的最大位数
typedef struct
{
char ch; //记录叶子节点的指代字符
float weight; //权值(记录该叶子节点的使用频率或频数)
int lchild,rchild,parent; //左右孩子和双亲节点
}hufmtree;
typedef struct
{
char bits[n]; //哈夫曼编码串[位串]
int start; //编码在位串中的起始位置
char ch; //字符(当前叶子节点指代字符)
}codetype;
void huffman(hufmtree tree[]);//建立哈夫曼树
void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码
void decode(hufmtree tree[]);//依次读入二进制电文，根据哈夫曼树译码为字符
void character(codetype code[]);//依次读入字符,根据哈夫曼树编码二进制电文
void main()
{
printf(" >>>>>Huffman树进行电文译码与编码<<<<<\n\n");
printf(" -----本转换程序仅适用于电文总共使用 %d 个字符的编码\n",n);
printf(" 所有输入文本都以'2'为输入结尾标识,用于判读结束\n");
hufmtree tree[m]; //使用结构体数组存储Huffman树(森林)
codetype code[n];
int i,j;//循环变量
huffman(tree);//建立哈夫曼树
huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
printf("\n >>每个字符的哈夫曼编码如下<<\n");
for(i=0;i<n;i++)
{
printf("%c: ",code[i].ch);//输出叶子结点指代字符
for(j=code[i].start;j<n;j++)
printf("%c ",code[i].bits[j]);//输出求得的哈夫曼编码
printf("\n");
}
int Lbool=1;
int temp;
while (Lbool)
{
printf("\n-------------------------功能选项卡------------------------\n");
printf("1、自然语言文本转码;\t2、Huffman数串译码;\t3、退出系统;\n\n");
scanf("%d",&temp);
getchar();
switch (temp)
{
case 1:
printf(" >>自然语言文本转码区<<\n");
character(code); //依次读入自然语言文本电文，根据哈夫曼树转码
break;
case 2:
printf("\n >>Huffman编码电文译码为自然语言区<<\n\n");
decode(tree);//依次读入二进制数电文，根据哈夫曼树译码(为人易读的自然语言)
break;
case 3:
Lbool=0;
break;
default:
break;
}
}
}
void huffman(hufmtree tree[])//建立哈夫曼树
{
int i,j,p1,p2;//p1,p2用于分别记住每次合并时权值最小和次小的两个根结点的下标
float small1,small2,f; //f用于接收键盘输入的权值
char c;
for(i=0;i<m;i++) //初始化二叉树集合(只有两个叶子结点的森林)
{
tree[i].parent=0; //此时节点是根结点,在合并前都设为0(在建立哈夫曼树时选择parent为0且weight最小的两个结点分编序号)
tree[i].lchild=-1;
tree[i].rchild=-1; //左右孩纸结点设为-1
tree[i].weight=0.0; //权值置零
}
printf("\n >>电文使用的各字符编码区<<\n\n");
for(i=0;i<n;i++) //读入前n个结点的字符及权值
{
printf("第%2d个字符和对应权值(空格分隔):",i+1);
scanf("%c %f",&c,&f);
getchar();
tree[i].ch=c;
tree[i].weight=f; //对二叉树集合(森林)中每一棵树赋值,记录下字符与权值
}
for(i=n;i<m;i++) //进行n-1次合并，产生n-1个新结点[m-n=(2*n-1-n)=n-1]
{
p1=0;p2=0; //每次合并时都要初始化记录权值最小和次小的两个根结点下标的变量p1,p2,因为每次合并后集合中权值情况都改变了,合并后可能不再是最小权值
small1=maxval;small2=maxval; //maxval是float类型的最大值.small1记录最小权值,small2记录次小权值
for(j=0;j<i;j++) //选出两个权值最小的根结点
if(tree[j].parent==0) //(选择parent为0且weight最小的两个结点分编序号,用p1,p2记录)
if(tree[j].weight<small1)
{
small2=small1; //改变最小权值、次小权值,最小权值赋给small1,次小权值给small2
small1=tree[j].weight;
p2=p1; //改变次小权值对应的位置,记录次小权值结点下标
p1=j; //改变最小权值对应的位置,记录最小权值结点下标
}
else
if(tree[j].weight<small2)
{
small2=tree[j].weight; //改变次小权值及位置,原small1<tree[j].weight<原small2,作为次小权值赋给small2
p2=j; //改变次小权值对应的位置,记录次小权值结点下标
}
tree[p1].parent=i;
tree[p2].parent=i; //合并最小权值与次小权值二叉树,(因为是结构体数组,将结构体成员中双亲结点赋值为i即可,便是新的第i个结点了)
tree[i].lchild=p1; //最小权根结点是新结点的左孩子
tree[i].rchild=p2; //次小权根结点是新结点的右孩子
tree[i].weight=tree[p1].weight+tree[p2].weight; //新节点的权值是左右孩纸的权值之和(合并前两个最小权值与次小权值二叉树权值之和)
}
}//huffman
void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
//codetype code[]为求出的哈夫曼编码
//hufmtree tree[]为已知的哈夫曼树
{
int i,c,p;
codetype cd; //中间变量(缓冲变量)
for(i=0;i<n;i++)
{
cd.start=n;
cd.ch=tree[i].ch;
c=i; //从叶结点出发向上回溯(从叶子到根逆向求每个字符的哈夫曼编码)
p=tree[i].parent; //tree[p]是tree[i]的双亲(parent记录了隶属关系,左右孩子[实际上是两个独立的结构体数据]在tree数组中的下标之和记录在parent中)
while(p!=0) //左小为'0',右大为'1'.用bits[]数组存贮编码后得到的二进制串
{
cd.start--; //每次都是从头码开始逐位逐位地形成编码位串
if(tree[p].lchild==c) //判断是否是双亲结点的左孩子
cd.bits[cd.start]='0'; //tree[i]是左子树，生成代码'0'
else
cd.bits[cd.start]='1'; //tree[i]是右子树，生成代码'1'
c=p; //进入上一层节点
p=tree[p].parent; //记住当前节点的双亲节点在数组中的位置,便于下一次用于判断当前节点是双亲节点的哪一个孩纸
}
code[i]=cd; //第i+1个字符的编码存入code[i].(解释:cd数据类型的第一个成员变量是bits[]数组,用cd作数组的首地址)
}
}//huffmancode
void decode(hufmtree tree[])//依次读入电文，根据哈夫曼树译码
{
int i,j=0;
char b[maxsize];
char endflag='2'; //电文结束标志取2
i=m-1; //从根结点开始往下搜索
printf("Huffman编码文本录入：\n");
gets(b);
printf("\n >>译码后的文本信息<<\n\n");
while(b[j]!='2')
{
if(b[j]=='0')
i=tree[i].lchild; //走向左孩子
else
i=tree[i].rchild; //走向右孩子
if(tree[i].lchild==-1) //tree[i]是叶子结点
{
printf("%c",tree[i].ch);
i=m-1; //回到根结点
}
j++;
}
printf("\n\n<><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><><>");
if(tree[i].lchild!=-1&&b[j]!='2') //二进制电文读完，但尚未到叶子结点
printf("\nInput Information Is Error!\n"); //输入电文有错
}//decode
void character(codetype code[]) //自然语言转码成Huffman编码
{
int i=0,j,k=0;
char b[maxsize]; //自然语言电文的接受
printf("自然语言文本录入:\n");
gets(b);
printf(" >>转码后的文本信息显示区<<\n\n");
while (b[k]!='2')
{
for(i=0;i<n;i++)
{
if(b[k]==code[i].ch) //code已经记录下所有的字符信息,这个时候拿来用还是很方便的O(∩_∩)O哈！
{
for(j=code[i].start;j<n;j++)
printf("%c",code[i].bits[j]);//输出对应的哈夫曼编码
}
}
k++;
}
printf("\n");
}
//运行效果图