一、实验任务
实验题目:数据结构与程序设计专题实验
二、实验内容
实验三:树的基本操作及基于霍夫曼树的编码/译码
(一)实验目的:掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的
原理。
(二)基本要求:熟练掌握树的操作。
(三)内容提要:给定一段字符,构建霍夫曼树;根据该树求每个字符的编码,并对该段
字符串进行编码;将得到的编码进行译码;基于该霍夫曼树,通过遍历算法来
输出该树中的叶子节点。
注:在实现时要求霍夫曼树的左右孩子的大小关系(左孩子节点值小于右孩子节
点),在遍历的时候也可以为递归与非递归办法寻找叶子节点。
三、要点分析
题目中涉及的主要知识点:
1、本程序参考霍夫曼算法(由给定的权值构造赫夫曼树):
(1)由给定的 n 个权值{w
0
, w
1
, w
2
, …, w
n-1
},构造具有 n 棵二叉树的集合
F = {T
0
, T
1
, T
2
, …, T
n-1
},其中每一棵二叉树 T
i
只有一个带有权值 w
i
的根
结 点,其左、右子树均为空。
(2)重复以下步骤, 直到 F 中仅剩下一棵树为止:
① 在 F 中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵
新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的
权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
2、用构造赫夫曼树以完成赫夫曼编码:
把 d
1
,d
2
,…, d
n
作为叶子结点,把 w
1
,w
2
,…,w
n
作为叶子结点
的权,构造赫夫曼树。在赫夫曼树中结点的左分支赋 0,右
分支赋 1,从根结点到叶子结点的路径上的数字拼接起来就
是这个叶子结点字符的编码。
3、译码的过程是分解电文中的字符串,从根出发,按字符‘ 0’或‘1’确定找 左
孩子或右孩子,直至叶子节点,便求得该子串相应的字符。
四、解题步骤
编程平台:Microsoft Visual C++ 6.0
编程平台应用:
第一步:打开 Microsoft Visual C++ 6.0 运行软件;
评论0