基于分層實驗和課程答辯的數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)改革研究

林麗惠 魏 毅

（武夷學(xué)院 數(shù)學(xué)與計算機學(xué)院，福建 武夷山 354300）

“數(shù)據(jù)結(jié)構(gòu)”是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，是計算機學(xué)科的核心課程，其在計算機科學(xué)中是一門綜合性的專業(yè)必修課。[1]“數(shù)據(jù)結(jié)構(gòu)”課程的重要性可以從其在用計算機解決問題的過程中發(fā)揮的作用體現(xiàn)出。用計算機解決問題的過程及數(shù)據(jù)結(jié)構(gòu)在此過程中發(fā)揮的作用如圖1所示。

圖1 計算機解決問題的過程及數(shù)據(jù)結(jié)構(gòu)在此過程中發(fā)揮的作用Figure 1 The process of solving a problem by computer and the role of data structure in this process

“數(shù)據(jù)結(jié)構(gòu)”課程的教學(xué)要求學(xué)生掌握分析計算機要處理的數(shù)據(jù)的特性，為這些數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)，并設(shè)計相應(yīng)的算法解決實際問題。學(xué)生學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”課程的過程也是進(jìn)行復(fù)雜程序設(shè)計訓(xùn)練的過程。通過“數(shù)據(jù)結(jié)構(gòu)”課程的學(xué)習(xí)，學(xué)生將具備編寫結(jié)構(gòu)清晰、正確易讀和符合軟件工程規(guī)范的程序的能力。[2-3]“數(shù)據(jù)結(jié)構(gòu)”教學(xué)包括理論教學(xué)環(huán)節(jié)和實踐教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)的邏輯思想能在理論教學(xué)環(huán)節(jié)中陳述清楚，但是邏輯思想的具體實現(xiàn)則要通過實踐教學(xué)環(huán)節(jié)完成。[4]實踐教學(xué)環(huán)節(jié)十分重要，通過實踐教學(xué)環(huán)節(jié)，可以加強和提升學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”理論教學(xué)環(huán)節(jié)內(nèi)容的理解。通過為某一種具體數(shù)據(jù)結(jié)構(gòu)選擇合適的存儲結(jié)構(gòu)，并設(shè)計相應(yīng)的算法解決問題，真正在計算機上實現(xiàn)某一種數(shù)據(jù)結(jié)構(gòu)，理解“數(shù)據(jù)結(jié)構(gòu)”的真諦；同時通過綜合型實驗，綜合運用所學(xué)課程知識，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)，并設(shè)計相應(yīng)算法解決實際問題，進(jìn)一步鍛煉學(xué)生進(jìn)行復(fù)雜程序設(shè)計的能力，讓學(xué)生感受軟件開發(fā)的規(guī)范，全面培養(yǎng)學(xué)生綜合運用知識的能力。

但是長期以來，我們發(fā)現(xiàn)“數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)環(huán)節(jié)并沒有達(dá)到預(yù)期的效果，存在多方面的問題，影響了計算機學(xué)科高素質(zhì)人才的培養(yǎng)。目前實踐教學(xué)的現(xiàn)狀存在以下問題：

（1）“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)對學(xué)生的程序設(shè)計能力要求較高，而學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”的先修課程中的程序設(shè)計知識點掌握不夠扎實，造成學(xué)生感覺編寫程序困難，對“數(shù)據(jù)結(jié)構(gòu)”的實踐產(chǎn)生畏懼心理。

（2）“數(shù)據(jù)結(jié)構(gòu)”課程內(nèi)容的理解比較抽象，“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)要求將抽象的理論知識通過程序設(shè)計實現(xiàn)，而學(xué)生不能將數(shù)據(jù)結(jié)構(gòu)中的邏輯結(jié)構(gòu)與實際在計算機中的存儲結(jié)構(gòu)有機結(jié)合并設(shè)計合適的算法解決問題，造成學(xué)生不能正確理解數(shù)據(jù)結(jié)構(gòu)，從而對“數(shù)據(jù)結(jié)構(gòu)”的學(xué)習(xí)喪失積極性和主動性。

