admin 管理员组文章数量: 1087652
2024年3月12日发(作者：laravel分页样式)
计算机时代２０１３年第９期 ・４ｌ・
Ｃ语言在Ｋ叉哈夫曼编码教学中的应用
郑文艳
（德州学院信息管理学院，山东德州２５３０２３）
摘要：字符编码与信息压缩是计算机应用的重要研究课题，许多学者对此作了很多非常有价值的研究。文章简单分
析了二叉哈夫曼树的构造及编码，通过比较三种构造三叉哈夫曼树的算法，提出了构造任意Ｋ叉哈夫曼树及Ｋ进制的最
优前缀编码的算法，并给出ｃ语言源程序，使哈夫曼编码的应用范围变得更为广阔。
关键词：哈夫曼树；三叉哈夫曼树；Ｋ叉哈夫曼树；哈夫曼编码
中图分类号：ＴＰ３１ ２ 文献标志码：Ａ 文章编号：１ ００６—８２２８（２０１ ３）０９—４１—０２
Ａｐｐｌｉｃａｔｉｏｎ ｏｆ Ｃ ｌａｎｇｕａｇｅ ｉｎ ｔｈｅ ｔｅａｃｈｉｎｇ ｏｆ Ｋ－ａｒｙ Ｈｕｆｆｍａｎ ｔｒｅｅ ｃｏｄｅ
Ｚｈｅｎｇ Ｗｅｎｙａｎ
（ｃｏｌｌｅｇｅ ｏｆ ｉｎｆｏｒｍａｔｉｏｎ ｍａｎａｇｅｍｅｎｔ，Ｄｅｚｈｏｕ Ｕｎｉｖｅｒｓｉｔｙ，Ｄｅｚｈｏｕ，Ｓｈａｎｄｏｎｇ ２５３０２３，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｔｈｅ ｃｈａｒａｃｔｅｒ ｅｎｃｏｄｉｎｇ ａｎｄ ｉｎｆｏｒｍａｔｉｏｎ ｃｏｍｐｒｅｓｓｉｏｎ ａｒｅ ｉｍｐｏｒｔａｎｔ ｒｅｓｅａｒｃｈ ｔｏｐｉｃｓ ｉｎ ｃｏｍｐｕｔｅｒ ａｐｐｌｉｃａｔｉｏｎ．Ｍａｎｙ
ｓｃｈｏｌａｒｓ ｈａｖｅ ｄｏｎｅ ａ ｌｏｔ ｏｆ ｖａｌｕａｂｌｅ ｒｅｓｅａｒｃｈ．Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ｔｈｅ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｃｏｄｅ ｏｆ ｂｉｎａｒｙ ｔｒｅｅ Ｈｕｆｆｍａｎ ａｒｅ ａｎａｌｙｚｅｄ．Ｂｙ
ｃｏｍｐａｒｉｎｇ ｔｈｅ ｔｈｒｅｅ ｋｉｎｄｓ ｏｆ ａｌｇｏｒｉｔｈｍｓ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｒｉｐｌｅ Ｈｕｆｆｍａｎ ｔｒｅｅ，ｔｈｅ ｏｐｔｉｍａｌ ｐｒｅｆｉｘ ｃｏｄｅ ａｌｇｏｒｉｔｈｍ ｃｏｎｓｔｒｕｃｔｉｎｇ ａｒｂｉｒｔａｒｙ
ｋ－ａｒｙ Ｈｕｆｆｍａｎ ｔｒｅｅ ａｎｄ ｔｈｅ ｂａｓｅ Ｋ ｉｓ ｐｒｏｖｉｄｅｄ．Ｔｈｅ Ｃ ｌａｎｇｕａｇｅ ｓｏｕｒｅｅ ｃｏｄｅ ｉｓ ｇｉｖｅｎ，ｗｈｉｃｈ ｍａｋｅｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｒａｎｇｅ ｏｆ ｔｈｅ
Ｈｕｆｆｍａｎ ｃｏｄｅ ｗｉｄｅｒ．
Ｋｅｙ ｗｏｒｄｓ：Ｈｕｆｆｍａｎ ｔｒｅｅ；ｔｒｉｇｅｍｉｎａｌ Ｈｕｆｆｍａｎ ｔｒｅｅ；Ｋ—ａｒｙ Ｈｕｆｆｍａｎ ｔｒｅｅ；Ｈｕｆｆｍａｎ ｃｏｄｉｎｇ
１二叉哈夫曼树 １的构造算法
（２）在Ｆ中选取三棵根结点的权值最小的树作为左、中、右
对于给定的数据序列，要生成带权路径长度最小的二叉
子树构造一棵新的三叉树，且新得到的三叉树的根结点的权值
树，应让权值越大的叶结点越靠近树根，权值越小的叶结点越
为其左、中、右子树的根结点的权值之和。
远离树根。哈夫曼最早给出了一个具有一般规律的算法，称之
（３）在Ｆ中删除这三棵树，同时将新得到的三叉树加入到
为哈夫曼算法。
集合Ｆ中。
（１）根据给定的ｎ个权值｛ｗ ，Ｗ ，Ｗ －－，ｗ ．－，ｗ ｝构成ｎ
（４）重复（２）和（３），直到集合Ｆ中只含有一棵树为止 。
棵二叉树的初始集合Ｆ＝｛ＴＪ，］ｒ２， …，Ｔｊ，…，］ｒＤ），其中每棵二叉
此算法由二又哈夫曼算法扩展而来，因而将它称为三又哈
树Ｔ．中只有一个权值为ｗ。的根结点，它的左右子树均为空。
夫曼树构造的扩展算法。
（２）在Ｆ中选取两棵根结点权值最小的树作为左右子树构
３ ｋ叉哈夫曼树的构造
造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、
设有ｎ个信源符号，在传输过程中的概率分别是ｗ ，ｗ ，
右子树的根结点的权值之和。
…
，
，
ｗｎ，将概率设为权值。ｋｏ＝（ｎ一１）ｍｏｄ（ｋ—１），当ｋ，：Ｏ时，
（３）在Ｆ中删除这两棵树，同时将新得到的二叉树加入到
（ｎ—１）／（ｋ＿１）为整数，哈夫曼树中只有度为０和ｋ的结点；当 ≠
集合Ｆ中。
０，即（ｎ一１）／（ｋ—１）不为整数时，需添加ｋ～１一ｋ个权值为０的结
（４）重复（２）和（３），直到集合Ｆ中只含有一棵树为止。这棵
点。算法思路如下。
树便是哈夫曼树。
（１）作ｎ棵树的集合Ｆ＝｛Ｔ ，Ｔ ，Ｔ －．，Ｔｉ，…，Ｔ ｌ，每棵树１＇ｉ
２三叉哈夫曼树构造的扩展算法
只有一个权值为ｗ｜的根结点，且均无子女。
与哈夫曼算法类似，可以每次取三个根结点权值最小的树
（２）计算ｋｏ＝（ｎ一１）ｍｏｄ（ｋ一１）；若ｋｏ≠Ｏ，则添加ｋ—ｌ—ｋ个权值
作子树，构造一棵新的三叉树，算法思路如下。
为０的结点，并作为ｋ＿ｌ＿ｋ，棵树添加到Ｆ中，否则不用添加。
（１）根据给定的ｎ个权值｛ｗ ，ｗ ，ｗ 一，ｗ 一，ｗ ）构成ｎ
（３）在Ｆ中选ｋ棵根结点权值最小的树作子树，构造一棵新
棵三叉树的初始集合Ｆ＝｛Ｔ。，Ｔ２， ，…，Ｔ。…，Ｔ ｝，其中每棵三叉
的ｋ又树，其根结点的权值为所有子树根结点的权值之和，并在
树Ｔ｜中只有—个权值为ｗ．的根结点，它的左、中、右子树均为空。
Ｆ中删除这ｋ棵树，且将新得到的ｋ叉树加入Ｆ中。
收稿日期：２０１３～７一ｌ６
作者简介：郑文艳（１９８０～），女，硕士，讲师，主要研究方向：Ｐｅｔｒｉ网应用。
版权声明：本文标题：C语言在K叉哈夫曼编码教学中的应用 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1710253545a564559.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论