数据结构应用设计设计报告.DOC

1、数据结构应用设计设计报告题目名称：_基于哈夫曼编码的文件压缩器_设计环境：_ _6.0 _指导教师：_ _蔡茂蓉_专业班级：_软件工程 0601 班_ _姓 名：_ _ _杨文辉_学 号：_ _20061540_ _联系电话：_ 13696574103 _电子邮件：_ 设计日期： 年 月 日至 年 月 日设计报告日期： 年 月 日指导教师评语：设计成绩：_ 指导教师签名：_11 题目 .22 需求分析 .22.1 文件压缩过程： .22.2 文件解压过程： .32.3 压缩文件的存储结构设计图： .32.4文件示例： .43 详细设计 .53.1 压缩流程图： .53.2 解压流程图： .53

2、.3 节点类设计： .53.4 编 码和译码时的控制结构的实现 .7调试分析 .116 测试结果 .126.1 文件压缩 .126.2 文件解压 .13实验 总结 .148 参考文 献 .1421 题目 基于哈夫曼编码的文件压缩器2 需求分析 哈夫曼编码在文件压缩中有其独特一点，它的编码方式特殊。在通信领域可以得到应用。本程序使用 C+编写，在 VC6.0 上调试，完成了文件的读取，文件字符的统计，哈夫曼树的建立，哈夫曼编码的实现，文件转换为哈夫曼编码成为压缩文件以及文件从压缩状态进行解码。2.1 文件压缩过程：1、 找出一个待压缩文件，进行读取，并且统计其每种字节出现的频率。2、 根据已经统

3、计的频率，进行哈夫曼树的构建。3、 对已经构建的哈夫曼树进行哈夫曼编码，将这个文件读入到一个新的文件中4、 再次读取文件并且对每一个字符编码，并继续读入到这个新的文件中，这个新的文件就是压缩后的文件5、 压缩时函数调用关系为，使用类 CHaffmanCode，所有的程度操作函数集中在该类中。float CHaffmanCode:OpenandCloseFile(char *OpenFile,char *CloseFile)/这个函数压缩函数，把所有要用的操作函数都集中在该函数中。CreateHaffmanTree(hArray); /使用得到的权值构建哈夫曼树，这里用矩阵实现EnHaffman

4、Code(hArray,codes);/对已经构建好的哈夫曼树的每个叶结点进行编码fCompre = ChangtoCode(OpenFile,CloseFile);/把所有的内容都按照编码存入一个新文件，返回文件压缩率3return fCompre；/这是返回文件压缩率2.2 文件解压过程：1、 从压缩文件读出前部分，就是压缩到文件中的各个节点的权值。2、 使用这些权值再次构建一个哈夫曼树 。3、 再读入文件其他的压缩信息，并且使用递推的方式，找到文件中应该有的字符4、 把这些字读入一个新文件，完成解压5、 解压时函数调用关系，使用类 CHaffmanCode，所有的程度操作函数集中在该类中

5、void CHaffmanCode:TranslateCodes(char* OpenFile,char *CloseFile) /这是个解压函数，把相关的操着都封装在其中CreateHaffmanTree(hArray); /再次使用这些权值建立一个哈夫曼树/再读出压缩文件中存储的原文件的后缀名，且保存在 CloseFile 的尾部/使用递推的办法在建立的哈弗曼树中找出各个压缩后字符的原子符/将其保存在 CloseFile 中2.3 压缩文件的存储结构设计图：文件的组成结构一、原始文件中各个字符的权值（共有个节点）二、原始文件的后缀名三、原始文件中各个字符被编码后的存入的信息4四、在压缩文件

6、时，由于编码长度不等，最后一个字符添加的的个数2.4文件示例：这是文件压缩时候产生的头部信息，存储的是每个节点的权值的信息，主要为 256 个节点的权值信息，每个节点的权值是由 1 个整数表示（即 8*4 个二进制位）。在存入节点信息的末尾，存入了 4 个字符型（即 8*4 个二进制位），用以存入文件的后缀名。综上，如果压缩的是空文件（即没有任何字符），那么在压缩文件头部（即 haf 文件组成前两部分）应该存储的是一个（4 * 256 + 4 * 1 = 1028（字节）。5这是文件压缩的信息部分，是对待压缩文件每个节点的编码，然后存储的信息。设计时每种叶子节点的编码为 24 个整型数据的组成