（3）“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)的考核，目前大多是依據(jù)實驗報告的成績作為實踐環(huán)節(jié)的考核成績，而部分學(xué)生在“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)中具有依賴心理，不喜歡動腦思考，不能獨立調(diào)試程序，依靠抄襲實驗報告來應(yīng)付實踐環(huán)節(jié)的考核，影響了“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)的教學(xué)效果。

因此，我們迫切需要對“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)的教學(xué)進(jìn)行改革，尋求突破，提高“數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)環(huán)節(jié)的效果，提高學(xué)生進(jìn)行復(fù)雜程序設(shè)計的能力[5-6]。

1 實踐教學(xué)內(nèi)容改革

合理安排和精心設(shè)置實驗內(nèi)容將有助于幫助學(xué)生逐步建立編寫程序的信心，讓學(xué)生體會到通過努力克服困難解決問題的成就感，提升學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”課程的理解和興趣，鍛煉學(xué)生將數(shù)據(jù)結(jié)構(gòu)理論轉(zhuǎn)化成編寫程序解決實際問題的能力[7]。

1.1 基礎(chǔ)知識實驗設(shè)置

根據(jù)多年的教學(xué)觀察發(fā)現(xiàn)，學(xué)生在“數(shù)據(jù)結(jié)構(gòu)”實驗編程的薄弱環(huán)節(jié)主要集中在以下方面的C語言程序設(shè)計知識點：描述存儲結(jié)構(gòu)時結(jié)構(gòu)體的定義、結(jié)構(gòu)體成員的引用方法，類型定義“typedef”的使用方法，指針、動態(tài)內(nèi)存分配的原理及方法，算法和程序的區(qū)別與轉(zhuǎn)換方法，函數(shù)返回執(zhí)行狀態(tài)的理解，程序組織及代碼復(fù)用的方法等。針對這部分學(xué)生掌握薄弱但是對“數(shù)據(jù)結(jié)構(gòu)”實驗編程又是極其重要的內(nèi)容，在“數(shù)據(jù)結(jié)構(gòu)”實踐環(huán)節(jié)的初始，設(shè)置基礎(chǔ)知識實驗，實驗內(nèi)容涵蓋上述知識點，對上述知識點內(nèi)容進(jìn)行編程集訓(xùn)，起到對C語言程序設(shè)計復(fù)習(xí)鞏固和查缺補漏的作用，為學(xué)生更好地理解“數(shù)據(jù)結(jié)構(gòu)”提供先修知識準(zhǔn)備，為“數(shù)據(jù)結(jié)構(gòu)”實驗編程消除先修知識上的技術(shù)障礙。

1.2 驗證型實驗設(shè)置

驗證型實驗主要是上機實現(xiàn)數(shù)據(jù)結(jié)構(gòu)課程各個章節(jié)中涉及的相關(guān)基礎(chǔ)算法，使學(xué)生進(jìn)一步領(lǐng)會其原理和驗證算法的正確性。驗證型實驗的實驗內(nèi)容主要是實現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)采用不同存儲結(jié)構(gòu)時的基本操作，包括建立、查找、插入、刪除等基本操作。學(xué)生通過做驗證型實驗，可以加深和鞏固對不同數(shù)據(jù)結(jié)構(gòu)不同操作的理解，深刻體會同一種數(shù)據(jù)結(jié)構(gòu)采用不同存儲結(jié)構(gòu)時有哪些不同的特點及操作方法的異同之處，同時也為后續(xù)的設(shè)計型實驗和綜合型實驗打下扎實的理論和實驗基礎(chǔ)。[8]驗證型實驗還能檢測學(xué)生的基礎(chǔ)編程能力，學(xué)生也可以在驗證型實驗的過程中對編程知識進(jìn)行補缺補漏，提高基礎(chǔ)編程能力。同時，通過驗證型實驗編程實現(xiàn)的算法可以保留，提供給后續(xù)的設(shè)計型實驗和綜合型實驗調(diào)用。這樣，在后續(xù)的設(shè)計型實驗和綜合型實驗中，學(xué)生就可以不要糾結(jié)在一些細(xì)小的編程問題，可以將精力用在更高層次的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計上。做好驗證型實驗?zāi)軌蚣ぐl(fā)學(xué)生學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”的興趣和信心。驗證型實驗的實驗內(nèi)容設(shè)置如表1。

