数据结构课程设计报告基于哈夫曼树的文件压缩/解压程序专业班级：信科（2）班
姓名：徐爱娟谢静
学号：20101614310051
20101614310050
2012-12_31
一需求分析
1.课题要求（实现文件的压缩与解压并计算压缩率）
A.描述压缩基本符号的选择方法
B.运行时压缩原文件的规模应不小于5K
2.设计目标
A软件名称：基于哈夫曼编码的文件压缩实用程序系统
B软件组成：huffman.exe
C制作平台及相关调试工具：
Windows XP sp3 Microsoft Visual C++ 6.0
D运行环境：dos/ win2K/win2003/winxp/
E性能特点：
1.软件由一个可执行文件组成
huffman.exe为dos系统应用程序，体积小，高效快捷，适用范围广。
2. 对单字节（256叶子）进行哈夫曼编码，压缩率良好
3. 使用二级缓冲压缩/解压技术，速度比一般算法高
4. 可压缩最大体积为4G的文件，达到Fat32文件系统极限
5. 文件索引体积比常规算法小50%
二概要设计
1.相关函数介绍
1. bool InitFromFile(string fileadd) 从文件中初始化哈夫曼树函数
2. void HTCreat(HTNode ht[],int n) 构造哈夫曼树函数
3. void HCCreat(HTNode ht[],HCode hcd[],int n) 构造哈夫曼编码函数
4. void ConvertFile(HCode hcd[],string fileadd,string fileadd2) 压缩and写入文件函数
5. void DecompressionFile(string fileadd2,string fileadd3) 文件解压函数
6. string Compression(string fileadd) 压缩函数
7. string Decompression(string fileadd2) 解压函数
三详细设计
1压缩算法部分
A核心算法：
Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。
B哈夫曼树构造算法：
Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子：比如有以下数据， ABFACGCAHGBBAACECDFGFAAEABBB先进行统计
G(3) H(1) 括号里面的是统计次数
生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中
运算的过程如下：
1:D+H(2)
2:DE+H(4)
3:F+G(6)
4:C+DEH(8)
5:B+FG(12)
6:A+CDEH(16)
7:ACDEH+BFG(28)
那么转化为Huffman树就是
Huffman树层数
Root
┌┴┐
ACDEH BFG 1
┌┴┐┌┴┐
CDEH A B FG 2
┌┴┐┌┴┐
DEH C F G 3
┌┴┐
DH E 4
┌┴┐
D H 5
取左面是1 右面是0 则有。
注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。
代码位数权值
A = 10 2 16
B = 01 2 12
C = 110 3 12
D = 11111 5 5
E = 1110 4 8
F = 001 3 9
G = 000 2 6
H = 11110 5 5
可以看出Huffman代码是唯一可解的(uniquely decodable)，如果你读到110就一定是C ，不会有任何一个编码是以110开始的。
如果不使用Huffman算法，而使用普通的编码，结果是什么呢？
Huffman树层数
Root
┌┴┐
ABCD EFGH 1
┌┴┐┌┴┐
AB CD EF GH 2
┌┴┐┌┴┐┌┴┐┌┴┐
A B C D E F G H 3
取左面是1 右面是0 则有
代码位数权值
A = 111 3 24
B = 110 3 18
C = 101 3 12
D = 100 3 3
E = 011 3 6
F = 010 3 9
G = 001 3 9
H = 000 3 3
利用Huffman编码得到的权值累计是 73，如果利用普通定长编码的话，则要用84字符长度。从这个比较，可以看出，Huffman是怎么进行压缩的。
C哈夫曼编码结构及算法
编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保留原始的Huffman树，主要是编码段的信息。一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。因为在解码的时候只需要用到code，所以只需要记录每个元素的编码就可以了。
解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。
2．解压缩算法部分
A.基于字符匹配的解压算法
读出结点数就能知道哈夫曼树存入部分的总长，方便读出树哈夫曼树（子结点值和权值），就能由次些信息重新构造完整的哈夫曼树，和各结点的哈夫曼编码。解压时，读取一个字节（8 bit）用一个函数转换为8个字符（用一个数组记录，其元素只是一个0或一个1），然后按哈夫曼树从顶向下查找，如果到达叶子结点，就读出该叶子结点的值，放入缓冲区中，如果不是，则继续找，如此重复，直到缓冲区满了，就写入到解压文件中，再循环以上过程，直到处理完所有数据。
B.缓冲输入输出
和压缩时采用1M二级缓冲相同，如果的压缩时也采用此技术，也会有很大的速度优化，当然程序也变得更加复杂。
四用户使用说明
1.运行huffman.exe程序，出现下面的界面
