25岁最适合用的眼霜:一步一步写算法（之哈夫曼树 上）

来源：百度文库 编辑：偶看新闻 时间：2024/04/27 14:58:52

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】


在数据传输的过程当中，我们总是希望用尽可能少的带宽传输更多的数据，哈夫曼就是其中的一种较少带宽传输的方法。哈夫曼的基本思想不复杂，那就是对于出现频率高的数据用短字节表示，对于频率比较低得数据用长字节表示。

比如说，现在有4个数据需要传输，分别为A、B、C、D，所以一般来说，如果此时没有考虑四个数据出现的概率，那么我们完全可以这么分配，平均长度为2，

view plaincopy to clipboardprint?

  1. /*
  2. * A - 00 B - 01
  3. * C - 10 D - 11
  4. */
但是，现在条件发生了改变，四个数据出现的频率并不一样，分别为0.1/0.2/0.3/0.4。那么这时候应该怎么分配长度呢，其实也简单。我们只要把所有数据按照频率从低到高排列，每次取前两位合并成新的节点，再把这个新节点放到队列中重新排序即可。新节点的左结点默认设为1，右结点默认设为0。然后重复上面的过程，直到所有的节点都合并成一个节点为止。如果应用到实际的示例中，合并的过程应该是这样的，

第一步，首先合并A和B，因为A和B是概率最小的

view plaincopy to clipboardprint?

  1. /*
  2. *
  3. * total_1(0.3) C (0.3) D(0.4)
  4. * / \
  5. * A(0.1) B(0.2)
  6. */
第二步，接着合并total_1和C，

view plaincopy to clipboardprint?

  1. /*
  2. * total_2 (0.6)
  3. * / \
  4. * total_1(0.3) C (0.3) D(0.4)
  5. * / \
  6. * A(0.1) B(0.2)
  7. */
最后一步，合并total_2和D，

view plaincopy to clipboardprint?

  1. /*
  2. * final (1.0)
  3. * / \
  4. * D (0.4) total_2 (0.6)
  5. * / \
  6. * total_1(0.3) C (0.3)
  7. * / \
  8. * A(0.1) B(0.2)
  9. */
所以按照上面的生成树，数据的编号应该这么安排，

view plaincopy to clipboardprint?

  1. /*
  2. * A - 011 B - 010
  3. * C - 00 D - 1
  4. */
看上去A和B的长度还增加了，但是D的长度减少了。那么整个数据的平均长度有没有减少呢？我们可以计算一下。3 * 0.1 + 3 * 0.2 + 2 * 0.3 + 0.4 = 1.9 < 2。我们发现调整后的数据平均长度比原来减少了近（2 - 1.9）/2 * 100% = 10 %，这可是巨大的发现啊。

为了完成整个哈夫曼树的创建，我们还需要定义一个数据结构：

view plaincopy to clipboardprint?

  1. typedef struct _HUFFMAN_NODE
  2. {
  3. char str;
  4. double frequence;
  5. int symbol;
  6. struct _HUFFMAN_NODE* left;
  7. struct _HUFFMAN_NODE* right;
  8. struct _HUFFMAN_NODE* parent;
  10. }HUFFMAN_NODE;
其中str记录字符，frequency记录字符出现的频率， symbol记录分配的数据，左子树为1、右子树为0，left为左子树，right为右子树，parent为父节点。接下来，我们从创建huffman结点开始。

view plaincopy to clipboardprint?

  1. HUFFMAN_NODE* create_new_node(char str, double frq)
  2. {
  3. HUFFMAN_NODE* pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE));
  4. assert(NULL != pNode);
  6. pNode->str = str;
  7. pNode->frequence = frq;
  8. pNode->symbol = -1;
  9. pNode->left = NULL;
  10. pNode->right = NULL;
  11. pNode->parent = NULL;
  12. return pNode;
  13. }


【未完，待续】

怎样用NOKIA7270通过数据线让笔记本电脑上（CMWAP）详细一点，最好一步一步 怎样才能把算法写好啊？ 写者问题的算法 如何一步一步的提高写公文材料的水平？ w2000要怎么设置上ADSL(请一步一步慢慢说) 大家帮帮忙,写一个算法:建一个哈夫曼树并对其编码 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 程序调度（时间片轮转算法）用C语言程序怎么写啊？？谢谢 用C语言写一个排序算法。 帮忙 写个算法 用C++语言 crc算法在单片机上的实现 crc算法在单片机上的实现 数学上的“概率”算法怎么计算？ 遗传算法在数学上的应用 瓶装的营养快线的百分百中奖，怎么得奖，一步一步写清THS qq空间开场的FLASH代码什么，谁能一步一步慢慢写清楚 谢 了 设计一个用链表表示的简单选择排序的算法，并实现之（试验报告） 我家没迅雷怎么下载（一步一步说清楚哦） 山市是怎么一步一步变化的（用原句回答） 根号9等于多少？（一步一步的演算出来，谢谢！） 根号5等于多少？（一步一步的演算出来，谢谢！） 根号45等于多少？（一步一步的演算出来，谢谢！） 根号720等于多少？（一步一步的演算出来，谢谢！）