表1 驗證型實驗的內(nèi)容Table 1 The content of verification experiment

例如，在驗證型實驗“線性表的基本操作”中，要求學(xué)生編寫程序分別實現(xiàn)順序表和鏈表的整體建表算法和各種基本運算，并在此基礎(chǔ)上設(shè)計一個主程序，完成建立順序表和鏈表以及插入元素、刪除元素、輸出順序表和鏈表元素的功能。通過做這個實驗，能夠增進(jìn)學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”本質(zhì)的理解，使學(xué)生能夠掌握非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及對象之間的關(guān)系的表示方法，能夠掌握對這些操作對象進(jìn)行各種操作的方法，同時也能夠更加深刻地理解“數(shù)據(jù)結(jié)構(gòu)+算法=程序設(shè)計”這個有關(guān)程序設(shè)計的經(jīng)典名句。

1.3 設(shè)計型實驗設(shè)置

設(shè)計型實驗通過采用數(shù)據(jù)結(jié)構(gòu)的基本方法，分析并且選擇某種數(shù)據(jù)結(jié)構(gòu)，采用某種存儲結(jié)構(gòu)，設(shè)計合適的算法并加以實現(xiàn)來求解問題。[9]通過設(shè)計型實驗，學(xué)生才能真正理解如何應(yīng)用“數(shù)據(jù)結(jié)構(gòu)”來解決實際的問題，真正理解學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”課程的意義。設(shè)計型實驗通常還具有一定的實用性和趣味性，可以增進(jìn)學(xué)生對實驗課的興趣。因此，根據(jù)教學(xué)目標(biāo)，精心設(shè)置出適當(dāng)難度和規(guī)模的設(shè)計型實驗是非常重要的。

例如，針對隊列的應(yīng)用，設(shè)置“猴子選大王”這個設(shè)計型實驗。給出“猴子選大王”的問題描述如下：n只猴子（n不超過50）圍成一個圈。從某一只開始依次給猴子們編號，從1到n。然后從第一只猴子開始依次報數(shù)，從1數(shù)到m，報到m的猴子離開此圈。離開此圈的猴子的下一只猴子再開始從1報數(shù)，報到m的猴子再離開此圈。以此循環(huán)，直到圈中剩下最后一只猴子,這只猴子就是大王。要求編程實現(xiàn)，輸入n和m，依次輸出離開圈子的猴子編號，然后輸出大王的編號。[10]對于此問題的解決,首先要求學(xué)生對問題進(jìn)行分析,選擇合適的數(shù)據(jù)結(jié)構(gòu)。根據(jù)問題描述，n只猴子圍成一個圈，正好對應(yīng)數(shù)據(jù)結(jié)構(gòu)里的循環(huán)鏈表，每只猴子為循環(huán)鏈表的一個結(jié)點?！皬哪骋恢婚_始依次給猴子們編號，從1到n。”的操作即為：給循環(huán)鏈表的結(jié)點編號，從某個結(jié)點開始編號，從1到n。“從第一只猴子開始依次報數(shù)，從1數(shù)到m，報到m的猴子離開此圈”的操作相當(dāng)于從循環(huán)鏈表中刪除一個結(jié)點。經(jīng)過分析可知，該問題的程序編寫包括以下實現(xiàn)過程：建立單鏈表；報數(shù)利用do-while循環(huán)實現(xiàn)猴子的出列 （即刪除結(jié)點操作）；判斷循環(huán)鏈表是否最終剩下一個結(jié)點，剩下的一個結(jié)點即為大王。

