哈夫曼树及应用
2020-03-02 04:29:29 来源：范文大全收藏下载本文
常熟理工学院微课教学比赛教学设计
1、课程基本信息
课程名称：哈夫曼树及应用
所属课程：数据结构与算法 课程所属专业：软件工程
适用专业：计算机类 选用教材：严蔚敏，吴伟明编著《数据结构（C语言版）》北京：清华大学出版社，2007 主讲人：周思林
时长：15分钟 所属学校：常熟理工学院
所属院系：计算机科学与工程学院
2.教学背景
《数据结构与算法》课程是计算机类专业的学科基础课程，本节微课“哈夫曼树及应用”属于数据结构课程中的“树与二叉树”章节中的重点及难点。 2.1《数据结构与算法》课程简介及特点
《数据结构与算法》课程是计算机类专业的学科基础课程，同时也是计算机类专业的核心课程。课程的主要目标是使学生理解和掌握基本数据结构的概念、经典算法的思想及实现方法，具备为应用所涉及的数据选择适当的逻辑结构、存储结构及其相应的操作算法的能力。数据结构与算法课程的学习也是复杂程序设计的训练过程，通过算法设计和实践，培养学生的数据抽象和复杂程序设计能力。
《数据结构与算法》课程由线性结构、树形结构、图状结构三种逻辑结构和查找、排序算法为主体，结合应用型本科院校特点，通过实践理解和掌握基本数据结构与算法，在实践中提高学生的专业素养和专业技能。 2.2本节微课课程特点
“树与二叉树——哈夫曼树及应用”是《数据结构与算法》课程中第六章“树与二叉树”的核心内容之一，同时也是该章节的教学难点。
本节微课采用案例驱动法进行教学，调动学生的学习积极性，引导学生发现问题、思考问题、解决问题，利用形象的多媒体动画展示案例的执行过程，将哈夫曼树及编码复杂的程序结构趣味化、形象化。由发送报文问题引入课程，循序渐进的介绍哈夫曼树的概念、逻辑特性、存储结构和算法实现，使学生掌握哈夫曼树及编码的基本概念和算法，提升学生的程序设计及逻辑思维能力。
3.教学设计
3.1教学目的
通过本节微课的学习，培养学生以下几个方面的能力： （1）理解哈夫曼树的应用范围和场景，并能灵活运用；
（2）掌握哈夫曼树及编码的概念、求解算法基本思想，针对实例，能构造哈夫曼树，求解哈夫曼编码；
（3）掌握哈夫曼树的存储结构，理解静态三叉链表结构；
（4）掌握哈夫曼树及编码的求解算法，并能在实验中实现并验证算法（难点）；
根据学生理论基础及程序编码能力，本微课教学目标分为三个水平：合格、中等、优秀，具体标准如下：
合格水平：熟练掌握哈夫曼树及编码的基本概念，能构造哈夫曼树，求解哈夫曼编码。 中等水平：掌握概念和算法思想的基础上，能上机实现验证哈夫曼树及编码的求解过程。 优秀水平：在上机实现算法的基础上，能理论联系实际，利用算法解决实际问题。 3.2教学内容
树与二叉树中哈夫曼树的构造和哈夫曼编码的求解。 （1）问题引入；
（2）哈夫曼树的定义； （3）哈夫曼树的构造； （4）哈夫曼编码的定义； （5）算法实现。 3.3教学重点及难点
教学重点：哈夫曼树及编码求解的算法思想。 教学难点：哈夫曼树的存储结构，算法的实现。 3.4教学方法
本微课内容在算法思想上较为容易，但在具体实现上具有一定难度，因此采用启发式教学和案例驱动式教学相结合的方法，提出问题引入课题，通过实例求解哈夫曼树，循序渐进求解哈夫曼编码，通过多次提问的方式充分调动学生的学习积极性，使用动画的形式演示实例的求解过程，增强课堂的形象性及趣味性，增加课堂容量。
课程设置由问题引入、哈夫曼树的概念、哈夫曼树的构造、哈夫曼编码、算法的实现共同组成，由浅入深，由理论到实践，实现微课课堂的完整性和连贯性。
（1）问题引入
由报文传送问题引入，如何来构建传送效率高，即报文长度最短的二进制编码。哈夫曼编码也常用在数据压缩中，是一种非常有效的压缩方法。
问题：如何使报文长度最短？ （2）哈夫曼树的定义
针对给出的二叉树实例T，回顾二叉树的基本概念，树的根节点、叶子结点，同时引入新的概念，结点的权值、路径长度、结点的带权路径长度，树的带权路径长度WPL。
分析实例，相同叶子结点权值，不同树的组成形态，WPL权值不一定，引出哈夫曼树的定义：带权路径长度最小的二叉树。
问题：如何构造哈夫曼树？ （3）哈夫曼树的构造
通过二叉树的实例引出哈夫曼树的构造原则和哈夫曼树的构造思想。
通过流程图的方式逐步介绍哈夫曼树的构造方法，利用标注给出每步详细事项。 通过动画的方式，逐步介绍以
7、
9、
5、
6、2为叶子结点的哈夫曼树构造过程。 问题：哈夫曼树是否唯一？ （4）哈夫曼编码
问题：哈夫曼树中是否存在度为1的结点？ 分析二进制编码和哈夫曼树的特点，讲解哈夫曼编码的求解过程。通过动画演示哈夫曼树进行“0”“1”编码的过程从而求解出哈夫曼编码。 问题：n个叶子结点的哈夫曼树总共有多少结点？引导出哈夫曼树的存储结构。
（5）算法实现
分析：在哈夫曼树的构造过程中，需要用到孩子和双亲的信息，因此存储结构中需要保存双亲及左右孩子的信息，采用三叉链表来表示，同时在求解编码过程需要从根到叶子结点，因此采用静态链表作为存储结构。
具体实现分以下部分进行：
a：根据叶子结点给静态三叉链表赋初值；
b：在静态三叉链表中依次构造根权值为
7、
13、
16、29的节点，删除所选两棵树的操作为修改该结点双亲的值；
c：产生哈夫曼编码，针对静态三叉链表的存储结构内容，从叶子结点a开始，依次找到双亲信息，并获得哈夫曼编码的逆序序列。
提炼出哈夫曼编码的产生方法，结合程序代码进行详细讲解。 总结本次课程主要内容，提出课后思考题。
4、教学总结
本次微课由报文传送引出主题，由理论到实现，结合形象的动画演示循序渐进的描述了哈夫曼树和编码的定义与实现。通过问题导入和案例驱动式教学方法的使用，使学生难以理解的二叉树结构与算法形象化、趣味化。通过实例的讲解，使学生快速掌握了哈夫曼树及哈夫曼编码的算法思想，再由实例结合存储结构的方式，让学生理解哈夫曼树的相关程序设计，提升学生的学习兴趣，增强学生逻辑结构分析能力和程序设计能力。
人人范文网 m.inrrp.com.cn 手机版