文档介绍：《数据结构与算法》
课程设计报告
学 号：20131002072
班级序号：116131-12
姓 名：陶剑浩
指导教师：吴亮
成 绩：
中国地质大学（武汉）信息工程学院
2015年1月
缩函数,成功返回 true 失败 false
bool decompress(char *input, char *output); //恢复函数,成功返回 true 失败false
void compare(char *input, char *output); //将原文件与压缩后的文件比较
void compare2(char *input, char *output); //将原文件与恢复后的文件比较
private:
int root; //记录根结点的位置
int leafnum; //记录不同字符的个数
HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1
char byte; //压缩文件时用来缓冲bit的变量
int bitsnum; //byte中bit的个数
int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数
};
主程序的流程及模块间关系：
主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：
1:压缩函数 bool compress(char *input, char *output)
2:恢复函数 bool decompress(char *input, char *output)
3:恢复文件与原文件的对比函数 void compare2(char *input, char *output)
并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。
（3）详细设计表示：
NO
YES
哈夫曼编码位操作压缩存储
压缩文件成功!
计算压缩率%
打开文本文件统计文件长度
初始化节点
构建哈夫曼树
计算左右分支权值大小,进行无重复前缀编码
压缩文件失败
核心算法----huffman算法：根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。在F中删除这两棵树，同时将所得到的二叉树加入F中。重复,直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。
Huffman编码流程
图编码流程
Huffman解码流程
NO
YES
解压压缩文件成功!
解压缩文件失败!
打开压缩文件读取原文件长度进行文件定位
根据哈夫曼编码的长短,对节点进行排序
通过哈夫曼编码的长短,依次解码,从原来的位存储还原到字节存储
在单字节内对相应位置补0
图解码流程
3．编码
问题：huffman编码是采用等长编码还是采用不等长问题，采用不等长编码要避免译码的二义性或多义性。假设用0表示字符D,用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。因此，若对某一个字符集进行不等长编码，则要求字符集合中任何一个字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。
解决方法：可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的 huffman树的问题。
4．程序及算法分析
程序运行结果：
时间复杂度：大部分函数应在O(n2) 。
5．小结
第一题的实****让我了解了对Huffman的理解运用，对压缩软件有了更深的认识。同时对于存