基于游戲競賽平臺的“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)模式

摘要：設(shè)計并應(yīng)用一個五子棋競賽平臺，允許學(xué)生開發(fā)具有一定人工智能的五子棋引擎相互對抗。在追求對抗獲勝的過程中，學(xué)生持續(xù)地評估和改進(jìn)五子棋引擎的智能和性能，鍛煉設(shè)計數(shù)據(jù)結(jié)構(gòu)及算法解決實(shí)際問題的能力。設(shè)計并應(yīng)用基于益智類游戲競賽平臺的“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計實(shí)踐教學(xué)模式，不但克服了傳統(tǒng)“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計實(shí)踐過程中的一系列問題，顯著提高了“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計的實(shí)踐教學(xué)效果，還可以推廣應(yīng)用于其他程序設(shè)計實(shí)踐課程當(dāng)中。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；五子棋競賽平臺；課程設(shè)計

作者簡介：孫連山（1977-），男，黑龍江集賢人，陜西科技大學(xué)電氣與信息工程學(xué)院，講師；侯濤（1977-），男，陜西興平人，陜西科技大學(xué)電氣與信息工程學(xué)院，講師。（陜西 西安 710021）

基金項目：本文系陜西科技大學(xué)教學(xué)改革研究項目（項目編號：11JG14）的研究成果。

中圖分類號：G642.0 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-0079（2013）25-0135-02

“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)專業(yè)的核心基礎(chǔ)課程，上承程序設(shè)計語言、離散數(shù)學(xué)，下啟操作系統(tǒng)、編譯原理等課程，其重要性不言而喻。一方面，數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)的基礎(chǔ)理論，具有難度大，抽象層次高，概念繁雜等特點(diǎn)，學(xué)生很難掌握。[1]另一方面，數(shù)據(jù)結(jié)構(gòu)又是程序設(shè)計實(shí)踐的核心基礎(chǔ)，數(shù)組、鏈表、樹、哈希表等數(shù)據(jù)結(jié)構(gòu)是構(gòu)成大多數(shù)軟件系統(tǒng)的基本成分，而查找和排序算法則是大多數(shù)軟件系統(tǒng)中都會應(yīng)用到的最基本算法。[2]“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)目標(biāo)必須注意理論與實(shí)踐并重，既培養(yǎng)學(xué)生掌握扎實(shí)的計算機(jī)科學(xué)基礎(chǔ)理論，能夠獨(dú)立設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法，又要培育學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)的理論知識解決實(shí)際問題的能力。除對應(yīng)課堂內(nèi)容的驗證型實(shí)驗之外，“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計是培養(yǎng)學(xué)生應(yīng)用數(shù)據(jù)結(jié)構(gòu)理論解決實(shí)際問題能力的重要環(huán)節(jié)。“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計通常為期2～3周，學(xué)生單獨(dú)（或組隊）完成具有一定規(guī)模的問題，并在此過程中分析對基本數(shù)據(jù)結(jié)構(gòu)和算法的應(yīng)用情況。

一、“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)實(shí)踐面臨的問題

“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)實(shí)踐的目標(biāo)雖好，但實(shí)際達(dá)到的效果卻往往差強(qiáng)人意。下面分析筆者在開展“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計實(shí)踐教學(xué)過程中發(fā)現(xiàn)的一些問題。

首先，課程設(shè)計課題的問題規(guī)模通常比較大，學(xué)生技術(shù)儲備不足。一方面，“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計的題目必須具有一定的規(guī)模，區(qū)別于小型的單元實(shí)驗。例如，單元實(shí)驗可能要求學(xué)生實(shí)現(xiàn)針對鏈表的某些操作，而“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計則可能要求學(xué)生綜合運(yùn)用數(shù)組、鏈表甚至散列表完成學(xué)生信息管理。這種較大規(guī)模的問題通常涉及較為復(fù)雜的人機(jī)交互，但是參與“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計的學(xué)生往往是計算機(jī)相關(guān)專業(yè)的低年級學(xué)生，通常不具備分析實(shí)際問題并設(shè)計相應(yīng)解決方案的能力。特別要指出的是，學(xué)生往往不具備熟練構(gòu)造可用人機(jī)界面的能力。因此，學(xué)生往往投入大量精力學(xué)習(xí)新技術(shù)完成人機(jī)界面設(shè)計，而沒有對數(shù)據(jù)結(jié)構(gòu)本身給予應(yīng)有的重視。

