电文编码与译码数制转换

1、电文编码与译码数制转换沈阳工程学院课程设计设计题目：电文的编码及译码、数制转换别信息学院班级计本151郭景辉程年李成宇学生姓名学号 18172322指导教师姜柳、吕海华职称副教授、讲师 起止日期：2016年6月13日起至2016年6月24日止沈阳工程学院课程设计任务书课程设计题目:电文的编码及译码系 别信息学院学生姓名杨满李成宇班级计本151学号 23 22指导教师姜柳、吕海华职称副教授、讲师课程设计进行地点：实训任务下达时间:2016年6月12日起止日期：2016年6月13日起一至2016年6月24日止 教研室主任张欣2016年6月11日批准一、问题描述在当今社会的一些领域，电文仍然被应用，

2、编写一个电文编码和译码 还是有必要的，该设计是对输入的一串电文字符实现哈夫曼编码，在对哈 夫曼编码生成的代码串进行译码，输出电文字符串。二、课程设计主要内容及要求l构造哈夫曼树2 .编码3 .译码三、对课程设计说明书撰写内容、格式、字数的要求1 .课程设计说明书是体现和总结课程设计成果的载体，主要内容包括: 设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问 题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000 字。2 .在适当位置配合相应的实验原理图、数据通路图、微程序流程图、 实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确 完整，书写工整，

3、装订整齐。3 .设计总结部分主要写本人完成工作简介以及自己的设计体会，包括 通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。 设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组 组长给出评语。” 4口课程设说明书手写或打印均可。手写要用学校统一的课程设计用 纸，用黑或蓝黑墨水工整书写；打印时采用a4纸，页边距均为20mm, 正文采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字， 一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题及图题 采用宋体五号字。5.课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、 正文、参考文献。四、设计完成后

4、应提交成果的种类、数量、质量等方面的要求1 .完成“任务书”中指定的操作功能，运行稳定。2 .课程设计说明书。五、时间进度安排顺序阶段日期计划完成内容备注1第1天阅读资料电文编码与译码数制转换2第23天系统分析设计3第48天程序编制、调试及运行4第9天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）1严蔚敏吴伟民.数据结构（c语言版）.北京:清华大学出版社.20072谭浩强.c程序设计.北京:清华大学出版社.1999.12滕国文.数据结构课程设计.北京:清华大学出版社.2010.09苏仕华 等编著.数据结构课程设计.北京：机械工业出版 社.2005.055李春葆.数据结构（c语言版

5、）习题及解析.北京:清华大学出版社.2002.047/71沈阳工程学院课程设计设计题目:电文的编码及译码、数制转换别信息工程系计本151学生姓名郭景辉程年李成宇学号 18172322指导教师姜柳、吕海华职称副教授、讲师 起止日期：2016年6月13日起至2016年6月24日止电文编码与译码数制转换沈阳工程学院课程设计任务书课程设计题目:系 别信息工程系班级计本151学生姓名郭景辉 程年学号 18 17指导教师姜柳、吕海华职称副教授、讲师课程设计进行地点：实训任务下达时间:2016年6月12日起止日期：2016年6月13日起一至2016年6月24日止 教研室主任张欣2016年6月11日批准一、课

6、程设计的原始资料及依据我们一把情况下所见到的数据都是十进制的，但是数不仅仅是以十进 制的形式存在，还有二进制数、八进制数、十六进制数等，对于这些不同 进制的数，我们无法对他们进行中和运算，因此就要求我们能够将不同进 制的数转换为相同的进制进行运算，这样就方便了不同数制之间的综合运 算o二:课程设计主要内容及要求基本要求：1、在任意不同的两种数制之间可以相互转换2、数制之间的转换在设计程序时要详细说明其转换的基本原理3、要使用栈、数组分别实现该功能4、程序代码逻辑思路清晰，添加适当注释，便于理解5、出设计者本人外其他人运行本程序都能够得到结果，不会产生理解上的错误导致运行结果出错 三、对课程设计

