实验七哈夫曼编码

算法设计与分析实验报告 姓名 杨勇涛 班级 计科 102 班 一 实验名称 哈夫曼编码 时间 2012 年 4 月 4 日 星期三 第四节 地点 12 311 二 实验目的及要求 设计任务 从键盘输入一串电文字符能输出对应的哈夫曼编码 同时 能翻译由哈夫曼 编码生成的代码串 输出相应的电文字符串 设计要求 1 从终端读入字符集大小 n 以及 n 个字符和 n 个权值 建立哈夫曼树及哈 夫曼编码 2 利用已经建好的哈夫曼树 对输入的字符串进行编码 输出编码序列 3 利用已建好的哈夫曼树对输入的二进制编码进行译码 并输出结果 设计任务 从键盘输入一串电文字符能输出对应的哈夫曼编码 同时 能翻译由哈夫曼编码生成的代 码串 输出相应的电文字符串 设计要求 1 从终端读入字符集大小 n 以及 n 个字 符和 n 个权值 建立哈夫曼树及哈夫曼编码 2 利用已经建好的哈夫曼树 对输入的字 符串进行编码 输出编码序列 3 利用已建好的哈夫曼树对输入的二进制编码进行译码 并输出结果 三 实验环境 Vc 四 实验内容 从键盘输入一串电文字符能输出对应的哈夫曼编码 同时 能翻译由哈夫曼编码生成的代 码串 输出相应的电文字符串 五 算法描述及实验步骤 一 对给定的 n 个权值 W1 W2 W3 Wi Wn 构成 n 棵二叉树的初始集合 F T1 T2 T3 Ti Tn 其中每棵二叉树 Ti 中只有一个权值为 Wi 的根结点 它的左右子 树均为空 为方便在计算机上实现算法 一般还要求以 Ti 的权值 Wi 的升序排列 二 在 F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树 新二叉树的根 结点的权值为其左右子树的根结点的权值之和 三 从 F 中删除这两棵树 并把这棵新的二叉树同样以升序排列加入到集合 F 中 四 重复二和三两步 直到集合 F 中只有一棵二叉树为止 六 调试过程及实验结果 七 总结 通过这次编程使我对哈弗曼编码有了更深刻的理解 并且学会了将之前学 过的东西运用到程序中来 八 源程序 include include include typedef char HuffmanCode 动态分配数组 存储哈夫曼编码 typedef struct unsigned int weight 用来存放各个结点的权值 unsigned int parent LChild RChild 指向双亲 孩子结点的指针 HTNode HuffmanTree 动态分配数组 存储哈夫曼树 选择两个 parent 为 0 且 weight 最小的结点 s1 和 s2 void Select HuffmanTree ht int n int s1 int s2 int i min for i 1 i n i if ht i parent 0 min i break for i 1 i n i if ht i parent 0 if ht i weight ht min weight min i s1 min for i 1 i n i if ht i parent 0 break for i 1 i n i if ht i parent 0 s2 min 构造哈夫曼树 ht w 存放已知的 n 个权值 void CrtHuffmanTree HuffmanTree ht int w int n int m i s1 s2 m 2 n 1 ht HuffmanTree malloc m 1 sizeof HTNode for i 1 i n i 1 n 号存放叶子结点 初始化 ht i weight w i ht i LChild 0 ht i parent 0 ht i RChild 0 for i n 1 i m i ht i weight 0 ht i LChild 0 ht i parent 0 ht i RChild 0 非叶子结点初始化 printf nHuffmanTree n for i n 1 i m i 创建非叶子结点 建哈夫曼树 在 ht 1 ht i 1 的范围内选择两个 parent 为 0 且 weight 最小的结点 其序号分别赋值给 s1 s2 Select ht i 1 ht s1 parent i ht s2 parent i ht i LChild s1 ht i RChild s2 ht i weight ht s1 weight ht s2 weight printf d d d n ht i weight ht s1 weight ht s2 weight printf n 哈夫曼树建立完毕 从叶子结点到根 逆向求每个叶子结点对应的哈夫曼编码 void CrtHuffmanCode HuffmanTree ht HuffmanCode hc int n char cd int i start p unsigned int c hc HuffmanCode malloc n 1 sizeof char 分配 n 个编码的头指 针 cd char malloc n sizeof char 分配求当前编码的工作空间 cd n 1 0 从右向左逐位存放编码 首先存放编码结束符 for i 1 i n i 求 n 个叶子结点对应的哈夫曼编码 start n 1 初始化编码起始指针 for c i p ht i parent p 0 c p p ht p parent 从叶子到根结点 求编码 if ht p LChild c cd start 0 左分支标 0 else cd start 1 右分支标 1 hc i char malloc n start sizeof char 为第 i 个编码分配空间 strcpy hc i free cd for i 1 i n i printf HuffmanCode of 3d is s n ht i weight hc i printf n void main HuffmanTree HT HuffmanCode HC int w i n wei m printf nn scanf d w int malloc n 1