电文的编码和译码

1、 数据结构课程设计报告课程设计题目：电文的编码和译码姓 名：*专 业：信息管理与信息系统学 号：*班 级：*指导教师：* 2014年6月东华理工大学课程设计评分表学生姓名：* 班级：* 学号：*课程设计题目：电文的编码与译码项目内容满分实 评选题能结合所学课程知识、有一定的能力训练。符合选题要求 （5人一题）10工作量适中，难易度合理10能力水平能熟练应用所学知识，有一定查阅文献及运用文献资料能力10理论依据充分，数据准确，公式推导正确10能应用计算机软件进行编程、资料搜集录入、加工、排版、制图等10能体现创造性思维，或有独特见解10成果质量总体设计正确、合理，各项技术指标符合要求。10说明书

2、综述简练完整，概念清楚、立论正确、技术用语准确、结论严谨合理；分析处理科学、条理分明、语言流畅、结构严谨、版面清晰10设计说明书栏目齐全、合理，符号统一、编号齐全。格式、绘图、表格、插图等规范准确，符合国家标准10有一定篇幅，字符数不少于500010总 分100指导教师评语： 指导教师签名： 年 月 日一、需求分析1二设计内容11）问题描述12）设计要求13)分析与实现14）功能要求25）概要设计2三. 调试61）建立哈夫曼树62）编码73）译码8四. 实验心得体会8一、需求分析 当今社会的一些领域，电文仍然被应用着，编写一个电文编码和译码系统还是有必要的，哈夫曼编码是广泛用于数据文件压缩的十

3、分有效的编码方法。其压缩通常在20%90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条分支上路径上的“0”或“1”的序列作为各个叶子对应的字符的编码，这就是哈夫曼编码。该设计是对输入的一串电文字符实现哈夫曼编码，或对哈夫曼编码生成的代码串进行译码，输出电文字符串。二设计内容1）问题描述 从键盘接收一串电文字符，输出对应的哈夫曼编码。同时能翻译有哈夫曼

4、编码生成的代码串，输出对应的电文字符串。2）设计要求（1）构造一颗Huffman树。（2）实现Huffman编码，并用Huffman编码生成的代码串进行译码。（3）程序中字符和权值时可变的，实现程序的灵活性。3)分析与实现 在电报通信中，电文是以二进制代码传送的。在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码转化为对应的字符序列，即译码。我们知道，字符集中的字符被使用的频率是非均匀的。在传送电文时，要想使电文总长尽可能短，就需要让使用频率高的编码长度尽可能的短。因此，若对某字符集进行不等长编码的设计，则要求任意一个字符的编码都不是其他字符编码的前缀，这种

5、编码称做前缀编码。由哈夫曼树求得的编码是最优前缀码，也叫做Huffman编码。给出字符集和各个字符的概率分布，构造哈夫曼树，将哈夫曼树种每个分支点的左分支标为0，右分支标为1，将根到每个叶子路径上的标号连起来，就是该叶子所代表字符的编码。4）功能要求（1）初始化，键盘输入字符集大小你，n个字符和n个权值，建立哈夫曼树。（2）编码，利用建好的哈夫曼树生成Huffman编码。（3）输出编码。（4）译码功能。（5）字符频度如下：字符ABCDEFGHIJKLM频度18664132232103211547571232字符NOPQRSTUVWXYZ频度205763151485180238181165）概要

6、设计(1)关系以及功能 程序由以下模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能： avoid main() b. int HuffmanCreate(HuffNode * ht) /生成huffman树/ cvoid Encoding(HuffNode ht,HuffCode hcd,int n) /编码部分/ d. void Decoding(HuffNode ht,HuffCode hcd,int n) /译码部分/main（）其流程图如下:输入待编码字符函数编码函数译码函数初始化函数(2) 主要模块程序流程图a. 函数流程图 结束 哈夫曼译码 哈夫曼编码 建立哈夫曼树

7、统计字符种类及频率字符总数n 打开文件？ 开始 否 是 流程图解释： 该图比较简单，主要是调用各个函数模块，首先打开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。 b. 构造哈夫曼树 开始 第i个节点权值 i=n？ 否 是 第i个根节点 i=2*n-1 否 是 创建哈夫曼树 输出字符统计情况 i=n？否 是 结束 流程图注释： 该图是表示构造哈夫曼树的过程。首先输入n个叶结点的权值，当i=n 是循环结束。然后进行哈夫曼树的构建，当i=2*n-1是循环结束。最后输出所得到的字符统计情况。c.

8、 哈夫曼编码 开始 d.start=n+1，cd-d.start=0htf.left=c?是 否d.cd-d.start=1d.cd-d.start=0i<=n? 是 否 结束流程图解释： 该流程图表示哈夫曼编码情况。首先初始化，d.start=n+1,d.cdd.start=0；然后进行编码，即当htf.left=c时，d.cdd.start=0，当htf.left!=c时，d.cd-d.start=1。这个编码循环一直到i=n时结束。（3）相关函数解释 a. 生成huffman树 【 int HuffmanCreate(HuffNode * ht) 】 哈夫曼树的建立由哈夫曼算法的定

9、义可知，初始森林中共有n棵只含有根节点的二叉树。然后将当前森林中的两棵根节点权值最小的二叉树htp1和p2（用p1和p2指示这两个节点在数组中的位置），合并成一棵新的二叉树hti，使得htp1和htp2成为hti的左右孩子，而且hti的权值为htp1和htp2的权值之和。每合并一次，森林中就减少一棵树，产生一个新节点。显然要运行n-1次合并，所以共产生n-1个新节点。它们都是具有两个孩子的分支节点。由此可知，最终求得的哈夫曼树中一共有2n-1个节点，其中n个节点是初始森林的n个孤立节点。由此可知，我们可以利用一个大小为2n-1的一维数组来存储哈夫曼树中的节点。b. 编码 【void Encod

10、ing(HuffNode ht,HuffCode hcd,int n)】 该函数实现对哈夫曼树的编码，先申请一个能存储字符编码的临时空间cd，编码从哈夫曼树的叶子节点hti开始，找到其父母节点htf，然后根据父母节点判断孩子节点的左右位置，左边置代码0，右边置代码1，代码存放在cdstrat中，然后把htf作为出发点，重复上述过程直到找到根节点为止。并将0,1这样的代码从后往前逆序存放在cd中，用变量start指示编码在数组cd中的起始位置，start的初始位置为n，生成一个代码后，start的值就减1。c. 译码 【void Decoding(HuffNode ht,HuffCode hcd

11、,int n)】 译码时，先输入一串由0和1组成的二进制代码串，并将单个字符依次存放在数组ch中，以#为结束标志。然后将代码与原先生成的哈夫曼编码表相比较，若为0，则转向左子树；若为1，则转向右子树，直到叶节点结束。三. 调试1）建立哈夫曼树A-Z 26个字母的哈夫曼树 2）编码3）译码四. 实验心得体会 通过这次的课程设计，我实在获益匪浅。数据结构是本学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我来说无疑是一个具大

12、的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，并最终运行出了结果。本次课程设计不但使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。而且许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我

13、们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。 作为信息管理专业的学生，我们应该很好的掌握这门学科。在课堂上，我们能够学到许多的理论知识，但我们很少有过自己动手实践的机会！课程设计就是为解决这个问题提供了一个平台。在课程设计过程中，我们每个人或者几个人选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。 数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是