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

1、数据结构应用设计设计报告 题目名称 ： _基于哈夫曼编码的文件压缩器 _ 设计环境 ： _ _ 6.0 _ 指导教师 ： _ _蔡茂蓉 _ 专业班级： _软件工程 0601 班 _ _ 姓 名： _ _ _杨文辉 _ 学 号： _ _20061540_ _ 联系电话： _ 13696574103 _ 电子邮件： _ 设计 日期： 年 月 日 至 年 月 日 设计 报告日期： 年 月 日指导教师评语： 设计 成绩： _ 指导教师签名： _ 1 1 题目 . 2 2 需求分析 . 2 2.1 文件压缩过程： . 2 2.2 文件解压过程： . 3 2.3 压 缩文件的存储结构设计图： . 3 2.

2、4文件示例： . 4 3 详细设计 . 5 3.1 压缩流程图： . 5 3.2 解压流程图： . 5 3.3 节点类设计： . 5 3.4 编码和译码时的控制结构的实现 . 7 调试分析 .11 6 测试结果 . 12 6.1 文件压缩 . 12 6.2 文件解压 . 13 实验总结 . 14 8 参考文献 . 14 2 1 题目 基于哈夫曼编码的文件压缩器 2 需求分析 哈夫曼编码在文件压缩中有其独特一点，它的编码方式特殊。在通信 领域可以得到应用。本程序使用 C+编写，在 VC6.0 上调试，完成了文件的读取，文件字符的统计，哈夫曼树的建立，哈夫曼编码的实现，文件转换为哈夫曼编码成为压缩

3、文件以及文件从压缩状态进行解码。 2.1文件压缩过程： 1、 找出一个待压缩文件，进行读取，并且统计其每种字节出现的频率。 2、 根据已经统计的频率，进行哈夫曼树的构建。 3、 对已经构建的哈夫曼树进行哈夫曼编码，将这个文件读入到一个新的文件中 4、 再次读取文件并且对每一个字符编码，并继续读入到这个新的文件中，这个新的文件就是压缩后的文件 5、 压缩时 函数调用关系为，使用类 CHaffmanCode， 所有的程度操作函数集中在该类中 。 float CHaffmanCode:OpenandCloseFile(char *OpenFile,char *CloseFile) /这个函数压缩函数

4、，把所有要用的操作函数都集中在该函数中。 CreateHaffmanTree(hArray); /使用得到的权值构建哈夫曼树，这里用矩阵实现 EnHaffmanCode(hArray,codes);/对已经构建好的哈夫曼树的每个叶结点进行编码 fCompre = ChangtoCode(OpenFile,CloseFile);/把所有的内容都按照编码存入一个新文件 ，返回文件压缩率 return fCompre； /这是返回文件压缩率 3 2.2文件解压过程： 1、 从压缩文件读出前部分，就是压缩到文件中的各个节点的权值。 2、 使用这些权值再次构建一个哈夫曼树 。 3、 再读入文件其他的压缩

5、信息，并且使用递推的方式，找到文件中应该有的字符 4、 把这些字读入一个新文件，完成解压 5、 解压时函数调用关系， 使用类 CHaffmanCode，所有的程度操作函数集中在该类 中 void CHaffmanCode:TranslateCodes(char* OpenFile,char *CloseFile) /这是个 解压函数 ，把相关的操着都封装在其中 CreateHaffmanTree(hArray); /再次使用这些权值建立一个哈夫曼树 /再读出压缩文件中存储的原文件的后缀名，且保存在 CloseFile 的尾部 /使用递推的办法在建立的哈弗曼树中找出各个压缩后字符的原子符 /将其

6、保存在 CloseFile 中 2.3压缩文件的存储结构设计图： 文件的组成结构 一、原始文件中各个字符的权值（共有个节点 ） 二、原始文件的后缀名 三、原始文件中各个字符被编码后的存入的信息 四、在压缩文件时，由于编码长度不等，最后一个字符添加的的个数 4 2.4文件示例： 这是文件压缩时候产生的头部信息，存储的是每个节点的权值的信息，主要为 256 个节点的权值信息，每个节点的权值是由 1 个整数表示（即 8*4 个二进制位）。在存入节点信息的末尾，存入了 4 个字符型（即 8*4 个二进制位），用以存入文件的后缀名。综上，如果压缩的是空文件（即没有任何字符），那么在压缩文件头部（即 ha