7、的数组。用这 24 个整数表示 24 个二进制位。但是由于编码的长度不等，所以字符存入的 长度不等，因此，设计一个数组（暂定 1024位），当数组被每个节点的编码（即 24 位整数中有效的整数位）填满了以后，对这个数组以 8 位为单位进行转换。最后一次会由的编码可能不足 1024 位，这时又对其单独处理。如果最后剩下的位数不是 8 位，那么就以加 0 的方式补充为 8 位，并在文件的末尾加上补 0的个数。如果未补零，自然这个补 0 的个数为 0。3 详细设计 3.1 压缩流程图：3.2 解压流程图：3.3 节点类设计：struct HaffNode统计每种节点的权值（权值）对每种叶子节点编码构

8、建哈夫曼树 对文件中每个字符编码目标文件haf 文件读取每个叶子节点权值构建哈夫曼树待解压文件编码解压后的文件6unsigned int iWeight;int iLeftChild; int iRightChild;int iParent;int iFlag;HaffNode()iWeight = 0;iLeftChild = -1; iRightChild = -1; iParent = -1; iFlag = 0; ;struct HaffNode 设计的作用是使用该节点类构建个叶子节点，个非叶子节点。最终构建成为一个哈夫曼树。struct Code /用于存每个叶子节点的编码int i

9、Start;/编码在数组中的开始端int Bit24;/每个都设置为 24 位的整数struct Code 类的设计旨在构建存储哈夫曼编码后的编码class CHaffmanCodeprivate:HaffNode *hArray ; Code *codes;7char TempiMax;int iNumofBits;public:void CreateHaffmanTree(HaffNode *p);/建立哈夫曼树 void EnHaffmanCode(HaffNode *p,Code *cd);/对哈夫曼树的每个节点编码float OpenandCloseFile(char *OpenFi

10、le,char *CloseFile);/打开文件，调用函数进行编码压float ChangtoCode(char *OpenFile,char *CloseFile);/使用已有的编码，压缩文件,返回压缩率void TranslateCodes(char *OpenFile, char *CloseFile);/译码，解压缩CHaffmanCode();virtual CHaffmanCode();3.4 编码和译码时的控制结构的实现class CHaffmanCode 是整个编码和译码的控制类，将函数封装在其中。CHaffmanCode:CHaffmanCode()hArray = new

11、 HaffNodeiNumofCode;/一共申请了 511 个节点，其中 256 个叶子节点codes= new Code256;/对每个叶子节点相应的编码8/float CHaffmanCode:OpenandCloseFile(char *OpenFile,char *CloseFile)/打开一个待压缩文件，提供压缩后存储的地址ifstream infile(OpenFile, ios:in | ios:binary);do /统计每个节点在 ASCII 中的出现频率 while(iNumofBits = iMax); /每次读入 1024 个字节CreateHaffmanTree(h

12、Array); /使用得到的权值构建哈夫曼树，这里用矩阵实现EnHaffmanCode(hArray,codes);/对已经构建好的哈夫曼树的每个叶结点进行编码reutrn ChangtoCode(OpenFile,CloseFile);/把所有的内容都按照编码存入一个新文件/void CHaffmanCode:CreateHaffmanTree(HaffNode *p)/构建哈夫曼树/void CHaffmanCode:EnHaffmanCode(HaffNode *p,Code *cd)9/使用已经构建的哈夫曼树对每个叶子节点进行编码/float CHaffmanCode:ChangtoC

13、ode(char *OpenFile,char *CloseFile)ifstream ifile(OpenFile,ios:in | ios:binary); /再次读入待压缩的文件ofstream outfile(CloseFile, ios:out | ios:binary);/保存压缩文件for(int iWright = 0; iWright 256; +iWright) /在压缩文件中存入每个叶子节点的权值 outfile.write(FileName,4);读入文件后缀名do /压缩后的文件读入到文件中 while(iNumofBits = iMax); /读入 1024 个字节ifile.seekg(0,ios:end);long double ldOriginSize = ifile.tellg();outfile.seekp(0,ios:end);long double ldChangedSize = outfile.tellp();return (float)(ldOriginSize - ldChangedSize)/ldOriginSize)*100;/计算压缩率