1、 计算机科学学院 数据结构课程设计 题题 目：基于哈夫曼树的文件压缩目：基于哈夫曼树的文件压缩/ /解压程序解压程序 学生姓名：学生姓名： 学学 号：号： 专专 业：计算机科学与技术业：计算机科学与技术 班班 级：级： 指导教师姓名及职称：指导教师姓名及职称： 讲师讲师 起止时间：起止时间： 2014 年 3 月 2014 年 4 月 1 1 需求分析需求分析 1.1 课题背景及意义 近年来，随着计算机技术的发展，多媒体计算机技术、计算机网络技术以及 现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应 用与发展，各个系统的数据量越来越大，给数据的存储、传输以及有效、快速获
2、取信息带来了严重的障碍。数据压缩技术能够比较有效地解决这个问题。 还有在最近几年中兴起的物联网和云计算都是对海量的数据进行处理和传 输的，如果不对数据进行压缩，那么数据传输所需的带宽要求就很高，物理成本 上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置，且涉及领域 多，应用广泛，与我们的生活息息相关。 1.2 课题要求 1.2.1实现一个基于哈夫曼树的文件压缩程序和文件解压程序。 1.2.2.压缩程序能输入源文件进行压缩，输出压缩文件； 1.2.3解压程序读入压缩文件，根据相应的哈夫曼编码解压还原 ，得到对应的 源文件。 1.2.4可选做：求出压缩率；打印哈夫曼树；对文件夹压缩；图形
3、图形化窗口 操作界面。 1.3 任务和要求 1.3.1 选择 1 时： 输入一个待压缩的文本文件名称(可带路径)。 如:D:1XXX.txt 压缩文件名称= D:1XXX.zip 1.3.2 选择 2 时： 输入一个待解压的压缩文件名称(可带路径)。 如:D:1YYY.txt 解压文件名称=D:1YYY.zip 2 2 概要设计概要设计 2.1 问题解决的思路概述 图 1 主程序流程图 2.2 算法思想： 2.2.1 输入要压缩的文件 首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示 选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压 缩软件的名称， 由键
4、盘输入文件路径和文件名称， 读入字符数组中， 打开该文件， 按照提示进行压缩。若打不开，则继续输入。 2.2.2 读文件并计算字符频率 文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体 数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。 2.2.3 根据字符的频率，利用 Huffman 编码思想创建 Huffman 树 将所记录的字符的频率作为权值来创建 Huffman 树， 依次选择权值最小的两 个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符 结点都成为叶子结点。 统计字符， 得出统 计出字符的权值 n 建立哈夫曼 树 生成二进制文件 对
5、二进制文件进 行解码 根据哈夫曼树编 码 对编码进行压缩 生成对应文件 根据哈夫曼树解 码 生成哈夫曼树 2.2.4 由创建的 Huffman 树来决定字符对应的编码，进行文件的压缩 根据创建的 Huffman 树来确定个字符的 01 编码，左孩子为 0，右孩子为 1。 读取文件，依次将每个字符用他们的编码表示，即完成一次编码。 2.2.5 解码压缩即根据 Huffman 树进行译码 读取编码文件，依据创建的 Huffman 树，定义一个指针指向根结点。从根结 点开始，每读一个字符，指针变化一次（当读取的字符是1时，指针指向当前 所指结点的右孩子，当读取的字符是0时，指针指向当前所指结点的左孩
6、子） ， 直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时） 。将当前 叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照 上述方法依次进行下去直至文件 2.3 数据结构定义 typedef struct node /哈夫曼树结构体 long w;/权重 short p,l,r; /定义双亲，左孩子，右孩子 htnode,*htnp; typedef struct huffman_code unsigned char len;/记录该结点哈夫曼编码的长度 unsigned char *codestr; /记录该结点的哈夫曼编码 hufcode; 2.5 主程序的流程及模块间关系 主函数实例化 huffmanTree 类，并实现菜单工具栏，通过用户的选择输入，用 switch 语句进行分支执行 huffmanTree 类中功能函数： 1:压缩函数 int compress(char *source_file,char *obj_file)； 2:解压函数 int de