7、说明书撰写内容、格式、字数的要求1 .课程设计说明书是体现和总结课程设计成果的载体，主要内容包括: 设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问 题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于3000 字。2 .在适当位置配合相应的实验原理图、数据通路图、微程序流程图、 实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确 完整，书写工整，装订整齐。3 .设计总结部分主要写本人完成工作简介以及自己的设计体会，包括 通过课程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。 设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组

8、组长给出评语。4. i赢设计器明书手写或打印均可。手写要用学校统一的课程设计用纸, 用黑或蓝黑墨水工整书写；打印时采用a4纸，页边距均为20mm,正文 采用宋体小四号字，行间距18磅。文中大标题采用黑体小三号字，一级 节标题采用黑体四号字，二级节标题采用黑体小四号字，表题及图题采用 宋体五号字。5.课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、 正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1 .完成“任务书”中指定的操作功能，运行稳定。2 .课程设计说明书。电文编码与译码数制转换五、时间进度安排顺序阶段日期计划完成内容备注1第1天阅读资料2第23天系统分析

9、设计3第48天程序编制、调试及运行4第9天成绩评定5第10天撰写课程设计说明书六、主要参考资料（文献）“严蔚敏吴伟民.数据结构（c语言版）.北京:清华大学出版社.20072谭浩强.c程序设计.北京:清华大学出版社.1999.12滕国文.数据结构课程设计.北京:清华大学出版社.2010.09苏仕华 等编著.数据结构课程设计.北京：机械工业出版 社.2005.055李春葆.数据结构（c语言版）习题及解析.北京:清华大学出版社.2002. .04#/71电文编码与译码数制转换沈阳工程学数据结构课程设计成绩评定表系（部）：信息工程班级:计本151学生姓名: 郭景辉指导教师评审意见评价内容具 体 要 求

10、权重评分加权 分调研论证能独立查阅文献，收集资料；能制 定课程设计方案和日程安排。0.15432工作工作态度认真，遵守纪律，出勤0.25432能力态度情况是否良好，能够独立完成设计工作，工作 量按期圆满完成规定的设计任务， 工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8）分加权分合计指导教师签名：年 月日评阅教师评审意见评价内容具 体 要 求权重评分加权 分查阅文献查阅文献有一定广泛性；有综合 归纳资料的能力0.25432工作 量工

11、作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.35432评阅教师评审成绩（加权分合计乘以4）分加权分合计评阅教师签名：年 月日答辩小组评审意见评价内容具 体 要 求权重评分加权 分学生汇报汇报准备充分，思路清晰；语言 表达准确，概念清楚，论点正确， 有层次，有重点，基本上反映了 所完成任务的全部内容；时间符 合要求。0.55432答辩思路清晰；回答问题有理论依据， 基本概念清楚；主要问题回答准 确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答

12、辩小组教师签名：年 月日课程设计总评成绩分系沈医数据结构必1工程学院存程设计成绩评定表i： 程年（部）：信息工程系班级:计本151学生姓名指导教师评审意见评价内容具 体 要 求权重评分加权 分调研论证能独立查阅文献，收集资料；能制 定课程设计方案和日程安排。0.15432工作 能力 态度工作态度认真，遵守纪律，出勤 情况是否良好，能够独立完成设 计工作，0.25432工作 量按期圆满完成规定的设计任务， 工作量饱满，难度适宜。0.25432说明书的质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.55432指导教师评审成绩

13、（加权分合计乘以8）分加权分合计指导教师签名：年 月日评阅教师评审意见评价内容具 体 要 求权重评分加权 分查阅文献查阅文献有一定广泛性；有综合 归纳资料的能力0.25432工作量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.35432评阅教师评审成绩 （加权分合计乘以4）分加权分合计评阅教师签名：年 月日答辩小组评审意见评价内容具 体 要 求权重评分加权 分学生 汇报汇报准备充分，思路清晰；语言 表达准确，概念清楚，论点正确， 有层次，有重点，基本上反映了 所完成任务的全部

