清華大學(xué)“數(shù)據(jù)結(jié)構(gòu)”精品課程建設(shè)

殷人昆　鄧俊輝

一、課程的定位和在學(xué)校的發(fā)展歷史

“數(shù)據(jù)結(jié)構(gòu)”課程是一門計(jì)算機(jī)專業(yè)的核心課程，它在整個計(jì)算機(jī)專業(yè)教學(xué)體系中處于舉足輕重的地位。我校數(shù)據(jù)結(jié)構(gòu)課程最初開設(shè)于1978年，長期以來，數(shù)據(jù)結(jié)構(gòu)教學(xué)得到計(jì)算機(jī)系領(lǐng)導(dǎo)高度重視，配備了優(yōu)秀師資。先后參加數(shù)據(jù)結(jié)構(gòu)教學(xué)組的教師包括嚴(yán)蔚敏、沈佩娟、唐澤圣、米寧、殷人昆、鄧俊輝等。1987年在對國外教材研究的基礎(chǔ)上，嚴(yán)蔚敏老師等編寫并出版了《數(shù)據(jù)結(jié)構(gòu)》新教材，成為國內(nèi)數(shù)據(jù)結(jié)構(gòu)教材的翹楚，1990年獲得國家級特等獎。該教材至今已發(fā)行100萬冊以上。與教學(xué)配套，教學(xué)組在嚴(yán)蔚敏老師的主持下，在學(xué)校教務(wù)處的支持下，開發(fā)了相應(yīng)的演示系統(tǒng)和練習(xí)系統(tǒng)，有力地支援了數(shù)據(jù)結(jié)構(gòu)的教學(xué)。

1992年，課程教學(xué)形成老、中、青三結(jié)合，教授、副教授、講師、博士生助教俱全的教學(xué)梯隊(duì)；采用課堂面授、電腦演示、網(wǎng)絡(luò)學(xué)習(xí)相結(jié)合的多種媒體教學(xué)手段，達(dá)到新的層次，被學(xué)校評為校級一類課。

從1996年起，課程內(nèi)容又一次更新。采用能支持面向過程方式和面向?qū)ο蠓绞降腃++語言，按照面向?qū)ο蠓绞浇M織各種數(shù)據(jù)結(jié)構(gòu)，使得數(shù)據(jù)結(jié)構(gòu)課程能夠適應(yīng)國際當(dāng)時水平，在實(shí)際教學(xué)中受到同學(xué)的歡迎。2002年數(shù)據(jù)結(jié)構(gòu)課程被評為校級精品課程，2005年通過了學(xué)校組織的驗(yàn)收。

2005年底，申報(bào)“教育部-微軟精品課程”建設(shè)項(xiàng)目，在全國批準(zhǔn)的15門課程項(xiàng)目中，我們數(shù)據(jù)結(jié)構(gòu)課程位居前列。

二、與國內(nèi)外高水平大學(xué)同類課程的比較

1.國外在20世紀(jì)90年代已將數(shù)據(jù)結(jié)構(gòu)教材改為用C++或Java描述，這主要是適應(yīng)軟件開發(fā)技術(shù)發(fā)展的需要，而當(dāng)時我們國內(nèi)仍然停留在用Pascal或C語言描述，這反映了兩種不同的開發(fā)模式。我們根據(jù)國際形勢，改為用面向?qū)ο蠓椒ê虲++描述來教數(shù)據(jù)結(jié)構(gòu)。學(xué)生反映，雖然開始學(xué)習(xí)，從過程性開發(fā)習(xí)慣轉(zhuǎn)換為面向?qū)ο蟮拈_發(fā)不太適應(yīng)，但一旦掌握，發(fā)現(xiàn)好處很多，對于后續(xù)的科研有很大的幫助。

