1、 课程设计报告课程设计报告 课程设计题目课程设计题目 ： 赫夫曼编码系统赫夫曼编码系统 学生姓名学生姓名 ： 专专 业业 ： 计算机科学与技术计算机科学与技术 班班 级级 ： 学学 号号 ： 指导教师指导教师 ： 2012 年年 06 月月 20 日日 1 目 录 一、设计要求-2 二、存储结构-2 三、设计思想-2 1、设计包含的几个部分-2 2、流程图-3 四、详细设计-4 五、算法复杂度分析-8 六、显示结果-9 七、心得体会-11 八、附录：源程序代码-11 2 一一、设计要求设计要求 赫夫曼树 任务 ：建立建立最优二叉树函数 要求：可以建立函数输入二叉树，实现赫夫曼树的编码和译码系统
2、，重复地 显示并处理编码/解码功能，直到选择退出为止。 二、存储结构：二、存储结构： 在本次课程设计中，每一个字符的信息用一个结构体存储，包含结点值、 权值、双亲结点、左孩子结点、右孩子结点等数据。赫夫曼码和所有字符都是用 一个一维数组建立存储的，所以本次课程设计的存储结构是顺序存储。 三、设计三、设计思想思想 哈夫曼编译码系统的主要功能是先建立哈夫曼树， 然后利用建好的哈夫曼树 生成哈夫曼编码后进行译码 。 在数据通信中，经常需要将传送的文字转换成由二进制字符 0、1 组成的二 进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表 0，右 分支代表 1，则从根节点到每个叶子节点所
3、经过的路径分支组成的 0 和 1 的序列 便为该节点对应字符的编码，称之为哈夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的 字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送 电文的总长度。哈夫曼树用于构造使电文的编码总长最短的编码方案。 （1）设计包含的几个方面： 赫夫曼树的建立 赫夫曼树的建立由赫夫曼算法的定义可知， 初始森林中共有 n棵只含有根结点的 二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并 成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然 要进行 n1 次合并，所以共产生 n1 个新结点，它们都是具有两个孩子的分支 结点。由此可知，最终求得的赫夫曼树中一共有 2n1 个结点，其中 n个结点是 初始森林的 n个孤立结点。并且赫夫曼树中没有度数为 1 的分支结点。我们可以 利用一个大小为 2n-1 的一维数组来存储赫夫曼树中的结点。 赫夫曼编码 要求电文的赫
