电文的编码与译码-数制转换

1、沈沈 阳阳 工工 程程 学学 院院课 程 设 计设计题目：设计题目：电文的编码与译码、数制转换电文的编码与译码、数制转换系系 别别 信息学院信息学院 班级班级 计本计本 151151 学生姓名学生姓名 郭景辉郭景辉 程年程年 杨满杨满 李成宇李成宇 学学 号号 1818 1717 2323 2222 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 起止日期：起止日期：20162016 年年 6 6 月月 1313 日起日起至至 20162016 年年 6 6 月月 2424 日止日止沈 阳 工 程 学 院课程设计任务书 课程设计题目：课程设计题目： 电文的编码

2、与译码电文的编码与译码 系系 别别 信息学院信息学院 班班 级级 计本计本 151151 学生姓名学生姓名 杨满杨满 李成宇李成宇 学学 号号 2323 2222 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 课程设计进行地点：课程设计进行地点： 实训实训 F F 座座 任任 务务 下下 达达 时时 间：间： 20162016 年年 6 6 月月 1212 日日起止日期：起止日期：20162016 年年 6 6 月月 1313 日起日起至至 20162016 年年 6 6 月月 2424 日止日止教教研研室室主主任任 张欣张欣 2 20 01 16 6 年年

3、 6 6 月月 1 11 1 日日批批准准一、问题描述在当今社会的一些领域，电文仍然被应用，编写一个电文编码和译码还是有必要的，该设计是对输入的一串电文字符实现哈夫曼编码，在对哈夫曼编码生成的代码串进行译码，输出电文字符串。二、课程设计主要内容及要求1.构造哈夫曼树2.编码3.译码三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线

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

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

6、设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C 语言版）习题与解析.北京:清华大学出版社.2002.04沈沈 阳阳 工工 程程 学学 院院课 程 设 计设计题目：设计题目： 电文的编码与译码、数制转换电文的编码与译码、数制转换系系 别别 信息工程系信息工程系 班级班级 计本计本 151151 学生姓名学生姓名 郭景辉郭景辉 程年程年 杨满杨满 李成宇李成宇 学学 号号 1818 1717 2323 2222 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师 起止日期：起止日期：20162016 年年 6 6 月月 1313 日起日起至至 20

7、162016 年年 6 6 月月 2424 日止日止沈 阳 工 程 学 院课程设计任务书课程设计题目：课程设计题目： 数制转换数制转换 系系 别别 信息工程系信息工程系 班级班级 计本计本 151151 学生姓名学生姓名 郭景辉郭景辉 程年程年 学号学号 1818 1717 指导教师指导教师 姜柳姜柳 、吕海华、吕海华 职称职称 副教授、讲师副教授、讲师课程设计进行地点：课程设计进行地点： 实训实训 F F 座座 任任 务务 下下 达达 时时 间：间： 20162016 年年 6 6 月月 1212 日日起止日期：起止日期：20162016 年年 6 6 月月 1313 日起日起至至 2016

8、2016 年年 6 6 月月 2424 日止日止教教研研室室主主任任 张欣张欣 2 20 01 16 6 年年 6 6 月月 1 11 1 日日批批准准一、课程设计的原始资料及依据我们一把情况下所见到的数据都是十进制的，但是数不仅仅是以十进制的形式存在，还有二进制数、八进制数、十六进制数等，对于这些不同进制的数，我们无法对他们进行中和运算，因此就要求我们能够将不同进制的数转换为相同的进制进行运算，这样就方便了不同数制之间的综合运算。二、课程设计主要内容及要求基本要求：1、在任意不同的两种数制之间可以相互转换2、数制之间的转换在设计程序时要详细说明其转换的基本原理3、要使用栈、数组分别实现该功能

9、4、程序代码逻辑思路清晰，添加适当注释，便于理解5、出设计者本人外其他人运行本程序都能够得到结果，不会产生理解上的错误导致运行结果出错三、对课程设计说明书撰写内容、格式、字数的要求1课程设计说明书是体现和总结课程设计成果的载体，主要内容包括：设计题目、设计目的、设备器材、设计原理及内容、设计步骤、遇到的问题及解决方法、设计总结、设计小组评语、参考文献等。一般不应少于 3000 字。2在适当位置配合相应的实验原理图、数据通路图、微程序流程图、实验接线图、微指令代码表等图表进行说明。应做到文理通顺，内容正确完整，书写工整，装订整齐。3设计总结部分主要写本人完成工作简介以及自己的设计体会，包括通过课