14、内容；时间符 合要求。0.55432答辩思路清晰；回答问题有理论依据， 基本概念清楚；主要问题回答准 确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名：年 月 日课程设计总评成绩分沈阳工程学院数据结构课程设计成绩评定表系（部）：信息工程系满班级：计本151学生姓名:指导教师评审意见评价内容具 体 要 求权重评 分加权 分调研论证能独立查阅文献，收集资料；能制 定课程设计方案和日程安排。0.15432工作能力态度工作态度认真，遵守纪律，出勤 情况是否良好，能够独立完成设 计工作，0.25432工作 量按期圆满完成规定的设计任务， 工作量饱满，难度

15、适宜。0.25432说明 书的 质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8）分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具 体 要 求权重评 分加权 分查阅文献查阅文献有一定广泛性；有综合 归纳资料的能力0.25432工作 量工作量饱满，难度适中。0.55432说明书的质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.35432评阅教师评审成绩 （加权分合计乘以4）分加权分合计评阅教师签名

16、：年月日答辩小组评审意见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言 表达准确，概念清楚，论点正确， 有层次，有重点，基本上反映了 所完成任务的全部内容；时间符 合要求。0.55432答辩思路清晰；回答问题有理论依据， 基本概念清楚；主要问题回答准 确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名：年月日课程设计总评成绩分沈阳工程学院数据结构课程设计成绩评定表系（部）:信息工程系班级:计本151学生姓名：李指导教师评审意见评价内容具 体 要 求权重评 分加权 分调研能独立查阅文献，收集资料；能制0.15 4 3 2

17、论证定课程设计方案和日程安排。工作能力态度工作态度认真，遵守纪律，出勤 情况是否良好，能够独立完成设 计工作，0.25432工作 量按期圆满完成规定的设计任务， 工作量饱满，难度适宜。0.25432说明 书的 质量说明书立论正确，论述充分，结 论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。0.55432指导教师评审成绩（加权分合计乘以8）分加权分合计指导教师签名：年月日评阅教师评审意见评价内容具 体 要 求权重评 分加权 分查阅文献查阅文献有一定广泛性；有综合 归纳资料的能力0.25432工作 量工作量饱满，难度适中。0.55432说明说明书立论正确，论述

18、充分，结0.35432书的质量论严谨合理，文字通顺，技术用 语准确，符号统一，编号齐全， 图表完备，书写工整规范。甘（力f阅教师评审成绩分1分合计口权分合计乘以4）加权评阅教师签名：年月日答辩小组评审意见评价内容具 体 要 求权重评 分加权 分学生汇报汇报准备充分，思路清晰；语言 表达准确，概念清楚，论点正确， 有层次，有重点，基本上反映了 所完成任务的全部内容；时间符 合要求。0.55432答辩思路清晰；回答问题有理论依据， 基本概念清楚；主要问题回答准 确，深入，有说服力。0.55432答辩小组评审成绩（加权分合计乘以8）分加权分合计答辩小组教师签名：年月日课程设计总评成绩21 / 71电

19、文编码与译码数制转换摘要数据结构及算法在计算机学科中的地位十分重要，是设计系统程序和大 型应用程序的重要基础。数据结构和算法课程是计算机科学及其相关专业 的一门核心课程，本课程的学习将为我们以后后续的操作系统、数据库、 编译技术等专业基础课和专业课程的学习，以及软件设计水平的提高打下 良好的基础。本课程的学习过程是一个复杂程序设计的训练过程，我们所 要编写的程序要结构清楚和正确易读，符合软件工程的规范。我们进行课程设计的目的是要掌握设计程序的思路，学习会用计算机语 言编写程序，以实现所需要处理的任务。算法的实现是课程设计的灵魂， 也就是我们学习设计的重中之重。算法的设计靠的不是语法规则，而是解

