重庆大学实验报告实验题目： 哈夫曼树的应用 学 院： 计算机学院 专业班级：计算机科学与技术 五班 六班 年 级： 2011级 姓 名： 陈云艳 许文丽 王福临 学 号： 20115351 20115352 20115394 完成时间： 2013 年 6 月 1 日指导教师： 石锐 重庆大学教务处制实验项目指导教师评定成绩表学号：20115394姓名：王福临班级：06班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 年 月 日实验项目指导教师评定成绩表学号：20115351姓名：陈云艳班级：05班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 实验项目指导教师评定成绩表学号：20115352姓名：许文丽班级：05班项目分值参考标准评分学习态度10积极与老师、助教讨论（10分）学习马虎，纪律涣散（5分）缺勤（0分）软件/系统质量60功能考虑完善，界面友好，Bug极少，针对异常情况有处理（55-60分）功能考虑完善，界面良好，有一定Bug（49-54分）功能较完善，Bug较多（43-48分）完成程序基本功能（36-42分）部分实现，无法运行（1-35分）抄袭、被抄袭（0分）实验演示答辩10重点突出、有特色、专业知识掌握好、能流畅回答老师提问（9-10分）有一定特色、能较好地回答老师提问（7-8分）能讲解项目的关键实现，能回答基本问题（0-6分）实验报告撰写质量20文档规范，文字、图表表达清楚（18-20分）文档较规范，文字、图表表达较清楚（11-17分）文档不规范，内容空泛、结构混乱（0-10分）指导教师评定成绩：指导教师签名： 重庆大学本科学生实验项目任务书实验题目哈夫曼树的应用学院计算机学院专业计算机科学与技术年级2011级任务描述： 综合运用C+编程技术和数据结构知识，用VS2010或QT设计实现一个简单的哈夫曼编码解码系统。最后提交完整的设计报告和软件程序拷贝。p 设计要求：Complete the implementation of the Huffman coding tree, building on the code presented in Section 5.6. Include a function to compute and store in a table the codes for each letter, and functions to encode and decode messages. This project extended to support le compression. To do so requires adding two steps: (1) Read through the input le to generate actual frequencies for all letters in the le; and (2) store a representation for the Huffman tree at the beginning of the encoded output le to be used by the decoding function. If you have trouble with devising such a representation, see Section 6.5.You can refer to the figure as below:参考资料：p Data Structures and Algorithm Analysis (C+ Version) Clifford A. Shafferp Data Structure and Algorithm Analysis in C+ (Third Edition)，Mark Allen Weiss， Pearson Education, 2006. p Data Structures, Algorithms, and Applications in C+，Sartaj Sahni， McGraw-Hill, 1998. p 数据结构（ C 语言版），严蔚敏，吴伟民编著，清华大学出版社，2007年第1版 任务下达日期 2013 年 5月 5 日完成日期 年 月 日实验报告正文一 需求分析1. 有时候我们需要用到将文件进行压缩，以节省空间，是信息得到更更好的存储，特别是一些现在不用到，可以将其进行压缩而以后需要用的时候再解压；2. 郝夫曼编码刚好可以实现我们的这一需要，利用郝夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本；3. 郝夫曼编码的原理比较简单：对于计算机存储文件，它是按照二进制，对应于每个字符的ASCII值，以01序列存储，但是，如果我们把某一个文件中不同字符出现的频率进行统计，然后按照权值排好序，构建一棵郝夫曼树，将权值较大的用较短的01序列编码，相反，将权值较小的用较长的01序列编码，这样就可以达到整个编码长度的最优，这样，用来存储每个字符的01序列在很大程度上比原来计算机的一般存储方式下的01序列要短，这样就达到了压缩的目的；或者可以看作是一个加密解密的过程，因为计算机存储是按照二进制进行的，但是我们是看不到底层的01序列的，它会把01序列转化为对应字符的ASCII值，然后存储该字符；4. 郝夫曼压缩实现方法主要在郝夫曼树的构建，压缩解压函数的实现，所以比较实用，易于实现。二 系统设计1. 我们首先要有一个控制面板，实现对程序的调试功能的操作：因此，在VS2010下建立一个Qt项目，通过对控制面板上的信息响应函数的实现以达到压缩解压的母的，而信息响应函数的内部又去调用我们事先写好的郝夫曼树类中的郝夫曼树的构建函数和压缩解压函数，所以，我们又在VS环境中声明并定义一些相关操作的函数，主要有compress(压缩函数)，decompress(解压函数)，select(选择函数)，change(对调函数)，getweight(得到权重函数)，return（返回参与编码的字符数）以及reinit（重初始化函数（重清空）;在QT中，我们有如下的函数及功能实现：Widget（对信息响应的函数进行初始化），open_source (打开要被压缩的目标文件) open_des（找出解压的文件另存的地址）dealstr（修改地址）des_info（解压后的文件长度）source_info （要压缩的文件的长度）Go（进行压缩/解压操作）2.具体类图如下：郝夫曼树类继承基类的一些树的基本信息，以实现接口连接；QT中Widget类中的函数（与界面信息直接相连的）来调用郝夫曼树中已经写好的压缩解压函数，具体的关系流程如下图： int parent;int lchild,rchild;char code;int weight;char letter;HuffTree 类 return_count（）; Compress（）； reinit（）; Decompress（）; Select（）; Change（）; Reinit（）； Node类继承 调用 调用 调用 调用 Widget 类open_source（）; des_info（）; open_des（）; Go（）； source_info（）; dealstr（）；3. 再来看看我们的界面：（1） 我们设计了encode和decode两个按钮是方便对压缩还是解压的选择，因为在程序内部我们的Go按钮是通过识别两个按钮传进来的信息进行相对应的操作的；（2） 在界面上，我们可以看到当点击压缩并打开路径文件时，下面的路径框里会自动