数据结构课程设计.doc

1、重庆科技学院 数据结构课程设计报告摘要Huffman编码能够广泛用于数据文件的压缩中，能对数据进行无损压缩。Huffman编码是通过统计文件中各ASSIC码频率，并以频率作为相应字符的权重，建立Huffman树。并用01串表示各字符的最优表示方式。通过0，1串替换字符，并压缩为比特流写入文件，从而实现文件的压缩，解压则通过读取文件头和文件尾的内容，并根据已经建立好的Huffman树来实现文件的解压。 该程序是基于以上原理设计，设计了具有压缩、解压和查看内容三个功能的应用程序。压缩是通过建立好的Huffman树来得来相应字符的编码，将编码切割成长度为八的字符串并写入压缩文件中，并在屏幕上显示文件

2、的压缩率。解压则是把文件中的数据看作比特流，把读出的字符串通过堆栈转化为Huffman编码，并根据Huffman树找到叶子节点，得到对应的字符。查看内容不仅可以查到每个字符重复的次数，也可以查询到Huffman树中的各个子树，还可以查看huffman编码。该程序实现文件的压缩和解压缩功能，可以将任意文件压缩成任意的压缩文件类型，并且能将压缩后的文件解压成相应的源文件，同时可以查询到文件的压缩率。关键词: Huffman编码 压缩 压缩率 解压 目录摘要II1目标任务和问题分析11.1目标任务11.2问题分析12算法思想描述22.1总体框架设计22.2 哈夫曼树节点的设计22.3 文件字符频率处

3、理32.4 构建哈夫曼树32.5 获得Huffman编码32.6 将文件进行压缩42.7 将压缩文件解压43程序结构设计63.1 HuffmanTree结构体63.2 使用函数说明63.3 核心函数说明73.3.1 Huffman编码73.3.2压缩函数83.3.3解压函数94. 测试结果114.1压缩函数测试114.2解压函数测试114.3 查看内容测试124.3.1 字符频率测试124.3.2 所有子树测试124.3.3 Huffman编码测试135.总结14致谢15参考文献16161目标任务和问题分析1.1目标任务利用赫夫曼编码的实现原理码对数据进行无损压缩，设计一个实现Huffman压

4、缩的编码和解码的程序。具体要求如下：1）读入待压缩的文本文件；2）统计分析文本文件中各字符的出现频度，以频度作为构造Huffman树的权值。3）根据各字符出现的不同频度构造Huffman树，然后规定每种字符的Huffman编码。4）再次读入待压缩的文本文件，然后根据各字符的Huffman编码逐一替代，将得到的编码流写入到新的文件中，并且计算压缩率。5）解码过程：先读入上一步骤得到的新文件，将其看作比特流，根据Huffman树，对比特流逐位译码，将解码结果又写入一个新的文件中。1.2问题分析首先是对需要压缩的文件中字符的频率进行统计，为了能够正确地处理汉字，应该将文件以二进制的方式进行打开，即对

5、文件采取一个个的字节（unsigned char）处理，根据统计的频率构造Huffman树，然后对每个字符进行Huffman编码，并把源文件的每个字符对应的Huffman编码存入新的文件中，即得到压缩文件。解压过程则利用Huffman树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 2算法思想描述2.1总体框架设计利用Huffman编码对文件进行压缩，首先要知道其字符相应的Huffman编码。通过扫描整个文本，统计文件中各个字符出现的频率。由于一个字符的范围在0-255之间，即共256个状态，所以可以直建立256个Huffman树节点空间，即数组空间来存储整个文件的信息，

6、节点中包括对应字符信息，即频率、左孩子、右孩子、父节点。整个程序中还要用到堆栈和队列，用堆栈来进行Huffman编码以及得到译码得到相应的字符，用队列来切割字符串，使Huffman编码能够切割成长度为八的字符，并写入压缩文件。整体框架图如2-1所示。图2-1 整体框架图图2.2 哈夫曼树节点的设计采用结构体NODE来存储节点的信息，其中有成员频率frequence、父节点parent、左节点lchild、右节点rchild，并在节点生成的时候就初始化，使其全部置为0。2.3 文件字符频率处理由于采用字节存取，而字符的最多个数就只能是256个，即ASCII码在0-255之间，而该程序中用的是数组

7、来存储文件的信息，建立Huffman256的下标来表示对应的字符。因此只需要在每读一个字节（ch）的同时,让对应的Huffmanch中的频率加一就可以达到统计字符频率的效果。2.4 构建哈夫曼树哈夫曼树的存储结构采用双亲孩子表示法，即用结构体数组来实现。由于256个叶子节点会产生255个父亲节点，所以该程序建立的数组为Huffman511来构建哈弗曼树。通过循环提取哈弗曼中权值最小的两个节点（节点无父节点才统计），将它们合并起来，组成一个新的根节点，直到最后哈夫曼树只剩下一个根节点为止。2.5 获得Huffman编码采用字节进行编码，每个字符的Huffman编码是一个0/1串，因此建立stri

