探讨数据结构基于游戏竞赛平台“数据结构”课程设计教学方式征文

摘要：设计并应用一个五子棋竞赛平台，允许学生开发具有一定人工智能的五子棋引擎相互对抗。在追求对抗获胜的过程中，学生持续地评估和改进五子棋引擎的智能和性能，锻炼设计数据结构及算法解决实际问题的能力。设计并应用基于益智类游戏竞赛平台的“数据结构”课程设计实践教学模式，不但克服了传统“数据结构”课程设计实践过程中的一系列问题，显著提高了“数据结构”课程设计的实践教学效果，还可以推广应用于其他程序设计实践课程当中。
关键词：数据结构；五子棋竞赛平台；课程设计
作者简介：孙连山（1977-），男，黑龙江集贤人，陕西科技大学电气与信息工程学院，讲师；侯涛（1977-），男，陕西兴平人，陕西科技大学电气与信息工程学院，讲师。（陕西 西安 710021）
基金项目：本文系陕西科技大学教学改革研究项目（项目编号：11JG14）的研究成果。
1007-0079（2013）25-0135-02
“数据结构”是计算机专业的核心基础课程，上承程序设计语言、离散数学，下启操作系统、编译原理等课程，其重要性不言而喻。一方面，数据结构是计算机科学的基础理论，具有难度大，抽象层次高，概念繁杂等特点，学生很难掌握。另一方面，数据结构又是程序设计实践的核心基础，数组、链表、树、哈希表等数据结构是构成大多数软件系统的基本成分，而查找和排序算法则是大多数软件系统中都会应用到的最基本算法。“数据结构”的教学目标必须注意理论与实践并重，既培养学生掌握扎实的计算机科学基础理论，能够独立设计数据结构和算法，又要培育学生应用数据结构的理论知识解决实际问题的能力。除对应课堂内容的验证型实验之外，“数据结构”课程设计是培养学生应用数据结构理论解决实际问题能力的重要环节。“数据结构”课程设计通常为期2～3周，学生单独（或组队）完成具有一定规模的问题，并在此过程中分析对基本数据结构和算法的应用情况。

一、“数据结构”课程设计教学实践面临的问题

“数据结构”课程设计教学实践的目标虽好，但实际达到的效果却往往差强人意。下面分析笔者在开展“数据结构”课程设计实践教学过程中发现的一些问题。
首先，课程设计课题的问题规模通常比较大，学生技术储备不足。一方面，“数据结构”课程设计的题目必须具有一定的规模，区别于小型的单元实验。例如，单元实验可能要求学生实现针对链表的某些操作，而“数据结构”课程设计则可能要求学生综合运用数组、链表甚至散列表完成学生信息管理。这种较大规模的问题通常涉及较为复杂的人机交互，但是参与“数据结构”课程设计的学生往往是计算机相关专业的低年级学生，通常不具备分析实际问题并设计相应解决方案的能力。特别要指出的是，学生往往不具备熟练构造可用人机界面的能力。因此，学生往往投入大量精力学习新技术完成人机界面设计，而没有对数据结构本身给予应有的重视。
其次，现有课程设计课题库中的课题虽然能够提示学生应用某种数据结构，但通常非常无趣，无法激发学生的主动性。例如，学生信息管理系统、课程查询系统、订票系统等等都暗示学生管理一定的数据集合并进行查询。往往学生都将之实现为最简单的线性表或链表并辅以简单的查询和排序，草草完成课程设计，缺乏探索其他更复杂的数据结构和算法的用法的动力，这就致使“数据结构”课程设计的教学目标无法达成。
最后，为了充分发挥学生的创造性并防止抄袭，往往要求学生选择不同的课程设计课题。但一方面，同学之间很难相互对比和讨论，无法形成积极向上、相互促进的学习氛围。另一方面，很难比较不同的课程设计结果，教师很难客观地评价课程设计的完成情况。
总之，为了达到“数据结构”课程设计的教学目标，必须选择具有一定规模且能够充分发挥学生创造性的课题，必须设计相关的课程设计实施平台或工具。一方面实现特定的人机界面，帮助学生仅关注应用数据结构解决问题，另一方面帮助教师分析和评价学生掌握和应用数据结构基本理论和库函数完成课程设计的情况。

