数据结构课程设计 设计题目： 哈夫曼树及其应用 学 院：计算机科学与技术 专 业：网 络 工 程 班 级：网 络 131 学 号：********** 学生姓名：谢 * 指导教师：叶 * 2 0 1 5 年 7 月 1 2 日 设计目的： 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码
树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码
哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串
1、熟悉树的二叉树的存储结构及其特点
2、掌握建立哈夫曼树和哈夫曼编码的方法
设计内容： 欲发一封内容为AABBCAB ……(共长 100 字符,字符包括 A 、B 、C 、D 、E 、F 六种字符)，分别输入六种字符在报文中出现的次数（次数总和为100）， 对这六种字符进行哈夫曼编码
设计要求： 对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串
通常我们把数据压缩的过程称为编码，解压缩的过程称为解码
电报通信是传递文字的二进制码形式的字符串
但在信息传递时，总希望总长度能尽可能短，即采用最短码
假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n 种字符，则电文编码总长度为∑WiLi
若将此对应到二叉树上，Wi 为叶结点的权，Li 为根结点到叶结点的路径长度
那 么 ，∑WiLi恰 好 为二叉树上带 权路径长度
因 此 ，设计电文总长最短的二进制前 缀 编码，就是以 n 种字符出现的频 率 作权，构造 一棵 赫夫曼树，此构造 过程称为赫夫曼编码
设计实现的功 能： 1
以二叉链 表存储， 2
建立哈夫曼树； 3
求每个字符的哈夫曼
