1、 1 课程设计说明书(论文) 题 目 哈夫曼编码问题的设计和实现哈夫曼编码问题的设计和实现 课 程 名 称 数据结构课程设计数据结构课程设计 院（系、部、中心） 专 业 班 级 学 生 姓 名 学 号 设 计 地 点 指 导 教 师 设计起止时间：2008 年 6 月 2 日至 2008 年 6 月 6 日 成 绩 2 目录目录 1 问题描述 3 1.1 题目内容 . 3 1.2 基本要求 . 3 1.3 测试数据 . 3 2 需求分析 3 2.1 程序的基本功能 . 3 2.2 输入值、输出值以及输入输出形式 . 3 2.3 各个模块的功能要求 . 4 3 概要设计 5 3.1 所需的 AD
2、T，每个程序中使用的存储结构设计说明（如 果指定存储结构请写出该存储结构的定义） . 5 3.2 主程序流程以及模块调用关系 . 5 3.3 各个模块的算法设计说明 . 5 4 详细设计 8 4.1 数据类型 . 8 4.2 函数调用 . 9 5 各个算法实现的源程序 9 6 调试分析 12 7 使用说明 13 8 测试结果 13 9 源程序 13 3 1 问题描述问题描述 1.1 题目内容 哈夫曼编码问题的设计和实现 输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以 其出现次数作为关键字建立哈夫曼树并进行编码，最后输出各个字符对应的码值。 1.2 基本要求 要求：设
3、计存储结构、基本算法（主要采用程序流程图体现） ；完成基本算法的实现 代码；设计测试输入数据对程序进行测试，分析输出结果数据、算法的时间复杂度分析， 如有改进算法则提出算法的改进方法。 1.3 测试数据 测试数据三组： AAAABBBCCD(判断连续的字符串是否可行) AABBAABCDC(判断间段的字符串是否可行) AAAA BBBCCD(判断含空格的字符串是否可行) 2 需求分析需求分析 2.1 程序的基本功能 该程序大体上有两个功能： 1 输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字符串的个数 作为权值。 2 已知不同字母的权值，以该权值作为叶结点，构造一棵带权路径最小
4、的树，对该树 从叶结点到根结点路径分支遍历，经过一个分支就得到一位夫曼编码值。 （规定哈夫曼 树中的左分支为 0，右分支为 1，则从根结点到每个叶结点所经过的分支对应的 0 和 1 组成的序列便为该结点对应字符的编码） 2.2 输入值、输出值以及输入输出形式 输入值 ：AAAABBBCCD 输出值 ：W =4 C=0 4 W=3 C=10 W=2 C=111 W=1 C=110 输入值 ：AABBAABCDC 输出值 ：W=4 C=0 W=3 C=10 W=2 C=111 W=1 C=110 输入值 ：AAAA BBBCCD 输出值 ：W=4 C=11 W=1 C=010 W=3 C=10 W
5、=2 C=00 W=1 C=011 2.3 各个模块的功能要求 1 统计模块 任意输入一个字符串，不论字母是否相联，字符串中是否含空格都能统计出不同字 母的个数。 2 建立哈夫曼树模块 以统计的字符串个数作为权值，利用仿真存储结构，建立带权路径最小的树。 其中对结点的存储需要六个域，分别是 weight 域，flag域， parent 域，leftChild 域，rightChild 域。weight 域是对权值的存放，flag 域是一个标志域，flag=0 时表 示该结点尚未加入到哈夫曼树中，flag=1 时表示该结点已加入到哈夫曼树中。 3 哈夫曼编码模块 从哈夫曼树的叶结点到根结点路径分
6、支逐步遍历，每经过一个分支就得到一 位哈夫曼编码。哈夫曼编码也利用仿真存储结构。 4 主函数模块 从屏幕上输入字符串，调用函数，输出每个字母的权值与编码。 5 3 概要设计概要设计 3.1 所需的 ADT，每个程序中使用的存储结构设计说明（如果指定存储结 构请写出该存储结构的定义） 抽象数据类型集合：在该程序中未用到抽象数据类型，主要用到的数据类型为 ： int ,char 。 在哈夫曼树的建立与哈夫曼树的编码中用到仿真存储 3.2 主程序流程以及模块调用关系 输入字符串调用 count 函数申请内存空间调用 Haffman 调用 HaffmanCode输出权值与编码。 3.3 各个模块的算法设计说明 1 主函数模块 n y y n n y 开始 定
