孫愛東 楊秋妹 肖媚燕

摘要:“數(shù)據(jù)結(jié)構(gòu)”的實踐教學(xué)不僅可以幫助學(xué)生鞏固和加深對課程內(nèi)容的理解,更重要的是可以進一步鍛煉程序設(shè)計的技能,培養(yǎng)學(xué)生運用知識的能力,并初步感受軟件開發(fā)的規(guī)范和培養(yǎng)團隊合作精神。本文針對實踐教學(xué)環(huán)節(jié)中存在的問題,設(shè)計與實現(xiàn)了由簡單到復(fù)雜、由單一到綜合的多層次實踐教學(xué)模式。

關(guān)鍵詞:數(shù)據(jù)結(jié)構(gòu);實踐教學(xué);多層次

中圖分類號: G642文獻標識碼:B

1引言

“數(shù)據(jù)結(jié)構(gòu)”是計算機科學(xué)與技術(shù)及相關(guān)專業(yè)的一門重要的核心專業(yè)基礎(chǔ)課程,側(cè)重介紹軟件設(shè)計中的基本技術(shù),包括程序設(shè)計中所涉及到的各種數(shù)據(jù)結(jié)構(gòu)、基本運算、各種存儲結(jié)構(gòu)以及算法實現(xiàn)和性能分析,排序和查找這兩種常用的運算以及遞歸技術(shù)等內(nèi)容。通過這門課程的學(xué)習(xí),幫助學(xué)生在軟件開發(fā)的過程中正確、合理地組織數(shù)據(jù)、選擇最優(yōu)的存儲結(jié)構(gòu),有效甚至高效地設(shè)計算法,從而提高軟件整體質(zhì)量。

“數(shù)據(jù)結(jié)構(gòu)”的課程實踐不僅可以幫助學(xué)生鞏固和加深對課程內(nèi)容的理解,更重要的是可以進一步鍛煉程序設(shè)計的技能,并初步感受軟件開發(fā)的規(guī)范,全面培養(yǎng)學(xué)生綜合運用知識的能力、進行研究性學(xué)習(xí)的能力、創(chuàng)新能力以及團隊合作的能力等。

2 “數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)中存在的問題

“數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)包括“數(shù)據(jù)結(jié)構(gòu)”課程實驗和課程設(shè)計兩部分。按照專業(yè)教學(xué)要求,在第3學(xué)期安排“數(shù)據(jù)結(jié)構(gòu)”教學(xué)72學(xué)時,其中52學(xué)時上課、20學(xué)時實驗;第4學(xué)期安排2周(40學(xué)時)的課程設(shè)計。

目前,“數(shù)據(jù)結(jié)構(gòu)”實踐教學(xué)中存在兩個主要問題。

(1) 大部分學(xué)生對代碼編寫有恐懼心理,程序設(shè)計能力薄弱,不同學(xué)生基礎(chǔ)不同,不適宜一刀切做一樣的要求。

(2) 在當(dāng)前的“數(shù)據(jù)結(jié)構(gòu)”教學(xué)中有兩種爭論,一種是“數(shù)據(jù)結(jié)構(gòu)”課程側(cè)重在教導(dǎo)學(xué)生怎樣實現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu),另外一種看法是教會學(xué)生如何通過編程環(huán)境提供的API調(diào)用數(shù)據(jù)結(jié)構(gòu),如STL、JDK等。部分學(xué)生誤認為只需要掌握接口調(diào)用就行,但作為計算機專業(yè)的學(xué)生,應(yīng)該要會自己實現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu),從而可以在遇到實際應(yīng)用時根據(jù)需求設(shè)計靈活高效的新結(jié)構(gòu)。

針對以上存在的問題,在“數(shù)據(jù)結(jié)構(gòu)”的實踐教學(xué)中設(shè)計由簡單到復(fù)雜、由單一到綜合的多層次實踐教學(xué)模式,將實踐內(nèi)容分為驗證性基礎(chǔ)實驗、綜合性實驗和課程設(shè)計三個層次,每個階段完成相應(yīng)的實踐目標,下面分別介紹這三部分的實施。