20、 题的思路。所以在开始设计前，我们要掌握好课本的基本内容，并且查阅 一系列的课外资料，锻炼我们设计算法的思路。本次数据结构课程设计电文的编码及译码这个题目,在存储方式上是运 用了三叉链表存储结构，同时在编写程序中使用的基本操作有建立哈夫曼 树以及根据哈夫曼树求出叶子结点的哈夫曼编码；其次，根据生成的哈夫 曼编码，在对自然语言进行编码；最后，输入二进制的数值，根据哈夫曼 编码译码成为自然语言；在编写程序的过程中遇到了许多问题。例如：在 建立哈夫曼树时，由于叶子结点比较多是由26个英文字母和逗号句号空 格来组成，在输入时，要输入29个字符及其对应的权值，所以这棵哈夫 曼树比较大，做的过于复杂；在某

21、些程序语句中，有些语句的逻辑关系比 较强，不易读透；不过在老师的帮助和指导下并经过讨论和改正，使程序 达到了预期的要求。在数制转换中，使用了三种方法来实现这个程序，分别为：数组法、栈、 递归法。数组法利用了一维数组的存储结构，并且利用数组来实现了进制 转换；栈法是先定义了一个栈的结构体，并做了建空栈、压栈、弹栈的函 数，在对数值进行一系列的压栈和弹栈等操作，实现了数制转换；递归法 是运用switch语句和数组的综合运用，在存储方式上使用了一维数组， 在转换过程中自身调用，实现了转换。又因为十进制数在现实和计算机上 运用比较广泛，所以单独做了一个函数getdex,是指把其他进制数转换成 为十进制

22、数，在每种方法中调用即可。此次课设利用模块化设计思想，主 要实现的功能有：给定一个进制数x,通过三种方法，随意进行进制转换, 最后得出想要的进制数。程序刚开始时，进行的语言描述可能有些不妥， 但经过讨论和修正以及老师耐心的指导使数制转换这个程序不断完善。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关健词 编码，译码，数制转换，哈夫曼树/ 71电文编码与译码数制转换目录摘要第一章问题分析01.1 引言0l2背景01.3 分析11.3.1 电文的编码及译码11.3.2 数制转换1第二章原理及运行环境32.1 数据结构理论32.1.1 电文的编码及译码数据结构理论32.1.2 数制转

23、换数据结构理论42.2 运行环境52.2.1 打开方法52.2.2 打开codeblocks中的c环境52.2.3 源程序的建立及编辑、连接6第三章系统分析及设计83.1电文的编码及译码分析及设计8i / 71电文编码与译码数制转换3.1.1 系统的功能83.1.2 系统模块分析及其流程图83.2数制转换分析及设计153.2.1 数制转换的功能153.2.2 系统模块分析及其流程图1519第四章系统功能实现4.1 电文的编码及译码功能实现194.1.1 定义主函数194.1.2 定义存储结构214.1.3 构造哈夫曼树224.l4 编码264.2数制转换功能实现314.2.1 定义主函数314

24、.2.2 定义存储结构324.2.3 数组法功能334.2.4 栈方法功能374.2.5 递归法功能41结论45致谢46参考文献47# / 71电文编码与译码数制转换第一章问题分析1.1 引言数据结构的教学要求是：学会分析研究计算机加工的数据结构的特征, 以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法， 并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习 过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确 易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会 用计算机语言编写程序，以实现所需要处理的任务。要正确处理

25、算法及语 法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学 习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正 确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读， 来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我 们的各方面的知识，特别是一些联系实际的课程设计，它的完成需要自己 平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课程 设计主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学 生应该把精力放在最基本，最常用的内容上，学好基本功。通过本次课程设计

26、，相信我们一定能加强对数据结构这门课程的学习， 尤其在动手实践上会有很大的进步。1.2 背景在当今信息爆炸时代如何采用有效的数据压缩技术节省数据文件的 存储空间和计算机网络的传送时间已越来越引起人们的重视。赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码 是一种编码方式以哈夫曼树一即最优二叉树，带权路径长度最小的二叉树, 经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符，例如 某文件中的一个符号，进行编码。这张编码表的特殊之处在于它是根据每 一个源字符出现的估算概率而建立起来的，出现概率高的字符使用较短的 编码；反之出现概率低的则使用较长的编码，这便使编码之后的字符串的

