游戏在《数据结构》课堂教学中的应用

摘要：折半查找算法是《数据结构》课程的一个重要算法，讲授时通过引入“猜价格”游戏以及形象、直观的动画演示来调动学生学习的兴趣点和积极性，营造良好的学习氛围。对学生学习满意度的调查结果表明，游戏融入折半查找算法教学具有事半功倍的效果。

关键词：折半查找算法；游戏；动画

中图分类号：TP3          文献标识码：A

文章编号：1009-3044（2022）33-0177-04

随着计算机应用领域的不断扩大，人们对数据结构的重视程度空前高涨。《数据结构》课程中的排序、查找算法是经典的、重点的算法。然而非常枯燥，教师难讲，学生课程也缺乏兴趣[1]。如果将教学与游戏巧妙地结合，对折半查找算法的教学将会是一个不错的教学思路。

1游戏对折半查找算法教学的适用性分析

1.1 游戏融入教学可以模拟实际的场景，使学生对知识的理解更深入

通过游戏可以将复杂、枯燥的知识通过形象的模拟来进行展示，使学生对折半查找算法的印象更深刻、理解更深入，进而为后续的算法实现环节打下良好的基础。

1.2 开拓学生的创新思维

在计算机发展日新月异的今天，为了满足 IT 企业的需求，适应市场需要，计算机专业必须开拓学生的创新思维。游戏的引入，可以使整个教学过程趣味性十足，学生发挥的想象力可以得到充分地发挥，进而可以开拓学生的创新思维[2]。

2折半查找算法的教学设计

2.1折半查找算法的基本思想

对已按关键字排序的序列，首先用待查找数据与数列中间元素比较，如果相等，则查找成功；如果不相等，则根据比较结果，来确定后续查找在哪半边进行，以此类推，直到查找成功，或者找不到待查找数据为止[3]。

2.1.1折半查找算法的基本思路

单纯文字描述算法思想不够直观，我们举例如下：已知如下 11 个数据元素的数组（6， 13， 19， 23， 37， 58， 64， 75， 82， 88， 92），现要查找关键字data为 23 和 85的元素。Low：查找区间的下界， high：查找区间的上界，mid：查找区间的中间位置，mid=（low+high）/2。

（1） k=23 的折半查找过程，如下所示：

① [1，11]，mid=6，23<58， high=mid-1;

② [1，5]，mid=3，23>19，low=mid+1;

③ [4，5]， mid=4，23=23，查找成功;

（2） k=85 的折半查找过程，如下所示：

① [1，11]，mid=6，58<85，low=mid+1;

② [7，11]，mid=9，82<85，low=mid+1;

③ [10，11]，mid=10，88>85，high=mid-1;

④ [10，9]low>high，查找失败；

2.1.2折半查找算法的实现

算法描述：

1）输入：待查找关键字data；

2）输出：若匹配成功，输出满足条件的数据元素下标；否则；输出“查找失败”；

3）运算过程：

a）计算中间值

mid=（low+high）/2；

b）移动操作：若 data<array[mid]，high 指向 mid 前一个元素，即high=mid-1；若data>array[mid]，low=mid+1；

c）循环条件：low<=high；

d）结束条件：data=arrray[mid]或low>high；

根据以上算法的关键点分析，通过C 语言程序实现折半查找算法：

#include<stdio.h>

int main（）

{

int array[11]={5，13，19，21，37，56，64，75，80，88，92}，low，high，mid，data;

printf（"请输入待查找的数："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

printf（"查找成功！%d在第%d个位置＼n"，data，mid+1）;

break;

}

else if（data<array[mid]）

high=mid-1;

else

low=mid+1;

}

if（low>high）

printf（"查找失败！＼n"）;

return 0;

}

2.1.3折半查找算法实现过程中常见问题分析

在算法实现过程中，移动操作环节是关键；若 data<array[mid]，high 指向 mid 前一个元素，即high=mid-1；若data>array[mid]，low=mid+1;可是有些同学容易遗漏移动操作，编写出如下的程序 [5]：

#include<stdio.h>

int main（）

{

int array[11]={5，13，19，21，37，56，64，75，80，88，92}，low，high，mid，data;

printf（"请输入待查找的数："）;

scanf（"%d"，&data）;

low=0;

high=10;

while（low<=high）

{

mid=（low+high）/2;

if（data==array[mid]）

{

printf（"查找成功！%d在第%d个位置＼n"，data，mid+1）;

break;

}

else if（data<array[mid]）

high=mid;

else

low=mid;

}

if（low>high）

printf（"查找失败！＼n"）;

return 0;

}

