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

合肥学院 计算机科学与技术系课程设计报告20102011学年第二学期课程C+课程设计课程设计名称基于哈夫曼编码的数据压缩/解压程序学生姓名龚天棚学号1012091010专业班级网络工程（1）班指导教师项响琴、徐静 2011年6月目 录一、需求分析- 3 -1.1课程设计目的- 3 -1.2课程设计名称及内容- 4 -1.3任务和要求- 4 -二、算法设计- 5 -2.1设计思想：- 5 -2.2 算法思想：- 5 -2.3 主要模块说明- 6 -2.4 部分重要函数的实现：- 6 -三、用户手册- 7 -四、测试结果- 9 -4.1 压缩过程：- 9 -4.2 解压过程- 10 -4.3 显示文本内容- 10 -4.4 显示帮助界面：- 11 -五、总结- 11 -六、参考资料- 12 -七、附录- 13 -7.1源代码- 13 -7.2 运行结果- 14 -一、需求分析1.1课程设计目的将理论教学中涉及到的知识点贯穿起来，对不同的数据类型、程序控制结构、数据结构作一比较和总结，结合设计题目进行综合性应用，对所学知识达到融会贯通的程度。通过课程设计，学生在下述各方面的能力应该得到锻炼：（1）进一步巩固、加深学生所学专业课程C+程序设计语言的基本理论知识，理论联系实际，进一步培养学生综合分析问题，解决问题的能力。 （2）全面考核学生所掌握的基本理论知识及其实际业务能力，从而达到提高学生素质的最终目的。 （3）利用所学知识，开发小型应用系统，掌握运用C+语言编写调试应用系统程序，训练独立开发应用系统，进行数据处理的综合能力。（4）对于给定的设计题目，如何进行分析，理清思路，并给出相应的数学模型。 （5）掌握结构化程序设计方法，熟悉面向对象程序设计方法。（6）熟练掌握C+语言的基本语法，灵活运用各种数据类型。（7） 进一步掌握在集成环境下如何调试程序和修改程序。1.2课程设计名称及内容课程设计名称：基于哈夫曼编码的数据压缩/解压程序设计内容：将任意一个指定的文本文件中的字符进行哈夫曼编码,生成一个编码文件(压缩文件);反过来,可将一个压缩文件解码还原为一个文本文件。1.3任务和要求1)可设计一个菜单:Q-QuitL-List Text DocumentD-DecodingC-Coding2)选择C时:输入一个待压缩的文本文件名称(可带路径)。如:D:lulu.txt统计文本文件中各字符的个数作为权值,生成哈夫曼树；将文本文件利用哈夫曼树进行编码,生成压缩文件。压缩文件名称=文本文件名.COD 如:D:lulu.COD压缩文件内容=哈夫曼树的核心内容+编码序列3) 选择D时:输入一个待解压的压缩文件名称(可带路径 )如:D:lulu.COD从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码；生成(还原)文本文件。文件文件名称=压缩文件名+_new.txt如:D:lulu_new.txt4)选择L时：输入一个待压缩的文本文件名称(可带路径)。如:D:lulu_new.txt显示出该文本文件的内容5)功能扩展(自己定制)：编码使用二进制位,利用位运算进行真正的数据压缩。可对任何文件进行压缩。显示出各种重要信息,如压缩率,各字符的哈夫曼编码表。 二、算法设计2.1设计思想：建立哈夫曼树根据哈夫曼树解码对二进制文件进行解码统计字符，得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成对应文件生成二进制文件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 主要模块说明 下面是该系统的模块首先定义一个结构体： struct headunsigned char b; /记录字符long count; /权重int parent,lch,rch; /定义双亲，左孩子，右孩子char bits256; /存放哈夫曼编码的数组header512,tmp; /头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511 然后是实现各个功能的函数：void show()显示文本文件的内容 unsigned char ctoa(char a) 将数组的前八位转成二进制形式bit位char *code(unsigned char temp,int leafnum) 寻找对应字符的编码串，并返回 void compress(char *infilename,char *outfilename) 对文本编码函数 void uncompress(char *infiname,char *outfilename) 对压缩文件解码void ctoa(unsigned char a,char code) 字符转为二进制形式存入8位数组 int strcmp1(char buf,struct head head,int n,unsigned char &c) 将buf字符串与headeri.bits中匹配，成功后对应的字符由c带回 void strcpy1(char buf,char a,int) 将字符串a中长度为j的部分复制到buf数组中 最后是主函数：在主函数中含有菜单函数void MainMenu()和帮助函数void help()，最后通过switch语句，调用各种函数，分别完成各自的功能。2.4 部分重要函数的实现：void compress(char *infilename,char *outfilename)的实现：1）记录文件中字符频度； 2）根据频度建树； 3）根据哈夫曼树编码； 4）对文件进行编码，写入新文件(核心)； 5）将字符编码对照表写入文件； 6) 将文件的哈夫曼编码输出到显示器上。void compress(char *infilename,char *outfilename)的实现：1）读入必要的数据； 2) 读入编码对照表，放入headeri.bits数组中；3) 对读入的编码对照表进行排序，长度短的排在前面； 4) 将编码读入内容，进行解码工作。三、用户手册运行后的主界面会提示用户进行想要的操作。 1）编码（压缩文件）操作。若用户想要对某一文件进行压缩，则按主界面的提示按“C”，然后界面提示输入进行压缩操作的文件路径和文件名，输入完成后按回车键，此时界面会提示输入压缩后文件的保存路径及其文件名，输入完成后再按回车键，便可完成编码，同时会显示出各字符的哈夫曼编码，系统也会提示用户压缩文件过程结束。 2）译码（还原文件）操作若用户想对某一压缩文件进行解压操作，则按主界面的提示按“D”，然后界面提示输入进行解压操作的文件路径和文件名，完成输入后按回车键，此时界面会提示输入解压后的文件的保存路径及其文件名，输入完成后再按回车键，便可完成译码，系统提示用户还原文件过程结束。3） 显示数据内容 若用户想知道文本输入的内容，可输入“L”， 然后界面提示输入文本文件的路径和文件名，完成输入后按回车键，界面会出现文本的内容。 4）帮助操作 若用户不知道怎么使用该软件，则按主界面的提示按“H”，然后界面会出现教您怎么使用该软件的界面。5）操作失败后的界面提示，若用户输入的文件路径和文件名错误，则界面会提示用户输出文件打开失败。用户根据需求，在操作过程中按“Q”可随时退出系统。四、测试结果4.1 压缩过程： 在D盘中建立一个文本文档，并命名为123.txt。通过程序编译： 在盘中生成一个COD的文档，并且名为123_new.COD: 4.2 解压过程解压过程就是将刚才压缩的文本文件还原。通过程序编译： 在D盘生成一个.txt的文件，并且名为456.txt，同时文本的内容与原来的文本信息相同，实现解压功能。 4.3 显示文本内容将文本的内容输出在显示器上 通过程序编译过后： 4.4 显示帮助界面： 五、总结在当今信息时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。在课程设计过程中，我选择了基于哈夫曼编码的数据压缩与解压程序这一课题，虽然这个课题所涉及的知识我们还没有学习到，属于数据结构与算法的内容，但通过借助书本，自己动手实践，还是掌握了一点关于数据结构的知识，通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，利用哈夫曼编码的思想方法，熟练掌握哈夫曼编码的过程。创建二叉树的方法和二叉树的存储结构，知道压缩文件是如何进行的，解压缩即为它的逆过程。程序的模块化结构尤其重要，应掌握各个模块间的逻辑关系和整体程序的结构。其实在这次课程设计中遇到很多问题，第一就是知识没有学到，必须从最基本的书本知识看起，谢谢指导老师借给我的那本数据结构与算法的课本，对我帮助很大，使我对程序的一些算法有了最基本的了解。其次通过网络资源使我了解的知识更加丰富，增强了我对网络资源的检索能力，使我能够更好的应用网络资源来完成自己需要完成的任务。所以课程设计不仅能培养我们的专业知识，而且还能培养我们的动手能力，使我们以后能够更加适应社会的发展。通过这次课程设计，使我的自学能力有所提高，让我知道了怎么去接受一个新的知识并且能够很好的掌握它。同时也增强我的独立思考能力和动手能力；通过编写程序代码和调试运行，我们可以逐步积累调试程序的经验，逐渐培养我们的编程能力和利用计算机解决实际问题的能力。课程设计为我们提供了一个自己动手实践的平台。另一方面，在课程设计的过程中，使我明白了面向对象与面向对象的差别。在面向对象过程中，类的设计是至关重要的，类设计好了等于程序就成功了一半，所以这次的课程设计帮助我复习了这一学期面向对象课程的学习，刚好可以弥补这一学期面向对象学习的不足。同时，也使我对数据结构与算法的知识有了一定的了解，帮我在大二学习数据结构与算法的课程中奠定了一定的基础，使我以后学习数据结构与算法的时候可以更加轻松。 这次课程设计不但使我掌握了一些知识，更重要的是使我认识到了作为程序员的艰辛和辛苦。一个星期面对着电脑，在你面前只有一行行的代码，在你的耳旁只有键盘的敲击声和点击鼠标的声音，说实话确实很无聊也很辛苦。但当自己看到自己编写的程序顺利通过的时候，心里的成就感就油然而生，心中的疲倦也消失了，我想，当程序员看到自己的程序能够编译成功的话，也是这种感觉吧！虽然这次课程设计结束了，但我们学习C+等语言的步伐不能停止，在今后的学习过程中，我会更加努力，争取在今后的课程中学得更好，下次的课程设计能够更加成功。六、参考资料1郑莉 等编著C+语言程序设计（第三版）北京：清华大学出版社2郑莉 等编著C+语言程序设计（第三版）学生用书北京： 清华大学出版社3李春葆 等编著C+程序设计学习与上机实验指导 北京：清华大学出版社4范辉 等编著Visual C+6.0程序设计简明教程 高等教育出版社5李龙澍C+程序设计实训教程北京：清华大学出版社 6洪国胜 等编著 C+ Builder程序设计轻松上手北京：清华大学出版社7严蔚敏等 数据结构（c语言版） 北京：清华大学出版社，1997年4月第1版8胡学钢等数据结构算法设计指导北京：清华大学出版社，1999年 第1版9 . 郑莉 等编著C+语言程序设计（第4版）学生用书北京： 清华大学出版社10.苏小红 等编著C语言大学实用教程 北京： 电子工业出版社11.王昆仑 等编著 数据结构域算法（高等学校计算机精品课程系列教材） 中国铁道工业出版社 七、附录7.1源代码#include #include #include #include #include using namespace std;struct headunsigned char b; /记录字符long count; /权重int parent,lch,rch; /定义双亲，左孩子，右孩子char bits256; /存放哈夫曼编码的数组header512,tmp; /头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511unsigned char ctoa(char a) /*将数组的前八位转成二进制形式比特位*/unsigned char c=0;for(int i=0;i8;i+) if(ai!=0) c=c+(int)(ai-0)*pow(2,8-1-i); return c;char *code(unsigned char temp,int leafnum) /寻找对应字符的编码串，并返回for(int i=0;ileafnum;i+) if(temp=headeri.b) return headeri.bits;return NULL;void compress(char *infilename,char *outfilename)long flength=0; /记录压缩前文件长度long clength=8; /编码从偏移量8记录，统计压缩后编码长度加8int leafnum; /定义叶子结点int pointnum; /定义总结点unsigned char temp; /定义unsigned char类型，暂存文件中字符的中间变量/*文件中字符频度*/for(int i=0;i256;i+) headeri.count=0; /初始化权重 headeri.b=(unsigned char)i; /初始化字符ifstream infile(infilename,ios:in|ios:binary);while(infile.peek()!=EOF) infile.read(char *)&temp,sizeof(unsigned char); /读入一个字符 headertemp.count+; /统计对应结点字符权重 flength+; /统计文件长度infile.close(); /关闭文件for(i=0;i256-1;i+) /对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j256-1-i;j+) if(headerj.countheaderj+1.count) tmp=headerj; headerj=headerj+1; headerj+1=tmp; for(i=0;i256;i+) if(headeri.count=0) break;leafnum=i; /取得哈夫曼树中叶子结点数pointnum=2*leafnum-1; /取得哈夫曼树中总结点数目/*根据频度建树*/long min; /尽量用long，如果文件过大，这里建树可能不是最优树了int s1,s2;for(i=leafnum;ipointnum;i+) min=999999999; for(int j=0;ji;j+) /挑权重最小的一个 if(headerj.parent=0&headerj.countmin) min=headerj.count; s1=j; headers1.parent=i; /填写第一个叶子结点信息 min=999999999; for(j=0;ji;j+) /挑权重最小的第二个 if(headerj.parent=0&headerj.countmin) min=headerj.count; s2=j; headers2.parent=i; headeri.count=headers1.count+headers2.count; /填写父结点信息 headeri.lch=s1; headeri.rch=s2;/*根据哈夫曼树编码*/char tmp256; /定义临时变量，暂存编码tmp255=0; /添加结束标志int start;int c; /记录当前叶结点下标int f; /存储父结点的下标for(i=0;i=8) /当buf中字符长度大于8时，一直处理写入，直至小于8 temp=ctoa(buf); /上面临时变量已经完成使命，可以赋新值了 outfile.write(char *)&temp,sizeof(unsigned char); /转成二进制写入 clength+; /统计代码结尾偏移加1,用于找到叶子结点位置 strcpy(buf,buf+8); /字符串前移八位 /当此循环结束时，表示buf中已经小于8了，没到文件末尾，读下一个，继续，否则退出 /while 此层循环退出时，表示已到末尾,再判断buf中是否写完，没写完，连满至少8个字符，再写一个字节，就够了if(strlen(buf)0) strcat(buf,0000000); temp=ctoa(buf); /前八位转成二进制形式 outfile.write(char *)&temp,sizeof(unsigned char); clength+; /统计代码结尾偏移加1,用于找到叶子结点位置outfile.seekp(4);outfile.write(char *)&clength,sizeof(long); /写入文件中将记录叶子结点位置infile.close(); /*将字符编码对照表写入文件*/long bytelen; /记录编码以二进制存储时需要占多少个字节outfile.clear();outfile.seekp(clength); /将文件指针移到编码后面的第一位置，在此处记录叶子结点数outfile.write(char *)&leafnum,sizeof(long); /写入叶子结点数for(i=0;ileafnum;i+) outfile.write(char *)&headeri.b,sizeof(unsigned char); /写入字符 headeri.count=strlen(headeri.bits); /不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度 outfile.write(char *)&headeri.count,sizeof(unsigned char); /写入长度的ASCII码 if(headeri.count%8=0) bytelen=headeri.count/8; else bytelen=headeri.count/8+1; strcat(headeri.bits,0000000); /在编码后面补0，使其最后凑满8的倍数， /超过无妨，可以用bytelen控制好写入字节的长度 for(int j=0;jbytelen;j+) temp=ctoa(headeri.bits); outfile.write(char *)&temp,sizeof(unsigned char); strcpy(headeri.bits,headeri.bits+8); cout该文件的哈夫曼的编码为:endl; for(i=0;iflength;i+) coutheaderi.bitsendl; /此循环结束后就完成了编码对照表的写入/compressvoid ctoa(unsigned char a,char code) /*字符转为二进制形式存入8位数组*/ int n=9;for(int i=0;i0) coden-=c%2+0; c=c/2;int strcmp1(char buf,struct head head,int n,unsigned char &c) /将buf字符串与headeri.bits中匹配，成功后对应的字符由c带回for(int i=0;in;i+)if(strcmp(buf,headi.bits)=0) c=headi.b; return 1;return 0;void strcpy1(char buf,char a,int j) /将字符串a中长度为j的部分复制到buf数组中for(int i=0;ij;i+)bufi=ai;bufi=0;void uncompress(char *infilename,char *outfilename)long flength; /定义原文件长度，从压缩后文件前四字节获取值long clength; /获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值int n; /叶子结点数，从编码尾端开始获取string str; /读取编码到字符串,好进行统一解码char code9; /将字符转为二进制数组形式暂存unsigned char temp; /读取字符存放此临时变量long readlen=0; /记录已经读取的长度(读文件解码时用)long writelen=0; /记录已经写入的字节long clen; /临时变量，读取字符编码对照表时使用/*读入必要的数据*/void ctoa(unsigned char a,char code); /需要调用的函数的声明ifstream infile(infilename,ios:binary);if(!infile) cerr文件打开失败endl; return;infile.read(char *)&flength,sizeof(long); /读入原始文件长度，用于解码时判断infile.read(char *)&clength,sizeof(long); /读入叶子结点起始位置infile.seekg(clength);infile.read(char *)&n,sizeof(int); /读入叶子结点数/*读入编码对照表，放入headeri.bits数组中*/infile.seekg(clength+4); /文件指针定位到字符编码对照表的起始for(int i=0;in;i+) /逐个读入叶子结点数，将编码进行读入 infile.read(char *)&headeri.b,sizeof(unsigned char); /读入字符 infile.read(char *)&headeri.count,sizeof(unsigned char); /读入编码长度 clen=(int)headeri.count; int diff=clen%8; if(0=clen%8) /计算需要读取多少个字节 clen=clen/8; else clen=clen/8+1; headeri.bits0=0; /初始化，方便后面进行连接 for(int j=0;jclen;j+) /连接编码,使之存入headeri.bits中 infile.read(char *)&temp,1); ctoa(temp,code); strcat(headeri.bits,code); /将转换过来的编码进行连接 int bitlen=strlen(headeri.bits); if(0!=diff) headeri.bitsbitlen-8+diff=0;/for(int i=0;in;i+)/*对读入的编码对照表进行排序，长度短的排在前面*/for(i=0;in;i+) for(int j=0;jheaderj+1.count) tmp=headerj; headerj=headerj+1; headerj+1=tmp; /*将编码读入内容，进行解码工作*/readlen=0;writelen=0;ofstream outfile(outfilename,ios:binary|ios:out); /打开编码后文件if(!outfile) cerr输出文件打开失败endl; return;char buf513=0; /读入编码缓冲区char buf1257=0;infile.seekg(8); /* 读取编码，解压连入缓冲区 */while(1) while(readlen(clength-8)&strlen(buf)=256) /处理缓冲区，直到少于256位，再读满它 for(i=0;i=flength) break; /如果写入达到原文件长度，退出 /while if(readlen=(clength-8)/*编码长度*/|writelen=flength) break; /如果写入或者读入编码完毕，退出/退出此循环后，还有未解码完成的buf/对buf缓冲的善后处理while(writelenflength) for(i=0;istrlen(buf);i+) strcpy1(buf1,buf,i+1); if(strcmp1(buf1,header,n,temp)=1) outfile.write(char *)&temp,sizeof(unsigned char); writelen+; strcpy(buf,buf+i+1); break; /forinfile.close(); /关闭文件outfile.close();/uncompress()void MainMeun() cout*哈夫曼编码/译码器*endl; coutendl; cout*Q-Quit*endl; cout*H-Help*endl; cout*C-Coding*endl; cout*D-Decoding*endl; cout*L-List Text Document*endl; void show() string contents; char filename200; /coutsfd; cout该文件的内容为：filename; ifstream in(filename,ios:out); while(!in.eof() incontents; coutcontents; void help()coutendl;cout 哈夫曼编码/译码器 endl;coutendl;cout使用说明:endl;coutendl;cout-1、压缩文件:-endl;coutendl;cout 在源文件中输入您所要压缩的文件!输入地格式为：路径压缩前文件名endl;cout 在目标文件中输入您压缩后将文件保存的地址!输入地格式为：路径压缩后文件名endl;cout 例如:源文件:d123.txt表示您要将D盘中123.txt文件进行压缩endl;cout 目标文件:d:123_new.COD表示你将压缩后的文件保存在D盘123_new.COD文件中endl;coutendl;cout-2、解压文件:-endl;cout 在源文件中输入您所要解压的文件！输入地格式为：路径压缩前文件名endl;cout 在目标文件中输入您解压后将文件保存的地址!输入地格式为：路径压缩后文件名endl;cout 例如:源文件:d:123_new.COD表示你要将D盘中123_new.COD文件解压endl;cout 目标文件:d:123.txt表示您要将解压后的文件保存到D盘123.txt文件中endl;cout3) strcpy(select,cmdline1); strcpy(infilename,cmdline2); strcpy(outfilename,cmdline3);else if(num=1) MainMeun(); coutchoice; switch(choice) case C: coutinfilename; coutoutfilename; compress(infilename,outfilename);break; case D: coutinfilename; coutoutfilename; uncompress(infilename,outfilename);break; case H: help();break; case Q:exit(0);break; case L: show();break; return 0; 7.2 运行结果 袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈蚅蚄膈膄蚄螇羁蒂蚃衿膆莈蚂羁罿芄螁蚁膄膀螁螃羇葿螀袅膃蒅蝿肈羆莁螈螇芁芇莄袀肄膃莄羂艿蒂莃蚂肂莈蒂螄芈芄蒁袆肀膀蒀罿袃薈葿螈聿蒄葿袁羁莀蒈羃膇芆蒇蚃羀膂蒆螅膅蒁薅袇羈莇薄罿膄芃薃虿羆艿薃袁节膅薂羄肅蒃薁蚃芀荿薀螆肃芅蕿袈芈膁蚈羀肁蒀蚇蚀袄莆蚇螂肀莂蚆羅袂芈