二、基于益智类游戏竞赛平台的“数据结构”课程设计教学方案

教学理论研究以及教学实践反馈均表明，学生主动学习的效果远较被动地接受老师灌输的效果好得多。若能充分调动学生的积极性和主动性，则“数据结构”课程设计教学实践中的很多问题将迎刃而解。为此，笔者学习并实践国外的先进教学研究成果，[3]抓住青年学生充满热情，勇于争先的天性，探索并将益智类游戏竞赛平台应用于“数据结构”课程设计教学实践当中，获得了良好的效果。具体来讲，源于：免费论文查重www.618jyw.com
笔者设计并应用一个五子棋竞赛平台，允许学生开发具有一定人工智能的五子棋引擎相互对抗，在追求对抗获胜的过程中，学生持续地评估和改进五子棋引擎的智能和性能，锻炼设计数据结构及算法解决实际问题的能力。较好地实现了教学目标。本节首先介绍五子棋竞赛平台的选择、设计和实现，其次介绍笔者在教学实践中应用该竞赛平台组织课程设计的具体措施并展示部分结果。

1.益智类游戏竞赛平台的选择、设计和实现

将益智类游戏竞赛平台应用于数据结构课程设计的关键是选择、设计和实现适当的游戏竞赛平台。游戏必须既通俗易懂，又充满趣味性和程序设计挑战性。通过与学生和同行的交流，笔者将五子棋游戏作为课程设计的课题。五子棋的棋盘可以建模为二维矩阵，五子棋引擎选择落子位置的过程是多次试探的过程。基于当前棋盘状态试探落子形成直接后继状态，称为一次试探。基于直接后继状态再次试探落子可称为二次试探。依此类推，五子棋引擎甚至可以进行任意次试探。显然，试探次数越多，状态树的深度越大，则五子棋的引擎越智能，但相应的五子棋引擎的实现难度和计算复杂性也越高。显然五子棋课题既具有趣味性又具有挑战性，既允许具有创造性和意愿的学生不断深化和探索，又不会让一般学生茫然无所适从，符合课程设计选题的需要。 整个竞赛平台的设计和实现均由高年级学生完成。一方面，这些学生均参加过“数据结构”课程设计实践，对课程设计的目的和方式比较了解。另一方面，这些学生正在学习可视化编程等技术，设计和实现五子棋竞赛平台对他们本身也是一种锻炼。采用这种方式，可以将不同层次学生的主动性和创造性充分发挥出来。另外，高年级学生构造可视化软件所展示出来的效果对低年级学生还具有一定的促进作用，激发低年级同学构造属于他们自己的更好的、更真实的软件系统。
如图1所示，竞赛平台本身将实现五子棋对弈的人机界面，维护棋局状态并管理对战信息，但其不包含五子棋引擎。竞赛平台将调用两个由学生独立开发和封装的五子棋引擎（已经封装为DLL）并协调二者进行对抗比赛。而两个相互对战的五子棋引擎之间并不存在直接的调用关系。竞赛平台将当前棋盘状态传给五子棋引擎1，五子棋引擎1评价棋盘状态并返回下一步落子的位置。五子棋竞赛平台更新棋盘状态，并将新棋盘状态传输给另一个五子棋引擎2，请求其评估和计算落子位置。这样，五子棋竞赛平台轮流调用由不同学生开发的五子棋引擎实现双方对抗。五子棋竞赛平台的主界面右侧是一张19*19的网格，左侧是一些按钮实现部分竞赛管理操作，如设置玩家、悔棋、暂停、单步执行、英雄榜等等。竞赛平台的界面开发非常简单，学生可采用集成开发工具提供的可视化界面设计工具能够很快实现主界面。

2.基于五子棋竞赛平台的课程设计组织和管理