3多層次的“數(shù)據(jù)結(jié)構(gòu)”實踐模式

3.1驗證性基礎(chǔ)實驗

“數(shù)據(jù)結(jié)構(gòu)”的實踐教學(xué)遵循由淺入深,由易到難的規(guī)律。在學(xué)生剛接觸“數(shù)據(jù)結(jié)構(gòu)”這門課時,為掌握課程基礎(chǔ)內(nèi)容及完成對知識點的回顧,數(shù)據(jù)結(jié)構(gòu)驗證性基礎(chǔ)實驗在實驗課程計劃學(xué)時內(nèi)完成,主要圍繞教材上的重要數(shù)據(jù)結(jié)構(gòu)上機實現(xiàn),深化理解和掌握理論知識。鑒于計劃學(xué)時的限制,實驗以驗證性實驗為主,如循環(huán)隊列的建立空隊、入隊、出隊操作,利用二叉樹的先序遍歷生成二叉樹并完成先、中、后序遍歷及層次遍歷。算法基本上是教材中所介紹的,同時包括有簡單應(yīng)用算法,如利用堆棧驗證括號的匹配問題等。驗證性實驗側(cè)重加深學(xué)生對基本數(shù)據(jù)結(jié)構(gòu)的理解,不要求應(yīng)用創(chuàng)新。

驗證性實驗是對書本的知識點進行實現(xiàn),趣味性相對比較低,為了提高學(xué)生的積極性,這部分實驗采取類似ACM競賽的方式進行考核,把整個學(xué)期的驗證性實驗分成若干次比賽,每次比賽包含一定題量的題目,規(guī)定學(xué)生在限定時間內(nèi)完成,并且按照完成時間的先后進行排名。在此階段,采用ACM/ICPC競賽中使用的Online Judge在線評判實驗系統(tǒng)對學(xué)生提交的代碼進行評判。Online Judge在線評判實驗系統(tǒng)采用程序黑箱子測試的方法,針對具體的題目預(yù)先設(shè)定若干組輸入數(shù)據(jù)以及其對應(yīng)的正確的輸出結(jié)果,評判時,先編譯、運行被測程序,再將設(shè)定好的輸入數(shù)據(jù)通過輸入重定向的方式傳遞給運行的被測程序,被測程序輸出后的結(jié)果與設(shè)定的正確的輸出結(jié)果進行對比,所有的輸出結(jié)果均符合則判定程序正確。在這一過程中,只要設(shè)定的輸入數(shù)據(jù)有代表性且覆蓋面足夠廣,就可以保證評判具有足夠的正確度。系統(tǒng)還能夠自動進行運行結(jié)果統(tǒng)計分析和代碼相似度評判等功能。通過評判系統(tǒng)的使用,學(xué)生初步了解在測試方法及在輸入、輸出格式受限情況下完成程序設(shè)計的方法。

通過這一階段的實踐教學(xué),學(xué)生基本掌握常用數(shù)據(jù)結(jié)構(gòu)的編寫,并且養(yǎng)成了一定的接口規(guī)范意識。

3.2綜合性實驗

通過完成驗證性基礎(chǔ)實驗,學(xué)生對教學(xué)內(nèi)容和要求有一定的了解并掌握初步實驗的方法。為了進一步引導(dǎo)、培養(yǎng)學(xué)生自己獲取知識的能力,在學(xué)期中后期,再布置1、2個綜合性實驗題目在課外開放實驗室完成。如題目一完成二叉排序樹的建立、遍歷、交換左右子樹、求深度、求葉子結(jié)點個數(shù)等各種操作。這個實驗安排在樹結(jié)構(gòu)部分,因此要求將查找部分的二叉排序樹的基本操作提前在樹這部分內(nèi)容中介紹。此實驗覆蓋樹、堆棧、隊列、遞歸等數(shù)據(jù)結(jié)構(gòu)課程知識點,是名副其實的綜合性實驗。題目二完成各種排序算法效率分析。要求完成在正序、逆序、小規(guī)模數(shù)據(jù)量和大規(guī)模數(shù)據(jù)量情況下分析算法的效率,除教材中的排序算法外可以由學(xué)生自己設(shè)計多個排序算法。同時本題為團隊實驗,開始實驗前,成員協(xié)商安排函數(shù)參數(shù)等接口,并通過排序過程中的移動次數(shù)和比較次數(shù)衡量算法的效率。

