哈夫曼编码 贪心算法(2)

《 算法分析与设计》实验报告 - 5 -

CrtHuffmanCode(&HT,&HC,n); }

实验结果

1 权值 0.32 哈夫曼编码 00 等长编码 000 字符 权值 2 0.16 010 001 0.20 10 001 3 0.07 011 010 0.04 0001 010 4 0.22 11 011 0.13 0000 011 0.04 01110 011 5 0.23 10 100 0.16 001 100 0.35 00 100 0.05 0011 100 6 0.29 01 101 0.28 10 101 0.24 10 101 7 8 平均码长 2.23 3.00 2.5 3.00 2.8 3.00 0.18 哈夫曼编码 11 等长编码 000 权值 0.17 哈夫曼编码 010 等长编码 000 权值 0.8 0.23 0110 11 001 010 0.09 111 001 0.01 01111 110 0.16 000 110 0.27 哈夫曼编码 01 等长编码 000

0.03 0.12 00101 110 010 011 0.04 00100 2.68 111 3.00 《 算法分析与设计》实验报告 - 6 -

说明：1，由表可知，哈夫曼编码的平均码长要比等长编码短。由此操作码得以优化。

2，哈夫曼二叉树的构造为左1右0。

3，因程序中权值设置为整型，故若输入权值中有小数，请经所有数乘以10^n倍，将其转换成整型集合。

实验体会

哈夫曼编码算法：每次将集合中两个权值最小的二叉树合并成一棵新二叉树，n-1次合并后，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快（或最慢）为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。

每次选择两个权值最小的二叉树时，规定了较小的为左子树。