其次，現(xiàn)有課程設(shè)計課題庫中的課題雖然能夠提示學(xué)生應(yīng)用某種數(shù)據(jù)結(jié)構(gòu)，但通常非常無趣，無法激發(fā)學(xué)生的主動性。例如，學(xué)生信息管理系統(tǒng)、課程查詢系統(tǒng)、訂票系統(tǒng)等等都暗示學(xué)生管理一定的數(shù)據(jù)集合并進(jìn)行查詢。往往學(xué)生都將之實(shí)現(xiàn)為最簡單的線性表或鏈表并輔以簡單的查詢和排序，草草完成課程設(shè)計，缺乏探索其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和算法的用法的動力，這就致使“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計的教學(xué)目標(biāo)無法達(dá)成。

最后，為了充分發(fā)揮學(xué)生的創(chuàng)造性并防止抄襲，往往要求學(xué)生選擇不同的課程設(shè)計課題。但一方面，同學(xué)之間很難相互對比和討論，無法形成積極向上、相互促進(jìn)的學(xué)習(xí)氛圍。另一方面，很難比較不同的課程設(shè)計結(jié)果，教師很難客觀地評價課程設(shè)計的完成情況。

總之，為了達(dá)到“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計的教學(xué)目標(biāo)，必須選擇具有一定規(guī)模且能夠充分發(fā)揮學(xué)生創(chuàng)造性的課題，必須設(shè)計相關(guān)的課程設(shè)計實(shí)施平臺或工具。一方面實(shí)現(xiàn)特定的人機(jī)界面，幫助學(xué)生僅關(guān)注應(yīng)用數(shù)據(jù)結(jié)構(gòu)解決問題，另一方面幫助教師分析和評價學(xué)生掌握和應(yīng)用數(shù)據(jù)結(jié)構(gòu)基本理論和庫函數(shù)完成課程設(shè)計的情況。

二、基于益智類游戲競賽平臺的“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)方案

教學(xué)理論研究以及教學(xué)實(shí)踐反饋均表明，學(xué)生主動學(xué)習(xí)的效果遠(yuǎn)較被動地接受老師灌輸?shù)男Ч玫枚唷Ｈ裟艹浞终{(diào)動學(xué)生的積極性和主動性，則“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)實(shí)踐中的很多問題將迎刃而解。為此，筆者學(xué)習(xí)并實(shí)踐國外的先進(jìn)教學(xué)研究成果，[3]抓住青年學(xué)生充滿熱情，勇于爭先的天性，探索并將益智類游戲競賽平臺應(yīng)用于“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)實(shí)踐當(dāng)中，獲得了良好的效果。具體來講，筆者設(shè)計并應(yīng)用一個五子棋競賽平臺，允許學(xué)生開發(fā)具有一定人工智能的五子棋引擎相互對抗，在追求對抗獲勝的過程中，學(xué)生持續(xù)地評估和改進(jìn)五子棋引擎的智能和性能，鍛煉設(shè)計數(shù)據(jù)結(jié)構(gòu)及算法解決實(shí)際問題的能力。較好地實(shí)現(xiàn)了教學(xué)目標(biāo)。本節(jié)首先介紹五子棋競賽平臺的選擇、設(shè)計和實(shí)現(xiàn)，其次介紹筆者在教學(xué)實(shí)踐中應(yīng)用該競賽平臺組織課程設(shè)計的具體措施并展示部分結(jié)果。

1.益智類游戲競賽平臺的選擇、設(shè)計和實(shí)現(xiàn)

將益智類游戲競賽平臺應(yīng)用于數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的關(guān)鍵是選擇、設(shè)計和實(shí)現(xiàn)適當(dāng)?shù)挠螒蚋傎惼脚_。游戲必須既通俗易懂，又充滿趣味性和程序設(shè)計挑戰(zhàn)性。通過與學(xué)生和同行的交流，筆者將五子棋游戲作為課程設(shè)計的課題。五子棋的棋盤可以建模為二維矩陣，五子棋引擎選擇落子位置的過程是多次試探的過程。基于當(dāng)前棋盤狀態(tài)試探落子形成直接后繼狀態(tài)，稱為一次試探。基于直接后繼狀態(tài)再次試探落子可稱為二次試探。依此類推，五子棋引擎甚至可以進(jìn)行任意次試探。顯然，試探次數(shù)越多，狀態(tài)樹的深度越大，則五子棋的引擎越智能，但相應(yīng)的五子棋引擎的實(shí)現(xiàn)難度和計算復(fù)雜性也越高。顯然五子棋課題既具有趣味性又具有挑戰(zhàn)性，既允許具有創(chuàng)造性和意愿的學(xué)生不斷深化和探索，又不會讓一般學(xué)生茫然無所適從，符合課程設(shè)計選題的需要。