笔者在开展“数据结构”课程设计教学的连续两个学年当中构思并实现了本文提出的课程设计实践教学模式。笔者基于前一学年的教学实践发现问题并形成解决方案。
为促动学生接受五子棋作为课程设计项目，对编写人工智能程序对抗产生兴趣，笔者在开始进行数据课程设计之前的两个月，就结合“数据结构”课堂教学分析和讨论数据结构在棋类游戏设计和实现当中的作用。为了激发学生的积极性，突出对抗性，笔者还组织集中答辩，即举行机器人五子棋锦标赛，从胜率、拟人程度、算法效率等多个方面评价对战效果，生成英雄榜。胜率体现了五子棋引擎的智能，拟人程度则体现为对战招法的多样性，算法效率则体现为基于复杂盘面落子所需的时间。英雄榜则促动学生不断改进程序代码，追求荣誉。为了使学生重视和源于：论文 格式www.618jyw.com
学习数据结构在编制五子棋引擎当中的作用，笔者要求学生明确地分析其五子棋引擎使用已有数据结构及算法的类型和比例，形成课程设计报告。为了成功地将五子棋竞赛平台应用到课程设计当中，必须明确规定学生必须满足的技术约束。五子棋竞赛平台需通过特定的接口才能调用学生编写的五子棋引擎，即学生设计的五子棋引擎必须实现相应的接口，必须按照给定的模板封装成为动态链接库。五子棋引擎只需实现一个接口函数MakeMove。
extern "C" int __declspec（dllexport） MakeMove（int * nRow，int * nCol，int Matrix[19][19]）.
其中，Matrix[NROW][NCOL]表示一个棋局的当前状态，NROW和NCOL分别表示棋局的总行数和总列数，nRow和nCol分别表示五子棋引擎评估当前的棋局Matrix之后拟落子位置的行列坐标。MakeMove的返回值则表示对当前棋局的评估是否成功的状态信息。

三、效果和需要注意的问题

实际应用益智类游戏竞赛平台开展“数据结构”课程设计教学的效果良好，克服了传统课程设计教学模式的问题，促进了学生的积极性和主动性。
首先，五子棋竞赛平台提供了人机（机机）对弈的界面，低年级同学可关注于数据结构在实现五子棋引擎中的作用，而不必在提前自学界面开发技术上浪费精力（到高年级将会系统地学习）。
其次，五子棋规则清晰，易学难精，学生对于能够开发五子棋游戏机器人挑战人类智慧兴趣盎然。
再次，五子棋竞赛平台允许学生各自开发五子棋引擎相会对战，促使学生不断改进代码，学习和应用数据结构理论知识。
最后，对于教师而言，基于五子棋引擎的智能、性能、拟人度等指标能够比较客观地评价不同学生完成课程设计的情况，基于学生的课程设计报告可以评价学生对数据结构理论知识的掌握和应用情况。
在开展基于益智类游戏竞赛平台的“数据结构”课程设计模式的过程中，需要特别注意几个问题。第一，必须注意学生的编程基础薄弱的现实，并进行必要的编程基础技术补充教学。第二，必须注意学生的分组规则。笔者将学生分成每两人一组，如每组包含人数较多，则可能导致部分学生的实际参与程度下降。第三，必须注意课题设计题目以及分组的确定要早于课程设计的实际开始时间，给学生充分的课外时间思考和准备。此外，可开展竞赛解说和录像等活动，进一步推动学生的积极性（此活动笔者未开展，事后学生建议开展）。
四、结语
本文分析了“数据结构”课程设计教学实践中的典型问题，并提出了应用益智类游戏竞赛平台解决相应问题的思路。本文具体介绍了设计、开发和应用五子棋竞赛平台的方式和将其应用于“数据结构”课程设计教学的具体方式。实践应用表明基于益智类游戏竞赛平台的“数据结构”课程设计模式实际可行且效果良好。
参考文献：
严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，
2008.
[美]柯奈汉·派克.程学设计实践[M].裘宗燕，译.北京：机械工业出版社，2006.
[3]Ramon Lawrence. Teaching Data Structures Using Competitive Games[J].IEEE TRANSACTIONS ON EDUCATION，2004，47（4）：459-466.
（责任编辑：王意琴）