数据结构分析
数据结构课程设计分析基于哈夫曼树的文件压缩/解压程序
计算机科学学院××专业××班××号×××
2010-10-20
一需求分析
1.课题要求（实现文件的压缩与解压并计算压缩率）
A.描述压缩基本符号的选择方法
B.运行时压缩原文件的规模应不小于5K
C.提供恢复文件与原文件相同性对比功能
2.设计目标
A软件名称：基于哈夫曼编码的文件压缩实用程序系统
B软件组成：Winhfm.exe dosHfm.exe
C制作平台及相关调试工具：
Windows2000sp4 Borland C++ Builder 6
Dev-C++ 4.9.6.0 UltraEdit-32
D运行环境：dos/win98/winMe/win2K/winxp
E性能特点：
1.软件由两个可执行文件组成，各具特点
DosHfm.exe为dos系统应用程序，体积小，高效快捷，适用范围广。
WinHfm.exe 为windows应用程序，界面友好，使用方便。
2. 对单字节（256叶子）进行哈夫曼编码，压缩率良好
2.使用二级缓冲压缩/解压技术，速度比一般算法高75%以上
3．可压缩最大体积为4G的文件，达到Fat32文件系统极限
4. 文件索引体积比常规算法小50%
5．压缩过程中显示压缩进度并有相关信息提示
6．WinHfm.exe可图形显示源文件的哈夫曼编码构造树
二概要设计
1.相关函数介绍
dos版本程序下的有关函数
１．.void Haffman(int nodeCode,int length,int sum,vector< pair
&hfmCode,vector
２．void indexSearch(int nodeCode,vector
３．void makeIndex(int nodeCode,int &tt,vector
４．void Compress() 压缩函数
５．void UnCompress() 解压缩函数
windows版本程序下的新增函数
１．AnsiString ShowNowTime()计算当前时间（精确到毫秒，以字符串返回）。
２. void search(int nodeCode,int &i,vector
&lchild,vector
３. void searchdraw(int nodeCode,int height,vector
&lchild,vector
４.void __fastcall TForm1::Paga1OnDrawTab(TCustomTabControl *Control,int TabIndex, const TRect &Rect, bool Active)
PageControl的标签页的色彩描绘
５．void __fastcall TForm1::CompareFiles(TObject *Sender) 文件比对函数
当然还有一些相关按钮的响应函数，在此不在赘述，详见程序清单部分
２．函数调用示意图
三详细设计
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节
点的编码，这样取某位压缩代码比较方便，但是因而所有叶子的编码实际上是一个二维数组，空间消耗比较大。
1Nicolai M. Josuttis《The C++ Standard Library--- A Tutorial and Reference》第157页
在此，现提出新的编码存储结构，一个编码用两个整形数表示，第一个数来表示编码长度，例如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的编码为111111*********
按整型数组的存储和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页
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页
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．文件索引算法
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..”
而且哈夫曼树有一个性质，如果一个节点有左孩子，就一定有右孩子，如果没有左孩子，也必然没有右孩子。由此没有必要再用点号来表示叶子了，因而树结构简化成”#A##B#CD”,再用1表示叶子，0表示非叶子，则为”01001011”，这就是它的存储实现。如下：
1胡学钢王浩〈〈软件系列课程实践教程〉〉第49页“扩展二叉树”
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。而非叶子节点的横坐标取
左右孩子的横坐标的平均值，显然这是一个递归算
法。
C.具体的描绘
知道每个节点的坐标后，就可以开始描绘了，画圆与直线的函数都有了，因而遍历所有的节点也就可以把整个树给画出来了。
D.细节问题
计算坐标和描绘节点都是递归方法，因为程序的主体就是二个递归程序。
由于节点众多，整个树画出来需要非常宽的幅面，大约５０００个象素的宽度。在windows98系统中不支持如此大的幅面，而在window2000和windowsXP中支持，因而本系统作图功能不能在win98下体现甚至出现异常而终止了整个压缩程序。因而作图这一部分得使用try/catch1这样的异常处理机制以确保压缩程序在各个系统的稳定运行。
画出来的图比较大，一个屏幕显示不下，而仅使用滚动条又比较麻烦，因而本系统采用了?手抓?功能，可以用鼠标拖动画面。
5. 文件比对算法
本系统具有文件比对功能，它的算法如下：
首先，如果两个文件长度不相等，显然文件不相等，无须进一步比较了。怎么知道指定的文件的长度呢？如果把文件读一遍当然可以知道它的长度，但这样太消耗时间。可以利用
如果两个文件长度相同，则可以正式比对。同样为了加快速度，在此也用了全部变量的缓冲器。文件A可以用１M的读入缓冲器，文件B可以用１M
的写出缓冲器。
然后一一对比，一旦出现不相同，则停止比对，输出?不相等”,程序返回。
如果均相同，则文件相等。
至此，整个算法的描述都已经叙述完了，本系统采用的算法均为以上各部分的最优算法，因而程序的结构比较复杂。
1任常锐黎涛《C++ builder高级编程》296页
四调试分析
五用户使用说明（略）
六测试结果
（一）各种类型文件的压缩率测试
（二）速度测试为避免偶然因素，本项测试选取一个600M左右
以上测试环境：CPU:celeron1.7GHz,内存：DDR256M,硬盘：60GB （7200rpm）,系统：windows XP.
七设计心得体会
数据结构是一门重要并且艰深的课程，学好这门课既需要聪明的大脑，更需要长期的编程实践。在做本课程设计中，前前后后花了一个半月的时间。算法也是越琢磨越明白，看问题也越来越深刻，本程序共做了四次比较大规模的修改，如果没有前面Pascal与c++的基础，光修改程序的工作量就是不可想象的，其间还重写了一次原代码，可见，数据结构和程序设计是密不可分的。
另外，本课程设计中，还直接或间接地联系到了计算机组成原理，微机接口，汇编语言等其它相关课程，可见，计算机是一个统一的学科，没有其他课程的知识储备，仍然是不能实现本设计的。
另外在本课程设计中，我了解到了快速应用程序开发的工具——borland c++ builder 6这是一个庞大的系统，我阅读很多相关的资料和网页，这种知识则是课内所学不到的。
最后，感谢老师在平时对我的指导与鼓励，正是课间给我的精辟回答使我有了更为明晰的思路，才有最终的设计结果。
八附录（此部分不用打印）
程序清单
在此，给出winhfm.exe的程序清单。Dos版本的程序清单在此略过。
#include
#pragma hdrstop
#include "Unit1.h"
#include "Unit3.h"
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#pragma package(smart_init)
#pragma resource "*.dfm"
char inputFileBuffer[1048576];
char wantFileBuffer[1048576];
vector
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 (sM.Length()==1)
sM="0"+sM;
if (sS.Length()==1)
sS="0"+sS;
if (sMs.Length()==1)
sMs="00"+sMs;
if (sMs.Length()==2)
sMs="0"+sMs;
return sH+"点"+sM+"分"+sS+"秒"+sMs;
}
void Haffman(int nodeCode,int length,int sum,vector< pair
{
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
{
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
{
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
if (nodeCode<256)
{
index.push_back(1);code.push_back(nodeCode);return;
}
index.push_back(0);
indexSearch(lchild[nodeCode],lchild,rchild,index,code);
indexSearch(rchild[nodeCode],lchild,rchild,index,code);
}
void makeIndex(int nodeCode,int &tt,vector
&lchild,vector
{
if (index[indexNum++]==1)
{
lchild[nodeCode]=code.front();code.pop_front();
}
else
{
lchild[nodeCode]=tt++;
makeIndex(lchild[nodeCode],tt,index,indexNum,code,lchild,rchild);
}
if (index[indexNum++]==1)
{
rchild[nodeCode]=code.front();code.pop_front();
}
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
vector
vector
vector < pair
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->Text.Length()+1];
strcpy(inputFileName,Edit1->Text.c_str());
char *wantFileName=new char[Edit4->Text.Length()+1];
strcpy(wantFileName,Edit4->Text.c_str());
int handle=open(inputFileName,O_RDONLY);
inputFileByte=filelength(handle);
close(handle);
int step;
fin.open(inputFileName,ios::binary);
//下面统计该文件的编码频率分布
Edit9->Text=ShowNowTime();
Label21->Font->Color=clOlive;
Label22->Font->Color=clNavy;
Form1->Update();
while(1)
{
fin.read(inputFileBuffer,1048576);
if (fin.eof())
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=fin.gcount();
Label6->Caption="原文件共"+AnsiString(inputFileByte)+"byte";
Form1->Update();
for(int i=0;i { int t=inputFileBuffer[i]; if (t<0) t+=256; frequent[t]++; } fin.close(); ProgressBar3->Position=100; //下面构建哈夫曼树 Edit10->Text=ShowNowTime(); Label22->Font->Color=clOlive; Label24->Font->Color=clNavy; Form1->Update(); set < pair for (int i=0;i<=255;i++) nodes.insert(make_pair(frequent[i],i)); while(nodes.size()>1) { set < pair a=nodes.begin(); if (a->first==0) { nodes.erase(a); continue; } b=++nodes.begin(); newNodeCode++; lchild[newNodeCode]=a->second; rchild[newNodeCode]=b->second; nodes.insert(make_pair(a->first+b->first,newNodeCode)); nodes.erase(a); nodes.erase(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 vector indexSearch(newNodeCode,lchild,rchild,index,code); //下面估计压缩后文件长度 wantFileIndexByte+=4; wantFileIndexByte+=1; wantFileIndexByte+=code.size(); int u=newNodeCode-255+code.size(); 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*100.0/inputFileByte)+"%"; //////////////////////////////////////////////////////////下面开始写入索引信息 fout.open(wantFileName,ios::binary); //写入文件长度 fout.put(inputFileByte/16777216); fout.put(inputFileByte%16777216/65536); fout.put(inputFileByte%65536/256); fout.put(inputFileByte%256); //写入根节点号码 fout.put(newNodeCode-256); for(int i=0;i fout.put(code[i]); int indexbuffer=0; int indexbuffersize=0; for(int i=0;i { indexbuffer=indexbuffer<<1; indexbuffer+=index[i]; indexbuffersize++; if (indexbuffersize==8) { fout.put(indexbuffer); indexbuffersize=0; indexbuffer=0; } } if (indexbuffersize!=0) { indexbuffer=indexbuffer<<(8-indexbuffersize); fout.put(indexbuffer); } //////////////////////////////////////////////////////////下面开始写入压缩编码fin1.open(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++) { fin1.read(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) { fout.write(wantFileBuffer,1048576); wantFileBufferSize=0; } } int CompressedByte=(i-1)*1048576+j; if (CompressedByte/double(inputFileByte)*100>=step)
- (完整版)数据结构教案
- 数据结构
- 856数据结构与组成原理
- 810数据结构和计算机组成原理
- 《数据结构及计算机组成原理》考试大纲和参考书目
- 841 数据结构及计算机组成原理
- 832计算机组成原理与数据结构
- 数据结构与算法分析 PPT
- 考试科目832计算机组成原理与数据结构
- 数据结构实验 密码的原理与实现
- 数据结构原理
- 数据结构与算法分析总结
- 数据结构_查找原理与典型查找算法
- 数据结构与算法分析课程设计
- 数据结构与算法(7)：数据库索引原理及优化
- 数据结构原理与分析013433519
- 编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、
- 计算机组成原理与数据结构
- 《数据结构》课程大纲分析
- 计算机组成原理与数据结构(计算机新增考试大纲)