数据结构课程设计--哈夫曼编码和译码报告

内蒙古科技大学本科生课程设计说明书题目：数据结构课程设计——哈夫曼编码和译码学生姓名：朱玉龙学号：1467159106专业：软件工程班级：1班指导教师：余金林日期：2016年1月8日内蒙古科技大学课程设计说明书1内蒙古科技大学课程设计任务书课程名称数据结构课程设计设计题目Huffman编码和译码指导教师余金林时间2015.12——2016.1一、教学要求1.掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风二、设计资料及参数每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。Huffman编码和译码根据给定的字符集和各字符的频率值，求出其中给定字符Huffman编码，并针对一段文本（定义在该字符集上）进行编码和译码，实现一个Huffman编码/译码系统。要求设计类（或类模板）来描述Huffman树及其操作，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数：求Huffman编码输入字符串，求出编码输入一段编码，实现译码并设计主函数测试该类。三、设计要求及成果1.分析课程设计题目的要求2.写出详细设计说明3.编写程序代码，调试程序使其能正确运行4.设计完成的软件要便于操作和使用5.设计完成后提交课程设计报告四、进度安排资料查阅与讨论（1天）系统分析（2天）系统的开发与测试（5天）编写课程设计说明书和验收（2天）五、评分标准1.根据平时上机考勤、表现和进度，教师将每天点名和检查2.根据课程设计完成情况，必须有可运行的软件。3.根据课程设计报告的质量，如有雷同，则所有雷同的所有人均判为不及格。4.根据答辩的情况，应能够以清晰的思路和准确、简练的语言叙述自己的设计和回答教师的提问六、建议参考资料1．《数据结构（C语言版）》严蔚敏、吴伟民主编清华大学出版社2004.112．《数据结构课程设计案例精编（用C/C++描述）》，李建学等编著，清华大学出版社2007.23.《数据结构:用面向对象方法与C++语言描述》，殷人昆主编，清华大学出版社2007内蒙古科技大学课程设计说明书2目录内蒙古科技大学课程设计任务书···························································1第一章需求分析··············································································31.1程序的功能·········································································31.2输入输出的要求···································································3第二章概要设计············································································32.1总体设计············································································32.2数据类型设计（或数据结构设计）···········································42.3接口设计//函数声明··························································5第三章详细设计············································································63.1工程视图············································································63.2类图视图············································································63.3函数的调用关系············································错误!未定义书签。3.4主程序流程图······································································83.5主要算法流程图···································································9第四章测试分析···········································································114.1测试程序执行情况·······························································11第五章用户手册（可选）·······························································12第六章课程设计总结·····································································13附录：程序代码················································································14内蒙古科技大学课程设计说明书3第一章需求分析1.1.程序的功能能对输入的字符串实现Huffman编码，且能利用生成的编码对Huffman代码串进行译码，输出相应字符串。2.2.输入输出的要求首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的次数，然后输出通过Huffman编码得到的各种字符的Huffman编码。此时程序要求输入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。第二章概要设计2.1总体设计主函数哈夫曼树初始化函数哈夫曼树编码函数哈夫曼树译码函数权值大小比较函数内蒙古科技大学课程设计说明书42.2数据类型设计（或数据结构设计）enumChild{none,lchild,rchild};//采用枚举，标记是左孩子还是右孩子classelement//元素类{public://类的公有成员elememt();//构造函数voidchange(charl,char*c,intp,Childh,intw)//对对象进行修改操作voidgetparent(intp)//对父结点的值进行修改操作voidgeta(Childh)//对孩子结点进行修改操作voidgetweight(intw)//对权值进行修改操作intreturnweight()//返回权值操作friendvoidSelect(elementh[],intk,int*a,int*b);//友元函数的声明friendvoidHuffmanTreeCode(elementHT[]);friendvoidHuffmanTreeYima(elementhuff[],charcod[],intb);private://类的私有成员charletter,*code;//letter为字符,*code指向编码字符串intweight;//权值intparent;//父结点Childa;//为父结点的左孩子还是右孩子};内蒙古科技大学课程设计说明书52.3接口设计主函数：对输入的字符段进行存储，并对字符数和对应的权值（字符个数）进行统计存储。哈夫曼树初始化函数：对给定的字符数和权值，创建一棵哈夫曼树。权值大小比较函数：找到每次所给集合的最小值和次小值，并返回给哈夫曼树初始化函数。哈夫曼树编码函数：对创建的哈夫曼树，为左孩子的赋值为0，右孩子赋值为1，然后对叶子结点依次编码。哈夫曼树译码函数：对输入的01二进制数一一与叶子结点的编码依次比较匹配。内蒙古科技大学课程设计说明书6第三章详细设计3.1工程视图图3.1工程视图3.2类图视图图3.2类图视图内蒙古科技大学课程设计说明书73.3函数的调用关系如下图：图3.3函数调用关系图主函数main()哈夫曼初始化函数InitHuffmanTree（）寻找最小和次小结点函数Select()字符编码函数HuffmanTreeCode（）字符译码函数HuffmanTreeYima（）内蒙古科技大学课程设计说明书83.4主程序流程图YESNO主函数编码字符的录入初始化字符和权值的统计寻找父结点为空的最小和次小结点哈夫曼树是否创建完毕？最小结点和次小结点相加生成新的结点，并置父结点为新生成结点的数组下标编码录入一段二进制数译码是否继续译码？结束YESNO内蒙古科技大学课程设计说明书9图3.4主程序流程图3.5主要算法流程图图3.5.1哈夫曼编码函数NOYESYESNO开始HT[i]调出结点孩子信息，若为左孩子，0进栈；右孩子，1进栈父结点是否为空？01字码依次出栈，并赋值给HT[i]的编码in?结束i++通过下标找到父结点i=0内蒙古科技大学课程设计说明书10图3.5.2哈夫曼译码函数YESNONOYESNOYES开始输入二进制字符进行译码操作，以#结束i=0调出HT[i]的编码与二进制编码进行匹配是否匹配成功？i++in?/用队列存储HT[i]的字符二进制编码是否结束？译码成功！输出队列中的字符译码结束输入有误！译码失败内蒙古科技大学课程设计说明书11第四章测试分析4.1测试程序执行情况准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：输入：编码输入演示图输出：编码输出演示图正确输入哈夫曼编码代号：正确译码输入演示图输出：正确输入译码译码结果输出演示图错误输入哈夫曼编码代号：错误输入哈夫曼编码代码串示意图输出：错误输入哈夫曼编码代码串输出示意图内蒙古科技大学课程设计说明书12第五章用户手册（可选）1.运行程序，程序首先会要求你输入需要编码的字符串，输入完毕按回车即可进行编码：程序启动画面输出：编码输出画面2.输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即可进行译码：译码输入界面输出：译码输出界面3.译码结束后，输入N可退出程序，输入Y可继续进行译码。内蒙古科技大学课程设计说明书13第六章课程设计总结此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西：首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，以致没有完全达到课题的要求。另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。最终在考核的时候，交给老师的是一个界面简陋，功能不全面的程序。通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