10、程设计学到了什么，哪里遇到了困难，解决的办法以及今后的目标。设计小组评语处注明设计组编号、设计组组长、设计组成员，并由设计组组长给出评语。4课程设计说明书手写或打印均可。手写要用学校统一的课程设计用纸，用黑或蓝黑墨水工整书写；打印时采用 A4 纸，页边距均为 20mm，正文采用宋体小四号字，行间距 18 磅。文中大标题采用黑体小三号字，一级节标题采用黑体四号字，二级节标题采用黑体小四号字，表题与图题采用宋体五号字。5课程设计说明书装订顺序为：封面、任务书、成绩评定表、目录、正文、参考文献。四、设计完成后应提交成果的种类、数量、质量等方面的要求1完成“任务书”中指定的操作功能，运行稳定。2课程设

11、计说明书。五、时间进度安排顺序阶段日期计 划 完 成 内 容备注1第 1 天阅读资料2第 23 天系统分析设计3第 48 天程序编制、调试及运行4第 9 天成绩评定5第 10 天撰写课程设计说明书六、主要参考资料（文献）1严蔚敏 吴伟民.数据结构（C 语言版）. 北京:清华大学出版社.20072谭浩强.C 程序设计.北京:清华大学出版社.1999.123滕国文.数据结构课程设计.北京:清华大学出版社.2010.094苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.055李春葆.数据结构（C 语言版）习题与解析.北京:清华大学出版社.2002.04沈沈 阳阳 工工 程程 学

12、学 院院数据结构课程设计成绩评定表数据结构课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本151151 学生姓名：学生姓名： 郭景辉郭景辉 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，

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

14、35 54 43 32 2评阅教师评审成绩评阅教师评审成绩（加权分合计乘以（加权分合计乘以 4 4）分分加权分合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘

15、以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈沈 阳阳 工工 程程 学学 院院数据结构课程设计成绩评定表数据结构课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本151151 学生姓名：学生姓名： 程年程年 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.2

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

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

18、；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈沈 阳阳 工工 程程 学学 院院数据结构课程设计成绩评定表数据结构课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：班级： 计本计本151151 学生姓名：学生姓名： 杨满杨满 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查

19、阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审成绩指导教师评审成绩（加权分合计乘以（加权分合计乘以 8 8） 分分加权分合计加权分合计指指 导导 教教 师师 签签 名：名： 年年 月月 日日评评 阅阅 教教 师师

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

21、准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计计 总总 评评 成成 绩绩分分沈沈 阳阳 工工 程程 学学 院院数据结构课程设计成绩评定表数据结构课程设计成绩评定表系（部）：系（部）： 信息工程系信息工程系 班级：

22、班级： 计本计本151151 学生姓名：学生姓名： 李成宇李成宇 指指 导导 教教 师师 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分调研论证能独立查阅文献,收集资料；能制定课程设计方案和日程安排。0.15 54 43 32 2工作能力态度工作态度认真，遵守纪律，出勤情况是否良好，能够独立完成设计工作， 0.25 54 43 32 2工作量按期圆满完成规定的设计任务，工作量饱满，难度适宜。0.25 54 43 32 2说明书的质量说明书立论正确，论述充分，结论严谨合理，文字通顺，技术用语准确，符号统一，编号齐全，图表完备，书写工整规范。0.55 54 43 32 2指导教师评审

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

24、合计加权分合计评评 阅阅 教教 师师 签签 名：名： 年年 月月 日日答答 辩辩 小小 组组 评评 审审 意意 见见评价内容具 体 要 求权重评 分加权分学生汇报汇报准备充分，思路清晰；语言表达准确，概念清楚，论点正确，有层次，有重点，基本上反映了所完成任务的全部内容；时间符合要求。0.55 54 43 32 2答 辩思路清晰；回答问题有理论依据，基本概念清楚；主要问题回答准确，深入，有说服力。0.55 54 43 32 2答辩小组评审成绩答辩小组评审成绩（加权分合计乘以（加权分合计乘以 8 8）分分加权分合计加权分合计答辩小组教师签名：答辩小组教师签名： 年年 月月 日日课课 程程 设设 计

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

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

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

