数据结构课程设计哈夫曼编码).doc

数据结构课程设计报告 采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。 要求：(1)压缩原文件的规模应不小于5K。 (2)提供恢复文件与原文件的相同性对比功能。 ——哈夫曼编码 班 级： 软件112班 姓 名： 刘路峰 指导教师： 兰红 成 绩： 信息工程学院 2012年 12月 28日 目录 1 需求分析 3 1.1 主要任务 3 1.2 课题要求 3 1.3 主要功能 3 1.4 主要工作 3 1.4.1 压缩部分 3 1.4.2 解压部分 3 2 概要设计 4 2.1 抽象数据 4 2.2 头文件及宏、结构体定义 5 2.3 主程序流程 6 2.4 各程序模块层次关系 7 3 详细设计 7 3.1 模块实现 7 3.1.1 主要模块（函数） 7 3.2 流程图 12 4 调试分析 12 4.1 遇到的问题 12 4.1.1 读取文件遇到值为-1的字符 12 4.1.2 文件读取问题导致程序停止工作 13 4.2 程序代码改进 14 4.2.1 FileExtract()函数改进 14 4.3 程序设计回顾 15 4.4 心得与体会 15 5 测试结果 16 5.1 英文文章测试 16 5.2 其他测试 19 参考文献 22 附录：源代码 22 1 需求分析 1.1 主要任务 实现文件的压缩和解压并计算压缩率 1.2 课题要求 (1)压缩原文件的规模应不小于5K。 (2)提供恢复文件与原文件的相同性对比功能。 1.3 主要功能 (1)压缩：实现对文件的压缩，生成一个比原文件还小的压缩文件。 (2)解压：能够对已经压缩的这个文件进行解压，恢复原来的文件。 1.4 主要工作 1.4.1 压缩部分 (1)读取文件，并统计文件中字符权值（个数）； (2)建立Huffman树； (3)对文件进行Huffman编码； (4)读取源文件，对字符进行翻译； (5)翻译结果写入压缩文件。 1.4.2 解压部分 (1)读取文件，获取各字符及字符权值（个数）； (2)建立Huffman树； (3)对字符串编码进行解码； (4)解码结果写入解压文件。 2 概要设计 2.1 抽象数据 抽象数据类型定义： ADT{ 数据对象：只包含英文字符和数字的文本文档 基本操作： CreateHuffmanTree(HuffmanTree HT) 初始条件：Huffman树已定义 操作结果：初始化Huffman树 FileRead(HuffmanTree HT,char filename[]) 初始条件：需压缩文档已存在 操作结果：统计文档中出现的字符和字符的权值（即出现次数，下同）cmp(const void *a,const void *b) 初始条件： 操作结果： Select(HuffmanTree HT,int k,int s1,int s2) 初始条件：文档中出现的字符和字符的权值已获得 操作结果：选出k个叶子结点中权值最小的两个结点 HuffmanCoding(HuffmanTree HT,HCode HC) 初始条件：文档中出现的字符和字符的权值已获得 操作结果：建立Huffman树，求各个字符的Huffman编码 FilePrint(HuffmanTree HT,HCode HC) 初始条件：Huffman编码以及各节点的权值已求得 操作结果：将求得的数据分别写入HuffmanCode.txt、Char.txt、Weight.txt FileWrite(HCode HC,char filename[]) 初始条件：Huffman编码以及各节点的权值已求得 操作结果：将文档翻译成Huffman编码，并以字符形式写入以filename为文件名的文件ReadSize(char filename[]) 初始条件：操作结果：以filename为文件名的文FileConvert(char filename[]) 初始条件：File.txt已存在 操作结果：将字符形式的Huffman编码翻译成二进制形式，每组成8 bit就通过位操作合并成一个字节写入以filename为文件名的文件，最后不足8 位时将最后的几位写入Tail.txtExFileRead(HuffmanTree HT,HCode HC) 初始条件：压缩生成的HuffmanCode.txt、Char.txt和Weight.txt已存在 操作结果：读取字符权值和其Huffman编码 FileExtract(char filename[]) 初始条件：压缩结果文件filename和tail.txt已存在 操作结果： 将