8、ng256数组来存放对应下标字符的Huffman编码。给每个节点设置一个编码标志，左孩子状态为0，右孩子状态为1，我们从Huffman树的叶子节点开始循环遍历。如果父节点的左孩子等于该字符，那么把“0”压入堆栈中，如果父节点的右孩子等于该字符，那么把“1”压入堆栈。当遍历到树顶节点，此时无父节点结束，并把堆栈内的字符串一个个弹出放到stringch中，就得到相应的Huffman编码。获得Huffman编码流程图如图2-5所示。图2-5 Huffman编码流程图2.6 将文件进行压缩要将文件进行压缩，必须把每个字节的编码转化拼接成八位的码字存入压缩文件中。故而先取得编码字符串的长度，并将其放入队

9、列中，当队列中码字的长度大于等于八，将前八个码字形成的字符串转化为十进制将得到的二进制数存入压缩文件中。如果队列中的码字个数不足八个，则把下一个字节的编码放入队列中，再循环，直到最后一个字节，如果最后队列中的码字个数不足八个，将其用0补全。就实现了文件的压缩过程。压缩流程图如图2-6所示。 图2-6 压缩流程图2.7 将压缩文件解压与压缩文件相似，以字节的形式依次读取压缩文件的每个字节（ch）。将得到的字节转化成二进制，并根据Huffman树从上至下遍历，如果遍历八个节点也没有到叶子节点，则再从文件中读出一个字节并转化为二进制后，继续遍历，得到叶子节点后，把叶子节点放到新文件中，再从树顶节点遍

10、历，得到下一个叶子节点，再放入文件，一直循环直到最后一个叶子节点。从而实现了文件的解压过程。如图2-7所示。 图2-7 解压流程图3程序结构设计3.1 HuffmanTree结构体结构体中定义了频率、父节点、左节点、右节点，并在节点生成的时候就初始化，使其全部置为0。struct NodeNode(int f=0, int l=0, int r=0, int p=0):frequence(f), lchild(l),rchild(r),parent(r)int frequence; /频率int lchild; /左孩子int rchild; /右孩子int parent; /父节点 ;3.2

11、 使用函数说明该程序中使用的部分函数，通过这些函数来完成Huffman编码所要求的功能，可以压缩文件，解压文件，查看文件压缩率，子树，Huffman编码等。void getfrequence(); / 频率的统计void createHuff(); / 创建huffman树void CharCode(); / 获取huffman编码void coding(); / 压缩int getlen(); / 获取huffman编成长度 void getyasuo(); / 获取文件压缩率int toDecimal(void); / 转化为十进制void yima(); / 解压void toBinar

12、y(int ); / 转化为二进制void choicemenu(); /主菜单void menu2(); / 字菜单void printcode(); / 打印huffman编码void printf(); / 打印字符频率void printf1(); / 打印所有子树3.3 核心函数说明3.3.1 Huffman编码Huffman编码是主要运用堆栈，从文件中获取到的字符由Huffman树从下至上遍历而得到的。如果父节点的左孩子等于该字符，那么把“0”字符压入堆栈中，同理，如果父节点的右孩子等于该字符，那么把“1”字符压入堆栈中。当遍历到树根节点，此时无父节点结束，并把堆栈内的字符一个个弹

13、出放到stringch中，就得到相应的Huffman编码。void CharCode() /获得对应字符编码ofstream outfile;int p,c,t; outfile.open(BinatyCode.txt,ios:out);stack = createStack();coutnn输出字符的编码如下*endl;for(int i = 1;i=n;i+)if(Huffmani.frequence!=0)p=Huffmani.parent;c=i;while(p!=0)if(Huffmanp.lchild=c)t=0;elset=1;pushStack(stack,t);c= p ;p

14、 = Huffmanp.parent;couticount!=0)sti+=popStack(stack);coutstiendl;outfileit;outfilestiendl;coutnn;3.3.2压缩函数该程序中通过队列来辅助完成压缩功能。主要使用队列先进先出的特性，把Huffman编码对应的二进制字符串放到队列，当队列中的字符个数超过八个，将前八个码字一个个地拿出来，并将其转化为ASSIC码，将其存压缩文件。void coding() /压缩函数int i=0,j=1,ch,k=1; char t;t=0;ifstream infile;ofstream outfile;queue

15、=createQueue(); / 创建队列cout请输入压缩码存储文件名,格式为:;cinsource_file2; infile.open(source_file1,ios:binary); / 打开源文件文件outfile.open(source_file2,ios:binary); / 打开压缩文件文件ch = infile.get(); while(ch!=EOF) / 没到文件末尾for (i=0;icount=8)/若队列的大小于等于8j = toDecimal(); / 转化成十进制outfile.put(j); / 放到文件中ch=infile.get(); / 获取下一个字