整個競賽平臺的設(shè)計和實(shí)現(xiàn)均由高年級學(xué)生完成。一方面，這些學(xué)生均參加過“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計實(shí)踐，對課程設(shè)計的目的和方式比較了解。另一方面，這些學(xué)生正在學(xué)習(xí)可視化編程等技術(shù)，設(shè)計和實(shí)現(xiàn)五子棋競賽平臺對他們本身也是一種鍛煉。采用這種方式，可以將不同層次學(xué)生的主動性和創(chuàng)造性充分發(fā)揮出來。另外，高年級學(xué)生構(gòu)造可視化軟件所展示出來的效果對低年級學(xué)生還具有一定的促進(jìn)作用，激發(fā)低年級同學(xué)構(gòu)造屬于他們自己的更好的、更真實(shí)的軟件系統(tǒng)。

如圖1所示，競賽平臺本身將實(shí)現(xiàn)五子棋對弈的人機(jī)界面，維護(hù)棋局狀態(tài)并管理對戰(zhàn)信息，但其不包含五子棋引擎。競賽平臺將調(diào)用兩個由學(xué)生獨(dú)立開發(fā)和封裝的五子棋引擎（已經(jīng)封裝為DLL）并協(xié)調(diào)二者進(jìn)行對抗比賽。而兩個相互對戰(zhàn)的五子棋引擎之間并不存在直接的調(diào)用關(guān)系。競賽平臺將當(dāng)前棋盤狀態(tài)傳給五子棋引擎1，五子棋引擎1評價棋盤狀態(tài)并返回下一步落子的位置。五子棋競賽平臺更新棋盤狀態(tài)，并將新棋盤狀態(tài)傳輸給另一個五子棋引擎2，請求其評估和計算落子位置。這樣，五子棋競賽平臺輪流調(diào)用由不同學(xué)生開發(fā)的五子棋引擎實(shí)現(xiàn)雙方對抗。五子棋競賽平臺的主界面右側(cè)是一張19*19的網(wǎng)格，左側(cè)是一些按鈕實(shí)現(xiàn)部分競賽管理操作，如設(shè)置玩家、悔棋、暫停、單步執(zhí)行、英雄榜等等。競賽平臺的界面開發(fā)非常簡單，學(xué)生可采用集成開發(fā)工具提供的可視化界面設(shè)計工具能夠很快實(shí)現(xiàn)主界面。

2.基于五子棋競賽平臺的課程設(shè)計組織和管理

筆者在開展“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)的連續(xù)兩個學(xué)年當(dāng)中構(gòu)思并實(shí)現(xiàn)了本文提出的課程設(shè)計實(shí)踐教學(xué)模式。筆者基于前一學(xué)年的教學(xué)實(shí)踐發(fā)現(xiàn)問題并形成解決方案。

為促動學(xué)生接受五子棋作為課程設(shè)計項目，對編寫人工智能程序?qū)巩a(chǎn)生興趣，筆者在開始進(jìn)行數(shù)據(jù)課程設(shè)計之前的兩個月，就結(jié)合“數(shù)據(jù)結(jié)構(gòu)”課堂教學(xué)分析和討論數(shù)據(jù)結(jié)構(gòu)在棋類游戲設(shè)計和實(shí)現(xiàn)當(dāng)中的作用。為了激發(fā)學(xué)生的積極性，突出對抗性，筆者還組織集中答辯，即舉行機(jī)器人五子棋錦標(biāo)賽，從勝率、擬人程度、算法效率等多個方面評價對戰(zhàn)效果，生成英雄榜。勝率體現(xiàn)了五子棋引擎的智能，擬人程度則體現(xiàn)為對戰(zhàn)招法的多樣性，算法效率則體現(xiàn)為基于復(fù)雜盤面落子所需的時間。英雄榜則促動學(xué)生不斷改進(jìn)程序代碼，追求榮譽(yù)。為了使學(xué)生重視和學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)在編制五子棋引擎當(dāng)中的作用，筆者要求學(xué)生明確地分析其五子棋引擎使用已有數(shù)據(jù)結(jié)構(gòu)及算法的類型和比例，形成課程設(shè)計報告。為了成功地將五子棋競賽平臺應(yīng)用到課程設(shè)計當(dāng)中，必須明確規(guī)定學(xué)生必須滿足的技術(shù)約束。五子棋競賽平臺需通過特定的接口才能調(diào)用學(xué)生編寫的五子棋引擎，即學(xué)生設(shè)計的五子棋引擎必須實(shí)現(xiàn)相應(yīng)的接口，必須按照給定的模板封裝成為動態(tài)鏈接庫。五子棋引擎只需實(shí)現(xiàn)一個接口函數(shù)MakeMove。

