張仕 吳聞 郭躬德 嚴宣輝 嚴曉明

文章編號：1672-5913（2015）03-0030-03

中圖分類號：G642

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

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

0 引 言

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

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

1 研究現(xiàn)狀

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

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

（2）程序問題不能及時解決。學生在編程練習遇到問題時沒有通暢的溝通渠道，不能及時得到教師的指導，而教師在課上與學生的溝通有限。

（3）實踐動手要求低。實驗課的練習只有一些代表性案例，學生雖然完成了實驗，但是實踐工作量嚴重不足；另一方面，實驗題目難度不大，這對于學有余力、對自己有更高要求的學生而言缺少了練習的強度。

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

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

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

2 PCOJ平臺的改進

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

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

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

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

3 基+PCOJ的實驗教學改革

3.1 分層次的實驗教學體系

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

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

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

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

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

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

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

3.3 基于論壇的師生交流

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

3.4 基于平臺的實驗測試

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

3.5 基于平臺的實驗考核

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

4 結(jié)語

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