1、 课课 程程 设设 计计 说说 明明 书书 课程名称： 数据结构与算法 设计题目： 哈夫曼编译码器 院 系： 计算机科学与信息工程学院 学生姓名： 学 号： 专业班级： 指导教师： 2017 年 12 月 11 日 设计题目 哈夫曼编译码器 限定人数 3 问题描述 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符 串的长度不小于 5000 字节。 读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对 编码文件进行解码， 获得文本文件。 将译码的文本文件和原文件进行比较， 恢复文件和原文件必须完全一致。 设字符集及频度如下表： 字符 空格 A B C D E F G H I
2、J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 基本要求 与说明 1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码 2、读取文本文件，并对文件内容编码，生成编码文件 3、对编码文件进行译码，获得恢复文件 4、比较恢复文件和原文件是否相同。 课课 程程 设设 计计 任任 务务 书书 设计题目 哈夫曼编译码器 学生姓名 所在院系 计算机科学与 信息工程学院 专业、年级、班 设计要求：设计要求： 1.
3、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码。 2.读取文本文件，并对文件内容编码，生成编码文件。 3.对编码文件进行译码，获得恢复文件。 4.比较恢复文件和原文件是否相同。 学生应完成的工作：学生应完成的工作： 1. 学生应认真学习参考程序，理解每个文件、每个函数以及各个变量的作用和意义。在此基础上 进一步改进程序，最后正确地运行程序。 2. 对程序进行测试，设计详细的测试计划，然后根据测试计划设计测试用例，对程序进行测试。 测试时应注意对各种边缘情况进行测试。 3. 完成课程设计报告。 参考文献阅读：参考文献阅读： 1. 严蔚敏数据结构（C 语言版） 清华大学出版社，2011 2
4、. 谭浩强C 程序设计（第四版） 清华大学出版，2010 3.蒋立翔C+程序设计技能百练 M中国铁道出版社，2004 工作计划：工作计划： 1. 小组审题，查阅资料，进行设计前的必要资料准备（3 天） 。 2. 把程序完整运行出来（4 天） 。 3. 增加改进程序（3 天） 。 4. 写课程设计报告（3 天） 。 5. 提交课程设计报告及答辩（1 天） 任务下达日期：2017 年 12 月 01 日 任务完成日期：2017 年 12 月 19 日 指导教师（签名） ： 学生（签名） ： 哈夫曼编哈夫曼编 译码器译码器 摘摘 要：要：采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串
5、的长 度不小于 5000 字节。 读取要编码的文本文件， 将文件的内容进行编码， 生成新的文件。 对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件 和原文件必须完全一致。 关键词：关键词：构建哈夫曼树 哈弗曼编码 哈夫曼译码 字符串编码 打印编码函数 目 录 1.设计背景 1 1.1 哈夫曼树的介绍 1 1.2 设计的作用、目的 1 1.3 设计任务及要求 2 2.设计方案 2 2.1 实验内容2 2.2 操作思路2 2.3 基本操作3 3. 方案实施 .4 3.1 C 语言编程 4 3.2 程序介绍.12 3.3 程序流程图以及说明 .13 图 3 主程序流程图
6、.13 4. 结果与结论 14 4.1 程序运行结果 .14 4.2 总结 16 5. 收获与致谢 17 6. 参考文献 17 1 1.设计背景 1.11.1 哈夫曼树的介绍哈夫曼树的介绍 Huffman Tree，中文名是哈夫曼树或霍夫曼树或者赫夫曼树，它是最优二叉树。 定义：给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若树的带权路径长度达到最 小，则这棵树被称为哈夫曼树。 (01) (01) 路径和路径长度路径和路径长度 定义： 在一棵树中， 从一个结点往下可以达到的孩子或孙子结点之间的通路， 称为路径。 通路中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点 的路径长度为 L-1。 (02)(02) 结点的权及带权路径长度结点的权及带权路径长度 定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点 的带权
