打开文本图片集
摘 要 利用哈夫曼编码可缩短信息传输时间，提高信道利用率。本文分析了用C语言实现哈夫曼编码译码。
关键词 C语言 哈夫曼 编码 译码
中图分类号：TP313 文献标识码：A
0引言
当今时代信息高速发展，利用哈夫曼编码进行通信可提高信道利用率从而获得更大的利润。
1算法设计
1.1算法说明
哈夫曼树也称最优二叉树。给定一组具有确定权值的叶子结点，可以构造出不同的二叉树，二叉树的带权路径长度记为：WPL=∑Wklk，Wk为第k个叶子结点的权值，lk为从根结点到第k个叶子结点的路径长度。
1.2算法所需数据结构
表1：结点结构
其中：
Weight：权值；
L_child：左孩子结点信息；
R_child：右孩子结点信息；
Parent：双亲结点信息；
Name：姓名。
1.3算法流程
1.3.1编码
（1）初始化哈夫曼树；
（2）初始化结构体；
（3）输入叶子权值及名称；
（4）选取两个最小权值的叶子；
（5）创建哈夫曼树。
1.3.2译码
（1）找寻哈夫曼树根节点；
（2）遍历哈夫曼树： 1->右子树，0->左子树；
（3）判断是否走到叶子节点，若是，打印字符并回归根节点。
2算法程序实现
2.1编码过程实现
void Encode（Huff_tree T）{
char r[1000]；
int i， j；
printf（"＼n＼n请输入需要编码的字符＼n"）；
gets（r）；
printf（"编码结果为："）；
for（j=0；r[j]！="＼0"；j++）{
for（i=0；i if（r[j]==T[i].Name） Path（T，i，j）； } } printf（"＼n"）； } 2.2译码过程实现 void Decode（Huff_tree T） { char r[1000]； int p，R，t，length； R=root（T，&p）； t=R； printf（"＼n请输入您需要译码的字符串：＼n"）； gets（r）； length=strlen（r）； printf（"＼n译码结果是：＼n"）； for（int i=0；i if（r[i]=="0"）{ t=T[t].L_child； if（T[t].L_child==-1）{ printf（"%c"，T[t].Name）； t=R； } } else if（r[i]=="1"）{ t=T[t].R_child； if（T[t].R_child==-1）{ printf（"%c"，T[t].Name）； t=R； printf（"＼n＼n"）； 3有效性检测 在Windows环境下对程序进行编码译码检测，结果如下： 编码测试： 输入值：acbdefacebadd 编码值：11101101111000110111011001111111100000 输入值：bacebdf 编码值：111111101100111110010 译码测试： 输入值：1110110100110000 译码值：acfefd 输入值：00110000111010110100101101001001100010 译码值：dcdecfcfeedcdf 经验证，程序运行正常。 4结语 本文给出了哈夫曼树的C语言实现方法并在windows环境下进行了实现。 参考文献 [1] 谭浩强.C语言程序设计（第三版）[M].北京：清华大学出版社，2014. [2] 屈婉玲，耿素云，张立昂.离散数学[M].北京：高等教育出版社，2008. [3] 严蔚敏，吴伟民.数据结构（C版）[M].北京：清华大学出版社，2012.