綜上，學(xué)生做設(shè)計型實驗的過程實際上就是進(jìn)行了包括分析、設(shè)計、編碼和調(diào)試等一系列操作的訓(xùn)練。因此，學(xué)生通過做設(shè)計型實驗，能夠更加深刻地理解和掌握數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、數(shù)據(jù)結(jié)構(gòu)的存儲表示方法，并且通過設(shè)計合適的算法鞏固并提高分析問題、解決實際問題的能力。

設(shè)計型實驗的實驗內(nèi)容設(shè)置如表2。

1.4 綜合型實驗設(shè)置

綜合型實驗是綜合運用“數(shù)據(jù)結(jié)構(gòu)”課程中多個相關(guān)知識點求解比較復(fù)雜的問題，或者同一個問題用多種方法求解，能夠提升學(xué)生對“數(shù)據(jù)結(jié)構(gòu)”的整體認(rèn)識，提高學(xué)生分析解決復(fù)雜問題的能力。綜合型實驗的題目有很多，常見的綜合型實驗題目有：通訊錄管理系統(tǒng)問題、停車場管理系統(tǒng)問題、校園導(dǎo)航系統(tǒng)問題、八皇后問題等。

例如，“停車場管理系統(tǒng)”的問題描述如下：有一個只有一個大門可以進(jìn)出的狹長停車場，可以停放n輛汽車。最早進(jìn)入停車場的車停放在狹長停車場的最靠里面的車位，其它車輛按到達(dá)時間依次從里往外停放。如果停車場車位已滿，后面到達(dá)的車輛依次在停車場大門外的便道上停放等待。如果停車場有車輛要離開，排在這輛車后面進(jìn)入停車場的車輛都要先退出停車場，等待這輛車離開后，再依原來的次序依次開進(jìn)停車場停放。一旦停車場有空余的車位，排在便道上的車輛依次開進(jìn)停車場停放。每輛車都依據(jù)其在停車場內(nèi)停放的時間長度交費。在便道上停放的車輛不收費。要求編制一程序?qū)崿F(xiàn)對停車場的管理。對于此問題的解決,首先要求學(xué)生對問題進(jìn)行分析,選擇合適的數(shù)據(jù)結(jié)構(gòu)。根據(jù)問題描述，可以設(shè)計兩個堆棧，分別用來模擬狹長停車場和臨時停車場。當(dāng)狹長停車場有車輛要離開時，排在這輛要離開的車后面進(jìn)入停車場的車輛都先退出到臨時停車場，為要離開的車讓路。選擇堆棧來模擬狹長停車場和臨時停車場是因為堆棧具有“后進(jìn)先出”的特點，這與停車場車輛進(jìn)出的順序要求是相符的。同時，使用一個鏈隊列來模擬當(dāng)停車場車位已滿時需要停放車輛的停車場大門外的便道。選擇隊列來模擬便道，是因為這個便道上的車輛將具有“先進(jìn)先出”的特點。一旦停車場有空余的車位，排在便道上的第一輛車離開便道，開進(jìn)停車場停放，便道上原來的第二輛車成為便道上的第一輛車。這個操作就是刪除鏈隊列的隊頭元素，并將這個隊頭元素插入到狹長停車場這個堆棧中。以上“停車場管理系統(tǒng)”問題同時使用到了棧和鏈?zhǔn)疥犃袃煞N數(shù)據(jù)結(jié)構(gòu)。

設(shè)計數(shù)據(jù)結(jié)構(gòu)的過程，首先要求設(shè)計邏輯結(jié)構(gòu)，然后再設(shè)計存儲結(jié)構(gòu)，最后是在此基礎(chǔ)上設(shè)計算法，解決問題。這過程中每個環(huán)節(jié)都對問題求解的性能有重要影響。這就要求學(xué)生對特定的問題不僅能夠設(shè)計出相應(yīng)的數(shù)據(jù)結(jié)構(gòu)和算法，還要對所設(shè)計的算法的相關(guān)性能（包括時間性能和空間性能等）進(jìn)行分析比較,然后給出最合適的選擇。因此，綜合型實驗還要求學(xué)生能夠?qū)ν粋€問題用多種方法求解，再根據(jù)實際情況選擇一種最優(yōu)的解決方法。