若按上面程序执行，会产生两个问题：一是当待查找关键字 data 不存在时，low<=high 永远成立，查找过程将永不停歇；其二是若查找关键字 data=6或者data=92，查找过程则陷入死循环，又无法找到正确的位置，这就需要教师们在教学过程中反复强调移动操作的重要性。

2.2 教学目标

知识目标：掌握可以实现折半查找的两个前提以及折半查找的基本思想；

能力目标：具备一定的逻辑思维能力和从具体问题中提炼出算法的能力；

操作性目标： 能通过计算机语言编写程序实现折半查找算法；

情感目标： 提升学生参与意识，培养学生自主探索问题的能力，让学生在自主探究的过程中深刻感受算法思想在解决实际问题时的重要性和魅力，以激发学生的学习热情。

2.3教材分析

教学重点：折半查找算法的基本思想；

教学难点：由折半查找算法思想到程序代码的转换。

2.4学情分析

学习对象是计算机科学与技术学院大一新生，同学们对数组的相关知识和顺序查找算法已经有一定的认识。但由于刚接触编程，对编程积极性不够高，基础相对欠缺，加上折半查找算法逻辑性比较强。所以在教学过程中应尽量想办法调动学生学习的兴趣点和积极性。

2.5教学策略

首先，寓教于乐，通过精心设计的“猜价格”游戏来调动学生的学习积极性和兴趣点，启发学生去探索游戏背后的科学原理；另外，通过算法动画的展示，将游戏环节中的猜价格方法进一步提升到算法原理中，可以激发学生学习编程的热情，也可以为后续的算法实现环节打下良好的基础。

2.6教学方法

本课采用游戏体验法、动画直观演示法和启发式教学法三种方法相结合的方式来完成。

2.7教学过程设计

首先，通过对前一节顺序查找内容的回顾，总结出顺序查找的优缺点；然后，通过一个“猜价格”游戏暖场，引导学生去探索游戏背后的科学原理，进而导入新课；接下来结合一个具体的案例，配合动画详细讲解折半查找的基本原理。然后，提炼出折半查找算法，绘制出折半查找算法的流程图，并设计出动画效果，使流程图当中的每一步都有与之对应的代码同步出现。相信，通过这种方法来完成算法实现这一环节的讲解，可以让同学们更清晰、更透彻地理解算法代码，并且可以激发学生对编程的热情和信心。随后，对本节课的内容进行总结，提醒学生本节课应该注意的关键点。再通过一道思考题，让学生更深刻地去感受折半查找在实际生活的用途和高效性，最后，布置作业让学生对本节课的知识进行巩固。

2.8多媒体课件设计的重要性

老师们进行教学设计时，往往都会对知识导入、教学目标（包含知识目标、能力目标、情感目标、操作目标等）、教学重点与难点、教学策略等方面耗费大量的时间与精力，却忽略多媒体课件的设计，然而课件的色彩搭配、动画效果、视频等往往会给学生带来一场非常震撼的视觉盛宴，进而吸引学生的注意力，使教学效果事半功倍。

2.9 《折半查找算法》教学设计的依据

由于学生的基础不同，理解问题的能力也参差不齐，《数据结构》课程内容又非常枯燥，要想提高学生学习的积极性与主动性，就必须改变过去以教师为中心“满堂灌”的教学模式。针对《数据结构》课程的特点，考虑到学习对象是大一新生，缺乏足够的编程热情、好奇心强、活泼、爱玩等实际情况，结合折半查找算法的教学目标，决定采用游戏体验法、动画直观演示法和启发式教学法三种方法相结合的方式来完成折半查找算法的教学。首先，通过游戏暖场可以让学生积极参与到课堂中来，以最大限度地激发学生的学习热情。接着，运用启发式教学引入本节课的主题——折半查找。然后，结合一个具体的实例配合形象、直观的动画展示出折半查找算法的基本思想及其实现的详细过程，将游戏环节中的“猜价格”方法进一步融合到折半查找算法原理中，一定可以激发学生学习的热情和信心。

2.10 教学效果调查

2.10.1 调查问卷和测试

为了调查此教学设计的效果，老师通过在问卷星上发布问卷，让学生填写自己对这一节课的感受和各项教学目标达成度，并对老师的教学方法提出相应的意见和建议。 通过问卷星平台反馈结果可以看出，90% 以上的学生认为本次课堂注意力高度集中，学习兴趣浓厚，对用折半查找算法实现课后作业非常有信心。随后，对学生进行折半查找算法知识的测试。结果证实， 85%以上的学生成绩达到优秀。调查结果表明，游戏融入本节课的教学，收到了良好的教学效果。