16、符while (queue-count8) /若队列的大小小于8的话则向队列补全0 enQueue(queue,&t); j=toDecimal();outfile.put(j);outfile.close(); /关闭压缩文件infile.close(); /关闭源文件 destoryStack(stack); coutn文件压缩成功，文件名为:source_file2nendl;getyasuo();coutendl; choicemenu();3.3.3解压函数解压程序和压缩文件是个完全相反的过程。解压程序中用到了堆栈，从文件中读取一个个字节，根据Huffman编码由Huffman树至上

17、而下地遍历，达到叶子节点则把此转化成对应下标的ASSIC字符，将其存入新文件，当压缩文件中的字节遍历完，就得到新文件，新文件与源文件完全一至，实现解压过程。void yima() /解压文件 int i=0,j=1,k=1,ch,root; ifstream infile;ofstream outfile;cout需要解压的文件名,格式为:;cinsource_file2;infile.open(source_file2,ios:binary); / 打开需解压的文件 cout请输入解压后的文件名,格式为:;cinsource_file3;coutendl;outfile.open(sourc

18、e_file3,ios:binary); / 打开解压后的文件 stack= createStack(); / 创建堆栈root = rootmost; / 获得树根节点ch=infile.get(); / 从文件中获取一个字节while (ch!=EOF) /文件不为空if (ch0) / 因为汉字是负，故而要加256ch+=256;toBinary(ch); / 将字节转为十进制字符，并将其压入堆栈中while (!emptyStack(stack) /堆栈不为空if (topStack(stack)=0) /堆栈顶字符是0 ，左孩子下标赋值给树根节点root=Huffmanroot.lc

19、hild;elseif (topStack(stack)=1) /堆栈顶字符是1 ，右孩子下标赋值给树根节点root=Huffmanroot.rchild;popStack(stack); /弹出原来根节点下标if (Huffmanroot.lchild=0 & Huffmanroot.rchild=0) /是叶子节点 outfile.put(root); /将下标对应字符放到解压后文件root=rootmost; /重新赋值根节点 ch=infile.get(); /从压缩文件中获取新的一个字节choicemenu(); / 返回到主菜单 4. 测试结果4.1压缩函数测试开始进入主菜单，选择

20、1开始压缩文件，得到Huffman编码文件是BinatyCode.txt。存储文件由使用者通过键盘输入，在压缩成功后，可以看到源文件和压缩文件的大小，并可以看到文件压缩率。如图4-1所示。图4-1 压缩文件测试图4.2解压函数测试进入主菜单，选择2开始解压文件，先输入需要压缩的文件，再输入解压文件名，解压成功后会提示“解压成功!解压后的文件为：xxx.xxx” 。如图4-2所示。图4-2 解压文件测试图4.3 查看内容测试查看内容可以进入子菜单，子菜单中有4 个选项，分别是获取字符频率，查看所有子树，查看huffman编码，返回主菜单。如图4-3所示。图4-3 查看内容测试图4.3.1 字符频

21、率测试选择1功能，可以查看到字符在文件中出现的频率，第一列则是表示ASSIC码为相应数值的字符，第二列就是其出现的频率。如图4-3-1所示。图4-3-1 字符频率测试图4.3.2 所有子树测试选择2功能，可以查看Huffman树中的所有子树，第一列则是表示ASSIC码为相应数值的字符，第二列就是其所有孩子出现次数之和，第三列表示当前字符在Huffman树中的左孩子，第四列表示当前字符在Huffman树中的右孩子。由于Huffman树在屏幕上显示太长，故而只截取一部分。如图4-3-2所示。图4-3-2 查看子树测试图4.3.3 Huffman编码测试选择3功能，可以查看Huffman编码，第一列

22、则是表示ASSIC码为相应数值的字符，第二列就是其对应的Huffman编码。如图4-3-3所示。图4-3-3 Huffman编码测试图5.总结经过一周多的时间，用Huffman编码实现了文件的压缩和解压，完成了任务书上的要求，下面对该程序作一个小总结： （1）Huffman编码进行解压缩软件设计时候，其核心是Huffman树，它是编码、压缩和解压的纽带。Huffman技术对多种文件压缩率很高，对于二进制也很成功。 （2）该程序中因为涉及文件操作，多次读写文件，为了保证操作后的文件与原文件的一致性，在打开或者建立新文件时都是以二进制进行操作，将解压后的文件和原文件相比较具有一致性，体现的程序的健

23、壮性。 经过多次实践发现该程序对文本压缩效果非常好，但是对于具有图形、表格之类的文件却不能正确地解压，因此以后针对这一问题进行改进，使其能够对任意东西正确地压缩和解压。 致谢在本次课程设计及报告的完成过程中，许多人给了我想当多的帮助。不仅有知道老师，还有其他同学，如洪钟、段志强、周涛等。在此，我给那些帮助我喝鼓励我的老师和同学表示真诚的感谢。 签名：张鹏 日期 2012.1.12 参考文献1 严蔚敏，吴伟民。 数据结构，清华大学出版社，2007.32 李春葆。数据结构教程，清华大学出版社，2005.13（美）Stephen Prata, C Primer Plus中文版（第五版），人民邮电出版社，2005.2