基于PCOJ的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)探索

張仕 吳聞 郭躬德 嚴(yán)宣輝 嚴(yán)曉明

文章編號(hào)：1672-5913（2015）03-0030-03

中圖分類號(hào)：G642

摘要：針對(duì)數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐教學(xué)中的若干問(wèn)題，在自主開(kāi)發(fā)的程序設(shè)計(jì)競(jìng)賽在線測(cè)試平臺(tái)上有針對(duì)性地提出平臺(tái)改進(jìn)、試題設(shè)計(jì)和教學(xué)改革的方法，闡述這些方法應(yīng)用到實(shí)際教學(xué)工作中對(duì)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)的促進(jìn)作用，最后說(shuō)明取得的良好效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；實(shí)驗(yàn)教學(xué)；教學(xué)改革；程序設(shè)計(jì)競(jìng)賽在線測(cè)試平臺(tái)

0 引 言

ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM inter-national collegiate programming contest，簡(jiǎn)稱ACM-ICPC或ICPC）是由美國(guó)計(jì)算機(jī)協(xié)會(huì)（ACM）主辦的，一項(xiàng)旨在展示大學(xué)生創(chuàng)新能力、團(tuán)隊(duì)精神和在壓力下編寫程序、分析和解決問(wèn)題能力的年度競(jìng)賽。福建師范大學(xué)從2003年開(kāi)始組織學(xué)生參加ICPC，同時(shí)組織開(kāi)發(fā)了程序設(shè)計(jì)競(jìng)賽在線測(cè)試（ programming contest online judge，PCOJ）平臺(tái)，用于程序競(jìng)賽的訓(xùn)練工作。

實(shí)踐教學(xué)是計(jì)算機(jī)專業(yè)教學(xué)過(guò)程中一個(gè)必不可少的環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程便是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)中理論和實(shí)踐緊密結(jié)合的一門核心課程，其主要研究?jī)?nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及操作，教學(xué)目的在于培養(yǎng)學(xué)生的數(shù)據(jù)抽象能力，為解決實(shí)際問(wèn)題時(shí)進(jìn)行數(shù)據(jù)的組織和操作奠定基礎(chǔ)。要學(xué)好數(shù)據(jù)結(jié)構(gòu)這門課，不但需要從理論上理解和掌握相關(guān)知識(shí)，而且需要通過(guò)實(shí)驗(yàn)和實(shí)踐環(huán)節(jié)提高實(shí)際動(dòng)手能力和在實(shí)際問(wèn)題中應(yīng)用數(shù)據(jù)結(jié)構(gòu)抽象、解決實(shí)際問(wèn)題的能力。

1 研究現(xiàn)狀

雖然多年的教學(xué)實(shí)驗(yàn)改革使計(jì)算機(jī)實(shí)踐教學(xué)逐步受到重視，在實(shí)驗(yàn)室建設(shè)和教學(xué)實(shí)踐中有了長(zhǎng)足的發(fā)展，但是學(xué)生仍然存在理論學(xué)習(xí)與程序設(shè)計(jì)能力嚴(yán)重脫節(jié)的情況。通過(guò)對(duì)學(xué)生的訪談、日常教學(xué)中的觀察，筆者總結(jié)出這種理論與實(shí)踐脫節(jié)的問(wèn)題主要有以下幾方面。

（1）重理論學(xué)習(xí)，輕實(shí)踐動(dòng)手。教學(xué)過(guò)程中教師布置的多是書面作業(yè)，學(xué)生完成編程后不需要進(jìn)行嚴(yán)格的程序檢查和調(diào)試運(yùn)行，只需理論可行，忽視實(shí)踐動(dòng)手的培養(yǎng)。

（2）程序問(wèn)題不能及時(shí)解決。學(xué)生在編程練習(xí)遇到問(wèn)題時(shí)沒(méi)有通暢的溝通渠道，不能及時(shí)得到教師的指導(dǎo)，而教師在課上與學(xué)生的溝通有限。

（3）實(shí)踐動(dòng)手要求低。實(shí)驗(yàn)課的練習(xí)只有一些代表性案例，學(xué)生雖然完成了實(shí)驗(yàn)，但是實(shí)踐工作量嚴(yán)重不足；另一方面，實(shí)驗(yàn)題目難度不大，這對(duì)于學(xué)有余力、對(duì)自己有更高要求的學(xué)生而言缺少了練習(xí)的強(qiáng)度。