28、成为十进制数，在每种方法中调用即可。此次课设利用模块化设计思想，主要实现的功能有：给定一个进制数 x，通过三种方法，随意进行进制转换，最后得出想要的进制数。程序刚开始时，进行的语言描述可能有些不妥，但经过讨论和修正以及老师耐心的指导使数制转换这个程序不断完善。最后，感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲。关键词关键词 编码，译码，数制转换，哈夫曼树沈阳工程学院课程设计报告 目录目录摘摘 要要.I I第一章第一章 问题分析问题分析.1 11.1 引言 .11.2 背景.11.3 分析 .21.3.1 电文的编码与译码 .21.3.2 数制转换 .2第二章第二章 原理与运行环境原理与

29、运行环境.3 32.1 数据结构理论 .32.1.1 电文的编码与译码数据结构理论 .32.1.2 数制转换数据结构理论 .42.2 运行环境 .52.2.1 打开方法.52.2.2 打开 CodeBlocks 中的 C 环境 .52.2.3 源程序的建立与编辑、连接.6第三章第三章 系统分析与设计系统分析与设计.7 73.1 电文的编码与译码分析与设计 .73.1.1 系统的功能 .73.1.2 系统模块分析及其流程图.7 3.2 数制转换分析与设计.123.2.1 数制转换的功能 .123.2.2 系统模块分析及其流程图 .12第四章第四章 系统功能实现系统功能实现.16164.1 电文的

30、编码与译码功能实现 .164.1.1 定义主函数 .164.1.2 定义存储结构 .174.1.3 构造哈夫曼树.174.1.4 编码.194.2 数制转换功能实现 .224.2.1 定义主函数 .224.2.2 定义存储结构 .234.2.3 数组法功能 .234.2.4 栈方法功能 .254.2.5 递归法功能.27结论结论.3030致谢致谢.3131参考文献参考文献.3232沈阳工程学院课程设计报告 第一章 问题分析0第一章 问题分析1.1 引言数据结构的教学要求是：学会分析研究计算机加工的数据结构的特征，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时

31、间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。在学习中，先要学习程序设计课程的目的掌握设计程序的思路，学习会用计算机语言编写程序，以实现所需要处理的任务。要正确处理算法与语法的关系，算法是程序的核心、是灵魂，语法是外壳、是工具。不应把学习重点放在语法规则上，语法是重要的，不掌握语法规则就无法编写出正确的程序。一定要把重点放在解题的思路上，通过思考，和大量的阅读，来构造一个完整的程序。请记住：重要的是学会编程，而不是背语法。程序设计是为了锻炼我们的实际动手能力，在一定程度上，又增加了我们的各方面的知识，特别

32、是一些联系实际的课程设计，它的完成需要自己平时积累的大量知识、并且需要勤于思考的能力和无限的激情。本次课程设计主要是学习程序设计的方法，进行程序设计的基本训练，大多数的学生应该把精力放在最基本，最常用的内容上，学好基本功。通过本次课程设计，相信我们一定能加强对数据结构这门课程的学习，尤其在动手实践上会有很大的进步。1.2 背景在当今信息爆炸时代如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用

33、一张特殊的编码表将源字符，例如某文件中的一个符号，进行编码。这张编码表的特殊之处在于它是根据每一个源字符出现的估算概率而建立起来的，出现概率高的字符使用较短的编码；反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径对路径上的各分支约定，指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代

34、码时可以编译成字符串。沈阳工程学院课程设计报告 第一章 问题分析11.31.3 分析分析1.3.1 电文的编码与译码电文的编码与译码电文的编码与译码运用的是建立哈夫曼树的表示方法，三叉链表作为存储结构。将26个英文字母和逗号句号空格作为哈夫曼树的结点，由键盘来输入对应的权值，生成一棵哈夫曼树，再求出每个结点的哈夫曼编码。这样一来，就可以实现此程序的功能。电文的编码与译码分为三个大部分，分别为哈夫曼树的建立及哈夫曼编码的生成，利用生成的哈夫曼编码进行语言的编码，最后还可进行代码的译码。哈夫曼树的建立的基本思想:赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有 n 棵只含有根结点的二叉树。算法