7、f 文件组成前两部分）应该存储的是一个（ 4 * 256 + 4 * 1 = 1028（字节）。 这是文件压缩的信息部分，是对待压缩文件每个节点的编码，然后存储的信息。设计时每种叶子节点的编码为 24 个整型数据的组成的数组。用这 24 个整数表示 24 个二进制位。但是由于编码的长度不等，所以字符存入的 长度不等，因此，设计一个数组（暂定 10245 位），当数组被每个节点的编码（即 24 位整数中有效的整数位）填满了以后，对这个数组以 8 位为单位进行转换。最后一次会由的编码可能不足 1024 位，这时又对其单独处理。如果最后剩下的位数不是 8 位，那么就以加 0 的方式 补充为 8 位，

8、并在文件的末尾加上补 0的个数。如果未补零，自然这个补 0 的个数为 0。 3 详细设计 3.1压缩流程图： 3.2解压流程图： 3.3节点类设计： struct HaffNode unsigned int iWeight; int iLeftChild; 统计每种节点的权值（权值） 对每种叶子 节点编码 构建哈夫曼树 对文件中每个字符编码 目标文件 haf 文件 读取每个叶子节点权值 构建哈夫曼树 待解压文件编码 解压后的文件 6 int iRightChild; int iParent; int iFlag; HaffNode() iWeight = 0;iLeftChild = -1;

9、iRightChild = -1; iParent = -1; iFlag = 0; ; struct HaffNode 设计的作用是使用该节点类构建个叶子节点，个非叶子节点。最终构建成为一个哈夫曼树。 struct Code /用于存每个叶子节点的编码 int iStart;/编码在数组中的开始端 int Bit24;/每个都设置为 24 位的整数 struct Code 类的设计旨在构建存储哈夫曼编码后的编码 class CHaffmanCode private: HaffNode *hArray ; Code *codes; char TempiMax; int iNumofBits;

10、7 public: void CreateHaffmanTree(HaffNode *p);/建立哈夫曼树 void EnHaffmanCode(HaffNode *p,Code *cd);/对哈夫曼树的每个节点编码 float OpenandCloseFile(char *OpenFile,char *CloseFile);/打开文件，调用函数进行编码压 float ChangtoCode(char *OpenFile,char *CloseFile);/使用已有的编码，压缩文件 ,返回压缩率 void TranslateCodes(char *OpenFile, char *CloseFi

11、le);/译码，解压缩 CHaffmanCode(); virtual CHaffmanCode(); ; 3.4编码和译码时的控制结构的实现 class CHaffmanCode 是整个编码和译码的控制类，将函数封装在其中。 CHaffmanCode:CHaffmanCode() hArray = new HaffNodeiNumofCode;/一共申请了 511 个节点，其中 256 个叶子节点 codes= new Code256;/对每个叶子节点相应的编码 / float CHaffmanCode:OpenandCloseFile(char *OpenFile,char *CloseF

12、ile) 8 /打开一个待压缩 文件，提供压缩后存储的地址 ifstream infile(OpenFile, ios:in | ios:binary); do /统计每个节点在 ASCII 中的出现频率 while(iNumofBits = iMax); /每次读入 1024 个字节 CreateHaffmanTree(hArray); /使用得到的权值构建哈夫曼树，这里用矩阵实现 EnHaffmanCode(hArray,codes);/对已经构建好的哈夫曼树的每个叶结点进行编码 reutrn ChangtoCode(OpenFile,CloseFile);/把所有的内容都按照编码存入一个

13、新文件 / void CHaffmanCode:CreateHaffmanTree(HaffNode *p) /构建哈夫曼树 / void CHaffmanCode:EnHaffmanCode(HaffNode *p,Code *cd) /使用已经构建的哈夫曼树对每个叶子节点进行编码 9 / float CHaffmanCode:ChangtoCode(char *OpenFile,char *CloseFile) ifstream ifile(OpenFile,ios:in | ios:binary); /再次读入待压缩的文件 ofstream outfile(CloseFile, ios:

14、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;/计算压缩率 / void CHaffmanCode:TranslateCodes(char* OpenFile,char *CloseFile)