（4）程序bug多。學(xué)生編寫的程序只用少量數(shù)據(jù)進(jìn)行簡(jiǎn)單的測(cè)試，不能全面測(cè)試到程序中的所有指令調(diào)用，這導(dǎo)致完成的實(shí)驗(yàn)代碼可能存在大量的bug，但學(xué)生卻不能及時(shí)發(fā)現(xiàn)并改正，程序的實(shí)用程度大大降低。

（5）考核不合理。當(dāng)前對(duì)數(shù)據(jù)結(jié)構(gòu)課程的考核大多是對(duì)書面作業(yè)、理論知識(shí)的考核，對(duì)實(shí)驗(yàn)環(huán)節(jié)的考核則主要是通過(guò)實(shí)驗(yàn)報(bào)告。教師很難了解學(xué)生對(duì)知識(shí)與技能的實(shí)際掌握情況，實(shí)驗(yàn)報(bào)告也很難客觀真實(shí)地反映學(xué)生的實(shí)驗(yàn)情況。

（6）現(xiàn)有的把ICPC和教學(xué)結(jié)合的教學(xué)改革，更加側(cè)重的是利用ICPC對(duì)現(xiàn)行的教學(xué)方法、教學(xué)體系進(jìn)行改革，鼓勵(lì)學(xué)生通過(guò)競(jìng)賽練習(xí)提高程序設(shè)計(jì)水平和解決問(wèn)題的能力，鮮有把ICPC競(jìng)賽平臺(tái)加以改進(jìn)再結(jié)合到實(shí)驗(yàn)教學(xué)中的思路。

2 PCOJ平臺(tái)的改進(jìn)

福建師范大學(xué)計(jì)算機(jī)系組織開(kāi)發(fā)了程序設(shè)計(jì)競(jìng)賽在線測(cè)試平臺(tái)（ PCOJ），用于ICPC競(jìng)賽的日常訓(xùn)練工作。競(jìng)賽訓(xùn)練平臺(tái)給學(xué)生提供大量的試題，讓學(xué)生能夠通過(guò)大量的訓(xùn)練，熟練利用綜合知識(shí)分析并通過(guò)編程序解決實(shí)際問(wèn)題。

和競(jìng)賽目的不同，數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)的目標(biāo)是要求學(xué)生能夠解決特定的問(wèn)題，更是要培養(yǎng)學(xué)生組織程序的能力、按照規(guī)定抽象數(shù)據(jù)類型定義要求實(shí)現(xiàn)特定數(shù)據(jù)結(jié)構(gòu)的能力、按照預(yù)定義接口實(shí)現(xiàn)函數(shù)的能力、規(guī)范化程序書寫的習(xí)慣。用一句話概括它們的區(qū)別：程序競(jìng)賽要求的是“學(xué)生具有特別突出的解決問(wèn)題能力”，數(shù)據(jù)結(jié)構(gòu)教學(xué)則是為學(xué)生“打好寬闊扎實(shí)的基礎(chǔ)”?；诖?，要把該平臺(tái)應(yīng)用到數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)中，需要根據(jù)具體的需求對(duì)該系統(tǒng)做以下兩點(diǎn)改進(jìn)。

（1）程序競(jìng)賽時(shí)所要求提交的是一個(gè)單一的文件，該文件包括解決特定問(wèn)題的完整程序。文件提交到平臺(tái)后，測(cè)試平臺(tái)先編譯該程序，生成可執(zhí)行文件，平臺(tái)會(huì)自動(dòng)讀出數(shù)據(jù)作為該可執(zhí)行文件的輸入，允許該可執(zhí)行文件運(yùn)行，產(chǎn)生結(jié)果和預(yù)先設(shè)定的結(jié)果對(duì)比。在數(shù)據(jù)結(jié)構(gòu)的實(shí)驗(yàn)環(huán)節(jié)中，，教師需要讓學(xué)生掌握程序設(shè)計(jì)的方法，還要求學(xué)生掌握程序組織方法、具體數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)重用思想，這些要求不同于競(jìng)賽要求。為此，平臺(tái)改進(jìn)的第一個(gè)方面是要允許學(xué)生利用文件組織具體的應(yīng)用，單獨(dú)的文件反映的是某一個(gè)具體內(nèi)容，要允許學(xué)生針對(duì)一個(gè)試題提交多個(gè)文件，所提交的文件可以包括完整可運(yùn)行的程序，也可以是某個(gè)模塊的實(shí)現(xiàn)。