35、的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行 n1 次合并，所以共产生 n1 个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的哈夫曼树中一共有 2n1 个结点，其中 n 个结点是初始森林的 n 个孤立结点。并且哈夫曼树中没有度数为 1 的分支结点。我们可以利用一个大小为 2n-1 的一维数组来存储哈夫曼树中的结点。编码。基本思想：从哈夫曼树的叶子结点出发，通过双亲找到其双亲结点，通过左右子树，可知该结点是其父结点的左分支或者是右分支，若是左分支，生成代码 0，若是右分支，生成代码 1，代码存

36、放在指定数组中，然后把其父结点作为出发点，重复上述过程，直到找到树根为止。但是，这样生成的代码序列与要求的编码次序相反，为了得到正确的代码，把最先生成的代码存放在数组最后一个元素中，再次生成的代码放在数组倒数第二个个元素中，依次类推，用变量指示编码在数组中的起始位置。这样编码过程就完成了。译码。基本思想：首先输入二进制代码串，存放在数组 char bmaxsize中并输入一个结束标志2，接下来，将代码与编码表比较，如果为 0，转向左子树；若为 1，转向右子树，直到叶结点结束，此时输出叶结点的数据域，即所对应的字符。继续译码，直到代码结束。1.3.2 数制转换数制转换运用的三种方法来实现此程序分

37、别为：数组法、栈、递归法。分别用到的数据结构是一维数组；顺序栈；递归函数与数组相结合，其中数制转换用栈来实现比较方便、简洁，是利用栈的先进后出的特点，栈是限定仅在表尾进行插入或删除操作的线性表。至于栈中每个数据元素的具体含义，在不同的情况下各不相同，它可以是一个数或者是一个符号等等。数制转换是比较适合用栈，其方便随时进行对余数进行压栈、弹栈等操作，实现动态管理。根据此次课设程序以及栈的先进后出的特点可以进行任意进制的转换。数制转换分为三个大模块，任意给出一个 M 进制数 x，实现：1 求出此数 x 的 10 进制值；2 实现对 x 向任意的一个非 M 进制的数的转换；3 至少用两种或两种以上的

38、方法实现上述要求（用栈解决、用数组解决、用递归方法解决）。最后实现二、八、十、十六进制之间的转换。沈阳工程学院课程设计报告 第二章 原理与运行环境2第二章第二章 原理与运行环境原理与运行环境2.1 数据结构理论2.1.1 电文的编码与译码数据结构理论哈夫曼树是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根节点的路径长度（若根结点为 0 层，叶结点到根结点的路径长度为叶结点的长度）。树的带权路径长度记为 WPL=（W1*L1+W2*L2+W3*L3+.+Wn*Ln），N 个权值 Wi（i=1,2,.n）构成一棵 N 个结点的二叉树，相应的叶结点的路径长度

