数据结构课程设计分析
基于哈夫曼树的文件压缩/解压程序
计算机科学学院××专业××班××号 ×××
2010-10-20
2
一 需求分析
1.课题要求（实现文件的压缩与解压并计算压缩率）
A.描述压缩基本符号的选择方法
B.运行时压缩原文件的规模应不小于 5K
C.提供恢复文件与原文件相同性对比功能
2.设计目标
A 软件名称：基于哈夫曼编码的文件压缩实用程序系统
B 软件组成：
C 制作平台及相关调试工具：
Windows2000sp4 Borland C++ Builder 6
Dev-C++ UltraEdit-32
D 运行环境：dos/win98/winMe/win2K/winxp
E 性能特点：
1. 软件由两个可执行文件组成，各具特点
为 dos 系统应用程序，体积小，高效快捷，适用范围广。
为 windows 应用程序，界面友好，使用方便。
2. 对单字节（256 叶子）进行哈夫曼编码，压缩率良好
2. 使用二级缓冲压缩/解压技术，速度比一般算法高 75%以上
3．可压缩最大体积为 4G 的文件，达到 Fat32 文件系统极限
4. 文件索引体积比常规算法小 50%
5．压缩过程中显示压缩进度并有相关信息提示
6． 可图形显示源文件的哈夫曼编码构造树
3
二 概要设计
1.相关函数介绍
dos 版本程序下的有关函数
１．.void Haffman(int nodeCode,int length,int sum,vector< pair<int,int> >
&hfmCode,vector<int> &lchild,vector<int> &rchild)哈夫曼树编码递归函数
２ ． void indexSearch(int nodeCode,vector<int> &lchild,vector<int>
&rchild,vector<int> &index,vector<int>&code)索引编码递归函数
３ ． void makeIndex(int nodeCode,int &tt,vector<int> &index,int
&indexNum,list<int> &code,vector<int> &lchild,vector<int> &rchild)索引解码
递归函数
４．void Compress() 压缩函数
５．void UnCompress() 解压缩函数
windows 版本程序下的新增函数
１． AnsiString ShowNowTime()计算当前时间（精确到毫秒，以字符串
返回）。
２. void search(int nodeCode,int &i,vector<int> &lchild,vector<int> &rchild)递
归计算每个节点的 X 坐标
３. void searchdraw(int nodeCode,int height,vector<int> &lchild,vector<int>
&rchild)递归做图函数
４.void __fastcall TForm1::Paga1OnDrawTab(TCustomTabControl *Control,int
TabIndex, const TRect &Rect, bool Active)
PageControl 的标签页的色彩描绘
５．void __fastcall TForm1::CompareFiles(TObject *Sender)
文件比对函数
当然还有一些相关按钮的响应函数，在此不在赘述，详见程序清单部分
4
２． 函数调用示意图
5
三 详细设计
1. 压缩算法部分
A 核心算法：
文件由若干个字节组成，一个字节有 8bits，故有 28=256 种字节构成形
式，对应字节码为 0-255。按此 256 种字节出现频率可构造 haffman 树进行
重新编码，编码后每字节的新编码平均长度将<=8bits，将每个字节对应了
压缩编码写到新文件中，从而达到压缩文件的目的。
B 哈夫曼树构造算法：
用数组 int fre[0..255]表示第 0 号至第 255 号字节节点的出现频率，找出
最小的 fre[a]与 fre[b]，则构建第 256 号节点，其左孩子为 a 号节点，右孩
子 为 b 号 节 点 ， 不 妨 用 数 组 记 录 ： left[256]=a,right[256]=b 。
fre[256]=fre[a]+fre[b].删除 a,b 节点。
然后，再在剩下的节点中找出最小的 fre[a]与 fre[b],构建第 257 号节
点，再删除 a,b 节点。
由此，每做一次，新生成一个节点，删除两个节点，即减少一个节点。
因而在做 255 次后，最后的第 510 号节点即为 haffman 树的根节点。又
由 left[]与 right[]数组，该 haffman 树得到确定。
C 关于 B 部分的优化
1．每次都得找最小的频率节点，所以存放节点的容器最好是已经排过
序的，这样取最小的节点就非常方便了，但新生成的节点就得按顺序插入
到该容器中，如果用顺序表则需要查找插入位置，比较费时——本程序采
用满足以上条件的最适合容器类：STL（标准模板库）下的 Set 集合类，它
以二叉排序树形式存储元素 1，有效地解决了这个问题。
2．某些节点的频率可能为 0，（例如英文文档，字节码即 ASCII 码，在
0-127 之间，故 fre[128..255]一般均为 0），此时，就没有必要将这些频率为
0 的节点加入到哈夫曼数中，因为它们在文件中没有出现，无须重新编码。
D 哈夫曼编码结构及算法
哈夫曼树构造完毕之后，可以利用递归算法遍历
该树，给每个叶子编码，如左图：A 编码为 0 ，B 为
编码 100 ，C 为 101 ，D 为 11 。直观上这样的编码可
以用字符串表示，但这样给写入编码到压缩文件造成
了困难，因为这涉及到字符串的拆分问题,时间上不允
许。
进而，可以用一个整形数组来表示一个编码例如
code[B][0]=1,code[B][1]=0,code[B][2]=1 即 可 表 示 B
节点的编码，这样取某位压缩代码比较方便，但是因
1 Nicolai M. Josuttis《The C++ Standard Library--- A Tutorial and Reference》第 157 页
6
而所有叶子的编码实际上是一个二维数组，空间消耗比较大。
在此，现提出新的编码存储结构，一个编码用两个整形数表示，第一个
数来表示编码长度，例如 code[B].Length=3,第二个数表示编码的十进制值，
因为 101[2]=5[10] 所以 code[B].Dec=5 。这样极大地节省了空间。但似乎这样
会给向压缩文件写入编码带来麻烦，难道还要把 Dec 值再转换为 101 才能
写到文件中？事实上不需要，而且在速度上反而比前面的结构更快。关于
使用此种编码结构在速度上的优势，将在后面详细解释。
E 压缩编码写入算法——一级 32 位缓冲器算法
Cpu 与 i/0 设备通讯是并行处理的办法，最小处理单元是一个字节，即
8bist,所以希望以 bit 为单位将编码写到压缩文件中这在硬件上就是不可能
的，C++语言也更不可能提供有关的语句了。因而我们要设置一个缓冲区，
当缓冲区中编码达到或超过 8bits 时，将前 8bits 做为一个 byte 写出到压缩
文件中。
如果编码存储结构是字符串，那么缓冲区也自然是一个字符串，写入文
件时涉及到字符串与数字的转换，效率上是很不划算的。
如果编码存储结构是整型数组，那么缓冲区实际上就是一个数值 t,t 初
始值为 0，此时读入压缩编码的第一 bit 加到 t 中，然后 t 左移一位；再读
一 bit 压缩编码，加到 t 中，t 左移一位；8 次之后，t 已经达到 8 位，将 t
（此时 t 是一个〈=255 整数，正好是一个字节〉写出到压缩文件中即可。
这是绝大多数人的方案。但是本软件的压缩编码是用两个整型数字表示
的，无法取得某个 bit 的值，应该怎么办呢？
在 VC,C++builder 和=dev-c++这些著名的编译器中，int 型是 32bits，也
就是定义 int a 后，a 本身就成了一个绝佳的 32 位缓冲器[在本设计中，称之
为一级缓冲器]。如前所说，缓冲器 8 位就够了，a 作为 32 位缓冲器,前面 8
位可用来缓冲输出，而后面的 24 位又为一次性向缓冲器输入压缩代码提供
了空间，因为哈夫曼树的深度一般不会超过 25 层（参见附录 1），这样 32
位缓冲器既给压缩代码的输出提供了方便又给其输入提供了方便。下面就
一个具体事例来比较说明。
例如 A 的编码为 10000000111，B 的编码为 111111011111111
按整型数组的存储和 8 位缓冲方案编码，则先读 A 的每位代码，达到 8
位时输出 byte=10000000；再按位读入 3 位 A 的剩余编码 111，然后按位读
入 5 位 B 的 编 码 11111 ， 输 出 byte=11111111, 以 此 类 推 ， 既 而 输 出
0111111，而 B 的最后 2 位与下面的字节编码再合成输出。
而用双整数存储和 32 位缓冲器方案编码，则可一次性将 A 的编码
(code[A].Dec)读入到缓冲器中（即缓冲器 a+=code[A].Dec）,此时缓冲器容量
为 11 位，11>8，输出前 8 位（用&操作可屏蔽掉后 24 位），此时缓冲器清
除前 8 位（a=a<<8）,然后一次性读入 B 的代码置入 a 中，此时 a 容量为
3+15=18 位，此时输出前 8 位，现在 a=10 位仍然大于 8,在输出 8 位，剩余
2 位与下面的编码继续组合输出。
显然，无论在运算时间上和存储空间上，后者均占明显优势。当然后者
出现了&与<<运算 1，而这样的运算相当于汇编语言的 AND 与 SAL2 指令，
1 王浩《面向对象程序设计》35-36 页
2 沈美明 温冬蝉《ibm-pc 汇编语言程度设计》61-62 页
7
是非常高效迅速的，比从内存读编码快捷，且操作次数也少的多。
F 写入算法另一角度的优化——使用二级 1024K 缓冲器
在写入编码的过程中，宏观的过程是：以字节形式读取原文件，然后找到
该字节的编码，进而以字节形式写到压缩文件中去。不停的字节读写会给
cpu 带来频繁的中断并且硬盘的磁头来回在磁道扇区中移动，减慢了速度。
而如果以数据块的形式读写则可以有效地利用到 DMA 通讯 1，减少了 cpu
中断，并使硬盘磁头连续移动，显著加快了速度。而 c++语言的 iofstream 类
的 read（）与 write（）成员函数为此思想的实现提供了可能。
所以，可以开辟一个 1024K 的缓冲区，先将文件前 1024K 的字节读入内存
缓冲区中（在本设计中，这称为二级缓冲器），编码后的字节也不急于写入
文件中，而是先写到另一个二级缓冲区中，当其足够 1024K 时再以数据块
的形式写到压缩文件中。然后清空缓冲区，继续做下一个 1024K 的编码写
入。
而 缓 冲 区 本 身 ， 其 实 就 是 二 个 整 形 数 组 ， read_buffer[1048576] 和
write_buffer[1048576] 。不过这样的数组声明已经太大了，可以用 STL 的
vector 向量类来代替这个数组（vector 结构实际也就是一个封装了的加强型
数组）。
一级缓冲器在微观上解决了写编码速度的问题，而二级缓冲器则在宏观上
改善了写编码的问题，两者关系的嵌套的关系，实际的程序主结构也就是一
个二重循环，外层控制二级缓冲器，内层控制一级缓冲器。
G 一些细节问题
采用以单字节为单位构造哈夫曼树，这样数的规模不会太过庞大，构造
的时间比较快，并且有比较良好的压缩率（详细的压缩报告见附录二）。如
果以双字节构造，则可能出现叶子数为 65536 的哈夫曼树，虽然压缩率可以
得到相对提高，但已经提升不明显，而整个的压缩过程将变的缓慢。如果进
行智能识别频率采样，一方面采样过程又要花费一定的时间，另一方面，哈
夫曼树本身的结构也决定了这样做并不划算，也给解压缩和写入索引带来了
许多麻烦。
用 left[]和 right[]数组来描述一颗二叉树而没有用指针，是为了避免指针
可能带来的由叶子到根的反向建树的麻烦；另一方面，树的节点和叶子数目
基本确定，没太多必要使用灵活的指针和相关的内存分配语句。
编码写出后，内层缓冲器可能剩几个 bit，没有达到 8bit,此时应补‘0’或
‘1’以凑齐 8 位再写出。
文件的大小也不大可能正好被 1024K 整除，要考虑到最后的剩余部分
字节的编码，即要计算好最后的实际字节读取个数，fstream 的成员函数
gcount()2能解决这个问题。
如果把整个压缩过程作为一个函数的话，二级缓冲区的定义最好在函数
外作为全局量定义，否则可能栈溢出。
1 戴梅萼 史嘉权《微型计算机技术及应用》第二版 199-201 页
2 王浩 《面向对象程序设计》 第 245 页
8
2．解压缩算法部分
A.基于字符匹配的解压算法
现在从已压缩过的文件中读取一段代码，
如”1001011101……”,哈夫曼树结构入图，先读如第一
个字节”10010111”,先取出“1”，在 ABCD 中均无这个
编码；于是再取出“0”和刚才的“1”组成“01”，仍无此
编码；再取出“0”，组成“010”，发现 B 叶子的编码与
之相等，此时解码得 B,输出到解码文件中，以此类
推。这是最容易想到的方法，但效率很低。首先，取
出一个编码后要和所有叶子的编码比对；其次，编码
比对是基于字符串的比对，比较慢。
对于前者的改进可以通过：1.一旦比对成功就不再和剩下的比对 2.按照编码
的长度之后长度相同的编码比对等等。而后者的改进则出现了 B 算法。
B.基于数值匹配的算法
既然字符比对比较慢，我们可以把编码用 2 个整数表示，前者是编码的
十进制值，后者是编码长度。这样只和编码长度相等的十进制相比就可以
了。这样把字符串的比较优化为数字比较，据测算，速度提高了约 10 倍。
但是这两种算法都基于与叶子编码比较，相当于不断的尝试，解压速度很难
突破 100KB/s。
C.基于循径法
既然所有的编码都隐藏在一个树中，那么根据遇 0 向左走遇 1 向右走的
方法自然就能很容易地找到叶子，从而得到解码。仍如前例，读入”1”向右
走，发现不是叶子，继续；读入”0”向左走，发现不是叶子，继续；读入”0”
向左走，发现是叶子 B，即可解码为 B 写入解码文件。也就是说，循径法充
分地利用了每次读进来的编码，能够以确定的路径找到叶子而不需要尝试。
不过要使用这种方法，就必须想建立一个原文件的哈夫曼树，详见索引算法
部分。使用此方法后速度有极大飞跃。
D.缓冲输入输出
和压缩时采用 1M 二级缓冲相同，如果的压缩时也采用此技术，也会有
很大的速度优化，当然程序也变得更加复杂。
E.细节问题
读入和写出仍然基于字节单位，基于位的操作同样要在程序内部通过位
运算完成。
最后一个字节在解码时必须注意到压缩时最后一个字节是用”0”或”1”填
充的，要避免多余解码，可以在索引中写入文件大小，详见下节。
3．文件索引算法
9
A. 简介
由解压缩的算法可知，一个压缩了的文件解压缩
的前提是知道原文件的具体每个字节的编码。这些信
息称为索引。上页的细节问题中提到最好在压缩后的
文件中标出原文件的长度，这也是索引信息。一般索
引信息放在文件的最前部分。
B. 写入编码法
最直接的方法就是，把每个字节的编码写到压缩后的文件
中去。入图，先写入’A’及其编码 0，接着是‘B’及编码 100,’C’101,’D’11。
即：
01000001 0 01000010 100 01000011 101 01000100 11
‘A’ ‘B’ ‘C’ ‘D’
当然直接这样写会给阅读信息造成困难，因为计算机不知道’A’的编
码是几位，它读入 0 后就不知道是否下一位究竟是‘A’的编码还是’B’的
ASCII 的开始。所以我们还得标识出编码的长度 A1 B3 C3 D2,即
01000001 00000000 0 01000010 00000011 100 01000011 00000011 101 01000100 00000010 11
A 长度 0 B 长度 3 C 长度 3 D 长度 2
这样的确是区别开了，没有歧义，可是编码变长了，我们可以规定叶子
是按顺序排列的，此时编码就变短了，即：
00000000 0 00000011 100 00000011 101 00000010 11
A 的长度 B 的长度 C 的长度 D 的长度
事实上最大一共有 256 个叶子，计算机依次读 256 次就可以了。这样索
引占用的长度一般是 512K 左右。不过一旦一个文件只有 5 片叶子，也得
有 256 个字节来标识编码长度，这在压缩只有几个字节的小文件时，反而
文件会扩大几十倍。
C. 写入树结构法
如果我们知道原文件的哈夫曼树的结构，也自然就可获知每个叶子的
编码，那么，把这棵树的结构作为索引存入文件也可以，如果树可大可小，
索引的长度也会可大可小，解决了 B 方法索引长度始终大于 256 字节的问
题 。 如 上 图 ， 如 果 非 叶 子 节 点 为 ’#’, 这 个 树 的 结 构 编 码 1就
是”#A..##B..C..D..”
而且哈夫曼树有一个性质，如果一个节点有左孩子，就一定有右孩
子，如果没有左孩子，也必然没有右孩子。由此没有必要再用点号来表示叶
1 胡学钢 王浩 〈〈软件系列课程实践教程〉〉第 49 页“扩展二叉树”
10
子了，因而树结构简化成”#A##B#CD”,再用 1 表示叶子，0 表示非叶子，则
为”01001011”，这就是它的存储实现。如下：
00000100 01000001 01000010 01000011 01000100 01001011
有 4 个节点 ‘A’ ‘B’ ‘C’ ‘D’ 树结构
对于一棵完整的有 256 个叶子的 haffman 树，大约需要 320 字节就可以
存储它了。比前面的方法节省了 38%。当然，要使用这种方法，就必须在压
缩时用一个递归函数来遍历这棵树以获得树结构编码。
D.关于索引的解码
AB 两种建索引的方法都很方便于索引的解码，但空间占用大后者灵活
性差，而若使用 C 方法，则索引的解码也成了问题。换句话说，我们得由
“01001011”来还原出一棵 haffman 树。
本系统是这样做的，首先得把树结构编码从文件中读到一个数组中，把
叶子编号读到另一个数组中，然后由这两个数组用递归的方法造出树。然
后由这棵树再求出每个叶子的编码。当然这一步可以略去了，因为解压缩
采用寻径法，不需要再求每个叶子的具体编码了。
E.相关细节问题
为了给正文部分解码代码方便并显示解码进度，本系统在压缩的文件开
头的四个字节记录了原文件的长度。
索引中，节点的顺序和结构树的顺序必须相同，例如都采用先序，中序
或后续，本系统采用先序。
索引的编码和解码都用到了递归，而递归的参数都相当多而且很多是数
组，为了节省空间，要运用引用操作。
4. 哈夫曼树显示算法
A.简介
在本系统的 windows 版本的程序中，有显示哈夫曼树的功能，这涉及到
了计算机做图以及一些具体的算法。
B.节点的布局
一棵树在描绘之前必须要计算好每个节点的坐
标，否则漫无目的地从头节点分左右画下去就很可能
造成节点位置的重合。Y 轴的坐标比较好控制，因为
它有节点的深度决定了。X 轴呢？本系统利用中序遍
历 haffman 树，对叶子节点 X 坐标递增的方法来确
定的。例如左树，中序依次遍历了 ABCD ，于是
ABCD 的横坐标就是 1 ，2 ，3 ，4 。而非叶子节点的
横坐标取左右孩子的横坐标的平均值，显然这是一个
递归算法。
11
C.具体的描绘
知道每个节点的坐标后，就可以开始描绘了，画圆与直线的函数都有
了，因而遍历所有的节点也就可以把整个树给画出来了。
D. 细节问题
计算坐标和描绘节点都是递归方法，因为程序的主体就是二个递归程
序。
由于节点众多，整个树画出来需要非常宽的幅面，大约５０００个象素
的宽度。在 windows98 系统中不支持如此大的幅面，而在 window2000 和
windowsXP 中支持，因而本系统作图功能不能在 win98 下体现甚至出现异
常而终止了整个压缩程序。因而作图这一部分得使用 try/catch1这样的异常处
理机制以确保压缩程序在各个系统的稳定运行。
画出来的图比较大，一个屏幕显示不下，而仅使用滚动条又比较麻烦，
因而本系统采用了“手抓”功能，可以用鼠标拖动画面。
5. 文件比对算法
本系统具有文件比对功能，它的算法如下：
首先，如果两个文件长度不相等，显然文件不相等，无须进一步比较了。
怎么知道指定的文件的长度呢？如果把文件读一遍当然可以知道它的长度，但
这样太消耗时间。可以利用<>库的 filelength 函数来直接求得文件长度。
如果两个文件长度相同，则可以正式比对。同样为了加快速度，在此也用
了全部变量的缓冲器。文件 A 可以用１M 的读入缓冲器，文件 B 可以用１M
的写出缓冲器。
然后一一对比，一旦出现不相同，则停止比对，输出“不相等”,程序返回。
如果均相同，则文件相等。
至此，整个算法的描述都已经叙述完了，本系统采用的
算法均为以上各部分的最优算法，因而程序的结构比较复
杂。
1 任常锐 黎涛《C++ builder 高级编程》296 页
12
四 调试分析
序号 时间 相关信息
1 10 月 30 日 dos 版，基于字符串编码
2 11 月 6 日 编码存储结构改为双整数表达，改进了解压缩的性能。
3 11 月 7 日 采用长度与数据分开存储的方法构建索引减少了索引长度
4 11 月 16 日 基于位操作编码及解码，大幅度提高效率
5 11 月 18 日 编码方案采用二重缓冲，进一步加快效率
6 11 月 20 日 采用寻径法解码，提高解码速度，并采用树索引，取代代码索引
7 11 月 22 日 开发 windows 版本
8 11 月 26 日 加入编码部分的进度提示
9 11 月 29 日 加入选取文件功能，交互性更强
10 12 月 4 日 图形显示哈夫曼构造树
11 12 月 5 日 改进显示外观 使树结构更加对称
12 12 月 6 日 加入“手抓”功能
13 12 月 10 日 更正了某些文件名不能压缩的问题
14 12 月 12 日 加入文件比对功能
15 12 月 13 日 更正了压缩时可能出现的一个重大错误
16 12 月 14 日 完善用户操作部分，避免了某些误操作
17 12 月 15 日 解决了 win98 下因无法作大图而终止运行的问题
五 用户使用说明（略）
13
六 测试结果
（一）各种类型文件的压缩率测试
文件大小 压缩后 压缩率%
文件 1（英文文本 1） 77465 51566 66．57
文件 2（英文文本 2） 65194 35116 53．99
文件 3（中文文本 1） 289772 221695 76．52
文件 4（中文文本 2） 110421 66088 59．85
文本文件
（txt）
文件 5（混合文本） 167979 132181 78．69
文件 1（英文文本 1） 261879 134172 51．23
文件 2（英文文本 2） 146432 107809 73．62
文件 3（中文文本 1） 50688 30836 60．83
文件 4（中文文本 2） 28672 15090 52．62
Word 文档
（doc）
文件 5（混合文本） 837632 649675 77．60
文件 1（无图片） 4317 3076 71．25
文件 2（有图片） 504539 373441 74．01
网页文件
（htm,mht）
文件 3（有图片） 165832 110556 66．74
文件 1 199680 141151 70．68幻灯片文件
（ppt） 文件 2 102912 56669 55．06
文件 1 33280 15452 46．43电子表格文
件（xls） 文件 2 358400 195286 54．48
文件 1（16 色文件） 308278 283395 91．92
文件 2（256 色文件） 137218 40755 29．70
位图文件
（bmp）
文件 3（24 位真彩） 430214 263175 61．17
文件 1 94208 67453 71．60
文件 2 663552 497400 74．96
可执行文件
（exe）
文件 3 1566278 1459349 93．17
（二）速度测试 为 避 免 偶 然 因 素 ， 本 项 测 试 选 取 一 个 600M 左 右
（621889873 byte）的虚拟光驱文件，压缩三次，取平均值。
压缩时间 压缩速率 解压缩时间 解压缩速率
第一次 5506Kb/s 4178Kb/s
第二次 5631Kb/s 4039Kb/s
第三次 5046Kb/s 4298Kb/s
平均值 5382Kb/s 4171Kb/s
以 上 测 试 环 境 ： CPU:, 内 存 ： DDR256M, 硬 盘 ： 60GB
14
（7200rpm）,系统：windows XP.
七 设计心得体会
数据结构是一门重要并且艰深的课程，学好这门课既需要
聪明的大脑，更需要长期的编程实践。在做本课程设计中，前
前后后花了一个半月的时间。算法也是越琢磨越明白，看问题
也越来越深刻，本程序共做了四次比较大规模的修改，如果没
有前面 Pascal 与 c++的基础，光修改程序的工作量就是不可想
象的，其间还重写了一次原代码，可见，数据结构和程序设计
是密不可分的。
另外，本课程设计中，还直接或间接地联系到了计算机组成
原理，微机接口，汇编语言等其它相关课程，可见，计算机是
一个统一的学科，没有其他课程的知识储备，仍然是不能实现
本设计的。
另外在本课程设计中，我了解到了快速应用程序开发的工具
——borland c++ builder 6 这是一个庞大的系统，我阅读很多相
关的资料和网页，这种知识则是课内所学不到的。
最后，感谢老师在平时对我的指导与鼓励，正是课间给我的
精辟回答使我有了更为明晰的思路，才有最终的设计结果。
15
八 附录（此部分不用打印）
程序清单
在此，给出 的程序清单。Dos 版本的程序清单在此略过。
#include <>
#pragma hdrstop
#include ""
#include ""
#include <>
#include <vector>
#include <set>
#include <utility>
#include <iterator>
#include <list>
#include <>
#include <>
using namespace std;
#pragma package(smart_init)
#pragma resource "*.dfm"
char inputFileBuffer[1048576];
char wantFileBuffer[1048576];
vector <double> X(511,0);
AnsiString ShowNowTime()
{
Word H, M, S,Ms;
DecodeTime(Now(), H, M, S,Ms);
AnsiString sH=AnsiString(H);
AnsiString sM=AnsiString(M);
AnsiString sS=AnsiString(S);
AnsiString sMs=AnsiString(Ms);
if (()==1)
sM="0"+sM;
if (()==1)
sS="0"+sS;
if (()==1)
sMs="00"+sMs;
if (()==2)
sMs="0"+sMs;
return sH+"点"+sM+"分"+sS+"秒"+sMs;
}
void Haffman(int nodeCode,int length,int sum,vector< pair<int,int> > &hfmCode,vector<int> &lchild,vector<int>
&rchild)
{
if (nodeCode==-1) return;
if (nodeCode<=255)
{
hfmCode[nodeCode].first=length;
hfmCode[nodeCode].second=sum;
return;
}
Haffman(lchild[nodeCode],length+1,sum*2,hfmCode,lchild,rchild);
Haffman(rchild[nodeCode],length+1,sum*2+1,hfmCode,lchild,rchild);
}
void search(int nodeCode,int &i,vector<int> &lchild,vector<int> &rchild)
{
16
if (lchild[nodeCode]==-1)
{
X[nodeCode]=i;
i++;
return;
}
search(lchild[nodeCode],i,lchild,rchild);
search(rchild[nodeCode],i,lchild,rchild);
X[nodeCode]=(X[lchild[nodeCode]]+X[rchild[nodeCode]])/2;
}
void searchdraw(int nodeCode,int height,vector<int> &lchild,vector<int> &rchild)
{
if (nodeCode==-1) return;
if (lchild[nodeCode]==-1)
{
Form3->Image1->Canvas->Brush->Color=clWhite;
Form3->Image1->Canvas->TextOut(X[nodeCode]*20-5,height*60+14,AnsiString(nodeCode));
Form3->Image1->Canvas->Brush->Color=clRed;
}
Form3->Image1->Canvas->Ellipse(X[nodeCode]*20-5,height*60-
4,X[nodeCode]*20+10+4,height*60+10+4);
Form3->Image1->Canvas->TextOut(X[nodeCode]*20-1,height*60-1,height);
Form3->Image1->Canvas->Brush->Color=clYellow;
if (lchild[nodeCode]!=-1)
{
Form3->Image1->Canvas->MoveTo(X[nodeCode]*20+5,height*60+10+4);
Form3->Image1->Canvas->LineTo(X[lchild[nodeCode]]*20+5,height*60+60-4);
searchdraw(lchild[nodeCode],height+1,lchild,rchild);
Form3->Image1->Canvas->MoveTo(X[nodeCode]*20+5,height*60+10+4);
Form3->Image1->Canvas->LineTo(X[rchild[nodeCode]]*20+5,height*60+60-4);
searchdraw(rchild[nodeCode],height+1,lchild,rchild);
}
}
void indexSearch(int nodeCode,vector<int> &lchild,vector<int> &rchild,vector<int> &index,vector<int>&code)
{
if (nodeCode<256)
{
_back(1);_back(nodeCode);return;
}
_back(0);
indexSearch(lchild[nodeCode],lchild,rchild,index,code);
indexSearch(rchild[nodeCode],lchild,rchild,index,code);
}
void makeIndex(int nodeCode,int &tt,vector<int> &index,int &indexNum,list<int> &code,vector<int>
&lchild,vector<int> &rchild)
{
if (index[indexNum++]==1)
{
lchild[nodeCode]=();_front();
}
else
{
lchild[nodeCode]=tt++;
makeIndex(lchild[nodeCode],tt,index,indexNum,code,lchild,rchild);
}
if (index[indexNum++]==1)
{
rchild[nodeCode]=();_front();
17
}
else
{
rchild[nodeCode]=tt++;
makeIndex(rchild[nodeCode],tt,index,indexNum,code,lchild,rchild);
}
}
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Compress(TObject *Sender)
{
if (!FileExists(Edit1->Text))
{
ShowMessage(Edit1->Text+" 文件不存在!");
return;
}
Edit8->Text="";
Edit9->Text="";
Edit10->Text="";
Edit11->Text="";
Edit12->Text="";
Edit13->Text="";
Label1->Caption="";
Label2->Caption="";
Label3->Caption="";
Label4->Caption="";
Label5->Caption="";
Label6->Caption="";
Label20->Caption="";
Label26->Font->Color=clOlive;
ProgressBar1->Position=0;
ProgressBar3->Position=0;
StatusBar1->Panels->Items[0]->Text="";
StatusBar1->Panels->Items[1]->Text="";
Edit8->Text=ShowNowTime();
Label21->Font->Color=clNavy;
Form1->Update();
ifstream fin,fin1;
ofstream fout;
vector <int> frequent(256,0);
vector <int> lchild(512,-1);
vector <int> rchild(512,-1);
vector < pair <int,int> > hfmCode(256);
int newNodeCode=255;
int inputFileByte;
int wantFileByte=0;
int wantFileIndexByte=0;
int wantFileContentBit=0;
int wantFileContentByte;
int buffer;
int buffersize;
int inputFileRestSize;
int inputFileMega=0;
char *inputFileName=new char[Edit1->()+1];
strcpy(inputFileName,Edit1->_str());
18
char *wantFileName=new char[Edit4->()+1];
strcpy(wantFileName,Edit4->_str());
int handle=open(inputFileName,O_RDONLY);
inputFileByte=filelength(handle);
close(handle);
int step;
(inputFileName,ios::binary);
//下面统计该文件的编码频率分布
Edit9->Text=ShowNowTime();
Label21->Font->Color=clOlive;
Label22->Font->Color=clNavy;
Form1->Update();
while(1)
{
(inputFileBuffer,1048576);
if (())
break;
for(int i=0;i<1048576;i++)
{
int t=inputFileBuffer[i];
if (t<0) t+=256;
frequent[t]++;
}
inputFileMega+=1;
ProgressBar3->Position=inputFileMega*1048576/double(inputFileByte)*100;
}
inputFileRestSize=();
Label6->Caption="原文件共"+AnsiString(inputFileByte)+"byte";
Form1->Update();
for(int i=0;i<inputFileRestSize;i++)
{
int t=inputFileBuffer[i];
if (t<0) t+=256;
frequent[t]++;
}
();
ProgressBar3->Position=100;
//下面构建哈夫曼树
Edit10->Text=ShowNowTime();
Label22->Font->Color=clOlive;
Label24->Font->Color=clNavy;
Form1->Update();
set < pair<int,int> > nodes;
for (int i=0;i<=255;i++)
(make_pair(frequent[i],i));
while(()>1)
{
set < pair<int,int> > ::iterator a,b;
a=();
if (a->first==0)
{
(a);
continue;
}
b=++();
newNodeCode++;
lchild[newNodeCode]=a->second;
19
rchild[newNodeCode]=b->second;
(make_pair(a->first+b->first,newNodeCode));
(a);
(b);
}
//下面调用 haffman 递归函数，对 haffman 树各叶子进行编码
Haffman(newNodeCode,0,0,hfmCode,lchild,rchild);
Label20->Caption="开始描绘哈夫曼树图";Form1->Update();
try
{
int t=1;
search(newNodeCode,t,lchild,rchild);
Form3->Image1->Canvas->Brush->Color=clWhite;
Form3->Image1->Canvas->Rectangle(0,0,6000,1500);
Form3->Image1->Canvas->Brush->Color=clYellow;
Form3->Image1->Canvas->MoveTo(X[newNodeCode]*10,40);
searchdraw(newNodeCode,1,lchild,rchild);
Form3->Show();
Form3->Update();
}
catch(...)
{
Label20->Caption="哈夫曼树图描绘失败,请使用 win2000";Form1->Update();
goto BEGININDEX;
}
Label20->Caption="完成哈夫曼树图";Form1->Update();
BEGININDEX:
//索引准备工作
Edit11->Text=ShowNowTime();
Label24->Font->Color=clOlive;
Label23->Font->Color=clNavy;
Form1->Update();
vector<int> index;
vector<int>code;
indexSearch(newNodeCode,lchild,rchild,index,code);
//下面估计压缩后文件长度
wantFileIndexByte+=4;
wantFileIndexByte+=1;
wantFileIndexByte+=();
int u=newNodeCode-255+();
if(u%8)
wantFileIndexByte+=u/8+1;
else
wantFileIndexByte+=u/8;
Label2->Caption="索引长度为"+AnsiString(wantFileIndexByte)+"byte";
for(int i=0;i<=255;i++)
wantFileContentBit+=frequent[i]*hfmCode[i].first;
if (wantFileContentBit%8)
wantFileContentByte=wantFileContentBit/8+1;
else
wantFileContentByte=wantFileContentBit/8;
wantFileByte=wantFileIndexByte+wantFileContentByte;
Label5->Caption=AnsiString(wantFileByte*
//////////////////////////////////////////////////////////下面开始写入索引信息
20
(wantFileName,ios::binary);
//写入文件长度
(inputFileByte/16777216);
(inputFileByte%16777216/65536);
(inputFileByte%65536/256);
(inputFileByte%256);
//写入根节点号码
(newNodeCode-256);
for(int i=0;i<();i++)
(code[i]);
int indexbuffer=0;
int indexbuffersize=0;
for(int i=0;i<();i++)
{
indexbuffer=indexbuffer<<1;
indexbuffer+=index[i];
indexbuffersize++;
if (indexbuffersize==8)
{
(indexbuffer);
indexbuffersize=0;
indexbuffer=0;
}
}
if (indexbuffersize!=0)
{
indexbuffer=indexbuffer<<(8-indexbuffersize);
(indexbuffer);
}
//////////////////////////////////////////////////////////下面开始写入压缩编码
(inputFileName,ios::binary);
buffer=0;
buffersize=0;
int wantFileBufferSize=0;
//核心编码过程
Edit12->Text=ShowNowTime();
Label23->Font->Color=clOlive;
Label25->Font->Color=clNavy;
Form1->Update();
step=0;
for(int i=1;i<=inputFileMega;i++)
{
(inputFileBuffer,1048576);
for(int j=0;j<1048576;j++)
{
int t=inputFileBuffer[j];
if (t<0) t+=256;
int a=hfmCode[t].second;
buffer+=a<<(32-buffersize-hfmCode[t].first);
buffersize+=hfmCode[t].first;
while (buffersize>=8)
{
int temp=buffer>>24;
wantFileBuffer[wantFileBufferSize++]=temp;
buffersize-=8;
buffer=buffer<<8;
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
}
21
int CompressedByte=(i-1)*1048576+j;
if (CompressedByte/double(inputFileByte)*100>=step)
{
ProgressBar1->StepIt();
StatusBar1->Panels->Items[0]->Text="已完成"+AnsiString(step)+"%";
StatusBar1->Panels->Items[1]->Text=AnsiString(CompressedByte)+"字节";
Form1->Update();
step++;
}
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
}
}
//写入外层缓冲区最后的部分字节
(inputFileBuffer,inputFileRestSize);
for(int i=0;i<inputFileRestSize;i++)
{
int t=inputFileBuffer[i];
if (t<0) t+=256;
int a=hfmCode[t].second;
buffer+=a<<(32-buffersize-hfmCode[t].first);
buffersize+=hfmCode[t].first;
while (buffersize>=8)
{
int temp=buffer>>24;
wantFileBuffer[wantFileBufferSize++]=temp;
buffersize-=8;
buffer=buffer<<8;
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
}
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
int CompressedByte=inputFileMega*1048576+i;
if (CompressedByte/double(inputFileByte)*100>=step)
{
ProgressBar1->StepIt();
StatusBar1->Panels->Items[0]->Text="已完成"+AnsiString(step)+"%";
StatusBar1->Panels->Items[1]->Text=AnsiString(CompressedByte)+"字节";
Form1->Update();
step++;
}
}
ProgressBar1->Position=100;
(wantFileBuffer,wantFileBufferSize);
//写入内层缓冲区残余的 bit
if (buffersize)
(buffer>>24);
();
();
Label3->Caption="内容长度为"+AnsiString(wantFileContentByte)+"byte";
22
Label4->Caption="压缩后文件长度为"+AnsiString(wantFileByte)+"byte";
Edit13->Text=ShowNowTime();
Label25->Font->Color=clOlive;
Label26->Font->Color=clNavy;
StatusBar1->Panels->Items[0]->Text="已完成 100%";
StatusBar1->Panels->Items[1]->Text=AnsiString(inputFileByte)+"字节";
Label1->Caption="ok";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::UnCompress(TObject *Sender)
{
Edit7->Text="";
Edit14->Text="";
Label7->Font->Color=clOlive;
Label8->Font->Color=clOlive;
Label18->Caption="";
StatusBar2->Panels->Items[0]->Text="";
StatusBar2->Panels->Items[1]->Text="";
StatusBar2->Panels->Items[2]->Text="";
if (!FileExists(Edit2->Text))
{
ShowMessage(Edit2->Text+" 文件不存在!");
return;
}
Label7->Font->Color=clNavy;
Edit7->Text=ShowNowTime();
Form1->Update();
ifstream fin;
ofstream fout;
int wantFileByte=0;
vector <int> lchild(512,-1);
vector <int> rchild(512,-1);
(Edit2->_str(),ios::binary);
(Edit3->_str(),ios::binary);
for (int i=1;i<=4;i++)
{
int t=();
if (t<0)
t=256+t;
wantFileByte=wantFileByte*256+t;
}
StatusBar2->Panels->Items[0]->Text="原文件长"+AnsiString(wantFileByte)+"字节";
//读入索引
int newNodeCode=256;
int leaf=();
if (leaf<0)
leaf+=256;
leaf+=2;
list<int>code;
for(int i=0;i<leaf;i++)
{
int t=();
if (t<0)
t+=256;
_back(t);
}
int indexSize=leaf*2-1;
int indexByteSize;
if(indexSize%8)
indexByteSize=indexSize/8+1;
23
else
indexByteSize=indexSize/8;
vector<int> index;
for(int i=1;i<=indexByteSize;i++)
{
int t=();
if (t<0) t+=256;
for(int j=1;j<=8;j++)
{
if(t&128)
_back(1);
else
_back(0);
if(()==indexSize)
goto end1;
t=t<<1;
}
}
end1:;
int indexNum=1;
int nodeCode=256;
int tt=257;
makeIndex(nodeCode,tt,index,indexNum,code,lchild,rchild);
int step=1;
int haveByte=0;
int searchNumber=newNodeCode;
int wantFileBufferSize=0;
while(1)
{
(inputFileBuffer,1048576);
if (()) break;
for(int i=0;i<1048576;i++)
{
int buffer=inputFileBuffer[i];
int buffersize=8;
while(buffersize)
{
if (buffer&128)
searchNumber=rchild[searchNumber];
else
searchNumber=lchild[searchNumber];
if (searchNumber<256)
{
wantFileBuffer[wantFileBufferSize++]=searchNumber;
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
haveByte++;
if (haveByte/double(wantFileByte)*100>=step)
{
StatusBar2->Panels->Items[1]->Text="已解压"+AnsiString(step)+"%";
StatusBar2->Panels->Items[2]->Text=AnsiString(haveByte)+"字节";
Form1->Update();
ProgressBar2->StepIt();
step++;
}
if (haveByte==wantFileByte)
goto end;
searchNumber=newNodeCode;
}
buffer=buffer<<1;
24
buffersize-=1;
}
}
}
for(int i=0;i<();i++)
{
int buffer=inputFileBuffer[i];
int buffersize=8;
while(buffersize)
{
if (buffer&128)
searchNumber=rchild[searchNumber];
else
searchNumber=lchild[searchNumber];
if (searchNumber<256)
{
wantFileBuffer[wantFileBufferSize++]=searchNumber;
if (wantFileBufferSize==1048576)
{
(wantFileBuffer,1048576);
wantFileBufferSize=0;
}
haveByte++;
if (haveByte/double(wantFileByte)*100>=step)
{
StatusBar2->Panels->Items[1]->Text="已解压"+AnsiString(step)+"%";
StatusBar2->Panels->Items[2]->Text=AnsiString(haveByte)+"字节";
Form1->Update();
ProgressBar2->StepIt();
step++;
}
if (haveByte==wantFileByte)
goto end;
searchNumber=newNodeCode;
}
buffer=buffer<<1;
buffersize-=1;
}
}
end:
StatusBar2->Panels->Items[1]->Text="已解压 100%";
StatusBar2->Panels->Items[2]->Text=AnsiString(haveByte)+"字节";
ProgressBar2->Position=100;
(wantFileBuffer,wantFileBufferSize);
();
();
Label7->Font->Color=clOlive;
Label8->Font->Color=clNavy;
Edit14->Text=ShowNowTime();
Form1->Update();
Label18->Caption="ok!";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::CompareFiles(TObject *Sender)
{
Edit15->Text="";
Edit16->Text="";
Label27->Caption="";
Label28->Caption="";
Label19->Caption="";
Label9->Font->Color=clOlive;
Label11->Font->Color=clOlive;
StatusBar3->Panels->Items[1]->Text="";
StatusBar3->Panels->Items[2]->Text="";
if (!FileExists(Edit5->Text))
25
{
ShowMessage(Edit5->Text+" 文件不存在!");
return;
}
if (!FileExists(Edit6->Text))
{
ShowMessage(Edit6->Text+" 文件不存在!");
return;
}
char * file1=new char[Edit5->()+1];
strcpy(file1,Edit5->_str());
char * file2=new char[Edit6->()+1];
strcpy(file2,Edit6->_str());
int handle=open(file1,O_RDONLY);
int file1size=filelength(handle);
close(handle);
handle=open(file2,O_RDONLY);
int file2size=filelength(handle);
close(handle);
if (file1size!=file2size)
{
Label28->Caption="文件 A 长度为"+AnsiString(file1size)+"字节,文件 B 长度为
"+AnsiString(file2size)+"字节";
Label19->Caption="文件长度不同!";
return;
}
Label28->Caption="文件 A,B 长度均为"+AnsiString(file1size)+"字节";
Edit15->Text=ShowNowTime();
Label9->Font->Color=clNavy;
Form1->Update();
ifstream fin1; ifstream fin2;
(file1,ios::binary);
(file2,ios::binary);
int Mega=0;
while(1)
{
(inputFileBuffer,1048576);
( wantFileBuffer,1048576);
if (()||())
break;
for(int i=0;i<1048576;i++)
{
if (inputFileBuffer[i]!=wantFileBuffer[i])
{
Label19->Caption="文件在第"+AnsiString(Mega*1048576+i)+"字节不相等!";
Edit16->Text=ShowNowTime();
Label9->Font->Color=clNavy;
Label11->Font->Color=clOlive;
return;
}
}
Label27->Caption="已经完成比对"+AnsiString(++Mega)+"M 字节";
StatusBar3->Panels->Items[1]->Text="已比对
"+AnsiString(int(Mega*1048576/double(file1size)*100))+"%";
StatusBar3->Panels->Items[2]->Text=AnsiString(Mega*1048576)+"字节";
26
Form1->Update();
}
for(int i=0;i<();i++)
{
if (inputFileBuffer[i]!=wantFileBuffer[i])
{
Label19->Caption="文件在第"+AnsiString(Mega*1048576+i)+"字节不相等!";
Edit16->Text=ShowNowTime();
Label9->Font->Color=clNavy;
Label11->Font->Color=clOlive;
return;
}
}
StatusBar3->Panels->Items[1]->Text="已比对 100%";
StatusBar3->Panels->Items[2]->Text=AnsiString(file1size)+"字节";
Edit16->Text=ShowNowTime();
Label9->Font->Color=clNavy;
Label11->Font->Color=clOlive;
Label19->Caption="文件相等";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::inputofCompress(TObject *Sender)
{
if (OpenDialog1->Execute()==True)
{
Edit1->Text=OpenDialog1->FileName;
}
int i;
for(i=1;i<=Edit1->()&&Edit1->Text[i]!='.';i++);
Edit4->Text=Edit1->(1,i-1)+".hfm";
StatusBar2->Panels->Items[0]->Text="";
StatusBar2->Panels->Items[1]->Text="";
StatusBar2->Panels->Items[2]->Text="";
Edit8->Text="";
Edit9->Text="";
Edit10->Text="";
Edit11->Text="";
Edit12->Text="";
Edit13->Text="";
Label1->Caption="";
Label2->Caption="";
Label3->Caption="";
Label4->Caption="";
Label5->Caption="";
Label6->Caption="";
Label20->Caption="";
Label18->Caption="";
Label26->Font->Color=clOlive;
ProgressBar1->Position=0;
ProgressBar3->Position=0;
StatusBar1->Panels->Items[0]->Text="";
StatusBar1->Panels->Items[1]->Text="";
}
void __fastcall TForm1::inputofSave1(TObject *Sender)
{
if (SaveDialog1->Execute()==True)
{
Edit4->Text=SaveDialog1->FileName;
}
}
27
void __fastcall TForm1::inputofUnCompress(TObject *Sender)
{
if (OpenDialog2->Execute()==True)
{
Edit2->Text=OpenDialog2->FileName;
}
Edit7->Text="";
Edit14->Text="";
Label7->Font->Color=clOlive;
Label8->Font->Color=clOlive;
ProgressBar2->Position=0;
Label18->Caption="";
}
void __fastcall TForm1::inputofSave(TObject *Sender)
{
if (SaveDialog1->Execute()==True)
{
Edit3->Text=SaveDialog1->FileName;
}
}
void __fastcall TForm1::ChooseFileA(TObject *Sender)
{
if (OpenDialog1->Execute()==True)
{
Edit5->Text=OpenDialog1->FileName;
}
Edit15->Text="";
Edit16->Text="";
Label9->Font->Color=clOlive;
Label11->Font->Color=clOlive;
Label27->Caption="";
Label28->Caption="";
Label19->Caption="";
StatusBar3->Panels->Items[1]->Text="";
StatusBar3->Panels->Items[2]->Text="";
}
void __fastcall TForm1::ChooseFileB(TObject *Sender)
{
if (OpenDialog1->Execute()==True)
{
Edit6->Text=OpenDialog1->FileName;
}
Edit15->Text="";
Edit16->Text="";
Label9->Font->Color=clOlive;
Label11->Font->Color=clOlive;
Label27->Caption="";
Label28->Caption="";
Label19->Caption="";
StatusBar3->Panels->Items[1]->Text="";
StatusBar3->Panels->Items[2]->Text="";
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Paga1OnDrawTab(TCustomTabControl *Control,
int TabIndex, const TRect &Rect, bool Active)
{
Control->Canvas->Font->Color=clBlue;
Control->Canvas->Font->Size=10;
Control->Canvas->TextOut(14,4,"压缩");
Control->Canvas->TextOut(60,4,"解压缩");
Control->Canvas->TextOut(114,4,"文件比对");
}
//---------------------------------------------------------------------------