（2）學(xué)生的組織方式，原有PCOJ平臺(tái)沒(méi)有對(duì)學(xué)生按照班級(jí)管理的功能，改進(jìn)后的平臺(tái)針對(duì)具體課程，教師可以注冊(cè)賬號(hào)、開(kāi)設(shè)班級(jí)，學(xué)生也可以申請(qǐng)賬號(hào)，加入某一個(gè)班級(jí)，實(shí)現(xiàn)以班級(jí)為單位的管理。這大大方便了教師了解學(xué)生的實(shí)驗(yàn)完成情況、練習(xí)和討論參與情況等，為課程成績(jī)的評(píng)定提供多維參考。

3 基+PCOJ的實(shí)驗(yàn)教學(xué)改革

3.1 分層次的實(shí)驗(yàn)教學(xué)體系

對(duì)于同一門課程，學(xué)生掌握的程度不同，針對(duì)不同層次的學(xué)生要指定不同難度的練習(xí)，因此我們把實(shí)驗(yàn)分為必做和提高兩人類必做實(shí)驗(yàn)重點(diǎn)考核學(xué)生對(duì)基礎(chǔ)知識(shí)的掌握情況；而提高類題目針對(duì)學(xué)有余力的學(xué)生，有的放矢，為他們提供一個(gè)更高的目標(biāo)。

例如二叉樹(shù)的遍歷實(shí)驗(yàn)，我們?cè)O(shè)置的必做實(shí)驗(yàn)是利用遞歸思想完成先序、中主序和后序遍歷提高類實(shí)驗(yàn)則要求在前面章節(jié)實(shí)現(xiàn)的線性表、棧和隊(duì)列基礎(chǔ)上，完成二叉樹(shù)先序、中序和后序遍歷操作的非遞歸實(shí)現(xiàn)。在排序和查找部分，提高類實(shí)驗(yàn)要求學(xué)生能夠利用多線程提高算法的效率。

3.2 分類的試題設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)目的除了要求學(xué)生掌握線性、樹(shù)、圖等結(jié)構(gòu)組織和操作知識(shí)外，還要訓(xùn)練學(xué)生進(jìn)行復(fù)雜程序設(shè)計(jì)的基本技能，培養(yǎng)良好的程序設(shè)計(jì)習(xí)慣（如面向接口的編程思想），加深對(duì)數(shù)據(jù)結(jié)構(gòu)定義、算法、算法應(yīng)用的理解，提高實(shí)踐能力?；诖耍覀儼褦?shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)試題分為三大類：數(shù)據(jù)結(jié)構(gòu)應(yīng)用類、數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)類、算法設(shè)計(jì)實(shí)現(xiàn)類，如圖l所示

數(shù)據(jù)結(jié)構(gòu)應(yīng)用類試題指已經(jīng)按ADT定義并實(shí)現(xiàn)了某個(gè)數(shù)據(jù)結(jié)構(gòu)，再提出基于該數(shù)據(jù)結(jié)構(gòu)的應(yīng)用題目，要求利用該數(shù)據(jù)結(jié)構(gòu)解決相應(yīng)的問(wèn)題并提交平臺(tái)測(cè)試和判定。例如利用棧實(shí)現(xiàn)迷宮問(wèn)題的求解，對(duì)該類試題，實(shí)驗(yàn)平臺(tái)發(fā)布的試題說(shuō)明中包括可以使用的具體數(shù)據(jù)結(jié)構(gòu)的類型定義（.h文件）、所要實(shí)現(xiàn)的具體應(yīng)用說(shuō)明、測(cè)試數(shù)據(jù)例。學(xué)生根據(jù)實(shí)驗(yàn)題目要求，在所定義數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的基礎(chǔ)上，應(yīng)用該數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)應(yīng)用要求。學(xué)生可以提交多個(gè)程序文件，其中一個(gè)是包含main（）的程序，其他文件則是在主程序文件中引用到的定義和實(shí)現(xiàn)。實(shí)驗(yàn)平臺(tái)將利用存在的數(shù)據(jù)結(jié)構(gòu)和學(xué)生提交的文件進(jìn)行編譯、運(yùn)行、測(cè)試，并根據(jù)最后測(cè)試結(jié)果返回相關(guān)信息。

