软件课程设计报告基于哈夫曼树的文件压缩/解压程序
计算机科学学院××专业××班××号×××
2009-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) { ProgressBar1->StepIt(); StatusBar1->Panels->Items[0]->Text="已完成"+AnsiString(step)+"%"; StatusBar1->Panels->Items[1]->Text=AnsiString(CompressedByte)+"字节"; Form1->Update(); step++; } if (wantFileBufferSize==1048576) { fout.write(wantFileBuffer,1048576); wantFileBufferSize=0; } } } //写入外层缓冲区最后的部分字节 fin1.read(inputFileBuffer,inputFileRestSize); for(int i=0;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) { fout.write(wantFileBuffer,1048576); wantFileBufferSize=0; } } if (wantFileBufferSize==1048576) { fout.write(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; fout.write(wantFileBuffer,wantFileBufferSize); //写入内层缓冲区残余的bit if (buffersize) fout.put(buffer>>24); fout.close(); fin1.close(); Label3->Caption="内容长度为"+AnsiString(wantFileContentByte)+"byte"; Label4->Caption="压缩后文件长度为"+AnsiString(wantFileByte)+"byte"; Edit13->Text=ShowNowTime(); Label25->Font->Color=clOlive; 计算机科学与技术学院数据结构实验报告 班级2014级计算机1班学号20144138021 姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5 一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。 3、译码。 利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型： 利用哈夫曼编码实现压缩和解压缩 1.问题描述 利用哈夫曼编码，实现压缩和解压缩的数据元素具有如下形式: 结点： weight:存储结点的权值 parent:是结点双亲在向量中的下标 lchild:结点的左儿子向量下标 rchild:结点右儿子向量下标 bits:位串，存放编码 ch:字符 start:编码在位串中的起始位置 文件操作记录： b:记录字符在数组中的位置 count:字符出现频率（权值） lch、rch、parent:定义哈夫曼树指针变量 bits[256]:定义存储哈夫曼编码的数组 2.功能需求 对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。 3.实现要点 （1）构造哈弗曼树过程中，首先将初始森林的各根结点的双亲和左、右儿子指针置-1；叶子在向量T的前n个分量中，构成初始森林的n个结点；对森林中的树进行n次合并， 并产生n-1个新结点，依次放入向量T的第i个分量中。 （2）编码过程中，从叶子T[i]出发，利用双亲的指针找到双亲T[p]；再根据T[p]的孩子指针可以知道T[i]是T[p]的左儿子还是右儿子，若是左儿子，则生成代码0，否则生成代码1； （3）在文件压缩和解压过程中，主要参考网上资料，每个步骤都基本理解，并注上了详细解析。 4．函数定义 功能：输入权重，构造一棵哈弗曼树 void huffman(hftree T) { if(n<1 || n > m)return; int i,j,p1,p2; float small1,small2; //初始化 cout<<"请输入叶子权重(5个)："< 一、需求分析 1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：①对需要传送的数据预先编码； ②对从接收端接收的数据进行译码； 2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman 树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 4、本演示程序将综合使用C++和C语言； 5、测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03， 0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和 一、概要设计 1、设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n} 基本操作： Initialization(&HT，&HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 实验二二叉树的遍历及霍夫曼编码 班级：计科1101班 学号：0909101605 姓名：杜茂鹏 2013年5月22日 一、实验目的 掌握二叉树的建立及遍历操作，霍夫曼编码基本操作及存储结构表示 二、实验内容 1. 系统要求包含以下功能 1）初始化：从终端读入字符集大小n，以及n个字符和n个权值（或者读入字符集和频度数据文件），建立哈夫曼树，并将哈夫曼树存入到文件HfmTree 中。 2）编码：利用已建好的哈夫曼树（如果不在内存中，则从文件中读入），从文件ToBeTran中读入原文，对原文进行编码，将编码后的结果存入文件CodeFile 中。 3）译码：利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。 4）打印：打印输出哈夫曼树，显示ToBeTran, TextFile和CodeFile文件的内容。 三、实验要求 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 四、概要设计 1）首先动态分配数组存储霍夫曼树及存储霍夫曼编码表，然后从终端或文件读入霍夫曼树的字符变量及其频度，初始化建立霍夫曼树并将其写入文件HfmTree.txt中。 2）从指定的文件succe.txt中读入原文，利用已经编好的霍夫曼树对其编码，将编码结果写入文件Coding.txt保存。 3）利用已建好的哈夫曼树将文件Coding.txt中的代码进行译码，结果存入文件decoding.txt中。 五、测试数据： 2．原文内容“THIS IS MY PROGRAM” 六、详细设计 实验内容(原理、操作步骤、程序代码) //建立霍夫曼树，对原文进行编码、译码 #include 哈夫曼编译码器课程设计报告完整版 XXX学院本科 数据结构课程设计总结报告 设计题目：实验一、哈夫曼编/译码器 学生姓名：XXX 系别：XXX 专业：XXX 班级：XXX 学号：XXX 指导教师：XXX XXX 6 月 21日 xxx学院 课程设计任务书 题目一、赫夫曼编译码器 专业、班级 xxx 学号 xxx 姓名 xxx 主要内容、基本要求、主要参考资料等： 1. 主要内容 利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端经过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（既能够双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。 2. 基本要求 系统应具有以下功能： （1）C：编码（Coding）。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中，将以此建好的哈夫曼树存入文件HuffmanTree中 （2）D：解码（Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。 （3）P：打印代码文件（Print）。将文件codefile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入 文件codeprint中。 （4）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。 3. 参考资料：数据结构（C语言版）严蔚敏、吴伟民编著； 数据结构标准教程胡超、闫宝玉编著 完成期限： 6月21 日 指导教师签名： 课程负责人签名： 6月 21 日 一、设计题目（任选其一） 实验一、哈夫曼编/译码器 二、实验目的 1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力； 2 深化对算法课程中基本概念、理论和方法的理解； 3 巩固构造赫夫曼树的算法； 4 设计试验用程序实验赫夫曼树的构造。 三、运行环境（软、硬件环境） Windows xp sp3，Visual C++ 6.0英文版 数据结构实验报告 实验名称：实验三树 学生姓名： 班级： 班内序号： 学号： 日期：2012年12月7号 1、实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频 度，并建立赫夫曼树 2、建立编码表(CreateT able)：利用已经建好的赫夫曼树进行编码，并将每个字符 的编码输出。 3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串 输出。 4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输 出译码结果。 5、打印(Print)：以直观的方式打印赫夫曼树（选作） 6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压 缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 2、程序分析 2.1存储结构 （1）二叉树 template 合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程数据结构与算法 课程设计名称英文文件的压缩和解压缩 学生姓名 学号 专业班级 指导教师李红沈亦军 2010 年 6 月 题目：（采用哈夫曼编码思想实现文件的压缩和解压缩功能，并提供压缩前后的占用空间之比）（1）压缩原文件的规模应不小于5K。（2）提供解压缩后文件与原文件的相同性比较功能。 一、问题分析和任务定义。 1.1问题分析 本实验是利用哈夫曼编码思想，设计对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。要解决以上问题，需从以下几个方面着手： （1）如何读入待压缩的文本文件，统计文本文件中各字符的频数及出现的字符个数； （2）如何构造huffman树，进行huffman编码，生成压缩文件（后缀名.txt （3）如何读入待解压的压缩文件名,并利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，生成解压文件（后缀名为.txt）； （4）如何提供压缩前后的占用空间之比 1.2输入、输出数据的形式、值的范围，算法（程序）所能达到的功能 本实验的数据主要是以字符型为主，还有一些自定义的整形和浮点型变量，该实验室对文件进行压缩和解压（被压缩文件容量要求大于>5KB），通过该算法程序可以大致上满足实验所要求的功能，即压缩原文件的规模不小于5KB，提供了压缩后的文件与原文件的压缩比例，也即提供了性能比较功能 1.3 测试用的数据 本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。 所测试的部分数据： 题目：哈夫曼编码器 班级：031021班姓名：李鑫学号：03102067 完成日期：2011/12 1. 问题描述 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。 2.基本要求 一个完整的系统应具有以下功能： (1) I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 (2) E：编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码（Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 以下为选做： (4) P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T：印赫夫曼树（Tree printing）。将已在内存中的赫夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint 中。 3.测试 (1)利用教科书例6-2中的数据调试程序。 (2) 用下表给出的字符集和频度的实际统计数据建立赫夫曼树，并实现以下报文的编码和译码：“THIS PROGRAME IS MY FA VORITE”。 字符 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 4.实现提示 (1) 编码结果以文本方式存储在文件Codefile中。 (2) 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。 (3) 在程序的一次执行过程中，第一次执行I，D或C命令之后，赫夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。 1.问题描述 哈弗曼树的编码与译码 —功能：实现对任何类型文件的压缩与解码 —输入：源文件，压缩文件 —输出：解码正确性判定，统计压缩率、编码与解码速度 —要求：使用边编码边统计符号概率的方法（自适应Huffman编码）和事先统计概率的方法（静态Huffman编码） 2.1程序清单 程序书签： 1.main函数 2.压缩函数 3.select函数 4.encode函数 5.解压函数 #include long weight; //权值 unsigned char ch;//字符 int parent,lchild,rchild; char code[256];//编码的位数最多为256位int CodeLength;//编码长度 }hfmnode[512]; void compress(); void uncompress(); //主函数 void main() { int choice; printf("请选择1~3：\n"); printf("1.压缩文件\n"); printf("2.解压文件\n"); printf("3.退出！\n"); scanf("%d",&choice); if(choice==1)compress(); else if(choice==2)uncompress(); else if(choice==3)return; else printf("输入错误！"); } XXX学院本科 数据结构课程设计总结报告 设计题目：实验一、哈夫曼编/ 译码器 学 生：系XXX 别：XXX 专业： XXX 班级： XXX 学号：XXX 指导教师：XXX XXX 2012 年 6 月21 日 xxx 学院 课程设计任务书 题目一、赫夫曼编译码器 专业、班级xxx 学号xxx xxx 主要容、基本要求、主要参考资料等： 1. 主要容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/ 译码系统。试为这样的信息收发站写一个哈夫曼的编/ 译码系统。 2. 基本要求 系统应具有以下功能： （1）C：编码（Coding）。对文件tobetrans 中的正文进行编码，然后将结果存入文件codefile 中，将以此建好的哈夫曼树存入文件HuffmanTree 中（2）D：解码（Decoding ）。利用已建好的哈夫曼树将文件codefile 中的代码进行译码，结果存入textfile 中。 （3）P：打印代码文件（Print ）。将文件codefile 以紧凑格式显示在终端上，每行50 个代码。同时将此字符形式的编码文件写入文件codeprint 中。 （4）T：打印哈夫曼树（Tree Printing ）。将已在存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint 中。3. 参考资料：数据结构（C 语言版）严蔚敏、吴伟民编著；数据结构标准教程胡 超、闫宝玉编著 完成期限：2012 年6 月21 日指导教师签名：课程负责人签名：、设计题目（任选其一） 实验一、哈夫曼编/ 译码器 二、实验目的 1 巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力； 2 深化对算法课程中基本概念、理论和方法的理解； 3 巩固构造赫夫曼树的算法； 2012 年 6 月21 日 实验报告 欧阳光明（2021.03.07） 实验名称 Huffman 编码 专业班级 计科三班 姓名 学号 指导教师 日期 .12.20 一、实验目的 熟练掌握二叉树应用（Huffman 编码）的基本算法实现。 二、实验内容 ● 1．对输入的一串电文字符实现Huffman 编码，再对Huffman 编码生成的代码串进行译码， 输出电文字符串。实现功能如下： ? Huffman 树的建立 ? Huffman 编码的生成 编码文件的译码 三、实验要求 设计思路： 数据结构： #define n 100 //叶子结点数 #define m 2*n1 //Huffman 树中结点总数 typedef struct { int weight; //权值 int lchild , rchild , parent; //左右孩子及双亲指针 }HTNode; //树中结点类型 typedef HTNode HuffmanTree[m+1]; //0号单元不用 主要实现函数： ? 统计字符串中字符的种类以及各类字符的个数的函数 ? 构造Huffman 树的函数 ? Huffman 编码的函数 ? 建立正文的编码文件的函数 ? 代码文件的译码函数 ? 主函数 四、实验概要设计 1)功能框图 五. 使用说明 1.运行环境：VC++ 6.0 2.首先选择主控菜单中的操作１，即建表，然后进行其它操作． 六．实验截图 Huffman 编码程序 Huffman 树的建立 从叶子到根逆向求编码Huffman 编码的生成 编码文件的译码 退出 七实验体会 1、构建哈夫曼树的关键在于找最小树；在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 2、由于学习的不足没有实现编码文件的译码，今后会加以改进 (╯﹏╰） 3、在逆向求编码的for循环里犯了一个逻辑错误导致求出来的3、4位编码串行，尝试了多钟数据输入才找到原因所在，并加以改正，编写程序需一步一步的去调试并找到错误所在。 附源程序： #include 数据结构 课程设计 题目名称：huffman编码与解码实现文件的压缩与解压专业年级： 组长： 小组成员： 指导教师： 二〇一二年十二月二十六日 目录 一、目标任务与问题分析 (2) 1.1目标任务 (2) 1.2问题分析 (2) 二、算法分析 (2) 2.1构造huffman树 (2) 2.1.1 字符的统计 (2) 2.1.2 huffman树节点的设计 (2) 2.2构造huffman编码 (3) 2.2.1 huffman编码的设计 (3) 2.3 压缩文件与解压文件的实现 (3) 三、执行效果 (4) 3.1界面 (4) 3.2每个字符的编码 (4) 3.3操作部分 (5) 3.4文件效果 (6) 四、源程序 (7) 五、参考文献 (16) huffman编码与解码实现文件的压缩与解压 一、目标任务与问题分析 1.1目标任务 采用huffman编码思想实现文件的压缩和解压功能，可以将任意文件压缩，压缩后也可以解压出来。这样即节约了存储空间，也不会破坏文件的完整性。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法分析 2.1构造huffman树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 字符的统计 用结构体huffchar来存放文件字符的信息。其中有文件中不同字符出现的种类Count、字符data。 struct huffchar{ //存放读入字符的类； int Count;//字符出现的个数； char data;//字符； }; 函数实现： bool char_judge(char c)//判断字符出现的函数； void char_add(char c)//添加新出现的字符； void read_file_count() //文件的读取 2.1.2 huffman树节点的设计 用结构体huff_tree来存储结点信息，其中有成员频率weight、父亲节点parent、左儿子节点lchild、右儿子节点rchild。 哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 计算机科学与技术学院数据结构实验报告 班级 2014级计算机1班学号姓名张建华成绩 实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的 本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 二、实验问题描述 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能： 1、接收原始数据。 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。 2、编码。 利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。 3、译码。 利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。 4、打印编码规则。 即字符与编码的一一对应关系。 5、打印哈夫曼树， 将已在内存中的哈夫曼树以直观的方式显示在终端上。 三、实验步骤 1、实验问题分析 1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为： Typedef strcut { Int weight；/*结点权值*/ Int parent； Int lchild； Int rchild； }HNodeType； 2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。 求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路 课程论文 题目：哈夫曼树及其应用课程设计报告学号： 201230210115 姓名：黄文宣 班级： 1232101 专业：信息安全 课程名称：数据结构 课程老师：王晓燕 二零一肆年一月 目录 1、课程设计的题目及简介 (3) 2、实验目的 (3) 3、设计说明 (4) 4、总体流图 (4) 5、详细设计 (5) 6、实现部分 (6) 7、测试程序 (9) 8、心得与体会 (10) 一、课程设计题目 哈夫曼树及其应用 数据的读入﹑存储，生成文件，将键盘输入的信息存入指定的文件中；设计一程序求解此问题．哈夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理 建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 哈夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。 二、实验目的 1 熟悉树的各种存储结构及其特点。 2 掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。 三、设计说明 建立哈夫曼树，将哈夫曼树的结构定义为一个结构型的一维数组，每个元素含有四项：权值，双亲，左孩子，右孩子。哈夫曼树上进行二进制编码：往左走，编码为0，往右走，编码为1，然后将从根结点到树叶中的所有0、1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。给定的权值从键盘输入，输出所建立的哈夫曼树编码，再从键盘输入二进制的编码进行译码，输出译码。 四、总体流图 哈夫曼树编码系统 初始化 编码 重新建立哈夫 曼树 译码 打印编码 Huffman编码对英文文本的压缩和解压缩中国地质大学计算机学院信息安全专业 信息论实验报告 #include gets(filename); ifp=fopen(filename,"rb"); if(ifp==NULL){ printf("\n\t文件打开失败!\n "); system("pause"); return; } printf("\t请您输入压缩后的文件名（如无路径则默认为桌面文件）："); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp==NULL){ printf("\n\t压缩文件失败!\n "); system("pause"); return; } flength=0; while(!feof(ifp)){ fread(&c,1,1,ifp); header[c].count++; //字符重复出现频率+1 flength++; //字符出现原文件长度+1 } 电子科技大学 实验报告 课程名称：数据结构与算法 学生姓名：陈*浩 学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼 实验时间： 2014-2015-2学期 信息与软件工程学院 实验报告(二) 学生姓名：陈**浩学号：*************指导教师：钱** 实验地点：科研教学楼A508实验时间：一、实验室名称：软件实验室 二、实验项目名称：数据结构与算法—树 三、实验学时：4 四、实验原理： 霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952年，David A. Huffman在麻省理工攻读博士时所发明的。 在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。 例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 霍夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。 可以证明霍夫曼树的WPL是最小的。 课程设计 题目：哈夫曼编码器 院系： 专业班级： 学号： 学生姓名： 指导教师： 2014年1月2日 课程设计需求分析报告 一、分析问题和确定解决方案 1.分析问题 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统,为这样的信息收发站写一个哈夫曼的编/译码系统。 2.确定解决方案 设计建立带权的哈夫曼树，确定哈夫曼树的类与成员函数，以及各函数之间的调用关系，采用动态数组的存储结构存储所需要的数据，通过不同的函数来实现编码，译码以及打印二进制编码、哈夫曼树，把不同的数据存入不同的txt文件中，通过主函数调用来实现功能检测。 3.输入的形式和输入值的范围 手动或者从文本中读入数据的形式初始化哈夫曼树，从键盘中或者文件中读入数据，以字母A-Z代表结点，以自然数代表权值，字符串提示使用者所要执行的操作。 4.输出的形式 在显示器界面上或者以文本的形式来实现程序调试的输出。 5.程序所能达到的功能 (1)初始化。手动输入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件WritehfmTree中,输出哈夫曼树及各字符对应的编码存于WritehfmCode;从文本中读入字符，建立哈夫曼树存于ReadhfmTree, 输出哈夫曼树及各字符对应的编码存于ReadhfmCode. (2)编码。手动输入一串大写英文字符，该字符存于WriteToBeTron中，对字符进行编码并将它存于WriteCodeFile中；从文件中读取字符编码并存于ReadCodeFile中。 (3)印代码文件。将文件ReadCodeFile以紧凑格式显示在终端上，每行50个代码。同时将 ———用哈弗曼算法实现图像压缩 姓名：黄函 学号：2011221104210146 班级：11计科3班 算法设计课程论文 1.数字图像的冗余表现为以下几种形式：空间冗余、时间冗余、视觉冗余、信息熵冗余、结构冗余和知识冗余。 (1)空间冗余：图像内部相邻像素之间存在较强的相关性所造成的冗余。 (2)时间冗余：视频图像序列中的不同帧之间的相关性所造成的冗余。 (3)视觉冗余：是指人眼不能感知或不敏感的那部分图像信息。 (4)信息熵冗余：也称编码冗余，如果图像中平均每个像素使用的比特数大于该图像的信息熵，则图像中存在冗余，这种冗余称为信息熵冗余。 (5)结构冗余：是指图像中存在很强的纹理结构或自相似性。 (6)知识冗余：是指有些图像还包含与某些先验知识有关的信息。 2.无损压缩很常见的例子是磁盘文件的压缩。有损压缩的实例是图像和声音的压缩。 3.图像压缩的目的就是在给定位速或者压缩比下实现最好的图像质量。但是，还有一些其它的图像压缩机制的重要特性： 可扩展编码：又称渐进编码、嵌入式位流，通常表示操作位流和文件产生的质量下降（没有解压缩和再压缩）。尽管具有不同的特性，在无损编码中也有可扩展编码，它通常是使用粗糙到精细像素扫描的格式。尤其是在下载时预览图像（如浏览器中）或者提供不同的图像质量访问时（如在数据库中）可扩展编码非常有用，有几种不同类型的可扩展性： 质量渐进：又称层渐进，位流渐进更新重建的图像。 分辨率渐进：首先在低分辨率编码图像，然后编码与高分辨率之间的差别。 成分渐进：首先编码灰度数据，然后编码彩色数据。 感兴趣区域编码：图像某些部分的编码质量要高于其它部分，这种方法可以与可扩展编码组合在一起（首先编码这些部分，然后编码其它部分）。 元数据信息：压缩数据可以包含关于图像的信息用来分类、查询或者浏览图像。这些信息可以包括颜色、纹理统计信息、小预览图像以及作者和版权信息。 压缩方法的质量经常使用峰值信噪比来衡量，峰值信噪比用来表示图象有损压缩带来的噪声。但是，观察者的主观判断也认为是一个重要的、或许是最重要的衡量标准。 4.以哈弗曼算法为实例了解图像压缩算法 Huffman码是一种变长码，其基本思想是：先统计图像（已经数字化）中各灰度出现的概率，出现概率较大的赋以较短的码字，而出现概率较小的则赋以较长的码字。我们可以用下面的框图来表示Huffman编码的过程： 在整个编码过程中，统计图像各灰度级出现的概率和编码这两步都很简单，关键的是Huffman树的构造。不但编码的时候需要用到这颗树，解码的时候也必须有这颗树才能完成解码工作，因此，Huffman树还得完整的传输到解码端。 Huffman树的构造可以按照下面图2的流程图来完成。首先对统计出来的概率从小到大进行排序，然后将最小的两个概率相加；到这儿的时候，先把已经加过的两个概率作为树的两个节点，并把他们从概率队列中删除；然后把相加所得的新概率加入到队列中，对这个新队列进行排序。如此反复，直到最后两个概率相加为1的时候停止。这样，Huffman树就建立起来了。 5.哈夫曼图像压缩算法性能评价 我们主要从三方面[ 2 ]来评价Huffman的性能： （1）压缩比的大小； （2）恢复效果的好坏，也就是能否尽可能的恢复原始数据； （3）算法的简单易用性以及编、解码的速度。 哈夫曼树实验报告 需求分析： 从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。 二、概要设计 程序分为以下几个模块： 1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。 2、对hfmTree进行编码，建立hfm编码表。 3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile 中去 4、对Codefile文件反向译码，结果储存在Textfile中去。 5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。 抽象的数据定义如下： 哈夫曼树结构 typedef struct //定义哈夫曼树的结构 { int weight; //权值 int parent; //双亲 int lchild; //左孩子 int rchild; //右孩子 }htnode,huffmantree[M+1]; 建立哈夫曼树 void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树 { int i,s1,s2,m; for(i=1;i<=n;i++) { ht[i].weight=w[i]; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].weight=0; ht[i].parent=0; ht[i].lchild=0; ht[i].rchild=0; } for(i=n+1;i<=m;i++) { select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i;哈夫曼树 实验报告
利用哈夫曼编码实现压缩和解压缩
哈夫曼树的实验报告1
霍夫曼树实验报告
哈夫曼编译码器课程设计报告完整版
实验三哈夫曼树实验报告
英文文件的压缩和解压缩
数据结构课程设计哈夫曼编码
哈夫曼树与文件解压压缩C言代码
哈夫曼编译码器课程设计报告(完整版)
2021年哈夫曼树实验报告 (1)之令狐采学创编
huffman编码译码实现文件的压缩与解压.
哈夫曼树实验报告
哈夫曼树课程设计论文
Huffman编码对英文文本的压缩和解压缩
哈夫曼树及其操作-数据结构实验报告(2)
哈夫曼树课程设计报告(DOC)
用哈夫曼树实现图像压缩
哈夫曼树实验报告(付原C语言程序)
相关主题
文本预览