綜合性實驗的檢驗方案分兩部分,首先,要求與驗證性試驗一致,學(xué)生要通過Online Judge在線評判實驗系統(tǒng)的黑箱子測試;其次,要求學(xué)生書寫實驗報告。綜合性實驗不僅僅是以實現(xiàn)相應(yīng)的程序為目標,更重要的是培養(yǎng)學(xué)生今后從事軟件開發(fā)所需要的各種能力與素質(zhì),包括測試能力和文檔寫作的能力,因此,能夠較規(guī)范書寫綜合性實驗報告很重要。實驗報告要求有統(tǒng)一報告的版面格式、封面格式,同時只收電子版,即環(huán)保又易存放。 一份完整的實驗報告至少應(yīng)包含需求分析、概要設(shè)計、詳細設(shè)計、測試分析、效率分析與算法完善和附錄等至少六個部分的內(nèi)容。

3.3課程設(shè)計

課程設(shè)計在“數(shù)據(jù)結(jié)構(gòu)”的課堂授課全部結(jié)束之后進行,做為一門獨立的實踐課程。對于沒有安排“數(shù)據(jù)結(jié)構(gòu)課程設(shè)計”的學(xué)?？梢宰鰹閿?shù)據(jù)結(jié)構(gòu)實踐教學(xué)的實訓(xùn)項目設(shè)計環(huán)節(jié)。這一階段主要目標是加深學(xué)生對數(shù)據(jù)結(jié)構(gòu)的理解,能應(yīng)用學(xué)習(xí)過的數(shù)據(jù)結(jié)構(gòu),并且可以根據(jù)實際的問題定義數(shù)據(jù)結(jié)構(gòu)。由于在驗證性基礎(chǔ)實驗這一階段,已經(jīng)訓(xùn)練了學(xué)生實現(xiàn)基本數(shù)據(jù)結(jié)構(gòu)的能力,所以在課程設(shè)計這一階段,可以引進STL的應(yīng)用。

為彌補課內(nèi)實驗的不足,課程設(shè)計題目覆蓋的知識點要盡可能覆蓋較多知識點,同時注意實用性、與其他課程后續(xù)課程如“操作系統(tǒng)”、“數(shù)據(jù)庫”和“編譯原理”等的知識銜接。要引導(dǎo)學(xué)生圍繞課程設(shè)計的目標,鍛煉對復(fù)雜問題進行分析與求解的能力,激發(fā)創(chuàng)造的意識和能力。根據(jù)多年課程設(shè)計實踐和從ACM題目庫中選取題目構(gòu)建題目庫。題目按知識點分為幾種不同類型,每種類型的題目按難度有不同分值權(quán)重,此外還有團隊完成的題目。

課程設(shè)計涉及到的內(nèi)容可以分成兩部分。第一部分,算法設(shè)計型,加強傳統(tǒng)的薄弱環(huán)節(jié)——樹、圖方面的練習(xí)。除此之外,引入對ACM競賽常用的高級數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí),如介紹并查集、線段樹等的應(yīng)用,這部分主要從北大ACM題庫中選題,側(cè)重歷年的競賽題目。第二部分,應(yīng)用工程型,增強學(xué)生數(shù)據(jù)結(jié)構(gòu)的應(yīng)用能力。這部分主要側(cè)重把數(shù)據(jù)結(jié)構(gòu)的知識用于解決日常生活中遇到的問題,如使用散列表實現(xiàn)電話查找系統(tǒng)等。