2.用C或Pascal描述數(shù)據(jù)結(jié)構(gòu)，不能很好地實(shí)現(xiàn)抽象數(shù)據(jù)類型的思想，只有用C++或Java中的類（class）才能很自然地實(shí)現(xiàn)抽象數(shù)據(jù)類型的思想，這為改良教學(xué)內(nèi)容，促進(jìn)軟件復(fù)用和設(shè)計(jì)良好的軟件架構(gòu)，打下了堅(jiān)實(shí)的基礎(chǔ)。

3.在課程改革的過程中，與美國密西根州立Grand Valley大學(xué)的教授陶永雷密切合作，在數(shù)據(jù)結(jié)構(gòu)教學(xué)中引入軟件工程思想，在軟件設(shè)計(jì)中遵循信息隱蔽和抽象的原則進(jìn)行數(shù)據(jù)設(shè)計(jì)，注意增強(qiáng)軟件架構(gòu)的穩(wěn)定性和靈活性，建立了軟件開發(fā)與數(shù)據(jù)結(jié)構(gòu)的良好溝通。

4.建立數(shù)據(jù)結(jié)構(gòu)網(wǎng)頁和其他相關(guān)輔助軟件，促進(jìn)教學(xué)手段的多樣化，幫助學(xué)習(xí)者自主學(xué)習(xí)，提供了有利條件。

5.為逐步實(shí)現(xiàn)雙語教學(xué)，我們指定了一種由機(jī)械工業(yè)出版社華章分社引進(jìn)的有455個練習(xí)的影印英文教材《數(shù)據(jù)結(jié)構(gòu)習(xí)題與解答》（全美經(jīng)典學(xué)習(xí)指導(dǎo)系列）作為教學(xué)輔助教材，同時參照從1995年到2004出版的英文教材，經(jīng)過消化和篩選，并結(jié)合教學(xué)經(jīng)驗(yàn)，遵循先進(jìn)性、實(shí)用性、系統(tǒng)性的原則，經(jīng)過整理而編寫出我們自己的主教材，其第二版已被列為教育部“十五”規(guī)劃教材即將出版。

總之，從教學(xué)體系、教學(xué)內(nèi)容和教學(xué)手段，我們的課程與國外相比，應(yīng)處于類似或相同的水平，無論從哪一方面講，都達(dá)到國外大學(xué)要求。而在國內(nèi)，則處于先進(jìn)水平。

三、貫徹“研究型”教學(xué)模式，抓好六個教學(xué)環(huán)節(jié)的工作

為體現(xiàn)研究性大學(xué)課程的特色，必須在“思考”和“創(chuàng)新”上下功夫。為此，我們在教學(xué)過程中把握教學(xué)的六個基本要素，做了許多工作。

1.改進(jìn)教學(xué)內(nèi)容和教學(xué)方法，提高面授效果。

在結(jié)合C++ STL源代碼研究的基礎(chǔ)上，對教學(xué)內(nèi)容作了全面更新，將課程內(nèi)容講授分成兩個層次：

(1)講授以STL為基礎(chǔ)的基本數(shù)據(jù)結(jié)構(gòu)，側(cè)重?cái)?shù)據(jù)結(jié)構(gòu)的應(yīng)用；

(2)講授數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)細(xì)節(jié)，了解在開發(fā)中選擇數(shù)據(jù)結(jié)構(gòu)和算法的原則。

在講課中引入軟件工程原理，注重程序設(shè)計(jì)的模塊化和結(jié)構(gòu)化，在設(shè)計(jì)類結(jié)構(gòu)時盡量滿足封裝性、繼承性和多態(tài)性等要求，使學(xué)生在理解程序時很自然地加深了對良好體系結(jié)構(gòu)和程序設(shè)計(jì)風(fēng)格的認(rèn)識。在講課過程中采用這種講法，學(xué)生反映良好。在每次結(jié)束講課時，贏得了同學(xué)的掌聲。

