合肥学院计算机科学与技术系课程设计报告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的文本文档，文档中内容为字符型数据。
所测试的部分数据：图1.原文档二、数据结构的选择和概要设计为了完成实验所要求的任务，解决的问题及方法如下：1.文件的读取及统计字符出现的个数和频率（1）文件的读取void read_file_count(){char c;ifstream infile;infile.open("huffman.txt");//打开huffman.txt文件if(!infile)//检查文件是否打开。
{cout<<"不能打开 huffman.txt文件";//输出文件未打开的标志exit(0);}cout<<"读入的文件中的内容为："<<endl;while((c=infile.get())!=EOF)//EOF是文件结束的标志cout<<endl;}(2)计所出现的字符个数void char_add(char c){huff[count].data=c;huff[count++].count++;//个数增加}(3)计每个字符出现的频率：bool char_judge(char c){for(int i=1;i<=count;i++)if(huff[i].data==c){huff[i].count++;return true;}//如果出现过，出现的频数加1return false;}2.构造huffman树解决了上述问题，接下来要考虑的是怎样去构造huffman树的问题，进行huffman编码，对文件进行压缩。
为了构造huffman树，我将每个字符出现的频率赋予huffman树中叶子结点的权值，从而构造huffman树，也即先查找两个权值最小的结点，合并为新的结点，并将新的结点存入数组中，继续比较合并，最后形成huffman树。
3.huffman编码利用构造好的huffman树，进行编码：设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn}，以d1,d2,……,dn作为叶结点，以w1,w2,……,wn作为各叶子结点的权值构造一棵二叉树，规定HUFFMAN树中的左孩子结点为0，右孩子结点为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。
这样的代码总长度最短的不等长编码就为HUFFMAN编码。
4.文件压缩问题采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样就能对文件进行压缩。
在计算机存储中，是以二进制来存储的，本来每个字符将占据8位，而通过huffman编码后，一个字符在计算机存储中，将占据的位数少于8位，这样将大大减少存储空间，从而实现对文件的压缩。
5.读入压缩文件，并对其解压。
对如何读取压缩文件，采用的方法大致和开始相同，在此不赘述。
为解压，利用构造好的 huffman 树，再根据读取的huffman 编码文件，在huffman 树中查找叶子结点，查找到叶子结点，放入另一个文本文档中，并输出。
其具体查找过程是从根结点开始，根据读入的二进制编码（huffman1.txt 中）及生成的huffman 树，查找叶子结点，当读到的是“0”时，从左孩子结点继续查找，当读到“1”时，则从右孩子结点继续查找，直到找到叶子结点，其判断语句是看一个结点的左右孩子是否为空，如果是则是，叶子结点找到，输入文件（huffman2.txt ）中，如果不是则继续查找，直到所有编码全部读完。
6.计算压缩比例算法如下： void evaluating() { float y1;y1=bitecount/8/remcount*100;cout<<"压缩比例是："<<y1<<"%"<<endl;} 三、详细设计和编码核心算法---huffman 算法： （1）根据给定的n 个权值{w1,w2,……,wn}构成n 棵二叉树的集合F={T1，T2，……,Tn},其中每棵二叉树Ti 中只有一个带权为wi 的根结点，其左右子树均空。
（2）在F 中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
（3）在F 中删除这两棵树，同时将所得到的二叉树加入F 中。
（4）重复（2）和（3），直到F 只含一棵树为止。
这棵树便是huffman 树。
huffman 树可用于构造代码总长度最短的编码方案。
为了详细说明这个问题，特以下面例子来说明:有四个叶子结点A ，B ，C ，D ，分别带权为9，4，5，2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL （树的带权路径长度）不同，要想由n 个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。
权值越大的结点离根越近的二叉树才是最优二叉树（huffman 树）。
按照上面的算法，则可按照下面图的构造过程生成huffman 树。
Huffman 树产生流程：以一例说明ABCDACDBACDBACDB图2.哈夫曼树产生流程 Huffman 编码流程：图3.huffman 编码流程 Huffman 解码流程：fp1>>inchar;if(inchar=='1ptr=huffman[ptr].rchild ptr=huffman[ptr].lchildif(huffman[ptr].lchild==0&&huffman[ptr].lchildfp2int rem,p;int count1=0; for(int y=1;y<=count;y++)rem=y;hcode[y].c=huff[y].data; p=huffman[y].parent;while(p!=0if(huffman[p].lchild==rem)hcode[y].bits[++count1]='0';hcode[y].bits[++count1]='1';图4.huffman解码流程四、上机调试开始考虑问题是，要对文件进行压缩，如何才能达到比较好的效果，那就是huffman 编码是采用等长编码还是采用不等长问题，采用不等长编码要避免译码的二义性或多义性。
假设用0表示字符D，用01表示字符C则当接受到编码串“…01…”，并译到字符0时，是立即译出对应的字符D，还是接着与下一个字符1一起译为对应的字符C，这就产生了二义性。
因此，若对某一个字符集进行不等长编码，则要求字符集合中任一个字符的编码都不能是其他字符编码的前缀。
符合此要求的编码叫做前缀编码。
显然等长编码是前缀编码，这从等长编码所对应的编码二叉树也可以直接看出，任何一个叶子结点都不可能是其它叶子结点的双亲，也就是说，只有当一个结点是另一个结点的双亲时，该结点的字符编码才会是另一个结点的字符编码的前缀。
为了使不等长编码为前缀编码，可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得文件的最短长度，特将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于文件的最短长度。
因此，对文件进行压缩，就可以转化字符集中的所有字符作为叶子结点，字符出现的频率作为权值所产生的huffman树的问题。
基本思路大致有了后，接下来是对程序的编写工作，程序初步形成后，对其测试，发现了一些变量还没有声明的错误，对遗漏的变量进行了声明后，再次调试，发现一个比较大的问题，就是字符都能读入，但是不能进行编码，也即不能构造huffman树，最后经过检查发现原来是结点方面存在问题，最后加入sum=2*count-1;语句，问题得到解决。
（该语句的作用是：例如提供了3个权值不同的结点，现在要构造huffman树，那就需要5个结点。
）五、测试结果图5（与图6同为测试结果）图6（与图5同为测试结果）被编码（部分字符）：图7.被编码后的文档被解码（部分文件）：图8.被解码后的文档六、用户使用说明用户运行本程序前，首先要在起工程文件下建立一个名字为Huffman.txt文本文档，再运行本程序后，第一步，按任意键来读取建立的 Huffman.txt文本文档,再据程序中提示完成第二步操作，也即是讲压缩的文件以Huffman编码放入一个由用户自己建立的文本文档中，接着再根据提示完成第三步操作，即对要压缩的文件解压后放入由用户建立的任意名的文本文档中，由此完成操作。
七、参考文献[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。
[2] 郑莉等.c++语言程序设计(第三版)[M].北京：清华大学出版社，2003年12月八、附录#include<iostream>#include<fstream>#include<string>#include<iomanip>using namespace std;string remfile[600000]; //存放原文件字符的数组int remcount=0; //记录元素个数float bitecount=0; //记录二进制码的个数typedef struct { //存放读入字符的类int count; //字符出现的个数char data; //字符}huffchar;int count=1; //记录huff数组中字符实际出现的个数huffchar huff[1000]; //类的对象//文件读入部分和统计字符出现的频率bool char_judge(char c){ //判断字符出现的函数for(int i=1;i<=count;i++)if(huff[i].data==c){huff[i].count++;return true;} //如果出现过，出现的频数加1return false;}void char_add(char c){ //添加新出现的字符；huff[count].data=c;huff[count++].count++; //个数增加}//文件的读取void read_file_count(){char c;ifstream infile;infile.open("huffman.txt"); //打开huffman.txt文件if(!infile){ //检查文件是否打开。