基于C语言实现的文件加密解密与压缩解压【100011224】

# 一、题目要求： - 文件加密 - 以某文件为样本进行哈夫曼编码或其它编码 - 输入待加密文件进行加密 - 输入待解密文件解密 以某文件为样本进行编码，即是事先将每个字符所对应的编码规定下来，用密码本记录，比如A->001,B->010。加密就是将加密文件的字符兑换成编码，解码就是将编码兑换成字符。仔细想想，这根本就没有难度，也不需要什么数据结构或算法。若是毫无创新的照搬要求，我想分数也顶多是及格水平吧。 我们自然是不甘心于此。所有我们改进了加密方法。密码本是动态的，根据加密文件，采用哈夫曼编码技术，生成密码本。加密文件时，生成两份文件，一份是加密后的文件，一份是密码本。解密时需要这两份文件参与。但是只有加密解密也太过于单调无趣了吧。所有，我们加入了一个更加复杂更加实用的功能——文件的压缩解压。 文件的压缩解压用到的数据结构和算法颇多。文件压缩思想是借鉴经典的lz77算法（zip等著名压缩软件便是采用这样算法），便在此上做些改动。我们的文件采用2步压缩原理，首先根据lz77算法思想将文件数据压缩成一个个的三元组（后面介绍），然后再将这些三元组采用哈夫曼编码技术进一步压缩。既然用到了哈夫曼编码，就必须得存储其哈夫曼树或每个字符和其对应的编码。那么如何利用更少的空间存储这些数据呢？就得借用deflate树了（一种特殊的哈夫曼树）。 注：为了兼容中英文问题，本系统所指的字符是指一个字节，取值范围0~255。我们将所有数据看成一个个字节序列，不做任何数据类型划分。也就是说，我们的系统可以兼容任何编码格式，因为数据都是由一个个字节组成的吗。 # 二、技术指标 - 开发平台：Microsoft Visual C++6.0 win32控制台 - 编程语言：C++ - 规范：C++11标准 - 交互方式：shell命令行交互 功能指标： - 文件的加密解密 - 文件的压缩解压 - Shell命令行交互方式模拟 ## 2.1 系统分析 系统主要分为三个模块，1个输入输出交互模块，2个功能模块。2个功能模块分别是加密解密模块和压缩解压模块。用户只需要通过交互模块来使用系统，而没必要关心内部具体实现。2个功能模块分别只对外提供2组接口（加密解密以及压缩解压），交互模块只需要调用这两组接口，即可调用功能。这使得交互模块与这2个功能模块达到了数据耦合层次。  2个功能模块是系统的核心，它们设计到的数据结构以及算法众多，且有很多相似的之处。为了提高系统的内聚性，我们将众多的数据结构封装成一个子模块。每个子模块以一种数据结构为主，只对外提供这些数据结构的接口。对于2个功能模块中相同或类似的代码，我们也将其抽出处理，封装成一个小模块，尽管这使得耦合度下降，但是确提高了内聚性和代码重用性。 每个模块间都尽量增加内聚性，但也不可避免的出现相互调用的关系。按照这种调用关系，我们将各主要模块之间的调用关系用如下图来表示，还有一些小模块没有加入。  # 三、功能描述 本系统的功能较为单一，对用户提供的接口较少。核心功能就是文件的加密解密和压缩解压。虽然接口单一，但是功能实现却是很复杂。下面来详细的介绍这两块功能。 文件加密解密： 文件加密： 接口：void Encryption(const char *Fn, const char *Fd, const char *Ft); //文件加密 参数描述：Fn:待加密的源文件，Fd:加密后的目标文件,Ft:生成的密码本文件。 功能描述： - 统计待加密源文件Fn文件中出现的字符以及其对应的频率。 - 将统计得到的字符数组和其对应频率作为构造哈夫曼树的参数。 - 将构造出来的字符码表（每个字符和其对应的编码）保存到密码本文件Ft中。 - 循环从Fn取出一定大小的字符串，对其进行哈夫曼编码。将其编码保存到目标文件Fd中，直到取完所有数据。 文件解密： 接口：void Decryption(const char *Fn, const char *Fd, const char *Ft); //文件解密 参数描述：Fn:待解密的源文件，Fd:解密后的目标文件，Ft:所需要的密码本文件 功能描述： - 从密码本文件Ft中获取字符码表。 - 以字符码表为参数构造哈夫曼树。 - 循环从Fn文件中取出一定大小的编码，对其进行哈夫曼译码。将其译码保存到目标文件Fd中，直到取完所有编码。   文件压缩解压： 文件压缩： - 接口：void Compression(const char *Fn, const char *Fd, int level=4); - 参数描述：Fn:待压缩源文件，Fd:压缩后的目标文件，level:压缩等级(1~9，默认4级)。 - 功能描述：分2级压缩。 - 利用lz77算法和kmp算法，将字符串用一个个三元组(距离，长度，下一个字符)的形式表述并将其保存到临时文件中。 - 利用哈夫曼编码技术将临时文件进一步压缩。将字符码表和编码数据都保存到目标文件Fd中。 文件解压： - 接口：void Uncompression(const char *Fn, const char *Fd); - 参数描述：Fn:待解压源文件，Fd:解压后的目标文件 - 功能描述：分2级解压。 - 读取Fn中的字符码表，利用其构造出哈夫曼树。 - 读取Fn中的编码数据，利用哈夫曼译码，将编码数据还原成一个个的三元组，保存到临时文件中 - 从临时文件读取三元组，复原成字符串，保存到目标文件Fd中。   除了上述两个核心模块，交互模块也是不可获取的。 用户交互： 接口：void shell() 参数：无 功能描述：这是一个无限循环的模块，提示用户输入后会一直等待着用户的输入。当用户输入指令后。会根据其输入的指令的不同而做出不同的选择。如执行加密解密功能、退出系统功能等。 # 四、详细设计：算法 见第六部分 # 五、数据结构及其接口： ## 5.1 堆 主要接口： ```c++ Heap(int size=30, bool flag=true); //构造大小为size的堆。flag=true:小根堆，flase:大根堆 void EnQueue(T data); //入队 DeQueue(); //出队 GetHead(); //获取对头元素 bool Empty(); //是否队空 ``` ## 5.2 循环队列 主要接口： ```c++ CirQueue(int size=100); //构造大小为size的空队列 void EnQueue(DataType data); //入队 DataType DeQueue(); //出队 DataType GetHead(); //获取对头元素 bool Empty(); //是否队空 bool Full(); //是否队满 ``` ## 5.3 哈夫曼树 数据结构： ```c++ //节点结构体 template <typename T> struct ElemType { element; //元素 int wei; //权重 ElemType<T> *lch; //左孩子下标 ElemType<T> *rch; //右孩子下标 }; //字符码表结构体 template <typename T> struct CodeTable { element; //元素 std::string code; //编码 }; ``` 主要接口： ```c++ HuffermanTree(T elements[],int wei[], int size); //根据元素和其对应的权重创建哈夫曼树 HuffermanTree(T elements[], std::string codes[], int size); //根