左子璇组哈夫曼编码——课程设计报告.doc

《左子璇组哈夫曼编码——课程设计报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、东北大学信息科学与工程学院数据结构课程设计报告题目基于堆的哈夫曼编码课题组长左子璇课题组成员梁天怡鲍婉婷专业名称物联网工程班级物联网1201指导教师  孟凡荣2014-7-17课程设计任务书题目：基于堆的哈夫曼编码问题问题描述：优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。设计要求:设计基于堆的优先队列的哈夫曼编码程序。（1）采用ST

2、L的堆、向量等数据结构。（2）用堆实现STL的优先队列类。（3）实现优先队列的哈夫曼树和哈夫曼编码。指导教师签字：年月日目录1.1课题任务51.2课题原理51.3相关知识52需求分析62.1课题调研62.2用户需求分析63方案设计63.1总体功能设计63.2数据结构设计63.3函数原型设计83.4主算法设计143.5用户界面设计184方案实现234.1开发环境与工具234.2程序设计关键技术234.3个人设计实现（按组员分工）4.3.1左子璇设计实现244.3.2鲍婉婷设计实现274.3.3梁天怡设计实现3

3、25测试与调试395.1个人测试（按组员分工）395.1.1左子璇测试405.1.2梁天怡测试405.1.3鲍婉婷测试405.2组装与系统测试415.3系统运行426课题总结426.1课题评价426.2团队协作426.3个人设计小结（按组员分工）436.3.1左子璇设计小结436.3.2鲍婉婷设计小结436.3.3梁天怡设计小结447附录A课题任务分工44A-1课题程序设计分工45A-2课题报告分工45附录B课题设计文档（光盘）B-1课程设计报告（电子版）B-2源程序代码（*.H，*.CPP）B-3工程与可

4、执行文件）B-4屏幕演示录像文件（可选）附录C用户操作手册（可选）C.1运行环境说明C.2操作说明1.课题概述1.1课题任务【问题描述】优先队列中的每一个元素都有一个优先级。在优先队列中，按照对象的优先级进行服务。用堆来实现优先队列可以获得较高的效率。在哈夫曼编码中，利用最小堆构造优先队列，一旦当前最小权值的两棵树合并成为一棵新树后，将新树重新插入队列中。【设计要求】设计基于堆的优先队列的哈夫曼编码程序。（1）采用STL的堆、向量等数据结构。（2）用堆实现STL的优先队列类。（3）实现优先队列的哈夫曼树和哈

5、夫曼编码。1.2课题原理堆是一种完全二叉排序树，利用堆实现优先队列的时间复杂度远远低于一般算法，利用堆的原理建立的初始队列实质就是建立一个空堆，成员的入队就是将对象插入队列的过程，而对于一个已经是堆的队列，只需将元素插入堆尾，根据哈夫曼编码原理，每次选取两个最小值进行合并，利用优先队列可以很简单的实现最小值的选择。利用范式哈夫曼编码可以容易实现后续的各种编码应用。1.3相关知识1.c的语法c++面向对象的思想2.霍夫曼编码的基本原理3.范式霍夫曼编码思想4.stl中的优先队列(priority_queue)

6、、对组(pair)5.二进制文件存储，读写6.数的不同进制换算2.需求分析2.1课题调研课题要求利用优先队列实现哈夫曼编码，而哈夫曼编码的简单实现并没有实际的应用价值也不好直观的展现，因此我们把哈夫曼编码的最主要应用压缩和解压作为附加功能进行实现，使之具有实际应用价值。2.2用户需求分析本程序可以实现的哈夫曼编码并且将之应用到文件的压缩和解压。3.方案设计3.1总体功能设计 程序文件调用Main.cppcompressor.cppcompressor.h3.2数据结构设计3.2.1compressor类的构

7、建class compressor{public:    compressor();    ~compressor();   void compress(char *src); //压缩文件的外部接口 负责压缩    void decompress(char *des); //解压文件的接口 复杂解压private:    char *src,*des;   //src是原文件 需要压缩的文件路径，des是需要解压的文件路径    int *asciiToNumber;  //每个字符对应的霍夫曼编码的数值

8、    int nOfChar,totBit;   //文件中出现的字符数量，最后一个字节中有效的位数    unsigned char *character,*length,*table;  //出现的字符以及他们的编码长度 table是按照排序后 每个字符的序号    void create(char *uncompressFile);   //从源文件中建立霍夫曼编码表    void recover(ch