綜上，通過做綜合型實驗，能夠增強學(xué)生綜合運用課程中的知識與方法的能力，能夠提升學(xué)生對給定的問題設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)和算法并解決實際問題的綜合實踐能力。

2 實踐教學(xué)模式改革

在實踐教學(xué)中，循序漸進(jìn)地安排實驗內(nèi)容，從驗證型實驗，到設(shè)計型實驗，再到綜合型實驗。每個章節(jié)的實驗內(nèi)容均按由淺入深、由易到難的原則設(shè)計不同層次的實驗。驗證型實驗和設(shè)計型實驗屬于必做實驗，綜合型實驗屬于選做實驗，以滿足不同層次的學(xué)生需求。

為增強教學(xué)效果，教師應(yīng)提前布置實驗任務(wù)，要求學(xué)生課前預(yù)習(xí)實驗內(nèi)容，帶著問題參加實驗。在實驗課上，教師重點講解實驗中比較關(guān)鍵的內(nèi)容，采用啟發(fā)式的方式輔助學(xué)生解決問題。在實驗課結(jié)束前，對實驗內(nèi)容和出現(xiàn)的問題進(jìn)行總結(jié)。并且在課后加強與學(xué)生交流溝通，通過課程網(wǎng)站和教師主頁進(jìn)行課后答疑，切實保證學(xué)生能真正掌握實驗所要求的內(nèi)容，切實保障實踐教學(xué)應(yīng)有的教學(xué)效果[11]。

3 實踐教學(xué)考核改革

對于實踐教學(xué)考核，除了提交實驗報告，增設(shè)課程答辯環(huán)節(jié)。答辯時主要采用學(xué)生講解、演示測試過程、老師提問和小組討論的方式，以便深入了解學(xué)生對實驗內(nèi)容的掌握情況。實踐教學(xué)考核的成績?yōu)閷嶒瀳蟾娉煽兒驼n程答辯成績的綜合成績。實踐教學(xué)考核增設(shè)課程答辯環(huán)節(jié)后，部分偷懶的學(xué)生就不能再依靠抄襲實驗報告來應(yīng)付實踐環(huán)節(jié)的考核，激發(fā)他們必須通過努力扎實掌握實驗內(nèi)容，[12]切實保障實踐教學(xué)應(yīng)有的教學(xué)效果。

4 結(jié)論

本研究從實踐教學(xué)內(nèi)容、實踐教學(xué)模式和實踐教學(xué)考核等方面進(jìn)行數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)改革研究，提出一個基于分層實驗和課程答辯的數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)改革方案。在實踐教學(xué)內(nèi)容上，循序漸進(jìn)地設(shè)計基礎(chǔ)知識實驗、驗證型實驗、設(shè)計型實驗、綜合型實驗等不同層次的實驗，以滿足不同層次的學(xué)生需求。在實踐教學(xué)模式上，加強實驗課課前和課后的輔導(dǎo)。要求學(xué)生課前預(yù)習(xí)實驗內(nèi)容，帶著問題參加實驗，通過課程網(wǎng)站和教師主頁進(jìn)行課后答疑。實踐教學(xué)考核增設(shè)課程答辯環(huán)節(jié)。使用本研究提出的數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)改革方案，經(jīng)過對連續(xù)四屆計算機科學(xué)與技術(shù)專業(yè)的《數(shù)據(jù)結(jié)構(gòu)》實踐教學(xué)進(jìn)行改革探索，教學(xué)實踐表明本研究實施的教學(xué)改革方案能夠切實保障數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)取得應(yīng)有的教學(xué)效果。主要體現(xiàn)在對《數(shù)據(jù)結(jié)構(gòu)》這門課程，學(xué)生學(xué)習(xí)的積極性和主動性提高了，綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識編寫程序的能力也提高了。