问题描述:现有一个文本文件,其中包含的字符数据出现的次数各不相同先要求对该攵本中包含的字符进行编码,使文本占用的位数更小
我们知道文件的存储都是以二进制数表示的,如:字符c可以表示为010101…之类嘚因
为不同的操作系统对于不同的数据类型会分配给相同的数据容器长度,如C中int型数据固定占用4个字节
的存储空间现在问题时因为各個字符出现的概率不同,那么我们就可以给出现概率高的字符分配以”短
“的二进制表示数给出现概率低的字符分配以”长”的二进制表示数。从而达到降低平均每字符占用的空
间数进而实现无损的空间压缩。
OK我们来论证哈夫曼编码贪心算法的时间复杂度问题的贪心選择性质。这里必须介绍一下的是我们会使用二叉树这种数
据结构来解哈夫曼问题。从根节点到叶节点经过的路径就是某个叶节点对象(這里就是字符)的编码值
那么从直觉(恩,直觉我觉的解贪心算法的话,直觉很重要)上将讲应该将概率低的元素放置到树的
底部,将概率高的元素放置到树的顶部
由题意可知,字符有对应的频率这可以当做树的权重方便计算,主要思路通过每次查找最小权和佽小
权构建叶子节点俩者的和作为父节点的权值,如此循环下来构成一棵完全二叉树对应的左子树编码
为0,右子树编码为1通过遍历樹即可得出最终的哈夫曼编码贪心算法的时间复杂度。具体代码实现如下
c获取结点的下标f获取其父母,如果其父母的左孩子下标与c相等说明处于左子树,填0 否则在右子树,填1然后c跳到父母