27、 平均期望长度降低，从而达到无损压缩数据的目的。赫夫曼编码的应用很 广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中 从根到每个叶子都有一条路径 对路径上的各分支约定，指向左子树的分 支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0” 或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈 弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以3/71电文编码与译码数制转换编译成字符串。1.3 分析1.3.1 电文的编码及译码电文的编码及译码运用的是建立哈夫曼树的表示方法，三叉链表作为存 储结构。将26个英文字母和逗号句号空格作为哈夫曼树的

28、结点，由键盘来 输入对应的权值，生成一棵哈夫曼树，再求出每个结点的哈夫曼编码。这 样一来，就可以实现此程序的功能。电文的编码及译码分为三个大部分，分别为哈夫曼树的建立及哈夫曼编 码的生成，利用生成的哈夫曼编码进行语言的编码，最后还可进行代码的 译码。哈夫曼树的建立的基本思想:赫夫曼树的建立由赫夫曼算法的定义可 知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当 前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合 并一次，森林中就减少一棵树，产生一个新结点。显然要进行n-1次合 并，所以共产生n-l个新结点，它们都是具有两个孩子的分支结点。由 此可知，最终求得的哈夫曼

29、树中一共有2n-l个结点，其中n个结点是初 始森林的n个孤立结点。并且哈夫曼树中没有度数为1的分支结点。我们 可以利用一个大小为2n-l的一维数组来存储哈夫曼树中的结点。编码。基本思想：从哈夫曼树的叶子结点出发，通过双亲找到其双亲结 点，通过左右子树，可知该结点是其父结点的左分支或者是右分支，若是 左分支，生成代码0,若是右分支，生成代码1,代码存放在指定数组中, 然后把其父结点作为出发点，重复上述过程，直到找到树根为止。但是， 这样生成的代码序列及要求的编码次序相反，为了得到正确的代码，把最 先生成的代码存放在数组最后一个元素中，再次生成的代码放在数组倒数 第二个个元素中，依次类推，用变量指

30、示编码在数组中的起始位置。这样 编码过程就完成了。译码。基本思想:首先输入二进制代码串，存放在数组char bmaxsize 中并输入一个结束标志2,接下来，将代码及编码表比较，如果为0, 转向左子树；若为1,转向右子树，直到叶结点结束，此时输出叶结点的 数据域，即所对应的字符。继续译码，直到代码结束。1.3.2 数制转换数制转换运用的三种方法来实现此程序分别为：数组法、栈、递归法。分别用到的数据结构是一维数组；顺序栈；递归函数及数组相结合，其中1 / 71电文编码与译码数制转换数制转换用栈来实现比较方便、简洁，是利用栈的先进后出的特点，栈是 限定仅在表尾进行插入或删除操作的线性表。至于栈中每

31、个数据元素的具 体含义，在不同的情况下各不相同，它可以是一个数或者是一个符号等等。数制转换是比较适合用栈，其方便随时进行对余数进行压栈、弹栈等操 作，实现动态管理。根据此次课设程序以及栈的先进后出的特点可以进行 任意进制的转换。数制转换分为三个大模块，任意给出一个m进制数x, 实现：1求出此数x的10进制值；2实现对x向任意的一个非m进制的 数的转换；3至少用两种或两种以上的方法实现上述要求（用栈解决、用 数组解决、用递归方法解决）。最后实现二、八、十、十六进制之间的转 换。#/71电文编码与译码数制转换笫二章原理及运行环境2.1 数据结构理论2.1.1 电文的编码及译码数据结构理论哈夫曼树是

32、一种带权路径长度最短的二叉树。所谓树的带权路径长度, 就是树中所有的叶结点的权值乘上其到根节点的路径长度(若根结点为。 层，叶结点到根结点的路径长度为叶结点的长度)。树的带权路径长度记 为 wpl= ( wl*ll+w2*l2+w3*l3+.+wn*ln) , n 个权值 wi (i=l,2,.n)构成一棵n个结点的二叉树，相应的叶结点的路径长度为li(i=l,2,.n) o可以证明哈夫曼树的wpl是最小的。在数据通信中，需要将传送的文字转换成二进制的字符串，用0码 的不同排列来表示字符。例如，需传送的报文为“after data ear are art area,这里用到的字符集为“a, e

