清華大學“數據結構”精品課程建設

殷人昆　鄧俊輝

一、課程的定位和在學校的發展歷史

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

1992年，課程教學形成老、中、青三結合，教授、副教授、講師、博士生助教俱全的教學梯隊；采用課堂面授、電腦演示、網絡學習相結合的多種媒體教學手段，達到新的層次，被學校評為校級一類課。

從1996年起，課程內容又一次更新。采用能支持面向過程方式和面向對象方式的C++語言，按照面向對象方式組織各種數據結構，使得數據結構課程能夠適應國際當時水平，在實際教學中受到同學的歡迎。2002年數據結構課程被評為校級精品課程，2005年通過了學校組織的驗收。

2005年底，申報“教育部-微軟精品課程”建設項目，在全國批準的15門課程項目中，我們數據結構課程位居前列。

二、與國內外高水平大學同類課程的比較

1.國外在20世紀90年代已將數據結構教材改為用C++或Java描述，這主要是適應軟件開發技術發展的需要，而當時我們國內仍然停留在用Pascal或C語言描述，這反映了兩種不同的開發模式。我們根據國際形勢，改為用面向對象方法和C++描述來教數據結構。學生反映，雖然開始學習，從過程性開發習慣轉換為面向對象的開發不太適應，但一旦掌握，發現好處很多，對于后續的科研有很大的幫助。

2.用C或Pascal描述數據結構，不能很好地實現抽象數據類型的思想，只有用C++或Java中的類（class）才能很自然地實現抽象數據類型的思想，這為改良教學內容，促進軟件復用和設計良好的軟件架構，打下了堅實的基礎。

3.在課程改革的過程中，與美國密西根州立Grand Valley大學的教授陶永雷密切合作，在數據結構教學中引入軟件工程思想，在軟件設計中遵循信息隱蔽和抽象的原則進行數據設計，注意增強軟件架構的穩定性和靈活性，建立了軟件開發與數據結構的良好溝通。

4.建立數據結構網頁和其他相關輔助軟件，促進教學手段的多樣化，幫助學習者自主學習，提供了有利條件。

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

總之，從教學體系、教學內容和教學手段，我們的課程與國外相比，應處于類似或相同的水平，無論從哪一方面講，都達到國外大學要求。而在國內，則處于先進水平。

三、貫徹“研究型”教學模式，抓好六個教學環節的工作

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

1.改進教學內容和教學方法，提高面授效果。

在結合C++ STL源代碼研究的基礎上，對教學內容作了全面更新，將課程內容講授分成兩個層次：

(1)講授以STL為基礎的基本數據結構，側重數據結構的應用；

(2)講授數據結構實現細節，了解在開發中選擇數據結構和算法的原則。

在講課中引入軟件工程原理，注重程序設計的模塊化和結構化，在設計類結構時盡量滿足封裝性、繼承性和多態性等要求，使學生在理解程序時很自然地加深了對良好體系結構和程序設計風格的認識。在講課過程中采用這種講法，學生反映良好。在每次結束講課時，贏得了同學的掌聲。

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

以抽象數據結構和可復用構件為基礎，用類和對象描述數據結構，用結構化程序設計風格描述算法，既能適應計算機硬件指令序列執行的特點，又能方便地進行算法分析。此外，使用面向對象程序設計方法（兼用結構化程序設計）和軟件工程原則訓練編寫小型的應用程序，為日后開發大型計算機系統，有了良好的鋪墊。

2.激發學生學習的興趣，鼓勵學生對教學內容提出問題，師生共同討論，提高教學和學習水平。

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

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

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

3.精心選擇部分習題和上機實習題，著眼于基本知識的理解和基本編程能力的培養。C++模板是一種實現設計復用和代碼復用的有力工具，在程序設計習題選擇時采取循序漸進、逐步積累的方式，引導學生自己建立可復用的構件，并在以后的練習中直接使用，提高編程的工程能力和思考能力。

4.本著“精講多練”的原則，改進考核方式?！皵祿Y構”課程內容很多，程序設計習題的涉及范圍非常廣泛。為此，課程考核從偏重期末考試改變到偏重進行階段考核：增加4次小考核，改變“一考定輸贏”的格局，使學生能夠在平時自覺地給自己加壓，認真對待每一部分的學習。

5.加強實習環節。通過實習，應用VC++環境，完成6個實習作業，讓學生在實習中學會軟件設計、程序編碼和測試，掌握用面向對象方法開發小應用軟件的方法。學生在完成實習作業中傾注了許多心血，當得到教師肯定后充滿成就感，拉近了教師和學生的距離，也為參加科研打下了基礎。

6.編寫高質量的教材和教輔材料?；谡n程目標的要求和計算機技術的發展，不斷改進教材的質量。啟用《數據結構（用面向對象方法和C++語言描述）》教材后，通過教學和參考追蹤國內外最新教材，每年更新電子教案，使得講授內容更符合最新進展。在此基礎上著手修訂新教材，并列入2001年國家教育部“十五”規劃教材系列（已于2005年4月交稿）。為幫助學生更好地學習，2002年出版了《數據結構習題解析（用面向對象方法與C++語言描述）》，作為主教材的輔助教材，在習題集中收集了一批較新的習題，并給出了解題的思路（見圖2）。

此外，在2003年開發完成新的試題庫和自動組題系統，可以根據難度要求和內容要求，自動從試題庫中抽取試題組成試卷。目前完成的還有新的“數據結構動態演示系統”和“動態網頁”（見圖3與圖4）。

四、建設課程教學梯隊

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

五、小結

數據結構課程的建設已經做了許多工作，并建立了國際合作關系。在信息學院和計算機系領導的支持下，通過全體課程組教師的努力，課程建設，包括課程內容的更新、教學方式的改革和網絡化，將有利于學生學習水平的提高。將來的教學將從以“教師”為中心變成以“學生”為中心，數據結構課程正在努力適應這種變化。

我們的下一步工作是：

1.在建設“教育部-微軟精品課程”的過程中，我們與哈爾濱工業大學合作，以我校為主，建立開放的“數據結構”網站，讓我們的資源能夠為全國院校共享。

2.向教育部申請，爭取將數據結構教學方法列入青年骨干教師研修課程計劃，開展數據結構教學經驗的培訓，計劃分C、C++、Java三個專題。

3.《數據結構》教材申報列入國家“十一五”教材規劃，繼續改進教學內容和教學方案。