贪吃蛇游戏在线性数据结构中的案例教学

郑 馨，江克勤，程玉胜

（安庆师范大学计算机与信息学院，安徽安庆246133）

数据结构课程在计算机科学与技术专业课程体系中占据非常重要的地位，是程序设计、操作系统、数据库管理系统、软件工程、编译原理、人工智能等后续课程的基础。数据结构课程是一门理论与实践并重的综合性很强的课程[1]，在教学上存在诸多难点。如果采用传统的“课堂集中教学+机房实践”的教学模式[2]，不但教师感到枯燥乏味，而且无法提高学生的积极性。将案例教学法[3]引入数据结构课程中，选择并设计趣味性强、难易适中、与生活紧密结合的案例，引导学生在具体情境中主动思考、积极讨论，可以明显改善教学效果。在数据结构中，线性表、栈和队列等线性结构[4]在内容上紧密连接、环环相扣；同时，线性结构又是学生在数据结构中接触到的第一类逻辑结构，也是后续非线性结构的基础，理解并掌握线性结构的逻辑结构与物理结构，对后续数据结构和算法的学习具有非常重要的意义。如果能在线性结构教学中调动学生的学习兴趣，那么后续的学习无疑将事半功倍。然而，在现有的案例教学中，通常采用对每一种数据结构分别设计相应的案例方式，并没有充分考虑不同数据结构之前的关联，特别是线性结构之间的紧密联系。鉴于此，本文就数据结构的线性结构进行深入研究，对该部分的案例教学模式进行探索。

1 以贪吃蛇游戏设计为案例的教学实施过程

贪吃蛇是一款经典的休闲益智类手游，玩家通过上下左右控制蛇头的方向寻找随机出现的食物不断增加贪吃蛇的长度。贪吃蛇存在唯一一个蛇头和蛇尾，除蛇头和蛇尾外，蛇身中每个节点均有且仅有一个前驱和后继，因此，贪吃蛇其实就是一种典型的线性结构。线性表和队列这两类线性结构的顺序存储表示和链式存储表示都可以作为贪吃蛇的结构体，然而，每种数据结构的具体实现过程各不相同，算法效率也有明显差异。如果能引导学生自己分析、讨论并动手实践，最终完成贪吃蛇游戏设计，可以将枯燥的教学转化为快乐的教与学过程；同时，以贪吃蛇游戏这条主线串联顺序表、单链表、循环队列和链队这些线性结构，既跳出了章节的限制，又把握了线性结构的主脉络，还起到了及时复习巩固作用；同时，提倡一题多解，鼓励学生自主学习，开拓学生创新思维。

本文设计的案例涉及顺序表、单链表、循环队列和链队列这4种线性结构。在具体的教学实施过程中，采用由浅入深、与教材章节同步的方式，通过数据结构知识讲解、贪吃蛇关键算法实现、代码解析、算法性能比较分析等步骤对该教学方式予以实施，如图1所示。

图1 以贪吃蛇游戏设计为案例的教学实施流程

为了实现更佳的教学效果，将贪吃蛇游戏简化为贪吃蛇结构体、蛇移动操作和吃食物操作的实现，可以使学生忽略繁杂的界面设计等编程问题，而专注于数据结构和算法的设计。在讲述每个线性结构相关知识之前，先通过贪吃蛇游戏演示，让学生从数据结构的角度重新看待贪吃蛇问题，引导学生思考贪吃蛇的结构如何实现、贪吃蛇移动的过程是怎样的、贪吃蛇怎样吃食物，让学生带着问题学习线性结构的结构体定义与基本操作等相关知识。介绍完一个线性结构后，立即启发学生讨论如何利用该数据结构设计贪吃蛇的结构体，以及如何实现贪吃蛇移动的操作，并分析算法的时间复杂度，直至所有线性结构都讨论完毕后得到最佳的实现方案。

2 顺序表实现贪吃蛇