33、, r, t, f, d ”，各字母出 现的次数为8,4,5,3,1。现要求为这些字母设计编码。要求区别6个字 母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别 用 000、001、010、011、100、101 对 “a, e, r, t, f, d ”，进 行编码传送，当对方接受报文时再按照三位一分进行译码。显然编码长度 取决于文中不同字符的个数。若报文可能出现26个不同字符，则固定编 码长度为5.然而，传送报文时总是希望总长度尽可能短，再实际应用中， 各个字符的出现频度或使用次数是不相同的，如a,b,c的使用频率远远高 于x, y, z,自然会想到设计编码时，让使用频率高

34、的用短码，使用频率低的用长码，以优化整个报文编码。为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生 成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现 频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就 等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化 为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所 产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足 前缀编码的条件，又保证报文编码总长最短。实现哈夫曼编码的算法可分为两大部分，构造哈夫曼树和在哈夫曼树上 求叶结点的编码。在构造哈夫曼树的时候，可以设置一个数

35、组hufmtreetree来保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n 个结点的哈夫曼树共有2n-l个结点，所以结点总数m设为2*1,数据 元素的结构如下：weight ichild rchild flag parent 其中 weight 是保存结点的权值,ichild和rchild分别保存结点的左右孩子结点在数组 中的序号，从而建立起来结点之间的关系。flag是电文结束标志，取2。3/71电文编码与译码数制转换在求各字符的编码时，要从叶子结点回退到根结点，因此要设置一个parent,用来保存结点的双亲结点在hufmtree tree中。求哈夫曼编码，实质上就是从叶子结点开始,

36、沿结点的双亲回到根结点, 每回退一步，就走过了哈夫曼树中的一个分支，从而得到了一位哈夫曼编 码值，由于一个字符的哈夫曼编码时从根结点到相应叶子结点所经过的路 径上各分支所组成的0、1序列，因此先得到分支代码为所求编码的低位 码，后得到的分支代码为所求的高位码。在通信中，若将字符用哈夫曼编码形式发送出去，对方接受编码后，将 编码还原成字符的过程，称为哈夫曼译码。此程序分为四个模块，分别如下：构造哈夫曼树编码译码主函数2.1.2 数制转换数据结构理论此次课程设计数制转换，本小组用了三种方法来实现，其中尤栈的方法 最为简便，实用。故介绍栈的一些数据结构理论。栈是限定仅在表尾进行插入和删除操作的线性表

37、。因此，对栈来说，表 尾端有其特殊的含义，称为栈顶，相应地，表头端称为栈底。不含元素的 空表称为空栈。其中栈的基本操作除了有在栈顶进行插入或删除外，还有 栈的初始化、判空及取栈顶元素等。当然，在此程序的栈方法中我们仅用 到了栈的初始化、插入、删除操作来实现功能。数制转换应用的是栈的存储结构，栈又称后进先出的线性表，栈的存储 结构的特点：0 1、而岸栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈 中的位置。描述顺序栈的通常的习惯做法是以top=0表示空栈，鉴于c语 言中数组的下标约定是从0开始，则当以c作描述语言时，如此设

38、定会带 来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估 计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较 合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空 间不够使用时再逐段扩大。为此，可设定两个常量：stackcsl （存储空 间初始分配量）和stackzl （存储空间分配增量）。2、链栈，链栈是没有附加头结点的运算受限的单链表。栈顶指针 就是链表的头指针。栈的初始化操作为：按设定的初始分配量进行 第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向 栈底的位置，若base的值为null,则表明栈结构不存在。插入（压 栈）：向顺序栈

