数据结构课程设计 设计题目： 哈夫曼树及其应用 学 院：计算机科学与技术 专 业：网 络 工 程 班 级：网 络 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.求每个字符的哈夫曼编码并 显 示。 一：赫夫曼树的构造 “（1）由给定的n 个权值{W1，W2，…，Wn}构成 n 棵二叉树的集合 F＝{T1，T2，…，Tn},其中每棵二叉树Ti 中只有一个带权为 Wi 的根节点，其左右子树均空。 （2）在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树， 这棵新的二叉树根结点的权值为其左、 右子树根结点权值之和； （3）在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合 F 中； （4）重复（2）（3）两步，当 F 中只剩下一...
