基于Huffman赫夫曼编码的文本压缩程序.doc

《基于Huffman赫夫曼编码的文本压缩程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构课程设计》课程设计报告基于赫夫曼编码的文本压缩程序班级：09计单学号：姓名：夏军指导教师：鞠训光成绩：2011年6月25日一、目的及意义通过课程设计的综合训练，旨在帮助学生进一步系统的掌握数据结构这门课的主要内容，并进一步培养学生分析问题和解决问题的能力，主要体现在能够让学生针对实际问题有效地组织数据，选择合适的数据结构，并进行正确和高效地算法设计，并用程序实现算法。该课的课程设计是一个良好的程序设计技能训练的过程使学生能够：1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。2.初步掌握软件开发过程的问题分析、系统设计、程序

2、编码、测试等基本技能和方法。3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力。4.训练用系统的观点和软件开发一般规范进行软件开发，培养计算机科学与技术专业学生所具备的科学的工作方法和作风。二、程序功能描述程序实现的功能：对文本文件进行压缩以及对压缩的文本文件进行解压缩。程序的实现的理论依据是赫夫曼编码。赫夫曼编码是一种无损的压缩算法，一般用来压缩文本和程序文件。赫夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的

3、位序列。程序由三个文件组成：头文件CourseDesign.h、函数实现文件CourseDesign.cpp、测试文件Test.cpp。在CourseDesign.h中声明数据的存储结构以及程序所需要的处理函数；CourseDesign.cpp文件实现在CourseDesign.h中声明的函数；Test.cpp负责对所实现的函数进行调用测试，确定是否满足程序设计要求。利用赫夫曼编码实现对文本的压缩的过程大致为：打开要压缩的文本文件，读取文件中的字符，统计文件中不同字符出现的频率，建立赫夫曼树，通过赫夫曼树对出现的互不相同的字符进行编码，建立编码表，接着将

4、将赫夫曼树（即解码表）写入压缩文件中。再次重新读取文件中的字符，对每个字符通过查阅编码表确定对应的编码，将该字符的赫夫曼编码写入压缩文件。对压缩文件的解压过程为：打开压缩文件，读取压缩文件解码表部分，读取压缩文件的编码数据，将压缩数据通过解码表进行解码，将解码出的字符写入解码文件中。程序执行后，用户按照程序的提示选择相应的功能选项。当用户选择压缩功能，此时程序要求用户输入要压缩的文本文件的路径，用户输入完成后。程序检查文件是否能够建立。检查完成后，程序将文件从硬盘读入内存。接着程序将统计不同字符出现的频率以及建立编码表的初步结构。例如当文件中存有如下表所

5、示字符。表1文件字符属性表字符第一字节机内码/ASCII第二字节机内码权重的18119620a9709把17620914表1772375班1762241补1781852百17621417防18319212飞1832019博17816913包1762522才1781976方1831898拜1762213A6503份1832215必1772165英文字符在计算机中是以标准ASCII码进行表示，一个英文字符占一个字节空间，编码范围为0~127；汉字在计算机中是以GB2312编码进行表示。每个汉字占两个字节存储空间，汉字的存储使用机内码，各字节的机内码编码范围为

6、160~254。现在需要考虑使用怎样的数据结构来存放这些字符，如果采用如下简单的数据结构存放：typedefstruct{chardata[3];//存放字符intinternal_code1;//存放第一字节的机内码/ASCII码intinternal_code2;//存放第二字节的机内码，英文默认为0intweight;//存放字符的权重char*code;//字符的赫夫曼编码}CodeList,*CodePList;分析所要处理的字符数据会发现：许多的字符的第一字节的机内码相同，如“防”、“飞”、“方”、“份”，第一字节机内码都是183。这是因为汉

7、字是通过划分区号和位号来表示的，所有汉字被划分成了94个区，94个位，所以当汉字属于同一个区，那么它的第一字节机内码就会相同。如果采用如上的数据结构建立的线性表来存放处理字符，就会存在大量数据冗余。在这种情况下，就有必要为特定的数据设计合适的数据结构。通过分析，采用如下数据结构：typedefstruct{charinternal_code;//存放第二字节机内码char*code;//存放字符的赫夫曼编码}InternalCode;typedefstruct{intcount;//已编码字符数charinternal_code;//存放第一字节机内码I

8、nternalCode*internal_code_address;//第二字节