39、的栈顶插入一个元素。先判断栈是否已满，如果栈4/71电文编码与译码数制转换不满，就直接进行插入操作，否则就使用realloc函数为该顺序栈 再多分配增量stackzl个元素的存储空间。如果分配成功，则修 改栈顶指针top的位置和栈的容量stacksize,然后将元素x插入 在栈顶位置。删除(弹栈)：该算法用于从顺序栈的栈顶删除一个 元素，并将该元素的值通过x返回。算法进行时，首先判断栈是否 为空，如果为空则是错误操作，不空则将栈顶指针向下移动一个位 置。由于栈结构具有后进先出的固有性质，致使栈成为程序设计中的有用工 具。数制转换就是利用栈的后进先出的特性最简单的例子。在这个程序中, 栈操作的序

40、列是直线型的，即先一味地入栈，然后一味地出栈。此程序分为四个模块，分别如下：(1)主函数(2)数组法来实现任意进制数之间的随意转换(3)栈法来实现任意进制数之间的随意转换(4)递归法实现任意进制数之间的随意转换2.2运行环境在数据结构程序的运行环境为codeblocks中的console application 的 c 环境。2.2.1 打开方法开始f所有程序一codeblocks如图2-1所示。co deb lockshl codeblocks(s? uninstall co deblocks1 逗目图2-1打开codeblocks的方法2.2.2 打开codeblocks中的c环境其工作环

41、境如图2-2所示。a 匕 edi 5*orchbuld dtowj *x9nh took 内凶 sec% h?lpkrece*enprojwf synecemt mineiincl-aoe iincl5* pr&atf |*sllo wnrldan1; return 力o orkpk .ft msi & scurcnhijr4q gp-r图 2-2 codeblocks 中的 console application 的 c 环境codeblocks中的console application的c环境的材料如下：(l)codeblocks中的console application的c环境可以划分为

42、三块区 域。最左边的区域是工作区，最下面的区域是输出区，最右边的区域是编 辑区。编辑区用来对原文件进行编辑，现在的编辑区是天蓝色的，表示等待 源文件进行编辑。输出区的作用是对程序进行编译和链接后，如果程序有错误或警告, 则显示在输出区。工作区的作用是用来管理各种源程序文件，在它的管理下，可以有条 不紊的进行各种源文件的编辑。总体来讲，codeblocks中的console application的c环境运行环 境方便快捷。2.2.3 源程序的建立及编辑、连接建立c语言源程序文件。建立方法:选择codeblocks”一“console application c uproject title “

43、finish” 程序的编辑及编译。编辑完成后，选择菜单栏中的“build”即可对 程序进行编译。当输出区显示“。errors, 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标 志会出现在源文件可能出错的位置，当然有时提示位置不一定很准确。程序的执行。单击工具栏上的“深蓝色三角号按钮，即可执行刚编 写的程序，如图2-3所示。5/71电文编码与译码数制转换，4二, r 0 mm 1-rnx，c embm) ，工 raum c cecmrmim fe)/,1 , 3mm d3n 八 %wrwri v图2-3对源程序进行编写9/71第三章系统分析及

44、设计3.1 电文的编码及译码分析及设计3.1.1 系统的功能本次任务要求实现电文的编码及译码，根据需要可以进行如下操作：构 建哈夫曼树、编码、译码。其功能模块图如图3-1所示译码构造哈夫曼树图3-1电文的编码及译码功能模块图3.1.2 系统模块分析及其流程图构建哈夫曼树根据哈夫曼算法：若已知有n个叶子结点，则构造的哈夫曼树有2n-l 个结点曾先，将所用结点数据初始化，从n个结点中找出父结点为0;权值 最小的结点作为第n+1个结点的左子树，权值次小的结点作为其右子树， 并将两者的权值相加作为其父结点的权值。循环该操作。其功能图如图3-2 所示。其内部选择左右子树功能流程图如图3-3所示。定义变量