由于在某些類定義和算法設(shè)計(jì)中隱藏了許多C++的語法細(xì)節(jié)，采用偽代碼的形式描述，這些細(xì)節(jié)很難表達(dá)出來。所以采用面授的方式是必要的。如果使用大段的文字描述，不如用圖形描述更直觀。為此，開發(fā)了動畫演示課件，在課堂上演示，獲得較好的效果，如圖1所示。

以抽象數(shù)據(jù)結(jié)構(gòu)和可復(fù)用構(gòu)件為基礎(chǔ)，用類和對象描述數(shù)據(jù)結(jié)構(gòu)，用結(jié)構(gòu)化程序設(shè)計(jì)風(fēng)格描述算法，既能適應(yīng)計(jì)算機(jī)硬件指令序列執(zhí)行的特點(diǎn)，又能方便地進(jìn)行算法分析。此外，使用面向?qū)ο蟪绦蛟O(shè)計(jì)方法（兼用結(jié)構(gòu)化程序設(shè)計(jì)）和軟件工程原則訓(xùn)練編寫小型的應(yīng)用程序，為日后開發(fā)大型計(jì)算機(jī)系統(tǒng)，有了良好的鋪墊。

2.激發(fā)學(xué)生學(xué)習(xí)的興趣，鼓勵學(xué)生對教學(xué)內(nèi)容提出問題，師生共同討論，提高教學(xué)和學(xué)習(xí)水平。

(1) 隨時在課堂上提出一些思考題，對一個結(jié)構(gòu)從不同角度討論。例如，在講課過程中，提出各種問題，引導(dǎo)學(xué)生討論。

(2) 鼓勵學(xué)生在學(xué)習(xí)過程中不拘于以往的解法，對同一個問題可以提出不同的解法，深化對問題的理解。例如在講使用棧的算法時，有同學(xué)從不同方面提出八種應(yīng)用，驗(yàn)證catalan數(shù)。對于這樣的學(xué)生，我們加以表揚(yáng)并適當(dāng)給予加分。

(3) 充分發(fā)揮博士助教和“奧賽”優(yōu)勝學(xué)生的作用。在各班選擇了十幾位“奧賽”優(yōu)勝者和優(yōu)秀學(xué)生，充當(dāng)小教員。由于這些同學(xué)的工作，溝通了教師和學(xué)生之間的聯(lián)系，他們協(xié)助助教成為學(xué)習(xí)、討論、答疑的骨干，這樣就構(gòu)成了生動活潑、互相幫助的良好學(xué)習(xí)氛圍。

3.精心選擇部分習(xí)題和上機(jī)實(shí)習(xí)題，著眼于基本知識的理解和基本編程能力的培養(yǎng)。C++模板是一種實(shí)現(xiàn)設(shè)計(jì)復(fù)用和代碼復(fù)用的有力工具，在程序設(shè)計(jì)習(xí)題選擇時采取循序漸進(jìn)、逐步積累的方式，引導(dǎo)學(xué)生自己建立可復(fù)用的構(gòu)件，并在以后的練習(xí)中直接使用，提高編程的工程能力和思考能力。

4.本著“精講多練”的原則，改進(jìn)考核方式?！皵?shù)據(jù)結(jié)構(gòu)”課程內(nèi)容很多，程序設(shè)計(jì)習(xí)題的涉及范圍非常廣泛。為此，課程考核從偏重期末考試改變到偏重進(jìn)行階段考核：增加4次小考核，改變“一考定輸贏”的格局，使學(xué)生能夠在平時自覺地給自己加壓，認(rèn)真對待每一部分的學(xué)習(xí)。

5.加強(qiáng)實(shí)習(xí)環(huán)節(jié)。通過實(shí)習(xí)，應(yīng)用VC++環(huán)境，完成6個實(shí)習(xí)作業(yè)，讓學(xué)生在實(shí)習(xí)中學(xué)會軟件設(shè)計(jì)、程序編碼和測試，掌握用面向?qū)ο蠓椒ㄩ_發(fā)小應(yīng)用軟件的方法。學(xué)生在完成實(shí)習(xí)作業(yè)中傾注了許多心血，當(dāng)?shù)玫浇處熆隙ê蟪錆M成就感，拉近了教師和學(xué)生的距離，也為參加科研打下了基礎(chǔ)。

