复杂算法的案例教学设计
来源:用户上传
作者:
摘 要： 当前，将案例教学运用于数据结构教学的研究尚存在设计过程不详细、缺少针对问题设置的分析、教学案例简单等不足。为此，提出面向复杂算法的案例教学设计方案。新方案符合“问题界定-数据获取-案例构建-案例应用”的四阶段教学案例开发框架。为了实现多个递进的能力培养教学目标，在教学过程的各环节设置了引导性、分析性和开放性问题。此外，还讨论了图解教学法和对比教学法在案例教学过程中的综合运用。
关键词： 数据结构; 二叉树; 案例教学法; 圖解教学法; 对比教学法
中图分类号：G642 文献标识码：A 文章编号：1006-8228（2020）02-109-04
A case teaching design scheme for complex algorithms
Liu Xin1，2， Zhang Bin1，2， Zhang Bo3
（1. School of Information Engineering， Shandong Youth University of Political Science， Jinan， Shandong 250013， China;
2. Key Laboratory of Information Security and Intelligent Control in Universities of Shandong （Shandong Youth University of Political Science）;
3. School of Information Science and Engineering， University of Jinan）
Abstract： At present， there are still many shortcomings in the research on the case teaching for data structure course， which are mainly manifested in the following aspects， such as the lack of a detailed design process， the absence of analysis of the raising of problem， the adoption of simple teaching cases， and etc. To solve these problems， a case teaching design scheme for complex algorithms is proposed. The new scheme conforms to the four-stage teaching case development framework of “problem definition， data acquisition， case construction and case application”. In order to achieve the teaching objective of multiple progressive ability building， analytical and open questions are designed in all aspects of the teaching process. In addition， the comprehensive application of graphic teaching method and comparative teaching method is also discussed.
Key words： data structure; binary tree; case teaching method; graphical teaching method; comparative teaching method
0 引言
数据结构是计算机科学与技术专业的核心专业基础课程。该课程在计算机学科中处于承上启下的核心地位，且可视为信息处理、人工智能、数据库等课程的重要基础[1]。该课程有理论性强、算法执行过程抽象等特点，使得传统教学方式难以取得理想效果。为此，许多院校在课程教学中引入了案例教学法。谭定英等人[2]以“哈夫曼算法的应用”为例介绍了案例教学的实施过程。郑馨等人[3]设计了基于贪吃蛇游戏的案例，且要求学生分别利用四种存储结构来实现。我们认为已有研究成果尚存在以下不足：①所提供的教学案例主题较为简单，或者设计过程不够详细;②缺少问题设置举例以及必要性分析;③教学手段较为单一，缺少与其他教学方法的配合;④案例教学实施步骤并不一致，也缺乏有关案例开发的基本框架等规律性问题的总结与分析;⑤缺少围绕具有一定难度的高级主题（如复杂算法）进行案例教学设计的讨论，无法提升学生的思维层次，不能满足创新思维培养的教学需要。
1 以“求二叉树宽度”为主题的案例教学设计方案
我们选取二叉树算法教学中的高级主题——“求二叉树宽度”问题进行教学案例设计，且设计过程遵循钱明辉等人[4]的“问题界定-数据获取-案例构建-案例应用”四阶段教学案例开发框架。新的教学案例设计可视为该框架在工程实践类问题教学方面的具体应用。
1.1 问题界定与资料获取
树型结构是数据结构课程的核心内容，并且涉多个基于二叉树的复杂算法。本案例的研究对象是“求二叉树宽度”的算法设计问题，该问题本身属于二叉树层次遍历算法（简称层次遍历算法）的应用范畴。本案例需要研究的问题是：通过详细分析算法设计的过程，使学生理解并掌握借助层次遍历求二叉树宽度的技术，进而领会层次遍历算法的高级应用。同时掌握根据现实应用需要为算法选择合适存储结构的方法。本案例的内容来自于权威考研复习教材和在考研答疑过程中收集到的历年考研复习题目。 1.2 案例构建
以下我们从背景信息、案例正文、问题设计和使用说明四个方面来详细设计。
1.2.1 背景信息
问题提出的背景是解决课程中有关层次遍历算法具体应用的教学难点问题。案例选择的背景是为了求二叉树的宽度，需要在执行过程和底层存储结构层面对层次遍历算法做出扩展。其理论依据是层次遍历算法、二叉链表存储结构、顺序队列存储结构的入队和出队操作。案例选择依据是求二叉树宽度的算法是层次遍历算法的重要应用。
1.2.2 案例正文
⑴ 需求讨论
二叉树T的宽度定义为：当T为空时，宽度为0;当T为非空时，取结点数最多的那层结点数作为T的宽度。需要解决的问题是设计求T宽度的算法。尽管可以利用层次遍历算法对T进行扫描，并且记录每层的结点数。但是，层次遍历算法将二叉树视为整体，并未在层次切换时进行停顿或做出判定。主要困难是如何在每层扫描开始时重新进行结点计数，并且在层次切换之前将本层结点数与此前遇到的最大层次结点数进行比较。
⑵ 情境分析
尽管利用层次遍历算法无法求出二叉树的宽度，但是求二叉树宽度的过程一定蕴含着层次遍历算法的执行框架。同时，层次遍历算法的底层存储结构为顺序栈或链式栈。该结构同样为求二叉树宽度提供了必要的结点信息。由此可见，为了求二叉树的宽度，需要修改层次遍历算法，使其在进行层次切换之前将结点的层号加1。同时，通过扩展底层存储结构，使得能算法在扫描过程中将结点的层号写入底层存储结构，从而为今后通过二次扫描求出二叉树的宽度奠定基础。
⑶ 过程描述
案例教学过程分以下步骤具体展开。
① 问题引入。通过该环节，引入二叉树宽度的定义。
② 分析讨论。首先复习层次遍历算法，然后讨论当前问题与层次遍历之间的关系，得出明确的技术路线。
③ 底层存储结构的遴选与扩展。我们选择顺序队列作为层次遍历算法的存储结构。为了保存结点的层次编号，需要在顺序队列的结构体定义中增加成员数组level[][5]。
④ 算法执行过程的圖解展示。为了可视化地展示教师的思维，我们采用特定的二叉树作为实例，并且以逻辑结构与存储结构相结合的方式展示算法的执行过程。假设有一棵基于二叉链表结构的二叉树，且根结点指针为b。该二叉树含有6个结点，且结点B，C，…，F的指针分别表示为pB，pC，…，pF。算法的执行过程分为两个阶段。在第一阶段，算法执行层次遍历，并且将所访问结点的指针和层次编号保存至队列。图1展示了算法在“层次遍历结束后”的情景（左图是基于存储结构的展示，右图是基于逻辑结构的展示）。
在第二阶段，利用双重while循环对底层队列的成员数组Qu.level[]进行“从左至右”的扫描。通过该过程，确定具有最大结点数的层次，而该层的结点数就是二叉树的宽度。
⑤ 其他解法介绍及比较。我们通过对一道算法阅读题进行修改，得到另一种解法（以下称算法2），将其作为对上述案例的补充。算法2的主要代码如下所示。
[ InitQueue（Q）;EnQueue（Q，bt）;
Width=1;LastWidth=1;CurrWidth=0;
while（Empty（Q）！=0）{
while（LastWidth！=0）{
DlQueue（Q，p）;visit（p->data）;
if（p->lchild）{EnQueue（Q，p->lchild）;CurrWidth++;}
if（p->rchild）{EnQueue（Q，p->rchild）;CurrWidth++;}
if（CurrWidth>Width）Width=CurrWidth;
LastWidth--; }
LastWidth=CurrWidth;CurrWidth=0;} ]
通过必要的注释以及图解（如图2所示），最终明确关键局部变量Width， LastWidth， CurrWidth的设置是算法2的最大亮点。其中，Width用于存储迄今为止所发现的“结点数量最多”一层的结点数。LastWidth表示当前层中尚未访问的结点数。当对于某一层的遍历结束而即将进入下一层时，CurrWidth表示下一层中待访问的结点数。
⑥ 课后思考与拓展练习。教师布置课后思考题，从而巩固课堂教学效果。
⑷ 结果呈现
除了培养学生算法设计和算法阅读能力之外，我们的另一个目标是通过引入对比教学法，加深学生对于两个算法核心设计思想的理解。具体做法是，教师从存储结构、算法执行、算法设计技巧和底层队列结构操作的角度进行示范对比（如表1所示），引导学生深入思考，进而潜移默化地影响学生的思维方式。
1.2.3 问题设计
为了在案例教学过程中创设情境、鼓励学生积极思考，以及引导讨论的方向，我们在过程描述部分各步骤中设置了多个问题（如表2）。同时要求这些问题涵盖引导性、分析性和开放性三种类型[6]。其中，引导性问题旨在引导学生回顾知识，促进达成理解与掌握知识的能力培养目标;分析性问题旨在培养学生设计和分析算法的能力;开放性问题旨在培养创新思维，形成解决实际问题的能力。
1.2.4 使用说明
本案例的适用对象是计算机科学与技术专业学生。适用课程是数据结构及后续进阶类课程。问题设计围绕对层次遍历算法的扩展而展开，使学生理解并掌握相关扩展技术。
1.3 案例应用
首先，明确教学目标及所含知识点。然后，针对每一个知识点，从案例情节、分析思路和理论依据的角度进行流程设计，从而实现教学目标。限于篇幅，省略了具体的流程设计。
2 结束语
本文研究了在数据结构课程中教师围绕复杂算法进行案例教学设计的问题。在案例教学实施过程中，始终遵循以问题为导向的原则，以掌握知识、培养算法设计与分析的能力和解决实际问题的能力为逐级递进的目标，在教学过程的各个阶段，精心设置有针对性的问题。通过将图解教学法和对比教学法融合于案例教学过程，实现了直观展示教师思维和影响学生思维方式的效果。本文案例的特点是讲授两个复杂算法，它们分别侧重于对算法的设计能力和阅读能力的培养。通过对算法进行多角度的对比，有利于促进学生思维方式的提升与锻造。
参考文献（References）：
[1] 张铭，耿国华，陈卫卫，等.数据结构与算法课程教学实施方案[J].中国大学教学，2011.3：56-60
[2] 谭定英，陈平平，刘慧玲.以问题为中心的案例教学法在数据结构与算法课程中的应用[J].计算机教育，2013.12：50-53
[3] 郑馨，江克勤，程玉胜.贪吃蛇游戏在线性数据结构中的案例教学[J].安庆师范大学学报（自然科学版），2018.24（4）：117-119，128
[4] 钱明辉，李天明，舒诗雅，等.教学案例开发框架模型的构建及其应用[J].管理案例研究与评论，2018.11（2）：210-220
[5] 王道论坛组编.2019年数据结构考研复习指导[M].北京：电子工业出版社，2018
[6] 严玲，陈雨薇，邓娇娇.以问题为导向的工作坊实践教学实施方式研究[J].现代大学教育，2016.5：94-103
转载注明来源:https://www.xzbu.com/8/view-15147994.htm