顺序表是采用顺序存储结构存储的线性表，利用一组地址连续的存储单元依次存储线性表的数据元素，逻辑上相邻的数据元素，其物理地址也相邻。由于贪吃蛇的每一个结点是连续的，每个结点可以视作一个数据元素，因此，利用顺序表实现贪吃蛇是非常直观的：蛇头即表头，蛇尾即表尾。由于贪吃蛇能够在一个二维平面上移动，因此这里的数据元素不再仅仅是一个整型或字符型，而必须包含每个结点的横、纵轴坐标。同时，顺序表表示贪吃蛇移动的过程，也与顺序表插入运算中的元素依次后移有异曲同工之妙。除了蛇头结点移动的位置是由上下左右4个方向键控制之外，从蛇头之后的结点直至最后一个结点均依次移动到它前一个结点的位置上。而顺序表表示的贪吃蛇吃食物的过程，则与顺序表在第一个位置插入元素的运算完全相同。因此，顺序表实现贪吃蛇时，移动和吃食物的时间复杂度都是O(n)。

首先，通过动画可以快速启发学生将贪吃蛇抽象为顺序表，将贪吃蛇移动和吃食物的动作抽象为顺序表的插入运算。要求学生参照书中顺序表的结构体给出贪吃蛇的结构体。鼓励学生给出多种结构体并进行对比分析；令学生自行投票，选出最受欢迎、最简洁的结构体表示。接着，让学生自己分析得出蛇移动和吃食物的关键步骤，将其与顺序表插入运算进行对比以发现相似之处，再引导学生参照插入运算仿写出该段关键代码。然后，结合顺序表表示的贪吃蛇结构体给出实现该步骤的示例代码，并带领学生一一解读。解读时，可以将该代码与往届学生写出的代码进行形式上和内容上的对比，既让学生从模仿开始养成良好的编程习惯，又使学生从工程上理解即使同一个算法的实现过程也有高效和低效之分。最后，让学生得出移动和吃食物算法的时间复杂度，再次说明顺序表在频繁插入运算中的劣势。

3 单链表实现贪吃蛇

单链表是采用链式存储结构存储的线性表。单链表的特点是用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的。因此，单链表中结点的逻辑顺序和物理顺序不一定相同。顺序表需预先分配好足够大的连续存储空间，即静态分配；而单链表支持动态分配，即在需要新的结点时再分配空间，因而更灵活。

单链表表示的贪吃蛇结点包括两个域：数据域用来存储结点的横、纵轴坐标，指针域用来存储数据元素的直接后继结点的位置。单链表表示的贪吃蛇正是通过每个结点的指针域将贪吃蛇身上的n个结点按其逻辑顺序链接在一起的。用单链表实现贪吃蛇移动的关键在于完成前驱结点与当前结点的坐标传递，其余步骤与顺序表实现贪吃蛇的过程一致，时间复杂度也是O(n)。单链表实现贪吃蛇吃食物的操作则比顺序表简单得多，与单链表插入操作完全一致，时间复杂度仅为O(1)。

单链表实现贪吃蛇重在对比单链表和顺序表的异同，帮助学生从结构体到具体运算步骤上理解二者的差异。首先，仍然通过动画启发学生将贪吃蛇抽象为单链表，重点体现每个结点在内存中的变化，让学生更直观地理解单链表结点，特别是指针的含义。然后，让学生仿照书中单链表结点的类型定义，修改先前顺序表表示的贪吃蛇的结构体，进而得到单链表表示的贪吃蛇结构体。通过比较结构体，再次阐述顺序表和单链表的不同。接着，让学生在先前顺序表实现贪吃蛇移动和吃食物的函数的基础上，指出该移动函数中需要修改的语句并尝试修改，紧接着给出修改后的参考代码。通过解读关键代码，从具体操作上深入对比线性表和单链表的异同。通过分析线性表和单链表实现贪吃蛇移动算法的时间复杂度，从算法效率上将二者再次进行对比。最后，再次演示动画，让学生仔细观察蛇移动过程中实际变化的结点，既为后续线性结构设置悬念，激发学习兴趣，又可以锻练学生的主动思维能力。

4 循环队列实现贪吃蛇