39、为Li(i=1,2,.n）。可以证明哈夫曼树的 WPL 是最小的。在数据通信中，需要将传送的文字转换成二进制的字符串，用 0,1 码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A, E, R，T， F，D ”，各字母出现的次数为8,4,5,3,1,1。现要求为这些字母设计编码。要求区别 6 个字母，最简单的二进制编码方式是等长编码，固定采用 3 位二进制，可分别用000、001、010、011、100、101 对“A, E, R，T， F，D ”，进行编码传送，当对方接受报文时再按照三位一分进行译码。显然编码长度取决

40、于文中不同字符的个数。若报文可能出现 26 个不同字符，则固定编码长度为 5.然而，传送报文时总是希望总长度尽可能短，再实际应用中，各个字符的出现频度或使用次数是不相同的，如 A,B,C 的使用频率远远高于X，Y，Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符

41、出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。实现哈夫曼编码的算法可分为两大部分，构造哈夫曼树和在哈夫曼树上求叶结点的编码。在构造哈夫曼树的时候，可以设置一个数组 hufmtree tree来保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有 n 个结点的哈夫曼树共有 2n-1 个结点，所以结点总数 m设为 2n-1，数据元素的结构如下：weight lchild rchild flag parent 其中 weight是保存结点的权值，lchild 和 rchild 分别保存结点的左右孩子结点在数组中的序号，从

42、而建立起来结点之间的关系。flag 是电文结束标志，取2。在求各字符的编码时，要从叶子结点回退到根结点，因此要设置一个 parent，用来保存结点的双亲结点在 hufmtree tree中。求哈夫曼编码，实质上就是从叶子结点开始，沿结点的双亲回到根结点，每回退一步，就走过了哈夫曼树中的一个分支，从而得到了一位哈夫曼编码值，由于一个字符的哈夫曼编码时从根结点到相应叶子结点所经过的路径上各分支所组成的 0、1 序列，因此先得到分支代码为所求编码的低位码，后得到的分支代码为所求的高位码。沈阳工程学院课程设计报告 第二章 原理与运行环境3在通信中，若将字符用哈夫曼编码形式发送出去，对方接受编码后，将编

43、码还原成字符的过程，称为哈夫曼译码。此程序分为四个模块，分别如下：构造哈夫曼树编码译码主函数2.1.22.1.2 数制转换数据结构理论数制转换数据结构理论此次课程设计数制转换，本小组用了三种方法来实现，其中尤栈的方法最为简便，实用。故介绍栈的一些数据结构理论。栈是限定仅在表尾进行插入和删除操作的线性表。因此，对栈来说，表尾端有其特殊的含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。其中栈的基本操作除了有在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。当然，在此程序的栈方法中我们仅用到了栈的初始化、插入、删除操作来实现功能。数制转换应用的是栈的存储结构，栈又称后进先出

44、的线性表，栈的存储结构的特点： 1、顺序栈，即栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。描述顺序栈的通常的习惯做法是以 top=0 表示空栈，鉴于 C 语言中数组的下标约定是从 0 开始，则当以 C 作描述语言时，如此设定会带来很大不便；另一方面，由于栈在使用过程中所需最大空间的大小很难估计，因此，一般来说，在初始化设空栈时不应限定栈的最大容量。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。为此，可设定两个常量：STACKCSL（存储空间初始分配量）和 STAC

45、KZL（存储空间分配增量）。2、链栈，链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。栈的初始化操作为：按设定的初始分配量进行第一次存储分配，base 可称为栈底指针，在顺序栈中，它始终指向栈底的位置，若base 的值为 NULL，则表明栈结构不存在。插入（压栈）：向顺序栈的栈顶插入一个元素。先判断栈是否已满，如果栈不满，就直接进行插入操作，否则就使用realloc 函数为该顺序栈再多分配增量 STACKZL 个元素的存储空间。如果分配成功，则修改栈顶指针top 的位置和栈的容量 stacksize，然后将元素 x 插入在栈顶位置。删除（弹栈）：该算法用于从顺序栈的栈顶删除一

46、个元素，并将该元素的值通过x 返回。算法进行时，首先判断栈是否为空，如果为空则是错误操作，不空则将栈顶指针向下移动一个位置。由于栈结构具有后进先出的固有性质，致使栈成为程序设计中的有用工具。数制转换就是利用栈的后进先出的特性最简单的例子。在这个程序中，栈操作的序列是直线型的，即先一味地入栈，然后一味地出栈。此程序分为四个模块，分别如下：（1）主函数（2）数组法来实现任意进制数之间的随意转换（3）栈法来实现任意进制数之间的随意转换（4）递归法实现任意进制数之间的随意转换沈阳工程学院课程设计报告 第二章 原理与运行环境42.2 运行环境在数据结构程序的运行环境为 CodeBlocks 中的 Con

47、sole application 的 C 环境。2.2.1 打开方法开始所有程序CodeBlocks 如图 2-1 所示。图 2-1 打开CodeBlocks的方法2.2.2 打开 CodeBlocks 中的 C 环境其工作环境如图 2-2 所示。图 2-2 CodeBlocks 中的 Console application 的 C 环境 CodeBlocks 中的 Console application 的 C 环境的材料如下：CodeBlocks 中的 Console application 的 C 环境可以划分为三块区域。最左边的区域是工作区，最下面的区域是输出区，最右边的区域是编辑区。

48、编辑区用来对原文件进行编辑，现在的编辑区是天蓝色的，表示等待源文件进行编辑。输出区的作用是对程序进行编译和链接后，如果程序有错误或警告，则显示在输出区。沈阳工程学院课程设计报告 第二章 原理与运行环境5工作区的作用是用来管理各种源程序文件，在它的管理下，可以有条不紊的进行各种源文件的编辑。 总体来讲，CodeBlocks 中的 Console application 的 C 环境运行环境方便快捷。2.2.3 源程序的建立与编辑、连接建立 C 语言源程序文件。建立方法：选择“CodeBlocks” “Console application” “C” “Project title” “Finish

49、”。程序的编辑与编译。编辑完成后，选择菜单栏中的“build”即可对程序进行编译。当输出区显示“0 errors， 0 warnings ”时表示没有错误和警告，反之，则会按序号列出错误和警告。双击错误或警告，编辑标志会出现在源文件可能出错的位置，当然有时提示位置不一定很准确。程序的执行。单击工具栏上的“深蓝色三角号”按钮，即可执行刚编写的程序，如图2-3 所示。图 2-3 对源程序进行编写沈阳工程学院课程设计报告 第三章 系统分析与设计6第三章 系统分析与设计3.1 电文的编码与译码分析与设计3.1.1 系统的功能本次任务要求实现电文的编码与译码，根据需要可以进行如下操作：构建哈夫曼树、编码

50、、译码。其功能模块图如图 3-1 所示图 3-1 电文的编码与译码功能模块图3.1.2 系统模块分析及其流程图 构建哈夫曼树 根据哈夫曼算法：若已知有 n 个叶子结点，则构造的哈夫曼树有 2n-1 个结点 首先，将所用结点数据初始化，从 n 个结点中找出父结点为 0；权值最小的结点作为第 n+1 个结点的左子树，权值次小的结点作为其右子树，并将两者的权值相加作为其父结点的权值。循环该操作。其功能图如图 3-2 所示。其内部选择左右子树功能流程图如图 3-3 所示。开 始定 义 变 量输 入 数 据电文的编码与译码构造哈夫曼树编 码译 码沈阳工程学院课程设计报告 第三章 系统分析与设计7否 是图

51、 3-2 构建哈夫曼树功能流程图 否 是 对 数 组 初 始 化键 盘 赋 初 值有 该 结 点选择左右子树将左右子树的权值相加，作为父结点的权值结 束开 始比较所有结点父结点 0结点权值最小，作为左子树沈阳工程学院课程设计报告 第三章 系统分析与设计8图 3-3 选择左右子树功能流程图 编码 从哈夫曼树的叶子结点出发，找到其双亲，通过双亲的左右子树，可以知道当前结点是父结点的左子树或右子树，若为左子树，生成代码 0；若为右子树，生成代码 1，代码存放在数组中，然后把父结点作为出发点，重复上述过程，知道树根为止。将生成的代码也存储在数组中。其功能流程图如图 3-4 所示。 否 是 是结点权值次

52、小，作为右子树结 束开 始定 义 变 量结 点 赋 初 值是否为叶结点？该结点是否为父结点的左子树？将 0 倒序放入存放该结点编码的数组结点树增加依次输出各结点及其编码将 1 倒序放入存放该结点编码的数组中沈阳工程学院课程设计报告 第三章 系统分析与设计9图 3-4 编码流程图（3）译码 首先输入二进制代码串，存放在数组中。接下来，将代码与编码表比较，如果为 0，转向左子树；若为 1，转向右子树，直到叶子结点结束，此时输出叶子结点的数据域，即所对应的字符。继续译码，直到代码结束。其功能流程图如图 3-5 所示。 是 否 否 是 否 是 图 3-5 译码功能流程图结 束开 始定 义 变 量输入电

53、文字符结束结点的左子树不为 0字符为 0将其存为左子树计数增加结 束将其存为右子树输出结点数据结点置为根结点沈阳工程学院课程设计报告 第三章 系统分析与设计10 （4）主函数流程图把每个功能函数封装好以后，在主函数中调用，最后做一个菜单，选择程序的功能。其流程图如图 3-6 所示。 否 是图 3-6 主函数流程图开 始定 义 变 量输入功能及代号键盘输入执行的功能代号菜单功能是否退出结 束沈阳工程学院课程设计报告 第三章 系统分析与设计113.23.2 数制转换分析与设计数制转换分析与设计3.2.1 数制转换的功能本课程设计任务要求实现数制转换。把 M 进制的数 x 由键盘输入，然后利用三种方

54、法来实现任意进制之间的转换，在运用函数调用模块的连接，输出转换成十进制的值和非 M 进制的值。其功能模块图如图 3-7 所示。 图 3-7 功能模块流程图3.2.2 系统模块分析及其流程图1、数值转换的主函数先选择转换方法，其次键盘输入要转换的 M 进制数和数值 x，最后转换成为想要的进制。（注：因为十进制在实际中实用广泛，所以单独做了一个函数 getdex，把十进制转换成为其他进制，并且在三种方法中调用此函数，就可以把 M 进制所对应的十进制输出）其流程图如图 3-8 所示。 是 否 开 始数制转换数组法实现栈法实现递归法实现二、八、十、十六进制之间随意转换二、八、十、十六进制之间随意转换二

55、、八、十、十六进制之间随意转换数组法 沈阳工程学院课程设计报告 第三章 系统分析与设计12 是 否 是 否 图 3-8 主函数流程图 2、数组法实现功能 先用键盘输入数据，再把数据存放在一维数组中，字符数组 char HexNum = 0123456789ABCDEF; char a1000=0; 输入要转化成进制数 q,用取余数的方法,把余数存储在数组 a1000,实现语句为 while 语句，倒序输出余数，定义变量 m，存储数组 a中余数的元素的个数，用 for 循环来输出。其流程图如图 3-9 所示。 结 束开始定义两个字符数组输入数据想要转换成为的进制栈法递归法实现数制转换沈阳工程学院

56、课程设计报告 第三章 系统分析与设计13图 3-9 数组法功能流程图 3、栈实现功能 栈的方式实现十进制转化为其他进制数。定义一个结构体，建立一个空栈，进行计算之后对余数进行入栈、出栈等操作。其功能流程图如图 3-10 所示。图 3-10 栈法功能流程图开始输入数据 M 进制及 x对应的十进制为用取余的方法，并把余数存放在 char a中使用 for 循环，倒序输出所有余数结束输入对应的十进制数请输入想要转换成为的进制数 N转换成的 N=%d 进制数为结束沈阳工程学院课程设计报告 第三章 系统分析与设计14 4、递归法功能 递归的方法把十进制转换成其他进制数。定义一个递归函数用 switch

57、语句判断转换成的四种情况，case 2、case 8、case 10、case 16。以十进制为例：输入十进制数 n，判断是否Huffman树进行电文译码与编码每个字符的哈夫曼编码如下n); for(i=0;in;i+) printf(%c: ,codei.ch);/输出叶子结点指代字符 for(j=codei.start;j自然语言文本转码区Huffman编码电文译码为自然语言区nn);沈阳工程学院课程设计报告 第四章 系统功能实现16 decode(tree);/依次读入二进制数电文，根据哈夫曼树译码 break; case 3: Lbool=0; break; default: brea