數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)類試題是指已經(jīng)設(shè)定好了數(shù)據(jù)結(jié)構(gòu)的應(yīng)用程序，學(xué)生應(yīng)按照要求的ADT實(shí)現(xiàn)特定的數(shù)據(jù)結(jié)構(gòu)，以便應(yīng)用程序得到支撐，如一個(gè)基于線性表的學(xué)生管理程序。對(duì)于該類試題，實(shí)驗(yàn)平臺(tái)發(fā)布的試題說(shuō)明中包括數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義（ ADT）、數(shù)據(jù)結(jié)構(gòu)應(yīng)用需要的接口、數(shù)據(jù)結(jié)構(gòu)應(yīng)用簡(jiǎn)單例、測(cè)試數(shù)據(jù)例。其中，具體數(shù)據(jù)結(jié)構(gòu)的抽象類型定義ADT清楚說(shuō)明了所需要實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)各類操作。學(xué)生在實(shí)驗(yàn)過(guò)程中可以提交多個(gè)程序文件，其中對(duì)于數(shù)據(jù)結(jié)構(gòu)應(yīng)用需要的數(shù)據(jù)結(jié)構(gòu)定義文件要按照要求進(jìn)行命名：實(shí)驗(yàn)平臺(tái)將利用系統(tǒng)中的數(shù)據(jù)結(jié)構(gòu)應(yīng)用程序和提交的相關(guān)文件進(jìn)行編譯，再利用平臺(tái)中的數(shù)據(jù)集對(duì)應(yīng)用進(jìn)行測(cè)試并根據(jù)最后測(cè)試結(jié)果返回相關(guān)信息。

算法設(shè)計(jì)實(shí)現(xiàn)類試題是指已經(jīng)有一個(gè)特定的應(yīng)用，該應(yīng)用基于某一數(shù)據(jù)結(jié)構(gòu)，但是在這一數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)中還缺少某一關(guān)鍵算法，要求學(xué)生根據(jù)算法的定義設(shè)計(jì)和實(shí)現(xiàn)該算法，以便應(yīng)用完整的某一數(shù)據(jù)結(jié)構(gòu)支撐應(yīng)用程序的運(yùn)行，如線性表的插入操作實(shí)現(xiàn)。對(duì)于該類試題，實(shí)驗(yàn)平臺(tái)發(fā)布的試題說(shuō)明中包括數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型定義（ ADT）、數(shù)據(jù)結(jié)構(gòu)的類型定義、特定算法的函數(shù)頭定義和算法需要實(shí)現(xiàn)的功能。學(xué)生在實(shí)驗(yàn)過(guò)程中只需要將該算法的實(shí)現(xiàn)提交到系統(tǒng)上測(cè)試和判定，這類試題適用于平時(shí)的小作業(yè)以及以算法設(shè)計(jì)為側(cè)重的數(shù)據(jù)結(jié)構(gòu)和算法實(shí)驗(yàn)。

3.3 基于論壇的師生交流

在實(shí)驗(yàn)教學(xué)體系中，我們還提供論壇作為師生交流的平臺(tái)。很多時(shí)候，教師不但會(huì)回答本班學(xué)生的提問(wèn)，而且會(huì)回答其他班級(jí)學(xué)生的提問(wèn)。教師通過(guò)論壇可以更好地了解學(xué)生對(duì)知識(shí)的掌握情況，發(fā)現(xiàn)不足，在課堂上加以彌補(bǔ)。論壇的設(shè)置緩解了學(xué)生碰到問(wèn)題不能夠及時(shí)交流的問(wèn)題，增加了師生的交流和了解，促進(jìn)教師實(shí)施更有針對(duì)性的課堂教學(xué)。