循环队列是队列的一种顺序表示和实现方法。队列是一种限定性的线性表，限定插入在队尾进行，删除在队头进行。队列的操作具有先进先出（Fist In Fist Out，FIFO）的特征。而贪吃蛇移动的过程就是不断将蛇尾结点移至蛇头处，即蛇尾结点出队，新蛇头结点入队。因此，实际上贪吃蛇仅有两个结点的位置发生了变化，而并不需要移动所有的结点。因此贪吃蛇就是典型的队列结构，只不过队头应设置在蛇尾，而蛇头实际上是队尾。在队列的顺序存储结构中，用一组地址连续的存储单元依次存放从队头到队尾的元素。由于队列中队头和队尾的位置是可变的，因此需要设置队头和队尾两个指针。为了克服“假上溢”现象，可以将顺序队列的数组看成一个首尾相接的圆环，即循环队列。用循环队列实现贪吃蛇的移动操作比顺序表和单链表都要快捷，时间复杂度仅为O(1)。

首先，揭秘在单链表实现贪吃蛇时设置的悬念，通过再次演示动画，重在突出变化的结点，揭示贪吃蛇移动的实质就是蛇尾结点出队、新蛇头结点入队的过程；用循环队列实现贪吃蛇吃食物的操作，就是新蛇头结点入队的过程。接着，令学生参照书中循环队列的结构体和入队、出队算法，再次改写贪吃蛇移动和吃食物的函数。然后，给出示例代码并解读，重点放在突出队尾指针和队头指针循环变化上。最后，通过分析时间复杂度，就贪吃蛇游戏设计问题将循环队列与顺序表和单链表的优劣进行对比，反复强化不同线性结构的相关算法在学生脑海中的印象。

5 链队列实现贪吃蛇

链队列是队列的链式存储结构的简称。从结构性上考虑，通常将队头指针和队尾指针封装在一个结构中。链队列与循环队列在逻辑结构上同属队列，因此，在贪吃蛇移动和吃食物的算法上几乎相同，仍是蛇尾结点出队、新蛇头结点入队的过程，其时间复杂度均为O(1)；链队列与单链表在物理结构上同属链式存储结构，因此，在贪吃蛇移动和吃食物操作的具体代码实现上十分相似，链队列入队和出队操作的本质仍然是单链表结点的插入和删除操作。因此，该部分的讲解重点放在与单链表实现贪吃蛇的对比上。

由于已经实现了单链表和循环队列实现贪吃蛇的过程，学生对线性结构的相关知识也有了一定程度的掌握，因此，不妨将链队列实现贪吃蛇的过程放在实验课上，让学生通过自主学习予以实现。通过学生自行阅读代码、理解代码、运行结果、编写代码、调试代码，反复进行上述步骤，让学生自己在编码中找到乐趣，发现解决问题的快乐。由于学生编程能力参差不齐，为了使所有学生都能专注于数据结构中的关键操作，并尽可能在课堂的有限时间内获得最大的收获，可以预先实现顺序表、单链表和循环链表实现贪吃蛇的全部代码供学生参考，仅预留链队列的关键算法让学生填充，让学生体会到自己编写代码并成功解决实际问题的乐趣，同时还可以方便教学检查。

6 结束语

本案例教学实践精心设计了贪吃蛇游戏作为案例导入，充分体现了线性数据结构知识体系的完整性、连续性和继承性。通过分别利用顺序表、单链表、循环队列和链队列实现贪吃蛇的关键操作，以一根主线串联多个章节，将不同章节的共同点凝练出来，跳出了章节划分的限制。通过一题多解，启发学生从不同角度、不同思路、利用不同数据结构，解决同一个问题，从而锻炼学生的创造性思维。对同类逻辑结构之间、同类存储结构之间反复对比，使学生可以深入理解与吃透每个章节的重要概念与重要算法。通过简化的贪吃蛇游戏，充分调动学生的学习热情。贪吃蛇是一款经典的手游，既具有较强趣味性和启发性，又为大多数学生所熟悉，以该游戏为例更能引起共鸣，从初接触数据结构开始即产生好奇心及学习相关知识的欲望。在简化贪吃蛇实现过程后，通过设计代码填空，既可以使学生消除畏难情绪，勇于动手编程，又有利于抓住本质，重点难点精讲。合理使用多种现代化教学手段，将书中抽象枯燥的静态文字转化为形象生动的动画效果，立体化、全方位将不同知识点直观地展现给学生，帮助学生更好地理解并消化知识，从而提升教学效果。