《数据结构》课程教学资源（教案设计）07 哈夫曼树

编号：008 课程 章节 数据结构 第五章树和二叉树 课程讲 45分钟 名称 名称 6.6哈夫曼树及其应用 授学时 学习要求 课堂 知识点 熟练 识记 理解 掌握 应用 分析 教学 综合 图的遍历 √ √ √ 目的 态度积极主动学习 能力>利用深度优先搜索、广度优先搜索解决简单的应用问题 教学内容（教学过程设计） 教学安排 导入新课 5分钟 由《信源编码》中关于数字编码的知识引入Huffman本人在编码和数据压缩 方面的贡献，引入本节课内容 1 6.6哈夫曼树及其应用 5分钟 结合具体实例介绍哈夫曼树的相关概念，重点解释权值 5分钟 利用课件演示，观察哈夫曼树的特点，给出哈夫曼算法的基本思想，运 5分钟 行一个实例构造哈夫曼树 10分钟 重新考察哈夫曼树的构造过程，总结要点 10分钟 哈夫曼树的应用实例简介 5分钟 介绍等长编码和不等长编码，通过实例强调在设计不等长编码时，必须 考虑解码的唯一性，引出前缀编码 给出用哈夫曼构造最短的不等长编码的方法，通过实例解释编码与解码 过程，体会树的带权路径长度的含义 分析哈夫曼编码与解码算法的关键问题，由学生课后完成算法 教学提示： 本讲是本章的应用篇，重点是应用本章知识解决哈夫曼树以及哈夫曼编 码问题，在讲授中要综合应用二叉树的性质、二叉树的存储结构、二叉 树算法的设计等知识，达到“不仅知其所以然，还要使其然”的教学目 的。 开篇要介绍哈夫曼算法产生的背景，使学生体会算法在程序设计中的重 要地位，对算法产生兴趣

编号：008 课程 名称 数据结构 章节 名称 第五章 树和二叉树 6.6 哈夫曼树及其应用 课程讲 授学时 45 分钟 课堂 教学 目的 知 识 点 学 习 要 求 识记 理解 熟练 掌握 应用 分析 综合 图的遍历 √ √ √ √ √ 态度 积极主动学习 能力 ➢ 利用深度优先搜索、广度优先搜索解决简单的应用问题 教学内容（教学过程设计） 教学安排 导入新课 由《信源编码》中关于数字编码的知识引入 Huffman 本人在编码和数据压缩 方面的贡献，引入本节课内容 ↓ 6.6 哈夫曼树及其应用 ↓ 结合具体实例介绍哈夫曼树的相关概念，重点解释权值 利用课件演示，观察哈夫曼树的特点，给出哈夫曼算法的基本思想，运 行一个实例构造哈夫曼树 ↓ 重新考察哈夫曼树的构造过程，总结要点 ↓ 哈夫曼树的应用实例简介 ↓ 介绍等长编码和不等长编码，通过实例强调在设计不等长编码时，必须 考虑解码的唯一性，引出前缀编码 给出用哈夫曼构造最短的不等长编码的方法，通过实例解释编码与解码 过程，体会树的带权路径长度的含义 分析哈夫曼编码与解码算法的关键问题，由学生课后完成算法 教学提示： ➢ 本讲是本章的应用篇，重点是应用本章知识解决哈夫曼树以及哈夫曼编 码问题，在讲授中要综合应用二叉树的性质、二叉树的存储结构、二叉 树算法的设计等知识，达到“不仅知其所以然，还要使其然”的教学目 的。 ➢ 开篇要介绍哈夫曼算法产生的背景，使学生体会算法在程序设计中的重 要地位，对算法产生兴趣 5 分钟 5 分钟 5 分钟 5 分钟 10 分钟 10 分钟 5 分钟

重点 哈夫曼树及应用。 重点 难点 哈夫曼编码操作的实现。 难点 教学策略： 对策 在授课过程中采用多媒体教学，首先还原问题的本来面目一 一提出问题，引导学生 积极参与 尝试解决问题，在讨论的基础上给出结论一一讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 教学方法：导入，配合图形、实例讲解，提问、讨论 方法 教学手段：PPT课件，板书，动画演示 与 手段 作业： (1)某通信电文由A、B、C、D、E、F六个字符组成，它们在电文中出现的 次数分别是16,5,7,3,8,1，试画出其哈夫曼树并确定其对应的哈夫曼编 作业 (2)编写一个递归算法，利用叶结点中空的右链指针域rchild,将所有叶结点自 左至右链接成一个单链表，算法返回最左叶结点的地址（链头】 课后导读： 推荐 资 树还有其他存储方法，请参见《数据结构与算法》（许卓群清华大学出版 哈夫曼编码是前缀编码以及哈夫曼是最短编码的证明请参见《数据结构与 算法》（齐德显清华大学出版社） 《数据结构与算法》许卓群编著，高等教育出版社。参阅相关章节：给出了 Huffman编码是前缀编码以及Huffman编码是最短前缀编码的证明 教学 后记

重点 与 难点 对策 重点： 哈夫曼树及应用。 难点： 哈夫曼编码操作的实现。 教学策略： 在授课过程中采用多媒体教学，首先还原问题的本来面目——提出问题，引导学生 积极参与——尝试解决问题，在讨论的基础上给出结论——讲授教学内容、解决 问题，最后采用课件进行算法的动态演示，加大课堂信息量，提高教学效率。 教学 方法 与 手段 教学方法：导入，配合图形、实例讲解，提问、讨论 教学手段：PPT 课件，板书，动画演示 作业 及 课外 推荐 资源 作业： （1） 某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的 次数分别是 16，5，7，3，8，1。试画出其哈夫曼树并确定其对应的哈夫曼编 码。 （2）编写一个递归算法，利用叶结点中空的右链指针域 rchild，将所有叶结点自 左至右链接成一个单链表，算法返回最左叶结点的地址（链头）。 课后导读： ➢ 树还有其他存储方法，请参见《数据结构与算法》（许卓群 清华大学出版 社） ➢ 哈夫曼编码是前缀编码以及哈夫曼是最短编码的证明请参见《数据结构与 算法》（齐德昱 清华大学出版社） ➢ 《数据结构与算法》许卓群编著，高等教育出版社。参阅相关章节：给出了 Huffman 编码是前缀编码以及 Huffman 编码是最短前缀编码的证明 教 学 后记