3.4 基于平臺(tái)的實(shí)驗(yàn)測(cè)試

針對(duì)當(dāng)前學(xué)生對(duì)實(shí)驗(yàn)程序測(cè)試不完全，導(dǎo)致程序中存在大量未被發(fā)現(xiàn)的bug的問(wèn)題，我們利用實(shí)驗(yàn)平臺(tái)的自動(dòng)測(cè)試功能發(fā)現(xiàn)問(wèn)題。學(xué)生所編寫的程序可以提交到平臺(tái)上進(jìn)行自動(dòng)編譯、測(cè)試和運(yùn)行，而運(yùn)行所使用的數(shù)據(jù)集是針對(duì)特定問(wèn)題特別設(shè)計(jì)的。由于在設(shè)計(jì)實(shí)驗(yàn)試題測(cè)試數(shù)據(jù)時(shí)可以綜合考慮各方面特別是一些邊界情況、規(guī)模問(wèn)題，自動(dòng)測(cè)試會(huì)幫助發(fā)現(xiàn)更多潛在bug并給出相應(yīng)提示。對(duì)程序測(cè)試的高要求自然會(huì)在潛移默化中培養(yǎng)學(xué)生程序設(shè)計(jì)的嚴(yán)密性，促使其重視程序設(shè)計(jì)中的細(xì)節(jié)問(wèn)題。

3.5 基于平臺(tái)的實(shí)驗(yàn)考核

有了這個(gè)實(shí)驗(yàn)平臺(tái)，教師布置的實(shí)驗(yàn)不再局限于每次實(shí)驗(yàn)的單個(gè)題目，還可以把平常的課堂作業(yè)也用實(shí)驗(yàn)試題（主要為算法設(shè)計(jì)實(shí)現(xiàn)類）的方式反映在實(shí)驗(yàn)平臺(tái)上，這樣學(xué)生完成的作業(yè)也就有更加客觀的考核和評(píng)價(jià)，同時(shí)減輕了教師的負(fù)擔(dān)，讓教師有更多時(shí)間與學(xué)生就相關(guān)實(shí)驗(yàn)進(jìn)行交流。對(duì)學(xué)生學(xué)習(xí)的評(píng)價(jià)，則可以充分利用學(xué)生使用實(shí)驗(yàn)平臺(tái)過(guò)程中產(chǎn)生的行為記錄，包括從該生平時(shí)所做練習(xí)、實(shí)驗(yàn)、提高實(shí)驗(yàn)和交流情況等進(jìn)行綜合考慮，從而提高評(píng)價(jià)的客觀性。

4 結(jié)語(yǔ)

我們通過(guò)把PCOJ的軟硬件平臺(tái)和數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)相結(jié)合并改進(jìn)，形成一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)體系；加強(qiáng)該數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)平臺(tái)的建設(shè)和應(yīng)用使數(shù)據(jù)結(jié)構(gòu)的實(shí)踐教學(xué)方法、平臺(tái)應(yīng)用、實(shí)驗(yàn)內(nèi)容、考核方式等越來(lái)越系統(tǒng)化，能夠服務(wù)于多層次、多角度的實(shí)驗(yàn)教學(xué)活動(dòng)。數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)改革不但能使學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)課程理論加深理解，也大大提高了學(xué)生的動(dòng)手能力，形成了理論和實(shí)踐相互促進(jìn)的良好態(tài)勢(shì)。實(shí)驗(yàn)平臺(tái)的使用能夠更好地訓(xùn)練學(xué)生進(jìn)行復(fù)雜程序設(shè)計(jì)的基本技能，培養(yǎng)良好的程序設(shè)計(jì)習(xí)慣，為后續(xù)課程實(shí)驗(yàn)奠定更加堅(jiān)實(shí)的基礎(chǔ)。當(dāng)然，在未來(lái)的教學(xué)過(guò)程中還不斷會(huì)有新的問(wèn)題和挑戰(zhàn)出現(xiàn)，這些都會(huì)促進(jìn)我們對(duì)實(shí)踐教學(xué)方法、手段繼續(xù)完善，使數(shù)據(jù)結(jié)構(gòu)的實(shí)踐教學(xué)水平不斷提高。