数据结构课程设计报告-哈夫曼树

《数据结构课程设计报告-哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机科学学院数据结构课程设计题目：基于哈夫曼树的文件压缩/解压程序学生姓名：林华学号：121345012021专业：计算机科学与技术班级：12级（2）班指导教师姓名及职称：陈明讲师起止时间：2014年3月——2014年4月1需求分析1.1课题背景及意义近年来，随着计算机技术的发展，多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展，各个系统的数据量越来越大，给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术能够比较有效地解决这个问题。还有在最近几年中兴起的物联网和云计算都是对海量的数据进行处理和传输的，如果不

2、对数据进行压缩，那么数据传输所需的带宽要求就很高，物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置，且涉及领域多，应用广泛，与我们的生活息息相关。1.2课题要求1.2.1．实现一个基于哈夫曼树的文件压缩程序和文件解压程序。1.2.2.压缩程序能输入源文件进行压缩，输出压缩文件；1.2.3．解压程序读入压缩文件，根据相应的哈夫曼编码解压还原，得到对应的源文件。1.2.4．可选做：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。1.3任务和要求1.3.1选择1时：输入一个待压缩的文本文件名称(可带路径)。如:D:1XXX.txt压缩文件名称=D:1XXX.

3、zip1.3.2选择2时：输入一个待解压的压缩文件名称(可带路径)。如:D:1YYY.txt解压文件名称=D:1YYY.zip2概要设计2.1问题解决的思路概述建立哈夫曼树根据哈夫曼树解码对二进制文件进行解码统计字符，得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成对应文件生成二进制文件图1主程序流程图2.2算法思想：2.2.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。

4、若打不开，则继续输入。2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即

5、完成一次编码。2.2.5解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘1’时，指针指向当前所指结点的右孩子，当读取的字符是‘0’时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件2.3数据结构定义typedefstructnode//哈夫曼树结构体{longw;//权重shortp,l,r;//定义双亲，左孩子，右孩子}htn

6、ode,*htnp;typedefstructhuffman_code{unsignedcharlen;//记录该结点哈夫曼编码的长度unsignedchar*codestr;//记录该结点的哈夫曼编码}hufcode;2.5主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：1:压缩函数intcompress(char*source_file,char*obj_file)；2:解压函数intdecompress(char*source_file,char*obj_file)；并可

7、在完成相应功能后安全退出，压缩或解压的文件在同文件夹下生成。3.详细设计核心算法----huffman算法：3.1根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,其中每棵二叉树T1中只有一个带权的w1的根据点，其左右子树均空。3.2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之