58、k; 4.1.24.1.2 定义存储结构定义存储结构引用头文件和定义哈夫曼树结构。具体代码如下： #include #define n 29 /叶子数目(设计为适用26个英文字母加空格逗号点号的叶子节点数) #define m (2*n-1) /结点总数 #define maxval 10000.0 /maxval是float类型数据的最大值 #define maxsize 100 /哈夫曼编码的最大位数 typedef struct char ch; /记录叶子节点的指代字符 float weight; /权值(记录该叶子节点的使用频率或频数) int lchild,rchild,paren

59、t; /左右孩子和双亲节点 hufmtree; typedef struct char bitsn; /哈夫曼编码串位串 int start; /编码在位串中的起始位置 char ch; /字符(当前叶子节点指代字符)codetype; 4.1.34.1.3 构造哈夫曼树构造哈夫曼树 根据哈夫曼算法：若已知有n个叶子结点，则构造的哈夫曼树有2n-1个结点。 首先，将所有数据初始化，从n个结点中找出父结点为0，权值最小的结点作为第n+1个结点的左子树，权值次小的结点作为其右子树，并将两者的权值相加得父结点的权值。循环该操作。具体代码如下： void huffman(hufmtree tree)

60、/建立哈夫曼树 int i,j,p1,p2;/p1,p2用于分别记住每次合并时权值最小和次小的两个根结点的下标 float small1,small2,f; /f用于接收键盘输入的权值 char c;沈阳工程学院课程设计报告 第四章 系统功能实现17 for(i=0;i电文使用的各字符编码区nn); for(i=0;in;i+) /读入前n个结点的字符及权值 printf(第%2d个字符和对应权值(空格分隔):,i+1); scanf(%c %f,&c,&f); getchar(); treei.ch=c; treei.weight=f; /对二叉树集合(森林)中每一棵树赋值,记录下字符与权值