基于哈夫曼编码的数据压缩解压程序论文

合肥学院计算机科学与技术系课程设计报告2010～2011学年第二学期课程C++课程设计课程设计名称基于哈夫曼编码的数据压缩/解压程序学生姓名龚天棚学号1012091010专业班级网络工程（1）班指导教师项响琴、徐静2011年6月-2-目录一、需求分析......................................................................................................-3-1.1课程设计目的..........................................................................................-3-1.2课程设计名称及内容..............................................................................-3-1.3任务和要求.............................................................................................-3-二、算法设计......................................................................................................-4-2.1设计思想：..............................................................................................-4-2.2算法思想：.............................................................................................-5-2.3主要模块说明.........................................................................................-5-2.4部分重要函数的实现：.........................................................................-6-三、用户手册......................................................................................................-6-四、测试结果......................................................................................................-8-4.1压缩过程：...........................................................................................-8-4.2解压过程...............................................................................................-9-4.3显示文本内容.........................................................................................-9-4.4显示帮助界面：...................................................................................-10-五、总结............................................................................................................-10-六、参考资料.....................................................................................................-11-七、附录............................................................................................................-12-7.1源代码....................................................................................................-12-7.2运行结果...............................................................................................-22--3-一、需求分析1.1课程设计目的将理论教学中涉及到的知识点贯穿起来，对不同的数据类型、程序控制结构、数据结构作一比较和总结，结合设计题目进行综合性应用，对所学知识达到融会贯通的程度。通过课程设计，学生在下述各方面的能力应该得到锻炼：（1）进一步巩固、加深学生所学专业课程《C++程序设计语言》的基本理论知识，理论联系实际，进一步培养学生综合分析问题，解决问题的能力。（2）全面考核学生所掌握的基本理论知识及其实际业务能力，从而达到提高学生素质的最终目的。（3）利用所学知识，开发小型应用系统，掌握运用C++语言编写调试应用系统程序，训练独立开发应用系统，进行数据处理的综合能力。（4）对于给定的设计题目，如何进行分析，理清思路，并给出相应的数学模型。（5）掌握结构化程序设计方法，熟悉面向对象程序设计方法。（6）熟练掌握C++语言的基本语法，灵活运用各种数据类型。（7）进一步掌握在集成环境下如何调试程序和修改程序。1.2课程设计名称及内容课程设计名称：基于哈夫曼编码的数据压缩/解压程序设计内容：将任意一个指定的文本文件中的字符进行哈夫曼编码,生成一个编码文件(压缩文件);反过来,可将一个压缩文件解码还原为一个文本文件。1.3任务和要求1)可设计一个菜单:Q----QuitL----ListTextDocumentD----DecodingC----Coding2)选择C时:输入一个待压缩的文本文件名称(可带路径)。如:D:\lu\lu.txt统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD如:D:\lu\lu.COD压缩文件内容=哈夫曼树的核心内容+编码序列3)选择D时:输入一个待解压的压缩文件名称(可带路径)如:D:\lu\lu.COD从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码；生成(还原)文本文件。-4-文件文件名称=压缩文件名+_new.txt如:D:\lu\lu_new.txt4)选择L时：输入一个待压缩的文本文件名称(可带路径)。如:D:\lu\lu_new.txt显示出该文本文件的内容5)功能扩展(自己定制)：编码使用二进制位,利用位运算进行真正的数据压缩。可对任何文件进行压缩。显示出各种重要信息,如压缩率,各字符的哈夫曼编码表。二、算法设计2.1设计思想：统计字符，得出统计出字符的权值n建立哈夫曼树生成二进制文件对二进制文件进行解码根据哈夫曼树编码对编码进行压缩生成对应文件根据哈夫曼树解码生成哈夫曼树-5-2.2算法思想：2.2.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。2.2.5解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件2.3主要模块说明下面是该系统的模块首先定义一个结构体：structhead{unsignedcharb;//记录字符longcount;//权重intparent,lch,rch;//定义双亲，左孩子，右孩子charbits[256];//存放哈夫曼编码的数组}header[512],tmp;//头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511然后是实现各个功能的函数：voidshow()显示文本文件的内容unsignedcharctoa(chara[])将数组的前八位转成二进制形式bit位char*code(unsignedchartemp,intleafnum)寻找对应字符的编码串，并返回voidcompress(char*infilename,char*outfilename)对文本编码函数voiduncompress(char*infiname,char*outfilename)对压缩文件解码voidctoa(unsignedchara,charcode[])字符转为二进制形式存入8位数组intstrcmp1(charbuf[],structheadhead[],intn,unsignedchar&c)-6-将buf字符串与header[i].bits[]中匹配，成功后对应的字符由c带回voidstrcpy1(charbuf[],chara[],int)将字符串a中长度为j的部分复制到buf数组中最后是主函数：在主函数中含有菜单函数voidMainMenu()和帮助函数voidhelp()，最后通过switch语句，调用各种函数，分别完成各自的功能。2.4部分重要函数的实现：voidcompress(char*infilename,char*outfilename)的实现：1）记录文件中字符频度；2）根据频度建树；3）根据哈夫曼树编码；4）对文件进行编码，写入新文件(核心)；5）将字符编码对照表写入文件；6)将文件的哈夫曼编码输出到显示器上。voidcompress(char*infilename,char*outfilename)的实现：1）读入必要的数据；2)读入编码对照表，放入header[i].bits[]数组中；3)对读入的编码对照表进行排序，长度短的排在前面；4)将编码读入内容，进行解码工作。三、用户手册运行后的主界面会提示用户进行想要的操作。1）编码（压缩文件）操作。若用户想要对某一文件进行压缩，则按主界面