计算机算法设计与分析赫夫曼编码

计算机算法设计与分析作业 1 题目描述 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法 其压 缩率通常在 20 90 之间 哈夫曼编码算法使用字符在文件中出现 的频率来建立一个用 0 1 串表示各字符的最优表示方法 现在给定 一串字符出现的频率 求出其哈夫曼编码 2 问题分析 1 根据伪代码 先来分析复杂度 建立树从 1 到 n 1 需时间为 O n 从优先队列选择频度最小的点 实际优先队列就是一个堆 所以所需时间为 O logn 综合来看 该 算法的时间复杂度为 O nlogn 2 赫夫曼算法的正确性 1 具有贪心选择性质 设 C 是编码字符集 C 中字符的频率为 f c 又设 x 和 y 是 C 中具有 最小 频率的两个字符 则存在 C 的最优前缀码使 x 和 y 具有相 同码长且仅最后一位编码不同 2 具有最有子结构 设 T 是表示字符集 C 的一个最优前缀码的完全二叉树 C 中字符 C 的出现频率为 f c 设 x 和 y 是树 T 种的两个叶子且为兄弟 z 是它们的父亲 若将 z 看做是具有频率 f z f x f y 的字符 则树 T T x y 表示字符集 C C x y z 的一个最优前 缀码 贪心选择性质 贪心选择性所做的是一个非线性的子问题处理过 程 即一个子问题并不依赖于另一个子问题 但是子问题间有严格 的顺序性 要证明一个问题具有 贪心选择性 就必须证明每一 步所做的贪心选择最终导致一个问题的整体最优解 这是必须的性 质 具有最优子结构的性质 即每个子问题的最优解的集合就是整体最 优解 这是必须的性质 因为贪心算法解决的问题流程就需要依序 研究每个子问题 然后综合之得出最后结果 必须拥有最优子结构 性质 才能保证贪心算法返回最优解 3 伪代码 算法思路 假设 C 是一个包含 n 个字符的集合 且每个字符 c 属于 C 都是一个 出现频度为 f c 的对象 算法以自底向上的方式构造出最有编码所 对应的数 T Q 是一个以 f 为关键字的最小优先队列 Huffman C n C Push C into Q For i from 1 to n 1 Allocate a new node z x y x EXTRACT MIN Q y EXTRACT MIN Q Z left x Z right y F z f x f y Push z into Q Return EXTRACT MIN Q 4 4 源代码源代码 include include include include using namespace std const int MAX 30 struct treeNode char ch int weight treeNode left treeNode right node MAX struct mycomp bool operator treeNode a treeNode b return a weight b weight treeNode Huffman priority queue treeNode vector mycomp q int n q size for int i 0 ileft ln z right rn z weight z left weight z right weight q push z return q top void dfs treeNode root int mark int n if root left NULL 叶子节点 cout ch for int i 0 i n i cout mark i cout left mark n 1 mark n 1 dfs root right mark n 1 int main int n priority queue treeNode vector mycomp pq cout n cout 分别输入各元素及其频度 endl for int i 0 i node i ch cin node i weight node i left NULL node i right NULL pq push node i