45、输入数据对数组初始化i电文编码与译码数制转换图3-2构建哈夫曼树功能流程图是图3-3选择左右子树功能流程图编码从哈夫曼树的叶子结点出发，找到其双亲，通过双亲的左右子树，可 以知道当前结点是父结点的左子树或右子树，若为左子树，生成代码0; 若为右子树，生成代码1,代码存放在数组中，然后把父结点作为出发点, 重复上述过程，知道树根为止。将生成的代码也存储在数组中。其功能流 程图如图3-4所示。电文编码与译码数制转换图3-4编码流程图(3)译码首先输入二进制代码串，存放在数组中。接下来，将代码及编码表比较, 如果为0,转向左子树；若为1,转向右子树，直到叶子结点结束，此时 输出叶子结点的数据域，即所

46、对应的字符。继续译码，直到代码结束。其 功能流程图如图3-5所示。图3-5译码功能流程图(4)主函数流程图把每个功能函数封装好以后，在主函数中调用，最后做一个菜单，选择 程序的功能。其流程图如图3-6所示。13 / 71定义变量菜单功能图3-6主函数流程图电文编码与译码数制转换3.2 数制转换分析及设计3.2.1 数制转换的功能本课程设计任务要求实现数制转换。把m进制的数x由键盘输入，然 后利用三种方法来实现任意进制之间的转换，在运用函数调用模块的连接, 输出转换成十进制的值和非m进制的值。其功能模块图如图3-7所示。图3-7功能模块流程图3.2.2 系统模块分析及其流程图1、数值转换的主函数

47、先选择转换方法，其次键盘输入要转换的m进制数和数值x,最后转 换成为想要的进制。（注：因为十进制在实际中实用广泛，所以单独做了 一个函数getdex,把十进制转换成为其他进制，并且在三种方法中调用此 函数，就可以把m进制所对应的十进制输出）其流程图如图3-8所示。15 7 71电文编码与译码数制转换图3-8主函数流程图2、数组法实现功能先用键盘输入数据，再把数据存放在一维数组中，字符数组char hexnum = 0123456789abcdefm; char a1000=0;输入要转化 成进制数q,用取余数的方法，把余数存储在数组a1000,实现语句为 while语句，倒序输出余数，定义变量

48、m,存储数组中余数的元素的个 数，用for循环来输出。其流程图如图3-9所示。# 7 71电文编码与译码数制转换图3-9数组法功能流程图3、栈实现功能栈的方式实现十进制转化为其他进制数。定义一个结构体，建立一个 空栈，进行计算之后对余数进行入栈、出栈等操作c其功能流程图如图3-10 所示。电文编码与译码数制转换图3-10栈法功能流程图4、递归法功能递归的方法把十进制转换成其他进制数。定义一个递归函数用switch 语句判断转换成的四种情况，case 2、case 8 case 10 case 160以十 进制为例：输入十进制数n,判断是否vo,如果是则putcharc-),然后 if(n/10

49、)判断商是否为0,再执行prind_d(n/10,10);!/3,直到商为0 时停止，case 2、case 8和case 16及case 10的思路一样。但是十六 进制数不太一样要把余数保存在一个数组中，char ch=0123456789abcdef”;然后倒序输出。其功能流程图如图3-11 所示。图3-11递归法功能流程图第四章系统功能实现4.1电文的编码及译码功能实现 4.1.1定义主函数主函数是程序的入口，采用模块化设计，实现开始的界面输入，并以此 调用各个函数，源代码如下：void main（）printf（n树进行电文译码及编码 vvvvvnrt）;printf（本转换程序仅适用

50、于电文总共使用%d个字符的编码n”,n）;printf（所有输入文本都以2为输入结尾标识,用于判读结束壮）；hufmtree treem; 使用结构体数组存储huffman树（森林）codetype coden;int i,j；/循环变量huffman（tree）;/建立哈夫曼树huffmancode（code,tree）;/根据哈夫曼树求出哈夫曼编码printf（n每个字符的哈夫曼编码如下for(i=0;in;i+)printf(%c: ”,codei.ch);/输出叶子结点指代字符for(j=codei .start;j自然语言文本转码区19 / 71电文编码与译码数制转换character(code);依次读入自然