6.編寫高質(zhì)量的教材和教輔材料?；谡n程目標(biāo)的要求和計(jì)算機(jī)技術(shù)的發(fā)展，不斷改進(jìn)教材的質(zhì)量。啟用《數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ê虲++語言描述）》教材后，通過教學(xué)和參考追蹤國內(nèi)外最新教材，每年更新電子教案，使得講授內(nèi)容更符合最新進(jìn)展。在此基礎(chǔ)上著手修訂新教材，并列入2001年國家教育部“十五”規(guī)劃教材系列（已于2005年4月交稿）。為幫助學(xué)生更好地學(xué)習(xí)，2002年出版了《數(shù)據(jù)結(jié)構(gòu)習(xí)題解析（用面向?qū)ο蠓椒ㄅcC++語言描述）》，作為主教材的輔助教材，在習(xí)題集中收集了一批較新的習(xí)題，并給出了解題的思路（見圖2）。

此外，在2003年開發(fā)完成新的試題庫和自動組題系統(tǒng)，可以根據(jù)難度要求和內(nèi)容要求，自動從試題庫中抽取試題組成試卷。目前完成的還有新的“數(shù)據(jù)結(jié)構(gòu)動態(tài)演示系統(tǒng)”和“動態(tài)網(wǎng)頁”（見圖3與圖4）。

四、建設(shè)課程教學(xué)梯隊(duì)

在學(xué)校和系有關(guān)部門的支持下，課程組已形成老中青相結(jié)合的教學(xué)梯隊(duì)?，F(xiàn)在教學(xué)梯隊(duì)包括殷人昆、鄧俊輝、舒繼武、朱仲濤等，今年又補(bǔ)充了原我校國際信息學(xué)奧賽隊(duì)教練王宏老師。其中鄧俊輝老師受學(xué)校派遣到美國進(jìn)修，直接與美國大學(xué)教授接觸和聽講，這對數(shù)據(jù)結(jié)構(gòu)課程改革起了直接促進(jìn)作用。其他參與教材編寫的還有美國密西根州Grand Valley州立大學(xué)的終身教授陶永雷。

五、小結(jié)

數(shù)據(jù)結(jié)構(gòu)課程的建設(shè)已經(jīng)做了許多工作，并建立了國際合作關(guān)系。在信息學(xué)院和計(jì)算機(jī)系領(lǐng)導(dǎo)的支持下，通過全體課程組教師的努力，課程建設(shè)，包括課程內(nèi)容的更新、教學(xué)方式的改革和網(wǎng)絡(luò)化，將有利于學(xué)生學(xué)習(xí)水平的提高。將來的教學(xué)將從以“教師”為中心變成以“學(xué)生”為中心，數(shù)據(jù)結(jié)構(gòu)課程正在努力適應(yīng)這種變化。

我們的下一步工作是：

1.在建設(shè)“教育部-微軟精品課程”的過程中，我們與哈爾濱工業(yè)大學(xué)合作，以我校為主，建立開放的“數(shù)據(jù)結(jié)構(gòu)”網(wǎng)站，讓我們的資源能夠?yàn)槿珖盒９蚕怼?/p>

2.向教育部申請，爭取將數(shù)據(jù)結(jié)構(gòu)教學(xué)方法列入青年骨干教師研修課程計(jì)劃，開展數(shù)據(jù)結(jié)構(gòu)教學(xué)經(jīng)驗(yàn)的培訓(xùn)，計(jì)劃分C、C++、Java三個專題。

3.《數(shù)據(jù)結(jié)構(gòu)》教材申報(bào)列入國家“十一五”教材規(guī)劃，繼續(xù)改進(jìn)教學(xué)內(nèi)容和教學(xué)方案。