extern \"C\" int __declspec（dllexport） MakeMove（int * nRow，int * nCol，int Matrix[19][19]）.

其中，Matrix[NROW][NCOL]表示一個棋局的當(dāng)前狀態(tài)，NROW和NCOL分別表示棋局的總行數(shù)和總列數(shù)，nRow和nCol分別表示五子棋引擎評估當(dāng)前的棋局Matrix之后擬落子位置的行列坐標(biāo)。MakeMove的返回值則表示對當(dāng)前棋局的評估是否成功的狀態(tài)信息。

三、效果和需要注意的問題

實(shí)際應(yīng)用益智類游戲競賽平臺開展“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)的效果良好，克服了傳統(tǒng)課程設(shè)計教學(xué)模式的問題，促進(jìn)了學(xué)生的積極性和主動性。

首先，五子棋競賽平臺提供了人機(jī)（機(jī)機(jī)）對弈的界面，低年級同學(xué)可關(guān)注于數(shù)據(jù)結(jié)構(gòu)在實(shí)現(xiàn)五子棋引擎中的作用，而不必在提前自學(xué)界面開發(fā)技術(shù)上浪費(fèi)精力（到高年級將會系統(tǒng)地學(xué)習(xí)）。

其次，五子棋規(guī)則清晰，易學(xué)難精，學(xué)生對于能夠開發(fā)五子棋游戲機(jī)器人挑戰(zhàn)人類智慧興趣盎然。

再次，五子棋競賽平臺允許學(xué)生各自開發(fā)五子棋引擎相會對戰(zhàn)，促使學(xué)生不斷改進(jìn)代碼，學(xué)習(xí)和應(yīng)用數(shù)據(jù)結(jié)構(gòu)理論知識。

最后，對于教師而言，基于五子棋引擎的智能、性能、擬人度等指標(biāo)能夠比較客觀地評價不同學(xué)生完成課程設(shè)計的情況，基于學(xué)生的課程設(shè)計報告可以評價學(xué)生對數(shù)據(jù)結(jié)構(gòu)理論知識的掌握和應(yīng)用情況。

在開展基于益智類游戲競賽平臺的“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計模式的過程中，需要特別注意幾個問題。第一，必須注意學(xué)生的編程基礎(chǔ)薄弱的現(xiàn)實(shí)，并進(jìn)行必要的編程基礎(chǔ)技術(shù)補(bǔ)充教學(xué)。第二，必須注意學(xué)生的分組規(guī)則。筆者將學(xué)生分成每兩人一組，如每組包含人數(shù)較多，則可能導(dǎo)致部分學(xué)生的實(shí)際參與程度下降。第三，必須注意課題設(shè)計題目以及分組的確定要早于課程設(shè)計的實(shí)際開始時間，給學(xué)生充分的課外時間思考和準(zhǔn)備。此外，可開展競賽解說和錄像等活動，進(jìn)一步推動學(xué)生的積極性（此活動筆者未開展，事后學(xué)生建議開展）。

四、結(jié)語

本文分析了“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)實(shí)踐中的典型問題，并提出了應(yīng)用益智類游戲競賽平臺解決相應(yīng)問題的思路。本文具體介紹了設(shè)計、開發(fā)和應(yīng)用五子棋競賽平臺的方式和將其應(yīng)用于“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計教學(xué)的具體方式。實(shí)踐應(yīng)用表明基于益智類游戲競賽平臺的“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計模式實(shí)際可行且效果良好。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，

2008.

[2][美]柯奈漢·派克.程學(xué)設(shè)計實(shí)踐[M].裘宗燕，譯.北京：機(jī)械工業(yè)出版社，2006.

[3]Ramon Lawrence. Teaching Data Structures Using Competitive Games[J].IEEE TRANSACTIONS ON EDUCATION，2004，47（4）：459-466.

（責(zé)任編輯：王意琴）