数据结构课程设计---赫夫曼树的建立及在电报编码中的应用

1、 目录目录 一、题目介绍. 4 1、题目4 2、任务4 3、要求4 二、需求分析 4 1、应用环境设定.4 2、用户界面命令行界面.4 3、输入方式.5 4、输出方式.5 5、数据存储方式.5 6、程序功能.5 三、概要设计5 1、自定义数据类型.5 2、数据存储结构.6 3、程序所用各函数功能.6 4、程序流程图.8 四、详细设计 9 1、自定义数据结构.9 2、主函数 main（）9 3、子函数一.11 4、子函数二.12 5、子函数三.13 6、case1.h.14 7、case2.h.15 8、case3.h.16 9、case4.h.17 五、调试结果.17 进入菜单界面.17 选择

2、 1，构建只含根结点的带权二叉树18 选择 2，输出对应二叉树的赫夫曼树18 选择 3，测试赫夫曼树在电报通信中的运用19 选择 4，退出菜单界面19 六、心得总结.20 七、参考资料.21 一、一、题目介绍题目介绍 1 1、 题题目：目： 赫夫曼树的建立 2 2、 任务：任务： 按给定的数据建立赫夫曼树 3 3、 要求：要求： （1）可以建立函数输入二叉树； （2）输出其赫夫曼树。 （3）在上交资料中请写明：存储结构、基本算法（可以使用程序流程 图）、输入输出、源程序、测试数据和结果。提供良好的菜单操作界 面 二、二、需求分析需求分析 1 1、应用环境设定：、应用环境设定： 电报通信的数码拨

3、号时，我通常会用到十进制、八进制、或者十六进 制数等。而输入数字后，数据将以二进制数编码后进行远距离通信传 送。电文传输过程中，为了提高通讯效率，通常会要求所传输的二进 制数码尽可能的短。如果对每个字符设计长度不等的编码，且让电文 中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可 减少。但是同时要求各数字编码之间互不为前缀，从而不出现误码。 设计一个程序构建一个赫夫曼树输出最优传输码。 2 2、用户界面命令行界面：、用户界面命令行界面： （1）构建只含根结点的带权二叉树。 （2）输出第一部对应二叉树的赫夫曼树。 （3）给定任意进制（小于 17）的数字在电报通信中各自出现的频率， 然

4、后分别列出十个数字各自的最佳编码(最佳前缀码)以及打印出传输 10 m 个按照给定频率出现的十进制数字时所需要的二进制数码的个数。 3 3、输入方式：、输入方式： （1）输入二叉树的个数（小于 17）以及各个二叉树的权值。 （2）输入相关数据： 、按顺序输入 n 个 n 个数字在电报中出现的频率。 、输入需要传输的 n 进制数字的个数参数 m(总数为 10 m 个)。 4 4、输出方式：、输出方式： （1）输出所创建赫夫曼树中各结点的信息：(权值，父节点位置，左 儿子位置，右儿子位置)。 （2）输出相关数据： （3）输出 0 到 n 各个数字的最佳编码(最佳前缀码)。 （4）输出所创建的赫夫曼树的树权值（WPL）。 （5）输出所传输的二进制数码（电文长度）的总长度。 5 5、数据存储方式：、数据存储方式： 全部在内存存放，不使用硬盘上的文件或其他数据源，程序执行过程 中和结束后不保存数据。 6 6、程序功能：、程序功能： （1）创建赫夫曼数。 （2）实现赫夫曼树在电报通信中的应用。 三、概要设计三、概要设计 1、自定义数据类型：、自