哈夫曼编译码系统

数据结构课程设计说明书哈夫曼树编码译码学院（部）：计算机科学与工程学院专业班级：物联网工程12-2班学号：2012303285学生姓名：陈喜慧指导教师：郝伟起止时间：2013年12月29日至2014年01月09日安徽理工大学课程设计（论文）任务书计算机科学与工程学院学号2012303285学生姓名陈喜慧专业（班级）物联网工程12-2班设计题目哈夫曼码的编/译码系统设计技术参数（1）用C++或C语言实现设计任务；（2）所设计的程序可读性好，执行效率高；（3）有良好的操作界面；（4）设计说明书能很好地反映设计内容设计要求（1）要求小组成员熟练掌握数据结构的基本知识和技能；（2）基本掌握数据结构的基本思路和方法；（3）能够利用所学的数据结构基本知识和技能，解决简单的相关的问题；（5）熟练掌握树的遍历；（6）利用哈夫曼树进行通信的二进制编码。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划2013.12.30-14.01.05根据课程设计大纲的要求，查找相关资料，完成需求分析；2014.01.06进行系统的概要设计；2014.01.07进行系统的详细设计和源代码的书写；2014.01.08-14.01.09对系统进行调试分析，写出课程设计报告。参考资料[1]严蔚敏,吴伟民编著.数据结构（C语言版）,北京:清华大学出版社,2002；[2]严蔚敏,吴伟民,米宁编著.数据结构题集（C语言版）北京:清华大学出版社,1996；指导教师签字教研室主任签字2014年01月09日安徽理工大学课程设计（论文）成绩评定表学生姓名：陈喜慧学号：2012303285专业班级:物联网工程12-2班课程设计题目：哈夫曼码的编/译码系统指导教师评语：1：文档不要出现空白页2：目录需要重新引用，更新不对3：多余的标点符号需要删除4：分页符的放置位置不合理重新编辑5：需求分析下应该插入引言6：测试数据这个标题应该改一下，有歧义7：标题上不能加括号8：详细设计下需要插入引言9：文档不要有空行10：参考文件需要再添加几个11：系统运行这一小节可以放到运行调试下面12：不需要完整源码，不需要用附录形式输出（见评分表）成绩：指导教师：年月日课程设计评分表课程设计评分标准分为前言、分析设计、主体内容、参考文献和排版五部分内容，每部分的得分标准参见下表。内容标准得分范围得分前言（10分）思路清晰，描述清楚。9-10思路基本清晰，描述基本清楚。6-8思路混乱，描述不清。0-5分析设计（30分）问题分析清楚，设计合理。25-30能够基本分析出关键问题，设计上基本能够满足要求。18-24分析问题有偏差，设计上存在问题。9-17分析有误，设计不能满足需求。0-8主体内容（30分）内容详实，能够充分表达整个课程设计的内容。25-30内容完整，能够基本表达清楚课程设计的主要内容。18-24内容有缺失，无法清楚完整表达整个设计内容。9-17内容空洞，无法表达设计内容。0-8参考文献（10分）参考文献在10篇以上，引用合理。9-10参考文献5-9篇，基本与设计内容相符。6-8参考文献少于5篇，且内容相关性差。0-5排版（20分）严格按课程设计模板要求排版。17-20基本按照课程设计模板要求排版，有部分错误。12-16与课程设计模板有大量不符，排版存在很多错误。0-11总分注1：整个课程设计内容必需完整，如果缺少某部分，该部分按0分处理。注2：主体内容包括总结或心得体会部分。评分人：日期：目录1需求分析.....................................................................................................................61.1问题描述..........................................................................................................61.2基本要求..........................................................................................................61.3测试要求..........................................................................................................71.4实现提示..........................................................................................................72总体设计.....................................................................................................................92.1哈夫曼编译码器的算法思想..........................................................................92.2简单函数..........................................................................................................92.3利用简单操作实现的复杂功能......................................................................92.4显示格式的实现............................................................................................103详细设计...................................................................................................................113.1编码函数........................................................................................................123.2译码函数........................................................................................................134调试分析...................................................................................................................155小结...........................................................................................................................19参考文献......................................................................................................................201需求分析在这次课程设计中，所进行的实验是：哈夫曼编码和编译器。对哈夫曼树进行建立，由节点的权值建立最小二叉树，哈夫曼树haftree，并由所建立的哈夫曼树进行编码，求出各个节点的编码。在由所求的哈夫曼树，输入一段二进制电文，能够输出那所建立的哈夫曼树中的节点。建立的haftree用图形化表示出来。在整个代码实现中，窗体的实现，功能的完善，哈夫曼树的建立，哈夫曼树的编码，遇到了许多难题haftree，对象数组的分配空间，节点的属性等都比较困难。在整个过程中，用的是C#语言，包的应用，字符串数组的空间分配，在计算每个字符的权值时，用的是sizeOf()检索整个字符串，计算字符的权值，建立字符出现频度的表格，根据表格中每个字符频度建立起哈夫曼树。从根节点出发检索每个节点的左右孩子，如果是左孩子遍历左边，路径为0，然后左孩子为根节点；如果是右孩子，遍历右孩子，路径为1，然后右孩子为根节点。在重新上述方法，直到所有的节点都遍历完，每个节点的编码就确定后输出来。在译码过程中，由所输入的二进制电文，根据所建立的哈夫曼树，如果是0走左边，如果是1，走右边，直到节点的左右孩子为空时，输出给节点的信息，在回到根节点重新遍历后面的二进制电文，直到所有电文都遍历完为止，输出所有从电文中译码出来的信息。关键词：编译器；频度；译码1.1问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。1.2基本要求一个完整的系统应具有以下功能：（1）I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E:编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D:译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P:打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5）T:打印哈夫曼树（Treeprinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。1.3测试要求（1）利用下面这道题中的数据调试程序。某系统在通信联络中只可能出现八种字符，其概率分别为0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计哈夫曼编码。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。（2）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811611.4实现提示（1）编码结果以文本方式存储在文件CodeFile中。（2）用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。（3）在程序的一次执行过程中，第一次执行I，D或E命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。2总体设计2.1哈夫曼编译码器的算法思想本程序分为统计字符频度，构造哈夫曼树，确定哈夫曼码，翻译哈夫曼码四部统计字符频度：逐一输入字符，如没出现过则建立一