数据结构与算法 课程设计报告
课程设计题目：哈弗曼编码/译码器
专业班级： 信息与计算科学1001班 姓 名： 学 号：
设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩：
哈夫曼算法的编码和译码系统
目录
一.设计要求 二.功能设计流程
三.详细设计
四.调试
五.总结
六.参考文献
七.附录源代码
一．设计要求
设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
1.1基本要求
1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)
2)分别采用动态和静态存储结构
3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树； 4)编码：利用建好的哈夫曼树生成哈夫曼编码； 5)输出编码；
6)设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
1.2进一步完成内容
1)译码功能； 2)显示哈夫曼树； 3)界面设计的优化。
二．功能流程图
2.1主要流程实现图
初始化哈夫曼树 编码 文件 打印哈夫曼树 译码 文件 图的算法实现 2.2主要菜单选择函数
Main函数中包裹四个主要功能函数，即
用于构造和初始哈夫曼树的HuffmanCoding函数
用于对指定文件进行编码的void Coding函数
用于对哈夫曼编码进行译码的void Decoding函数
用于在屏幕终端上显示哈弗满树的void Print_tree函数 其相互联系如下图所示
void Coding HuffmanCoding Main函数 Decoding() Print_tree
其中用于初始化哈夫曼树的 Huffman coding()函数包含两个子函数，即 （1）void select(HuffmanTree HT,int j,int *s1,int *s2)
从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点 （2）void Init()
输入n个字符及其对应的权值，根据权值建立哈夫曼树，其相互联系如图所示
在本程序中，主界面为一个功能选择界面，根据提示，使用者可以选择不同的功能进行操作。但由于在编制写程序的源代码中，出于方便编写的考虑，我们对一些功能所要引用的文件进行了提前的命名，因此在使用之前使用者应该提前知晓操作程序所需要的特定文件名，现总结如下：
Tobetrans.txt:用于存储待编码的文本文件
Codefile.txt:用于存储由Tobetrans.txt编码得到的哈弗曼编码信息 Textfile.txt: 用于存储由Codefile.txt译码得到的文本文件
void select void Init() HuffmanCoding（） hfmtree.txt:用于存储哈夫曼树的文本文件
三．详细设计
3.1初始化哈夫曼树：
基本思想：首先根据使用者输入的待编码字符和相应的权重值，再根据哈夫曼树的建立过程机型哈夫曼树的构造
主要步骤及主要功能函数：
（1）首先根据给定的权重构造n棵二叉树的森林，其中每个二叉树都只有一个权值为w[i]的根节点
（2）在森林中选取两个权值最小的根节点作为一个新二叉树的左右结点 其具体函数为
void select(HuffmanTree HT,int j,int *s1,int *s2) //其中s1,s2为权值最小的两个根节点
for (i=1;i<=j;i++) if (HT[i].parent==0) {
*s1=i; break; }
for (;i<=j;i++)
if ((HT[i].parent==0)&&(HT[i].weight HT[*s1].parent=1; 通过遍历所有节点找到权值最小的结点 （3）设新二叉树的根节点为左右子结点的权值和 其函数表达为 for(i=n+1;i<=m;++i) { select(HT,i-1,&s1,&s2); 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; （4）从森林中删除选中的那两棵二叉树，同时加入新构造的那个二叉树 （5）重复上述步骤，得到所需的哈弗曼二叉树 3.2编码： 基本思想：根据已构造好的哈夫曼树，对于每一个根节点从自身位置开始往根节点回溯，，并且规定哈夫曼树中的左节点代表0，有节点代表1，从而得到每个字符的哈弗曼编码 主要步骤及主要功能函数： for(i=1;i<=n;++i) {