為了更好地實現(xiàn)課程設(shè)計的目標,將不同基礎(chǔ)的學(xué)生分為三類:薄弱、較好和優(yōu)秀,分類的依據(jù)是“數(shù)據(jù)結(jié)構(gòu)”考試成績、驗證性基礎(chǔ)實驗和綜合性實驗的成績,其中較好的學(xué)生數(shù)居多,占總?cè)藬?shù)的80%左右。限定不同類型的學(xué)生只能選擇不同權(quán)重的題目?；A(chǔ)薄弱的學(xué)生是教師指導(dǎo)的重點。鼓勵優(yōu)秀的學(xué)生在團隊項目中挑戰(zhàn)自己,選擇圍繞數(shù)據(jù)挖掘的幾個算法如決策樹算法、遺傳算法等進行選題或自行設(shè)定的題目,通過查找與分析資料進行探索式學(xué)習(xí),初步掌握科學(xué)研究的方法。課程設(shè)計成績由個人完成題目和團隊題目,比例為60:40,按選題的權(quán)重、運行情況和設(shè)計報告的質(zhì)量給分。成績優(yōu)異者最后要通過答辯,一方面鍛煉表達能力同時大家見識更多的算法,開闊視野。

3.4實驗中注意事項

即使同是計算機專業(yè)的學(xué)生,不同班級因為基礎(chǔ)、學(xué)風(fēng)等因素,實驗基礎(chǔ)會有較大差別。任課和實驗指導(dǎo)教師要對學(xué)生進行摸底測驗,及時掌握學(xué)習(xí)狀態(tài),合理安排實驗。

上課和實驗前首先讓學(xué)生了解整個教學(xué)與實驗的安排和考察方法,每個實驗的最遲完成期限,從而讓學(xué)生有一定緊迫感,合理安排實驗進度。自編的實驗指導(dǎo)書可以保證實踐教學(xué)的順利完成及節(jié)省時間。

驗證性基礎(chǔ)實驗與理論教學(xué)同時進行,而綜合性實驗只能利用實驗室開放時間,但適時的指導(dǎo)是必要的,所以數(shù)據(jù)結(jié)構(gòu)實驗部分的指導(dǎo)與課程設(shè)計指導(dǎo)應(yīng)由同一教師完成,由指導(dǎo)教師協(xié)調(diào)分配實驗指導(dǎo)時間。

4結(jié)束語

經(jīng)過一系列的實踐教學(xué),取得了不少寶貴的經(jīng)驗和可喜的成績。多層次的實驗內(nèi)容調(diào)動了學(xué)生學(xué)習(xí)的積極性,學(xué)生解決問題的能力得到提高。Online Judge系統(tǒng)的使用提高實踐教學(xué)指導(dǎo)效率,實驗報告的要求強化了學(xué)生的文檔書寫能力。今后,將進一步完善數(shù)據(jù)結(jié)構(gòu)題庫的建設(shè)、豐富數(shù)據(jù)結(jié)構(gòu)課程的實驗內(nèi)容。另外,還需要在實踐教學(xué)中,重視新老教師經(jīng)驗交流、方法創(chuàng)新,在教和學(xué)的過程中不斷探索和實踐,適時調(diào)整實踐教學(xué)內(nèi)容、改進教學(xué)方法,使數(shù)據(jù)結(jié)構(gòu)實踐教學(xué)質(zhì)量提高到一個新的水平。

參考文獻:

[1] 陳越,何欽銘,馮雁. “數(shù)據(jù)結(jié)構(gòu)”綜合性課程設(shè)計教學(xué)探索與實踐[J].計算機教育, 2008(8):54-55.

[2] 王德興,胡學(xué)鋼,張玉紅,等. 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計的改革與創(chuàng)新探討[J].合肥工業(yè)大學(xué)學(xué)報,2008,22(5):94-97.

[3] 陳湘驥,劉財興,陳志民. 在線評判系統(tǒng)在程序設(shè)計類課程大規(guī)模教學(xué)中的應(yīng)用[C]// 張鳳祥.全國計算機新科技與計算機教育論文集(第16卷). 成都:西南交通大學(xué)出版社,2008.