1、 1 数据结构课程设计 设计说明书 （题目） 哈夫曼编译器 起止日期： 2011 年 6 月 20 日 至 2011 年 6 月 27 日 学生姓名 班级 学号 成绩 指 导 教 师 ( 签 字 ) 计算机与通信学院 2011 年 6 月 23 日 2 一、课题任务与说明课题任务与说明 1编辑一个哈夫曼编译器系统程序 2问题描述 设某编码系统共有 n 个字符，使用频率分别为w1,w2,wn，设 计一个不等长编码方案，使得该编码系统的空间效率最好。 3.所具有的功能： (1) 为一字符文本编码功能：将一字符文本复制到指定的文本 中，并保存到指定路径，让程序自动为它编码。 (2) 为部分字符编码功
2、能：输入部分字符与对应的字符频率， 让程序为之编码（需注意输入格式） 。 (3) 保存输出到文本功能：将编码结果输出到文本。 (4) 输出保存文本信息功能：将功能 3 保存的文本信息输出到 屏幕上，用于查看结果是否正确。 4.设计要求 （1）设计数据结构； （2）设计编码算法； （3）分析时间复杂度和空间复杂度。 （4）字符和频度如下： 字符 空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 频度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 15 1 48 51 80 23 8 18
3、 1 16 5.设计内容与步骤 （1）选择合适的数据结构 （2）结点结构的设计 （3）算法设计与分析 （4）程序设计、实现、调试 （5）课程设计说明书 6.设计工作计划与进度安排 （1）设计工作 4 学时 （2）实现与调试 16 学时 （3）课程设计说明书 4 学时 3 二、算法设计二、算法设计 Huffman 编码是一种可变长编码方式，是由美国数学家 David Huffman 创立的，是二叉树的一种特殊转化形式。编码的原理是：将 使用次数多的代码转换成长度较短的代码， 而使用次数少的可以使用 较长的编码，并且保持编码的唯一可解性。Huffman 算法的最根本的 原则是：累计的(字符的统计数
4、字*字符的编码长度)为最小，也就是 权值(字符的统计数字*字符的编码长度)的和最小。 三、程序的功能设计三、程序的功能设计 为实现系统功能，本程序主要分为五个模块。它们分别为： 1.初始化功能模块 此功能模块的功能为从键盘接收字符集大小 n,以及 n 各字 符和 n 个权值。 2.建立哈弗曼树的功能模块 此模块功能为使用 1 中或从一文本中得到的数据按照教材 的构造哈夫曼树的算法构造哈夫曼树。 3.建立哈夫曼编码与译码的功能模块 此模块功能为读入相关的字符信息进行哈夫曼编码， 并将译 码结果输出，在必要时也可保存到文件中。 其中各个函数的功能分别如下： notesave 函数用于保存输出的结果； hfmtree 函数用于建立结点哈夫曼树并输出最终结果； readnote 函数用于读取目标文本字符信息； 4.流程图： 界面 结束 main() Hfmtree() Exit() Readnote() Notesave() Main() 4 四、函数编码及调试四、函数编码及调试 由于本人能力有限难免不会在编码与调试过程中遇到这样或 那样的问题，
