文件压缩程序设计报告.doc

课程设计报告 课程名称：操作系统 实验题目：文件压缩程序 院 系：计算机科学与工程学院 班 级： 姓 名： 学 号： 二○一一年七月一日 需求分析： 有两种形式的重复存在于计算机数据中，就是对这两种重复进行了压缩。　　一种是短语形式的重复，即三个字节以上的重复，对于这种重复，用两个数字：1.重复位置距当前压缩位置的距离；2.重复的长度，来表示这个重复，假设这两个数字各占一个字节，于是数据便得到了压缩第二种重复为单字节的重复，一个字节只有256种可能的取值，所以这种重复是必然的。给 256 种字节取值重新编码，使出现较多的字节使用较短的编码，出现较少的字节使用较长的编码，这样一来，变短的字节相对于变长的字节更多，文件的总长度就会减少，并且，字节使用比例越不均匀，压缩比例就越大。编码式压缩必须在短语式压缩之后进行，因为编码式压缩后，原先八位二进制值的字节就被破坏了，这样文件中短语式重复的倾向也会被破坏（除非先进行解码）。另外，短语式压缩后的结果：那些剩下的未被匹配的单、双字节和得到匹配的距离、长度值仍然具有取值分布不均匀性，因此，两种压缩方式的顺序不能变。Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。 概要设计： 主程序流程图： 压缩过程的实现: 压缩过程的流程是清晰而简单的: 1. 创建 Huffman 树 2. 打开需压缩文件 3. 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出生成压缩文件压缩结束。 其中，步骤 1和步骤 3是压缩过程的关键。 ? 步骤1:这里所要做工作是得到 Huffman数中各叶子结点字符出现的频率并进行创建.统计字符出现的频率可以有很多方法:如每次创建前扫描被创建的文件，“实时”的生成各字符的出现频率;或者是创建前即做好统计.这里采用的是前一种方法。 ? 步骤 3: 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit 单位输出. 这是本压缩程序中最关键的部分: 这里涉及“转换”和“输出”两个关键步骤： “转换”部分大可不必去通过遍历 Huffman 树来找到每个字符对应的哈夫曼编码，可以将每个 Huffman 码值及其对应的 ascii 码存放于如下所示的结 构体中： 解压缩过程的实现: 如果说,压缩的过程可以通过查找 codeList 来加速实现的话，而解压缩则必须通过查找 huffman 树才能加以实现.查找的过程是简单的，可以根据 huffman 树的性质来做，当 haffCode的当前 bit 位为 0 时，则向左枝展开有哪些信誉好的足球投注网站;当前bit 位为1时，则向右枝展开有哪些信誉好的足球投注网站，当遇到叶子结点时，则输出haffCode对应的 asciiCode。 详细设计： 核心算法源程序： Huffman树建立源程序： //------------------------------------------------------------- //huffmantree.h //霍夫曼树 #ifndef HUFFMANTREE #define HUFFMANTREE #define Defaultsize 300 #include iostream.h #include bintree.h #include heap.h class Code { public: int code; Code *link; Code(int c=0,Code *l=NULL):code(c),link(l){}; }; class CharNameNode { public: unsigned char charname; //要这样才行 Code *link; CharNameNode(unsigned char c=0,Code *l=NULL):charname(c),link(l){}; }; template class Type class HuffmanTree:public BinaryTreeType { public: int key; HuffmanTree(){}; HuffmanTree(HuffmanTreeType ht1,HuffmanTreeType ht2) { Type temp=0; //可能有变 key=ht1.key+ht2.key;