rogerceng的博客
rogerceng · 共 2 篇文章
Huffman编码算法及C语言实现(2)
构造完成后HT数组的状态如下: 通过huffman树,得到每一个叶子结点的huffman编码。在此采用的从叶子结点到根结点求每个字符huffman编码方法。从叶子c开始,通过结点c的双亲结点域,找到双亲,然后判断双亲结点的左孩子和右孩子是否为c,如果是左孩子,则编码为0,如果是右孩子则编码为1。按照这个方法,直到根结点,即求出每个叶子结点对应的huffman编码。 另外在构造huffman树中使用了Select函数实现选取n个叶子结点中权重最小的2个结点,算法很巧妙,请大家仔细研究: 主函数:
2010-09-01 16:55 · 评论(0)
Huffman编码算法及C语言实现(1)
Huffman编码算法的数学模型依赖于Huffman Tree Huffman Tree的定义? 假设有n个权值{w1,w2,w3......wn},试构造一棵有n个叶子节点的二叉树(节点总数为m=2*n-1),每个叶子带权值为wi,其中WPL(树带权路径)最小的二叉树成为Huffman树或者最优二叉树。在一些判断性问题中,可以利用Huffman树得到最佳的判断算法,比如编制一个将百分制转换为五分制问题(参见《数据结构》清华版p144)。如有10000个输入数据,一般二叉树的判断过程需要31500次判断操作,而最优二叉树只需22000次。 如何构造Huffman Tree? (1)根据给点的…
2010-09-01 16:39 · 评论(0)