哈弗曼编码译码器的实现.doc

“数据结构”课程设计报告（哈夫曼编码/译码器的实现）学生姓名： _ 指导教师： _ 所 在 系： 电 子 信 息 系 _ 所学专业： 计算机科学与技术_ 年 级： 目录1、需求分析11.1课程设计要求11.2选题的意义及背景11.3本组课程设计目标12、概要分析22.1输出哈夫曼树22.2哈夫曼编码22.3哈夫曼译码33、详细设计431哈夫曼建树43.2哈夫曼编码43.3哈夫曼译码43.4主函数54、调试分析54.1输入要压缩的文件54.2读文件并计算字符频率64.3根据字符的频率，利用Huffman编码思想创建Huffman树64.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩64.5解码压缩即根据Huffman树进行译码65、用户手册86、测试结果97、总结108、参考文献119、小组人员分工11 1、需求分析1.1课程设计要求基于哈夫曼编码的思想进行文件的压缩处理(1) 能够将一个文件进行编码压缩(2) 能够将压缩的文件解码还原1.2选题的意义及背景锻炼我们的编码能力，真正理解数据结构的编码思想,并且锻炼我们的动手能力和成员间的配合，提高程序编写能力。在信息传递时，希望长度能尽可能短，即采用最短码。赫夫曼编码的应用，就是采用这种有效的数据压缩技术可以节省数据文件的存储空间和计算机网络的传送时间。1.3本组课程设计目标实现赫夫曼树的建立，赫夫曼编码的对对应的文件进压缩和对压缩文件的进行译码。调试程序，最后完成程序设计，完成设计报告，总结经验。2、概要分析主要模块及调用关系建立哈夫曼树根据哈夫曼树解码对二进制文件进行解码统计字符，得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成二进制文件生成对应文件2.1输出哈夫曼树求字符结点数const unsigned int n=256; /字符数const unsigned int m=256*2-1; /结点总数用类编码哈夫曼树class HuffmanTree /Huffman树 public: void Code(); /编码 void UnCode(); /译码private: HTNode HTm+1; /树结点表(HT1到HTm) char Leafn+1; ; /叶结点对应字符(leaf1到leafn)2.2哈夫曼编码char *HuffmanCoden+1; /叶结点对应编码(*HuffmanCode1到*HuffmanCoden) unsigned int count; /频度大于零的字符数 unsigned int char_indexn; /字符对应在树结点表的下标(char_index0到char_indexn-1) unsigned long size; /被压缩文件长度 FILE *infp,*outfp; /输入/出文件 Buffer buf; /字符缓冲 void Stat(); /统计字符出现频度并过滤掉频度为零的字符 /在HT0HTk中选择parent为-1，树值最小的两个结点s1,s2 void Select(unsigned int k, unsigned int &s1, unsigned int &s2); void Write(unsigned int bit);/向outfp中写入一个比特 void Write(unsigned int num,unsigned int k);/向outfp中写入k个比特 void WriteToOutfp(); /强行写入outfpint NToBits(unsigned int num);/0num之间的整数用二进位表示所需的最少位数2.3哈夫曼译码void Read(unsigned int &bit); /从infp中读出一个比特void Read(unsigned int &num,unsigned int k);/从infp中读出k个比特int NToBits(unsigned int num);/0num之间的整数用二进位表示所需的最少位数void CreateFromCodeFile(); /由编码文件中存储的树结构建立Huffman树 void CreateFromSourceFile();/由被压缩文件建立Huffman树,将树结构存入编码文/件的文件头部中,并求每个字符的Huffman编码 3、详细设计31哈夫曼建树统计字符得出结果字符的权值，然后建立对应的哈夫曼树。CreateFromCodeFile();Read(bit);for(i=0;isize;i+) c=2*count-1;while(HTc.lchild!=0|HTc.rchild!=0)&(feof(infp)=0)if(bit=0)c=HTc.lchild;else c=HTc.rchild;Read(bit); fputc(Leafc,outfp);3.2哈夫曼编码对存放在某硬盘的一文件进行编码fgetc(infp);if(feof(infp) coutEmpty source file:infNameendl;system(PAUSE);exit(1);对输入的文件进行压缩，生成二进制文件int HuffmanTree:NToBits(unsigned int num)unsigned int l=0,power=1;while(power=num)l+;power=power*2; return l;3.3哈夫曼译码由被压缩文件建立哈夫曼树, 利用write函数对已压缩的文件中的代码进行译码,将译码结果保存到文件中，此操作实际上就是对某一文件进行解压处理。void HuffmanTree:Write(unsigned int bit)buf.bits+;buf.ch=(buf.ch1)+bit;if(buf.bits=8)fputc(buf.ch,outfp);buf.bits=0;buf.ch=0; void HuffmanTree:Write(unsigned int num,unsigned int k)Stack s;unsigned int i,bit;for(i=1;i1);for(i=1;i=k;i+)s.top(bit);Write(bit);s.pop(); 3.4主函数利用switch函数实现选择编码和译码，以实现整个程序的功能。while(c!=3) coutendl1.Huffman compress(编码).;coutendl2.Huffman decompress（译码）.;coutendl3.Exit（退出）.;coutendlc;switch(c)case 1: hf.Code();break;case 2:hf.UnCode();break; 4、调试分析4.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的选项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。4.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。4.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。4.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。 4.5解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是1时，指针指向当前所指结点的右孩子，当读取的字符是0时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件结束时为止。5、用户手册运行后的主界面会提示用户进行想要的操作。1）编码（压缩文件）操作。若用户想要对某一文件进行压缩，则按主界面的提示按“1”，然后界面提示输入进行压缩操作的文件路径和文件名（文件大小应小于4GB），输入完成后按回车键，此时界面会提示输入压缩后文件的保存路径及其文件名，输入完成后再按回车键，便可完成编码，系统提示用户压缩文件过程结束。2）译码（还原文件）操作若用户想对某一压缩文件进行解压操作，则按主界面的提示按“2”，然后界面提示输入进行解压操作的文件路径和文件名，完成输入后按回车键，此时界面会提示输入解压后的文件的保存路径及其文件名，输入完成后再按回车键，便可完成译码，系统提示用户还原文件过程结束。3）操作失败后的界面提示，若用户输入的文件路径和文件名错误，则界面会提示用户文件打开失败的信息。用户根据需求，在操作过程中按“3”可随时退出系统。注意：选择的文件大小应该大于几十KB，不超过4GB。文件过小就没有压缩的意义。6、测试结果需进行编码译码的文件类型可任意，测试用例有多种选择，所以选G盘里图片1.bmp（大小为576KB）为本课题测试用例。测试结果为：原文件经编码后，压缩为s.zip（大小为73KB）形式，在译码解压后，将其还原成d.bmp形式，打开后与原文件完成相同。故可利用这种有效的数据压缩技术实现节省数据文件的存储空间和计算机网络的传送时间的功能。7、总结在当今信息时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。在课程设计过程中，我们选择哈夫曼编码/译码的实现这一课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂内容，还可以增强我们的独立思考能力和动手能力；通过编写程序代码和调试运行，我们可以逐步积累调试程序的经验，逐渐培养我们的编程能力和利用计算机解决实际问题的能力。课程设计为我们提供了一个自己动手实践的平台。通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，利用哈夫曼编码的思想方法，熟练掌握哈夫曼编码的过程。创建二叉树的方法和二叉树的存储结构，知道压缩文件是如何进行的，解压缩即为它的逆过程。程序的模块化结构尤其重要，应掌握各个模块间的逻辑关系和整体程序的结构。在此过程中，我们不但独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，小组成员在对问题的认识方面可以交换不同的意见，老师 的悉心指导给了我们极大的鼓励和帮助！8、参考文献1 苏仕华编著.数据结构与算法分析.合肥：中国科技大学出版社，20042 苏仕华等著.数据结构课程设计.北京：机械工业出版社，20053 严蔚敏.吴伟民编著,数据结构C语言版.北京：清华大学出版社,20074 刘正安编著.C+及Windows可视化程序设计.北京：清华大学出版社，20035 严蔚敏，陈文博