课程设计哈弗曼编码译码器.doc

哈弗曼编码译码器 软件121班 2012023040 王祥袁 PAGE \* MERGEFORMAT 1 PAGE \* MERGEFORMAT 1 目录 评分表…………………………………………………………………………………………………………2 问题描述………………………………………………………………………………………………………3 功能分析………………………………………………………………………………………………………3 系统设计 数据结构类型…………………………………………………………………………………………3 主要模块算法描述……………………………………………………………………………………3 详细设计………………………………………………………………………………………………7 测试…………………………………………………………………………………………………………20 总结…………………………………………………………………………………………………………33 第 PAGE \* MERGEFORMAT 第 PAGE \* MERGEFORMAT 2 页 共 NUMPAGES \* MERGEFORMAT 35 页 软件工程课程设计评分表 班级 姓名 指导教师 题目： 评分标准 评分标准 分数权重 评分的依据 得分 A C 工作态度 10 态度端正，能主动认真完成各项内容，不迟到早退，出勤好。 能够完成各环节基本工作，出勤较好。 程序设计，完成及运行情况 20 功能达到设计要求，程序稳定、界面美观、符合规范、程序易读、完成率100%、程序运行正确。 功能实现了大部分，程序较稳定、界面可用性一般、程序有注释、完成率不足70%。 相关文档 40 格式规范，层次清晰，设计思想明确，解决问题方法合理，文档编写完整规范，编写过程符合软件工程开发设计流程等。 格式较规范，设计思想基本明确，解决问题方法较合理，基本遵循软件工程开发流程。 答辨问题回答 30 能准确回答老师提出的问题，并充分理解数据库开发技术，程序逻辑清晰。 能基本准确回答老师提出的问题 总分 指导教师（签字）： 注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。 问题描述： 用电子方式处理符号时，需先对符号进行二进制编码。例如，在计算机中使用的英文字符的ASCII编码就是8位二进制编码，ASCII编码是一种定长编码，即每一个字符用相同的二进制位编码。为了提高传输效率及缩短数据文件（报文）长度，可采用不定长编码。这里就应用到了哈弗曼编码。那么，如何创建一个哈弗曼树，并能对一篇英文文章进行编码，同时还能对电文进行译码呢？ 功能分析： 1、输入的形式和输入值的范围：本演示程序中，字符及相应权值的输入有三种方式：从文件读入、手动输入、由电文随机生成。电文编码及译码翻译均直接从文件读入，电文内容根据权值有所限定，仅支持英文字符组成的电文，在不支持其他语言组成的电文。对于菜单的选择，按照菜单提供的选择项进行选择即可，若输出位置菜单项，会提示错误，只需重新输入即可。 2、输出的形式：演示程序以人机交互的方式执行，即在计算机终端上显示“提示信息”之后，由用按需户求在键盘上作相应的选择，哈夫曼树、电文编码及译码均输出到文件，哈夫曼编码输出到屏幕。 3、程序所能达到的功能：（1）多级演示菜单显示 （2）创建哈夫曼树 （3）从文件读入已有的哈夫曼树 （4）查看哈夫曼编码的编码方式 （5）对电文进行编码 （6）对电文进行译码 （5）以上功能的反复进行 （6）结束 系统设计 所选用的数据结构： 采用哈弗曼树的树形存储结构，由于哈弗曼树是具有相同叶字个数的二叉树中带权路径长度最小的二叉树，涉及根据叶子数求其“规模最小”的二叉树问题，用哈弗曼树构造哈弗曼编码是其典型应用。 主要模块算法描述： （1）建立哈弗曼树： 开始 开始 初始化非叶子节点 初始化非叶子节点 I=huffmanleaf I=huffmanleaf I2*huffmanleaf-1！ 否 I2*huffmanleaf-1！ 是 I++ I++ 选两个最小权值的结点 选两个最小权值的结点 HufNode[s1].parent=i HufNode[s1].parent=i HufNode[s2].parent=i HufNode[s2].parent=i HufNode[i].lchild=s1 HufNode[i].lchild=s1 HufNode[i].rchild=s2 HufNo