c语言实现的哈夫曼树代码

  次阅读 作者:智能小宝 来源:互联网 2016-01-26 10:06 我要评论(0)

着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码

我们设置一个结构数组 HuffNode 保存哈夫曼树中各结点的信息。根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 。HuffNode 结构中有 weight, lchild, rchild 和 parent 域。其中,weight 域保存结点的权值, lchild 和 rchild 分别保存该结点的左、右孩子的结点在数组 HuffNode 中的序号,从而建立起结点之间的关系。为了判定一个结点是否已加入到要建立的哈夫曼树中,可通过 parent 域的值来确定。初始时 parent 的值为 -1。当结点加入到树中去时,该结点 parent 的值为其父结点在数组 HuffNode 中的序号,而不会是 -1 了。

求叶结点的编码:

该过程实质上就是在已建立的哈夫曼树中,从叶结点开始,沿结点的双亲链域回退到根结 点,每回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值。由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上各分支所组成的 0、1 序列,因此先得到的分支代码为所求编码的低位,后得到的分支代码为所求编码的高位码。我们可以设置一个结构数组 HuffCode 用来存放各字符的哈夫曼编码信息,数组元素的结构中有两个域:bit 和 start。其中,域 bit 为一维数组,用来保存字符的哈夫曼编码, start 表示该编码在数组 bit 中的开始位置。所以,对于第 i 个字符,它的哈夫曼编码存放在 HuffCode[i].bit 中的从 HuffCode[i].start 到 n 的 bit 位中。

复制代码 代码如下:

/*-------------------------------------------------------------------------

* Name:哈夫曼编码源代码

* 在 Win-TC 下测试通过

* 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中

*自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在

*父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。

*------------------------------------------------------------------------*/

#include <stdio.h>

#define MAXBIT100

#define MAXVALUE10000

#define MAXLEAF30

#define MAXNODEMAXLEAF*2 -1

typedef struct

{

int bit[MAXBIT];

int start;

} HCodeType;/* 编码结构体 */

typedef struct

{

int weight;

int parent;

int lchild;

int rchild;

} HNodeType;/* 结点结构体 */

/* 构造一颗哈夫曼树 */

void HuffmanTree (HNodeType HuffNode[MAXNODE],int n)

{

/* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,

x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/

int i, j, m1, m2, x1, x2;

/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */

for (i=0; i<2*n-1; i++)

{

HuffNode[i].weight = 0;

HuffNode[i].parent =-1;

HuffNode[i].lchild =-1;

HuffNode[i].lchild =-1;

} /* end for */

/* 输入 n 个叶子结点的权值 */

for (i=0; i<n; i++)

本站文章信息来源于网络以及网友投稿,本站只负责对文章进行整理、排版、编辑,是出于传递更多信息之目的,并不意味着赞同其观点或证实其内容的真实性。如果您有什么意见或建议,请联系QQ28-1688-302!

人工智能实验室
相关文章相关文章
  • 韩春雨称已能重复实验结果 近期将有消息公布

    韩春雨称已能重复实验结果 近期将有消息公布

  • 未来两年人工智能要怎么走?看这篇就够了

    未来两年人工智能要怎么走?看这篇就够了

  • 无人驾驶汽车如何改变城市生活?听听他们怎么说

    无人驾驶汽车如何改变城市生活?听听他们怎么说

  • 英国研发“杀生”机器人 通过生命体获取能量

    英国研发“杀生”机器人 通过生命体获取能量

网友点评网友点评
阅读推荐阅读推荐

据国外媒体报道,在过去两年内,聊天机器人(chatbot)、人工智能以及机器学习的研发和采用取得了巨大进展。许多初创公司正利用人工智能和...

霍金 视觉中国 图 英国著名物理学家霍金(Stephen Hawking)再次就人工智能(AI)发声,他认为:对于人类来说,强大AI的出现可能是最美妙的...

文|郑娟娟 今年,人工智能(AI) 60岁了。在AI60岁的时候,笔者想要介绍一下AI100,一个刚刚2岁的研究项目,但它的预设寿命是100年,甚至更长...

AlphaGo与李世石的人机大战,为大众迅速普及了人工智能的概念。 但对谷歌而言,除了下围棋,现在的人工智能进展到哪一步了?未来,人工智能...