1.哈夫曼编码
根据字符在文件中出现的频率,用二进制串表示各字符的最佳编码方式
2.基本思想
1)所有字符均作为叶子节点放入一个树集合T
2)字符的使用频率作为权值
3)贪心策略:每次从树集合T中取出没有双亲且权值最小的两棵树作为左右子树构造一棵新树放回树集合T中,直到T中只剩下一棵树
4)特点:以自底向上的方式通过n-1次合并构建出一棵树;权值越大的叶子离根越远
3.算法设计
1.定义一个树的结构体,包含权值、双亲(节点编号)、左孩子(节点编号)、右孩子(节点编号)、表示的字符
2.定义一个编码的结构体,包括储存编码的数组和编码开始的下标
时间复杂度
O(n2)
代码实现
未完待续