Hffman编码与解码实现文件压缩与解压.doc

数据结构课程设计报告 数据结构课程设计报告 Huffman编码与解码实现文件压缩与解压 学 号： 姓 名： 李爱武 指导教师： 陈波 二○一零年九月三日 目录 目录 ..………………………………….2 目标任务和问题分析 ..………………………………….3 算法及思想描述 ..………………………………….3 ---------建立哈夫曼树、压缩、解压缩 程序结构及测试流程 ..………………………………….5 测试结果分析 ..………………………………….12 收获与体会 ..………………………………….12 参考文献 ..………………………………….13  Huffman编码与解码实现文件压缩与解压 一、目标任务与问题分析 1.1目标任务 采用哈夫曼编码思想实现文件的压缩和解压缩功能，可以将任意文件压缩成任意的压缩文件类型，并且能将压缩后的文件解压成相应的源文件。 1.2问题分析 本问题首先应该是利用哈夫曼思想，对需要压缩的文件中的个字符进行频率统计，为了能对任意的文件进行处理，应该所有的文件以二进制的方式进行处理，即对文件（不管包含的是字母还是汉字）采取一个个的字节（unsigned char）处理，然后根据统计的频率结果构造哈夫曼树，然后对每个字符进行哈夫曼编码，然后逐一对被压缩的文件的每个字符构建的新的哈夫曼编码存入新的文件中即得到的压缩文件。解压过程则利用相应的哈夫曼树及压缩文件中的二进制码将编码序列译码，对文件进行解压，得到解压文件。 二、算法思想描述 2.1 构造哈夫曼树 要利用哈夫曼编码对文本文件进行压缩，首先必须知道期字符相应的哈夫曼编码。为了得到文件中字符的频率，一般的做法是扫描整个文本进行统计，编写程序统计文件中各个字符出现的频率。由于一个字符的范围在[0-255]之间，即共256个状态，所以可以直接用256个哈夫曼树节点即数组（后面有节点的定义）空间来存储整个文件的信息，节点中包括对应字符信息，其中包括频率。 2.1.1 哈夫曼树节点的设计 用结构体NODE来存储节点的信息，其中有成员频率weight、父节点parent、左枝节点lchild、右枝节点rchild、对应的编码code。 2.1.2文件字符频率处理 由于所有的文件都采用字节存取，字符的最多个数就只能是256个，即ASCII码在0-255之间，而我们用的是数组来存储文件的信息，我们用NODE[256]来统计文件的所有信息。此操作的过程中应用的关键技术在于我们直接用该数组 的下标来保存每个字符的信息，原因在于字符为单字节，正好与每个下标0-255对应。这样既减少了内存的开销，而且还精简了代码。我们只需要在每读一个字节（inByte）的同时,让对应的NODE[inByte]加一就可以达到统计字符频率的效果。 2.1.3构建哈夫曼树 哈夫曼树的存储结构采用双亲孩子表示法，即用结构体数组来实现。为了让程序设计更加的精简，我们直接用扩大节点数组的方法来保存，由于原来的256个叶子节点会产生255个父亲节点，所以我们将原来的空间为256的数组扩大为NODE[511]来构建哈弗曼树。扩充空间后，我们开始初始化哈夫曼树，即通过上述统计的叶子节点循环提取哈弗曼中权值最小的两个节点，将它们合并起来，组成一个新的根节点，直到最后哈夫曼树只剩下一个根节点为止。 2.1.4 获得哈夫曼编码 采用字节进行编码，每个字符的Huffman编码是一个0/1串，最高效的方法是采用的是采用位串的形式，我们先定义每个字符的编码为一个字符串。我们从哈夫曼树的根节点开始循环遍历，并给每个节点设置一个编码标志，约定如果没编码状态为0,，左孩子已编码状态为1，右孩子已编码状态为2，首先如果编码状态为0从左孩子开始，如果有左孩子，那么编码字符串加上“0”字符，状态设为1，如果没有左孩子并且没有右孩子则该节点的编码结束；接着考虑没有左孩子但有右孩子并且右孩子没编码的情况，如果有右孩子则编码字符串加“1”，编码状态为2，如果做有节点都已编码，则再对该节点的兄弟节点进行编码，因为此时除了最后面一个编码字符外，兄弟节点的前部分编码和已完成编码的节点是相同的，没必要重复遍历。 2.1.5 将文件进行二进制压缩 以上只能得到文件中每个字符的0/1形式的字符串编码，然而如果想要文件起到真的压缩效果，还必须在读取被压缩文件得到每个字节的编码的同时将字符串编码转化拼接成八位的字节存入压缩文件中。为此我们采用的是将编码字符串切割成长度为八的字串，然后再将其通过从低位遍历如果为“1”则与字节（inByte）值为0