數據結構課程實踐環(huán)節(jié)的設計

周世平+武秀川+盧云宏

摘 要 文章針對數據結構課程的特點，分析了該門課程實踐環(huán)節(jié)面臨的問題，提出了學生實踐應由簡單驗證、設計、到綜合創(chuàng)新的觀點，對實踐環(huán)節(jié)的實驗課和課程設計兩個階段分別規(guī)劃了驗證型、設計型和綜合型實驗。并且設計型實驗相互關聯，有助于學生過渡到綜合實驗。兩個年級的教學試驗表明，這樣的實踐規(guī)劃幫助學生理解課程，增強學生的數據結構和算法的設計能力，提高了學生的綜合分析、合作完成項目的能力。

關鍵詞 數據結構 實踐環(huán)節(jié) 實驗課 課程設計

中圖分類號：G424 文獻標識碼：A

數據結構課程是計算機科學技術、軟件工程專業(yè)的專業(yè)核心基礎課。其范疇涉及數學、計算機硬件、計算機軟件、數據存儲器分配、數據組織及查找。數據結構課程是程序設計提高的基礎，也是操作系統、編譯系統和數據庫系統等系統程序的重要基礎，尤其對于進行高效率的計算機程序開發(fā)非常重要。

計算機專業(yè)的數據結構課程通常設置在大學的一、二年級，它包括兩個環(huán)節(jié)：課堂教學和實踐環(huán)節(jié)。實踐環(huán)節(jié)設置的目的：首先是讓學生學會將抽象的數據結構表示為具體的物理存儲并使用，將算法轉化為程序，加強對算法的理解；其次，學生要在實踐環(huán)節(jié)實現算法設計、進一步理解算法；最后，學生在實踐環(huán)節(jié)完成算法的測試和比較，理解算法的復雜性。對于僅僅學了一門程序設計課程的學生，不習慣在抽象的層次上解決問題。難以建立數據結構的概念、算法的思想。這樣，實踐環(huán)節(jié)在數據結構課程中占據著極其重要的地位。近年來，人們在實踐環(huán)節(jié)上進行了一些理論方面的探討，①②實踐環(huán)節(jié)有專門的實踐教程，③課程設計不再是一個小項目的實現，也有專門的指導。④多年的教學實踐，我們深切體會到，數據結構課程能否順暢進行，很大程度上取決于實踐環(huán)節(jié)的有效實現。

1 實踐環(huán)節(jié)面臨的問題

實踐環(huán)節(jié)由實驗課和課程設計兩個階段組成。其中實驗課與理論課同步進行，與所學章節(jié)內容密切相關；課程設計是在課堂教學和實驗課結束之后進行的集中的綜合設計，內容可涵蓋課程的全部內容。目前各高校通常在實驗課程階段采用驗證型實驗，即針對給定的數據結構，將教科書中的算法轉化為程序，驗證算法的正確性；在課程設計階段采用設計型實驗，給出若干個題目，讓學生自行考慮所使用的數據結構并設計算法完成題目。我們對這樣的實踐課程進行了分析，并結合學生的反饋信息，總結出實踐環(huán)節(jié)中面臨的主要問題是：（1）數據結構的選擇問題。傳統的實驗課階段是以章節(jié)內容為核心，驗證算法為主，忽略了抽象化的訓練，導致學生在課程設計階段及應用程序開發(fā)中數據結構選擇方面的不足。（2）算法應用的問題。實驗課階段的驗證型實驗誤導學生將算法與程序視為等同，忽略了算法的重要性，看不到算法的應用，直接導致學生在項目設計中很少應用算法設計。還有算法測試部分的缺乏導致學生較少地分析和比較算法。（3）課程設計階段的問題。課程設計往往是單獨一個項目，缺少綜合性。還有，由于實驗課階段與課程設計階段的內容缺少銜接，學生由被動的驗證型實驗過渡到綜合型實驗呈現困難， 喪失完成課程設計的信心，趨于抄襲。（4）實踐環(huán)節(jié)的設計。本文對數據結構課程實踐環(huán)節(jié)的教學內容進行了設計。對實驗課和課程設計兩個階段的內容重新進行了規(guī)劃。強調了實驗階段的設計性和課程設計的綜合性。兩個階段進行有效銜接是數據結構課程實踐教學環(huán)節(jié)任務完成的保障。

2 實踐環(huán)節(jié)的設計思想

實踐環(huán)節(jié)由實驗課和課程設計兩個階段組成。實驗課程階段與理論課同步進行，其內容與教學章節(jié)緊密相關。實驗課階段的實驗可分為驗證型實驗和設計型試驗。驗證型實驗的目的是促進學生對于所學的數據結構與算法的理解，并學會將算法程序實現。設計型實驗的目的是通過具體實例，訓練學生將具體問題進行抽象，設計數據結構和算法。為了向課程設計階段過渡，設計型實驗的題目相互關聯，比如可采用一個綜合項目的子項目作為一個設計型實驗。

課程設計階段采用綜合型實驗，其目的是訓練學生對于比較大的項目能夠進行綜合設計，從項目總體需求設計數據結構和算法，將項目劃分為若干個獨立的子項目。學生可借用前期的設計型實驗，綜合成較大的項目。

3 實驗課階段的實驗設計

實驗課階段的實驗包含驗證型和設計型實驗。下面樣例是關于鏈表的實驗。

3.1 驗證型實驗樣例

【內容】鏈表的實現和基本操作。

【要求】定義鏈表結點，假設鏈表的元素為int類型數據。

（1）程序實現鏈表的基本操作

（a）初始化LinkedListInit（）

（b）創(chuàng)建鏈表LinkedListCreate（）

（c）求表長LinkedListLenth（LinkedList L）

（d）按值查找 LinkedListLocate（LinkedList L， Elemtype x）

（e）插入一個元素 LinkedListInsert（LinkedList L，int i， Elemtype x）

（f）刪除一個元素 LinkedListDelete（LinkedList L，int i）

（g）遍歷順序表 LinkedListInsertTraverse（LinkedList L）

（2）編寫main（）函數，給出實例測試各個基本操作。

3.2 設計型實驗樣例

【內容】鏈表的應用。

已知本市的某一線路公共汽車在早晨高峰期間極其擁擠，乘客要求汽車公司增加早班車的數量?，F在公司派你去調查該線路汽車的乘客數目變化情況，報告上午7：00-8：00該線路在各站的乘客流量。

【要求】創(chuàng)建BusStop類型的結點用以表示站點。用鏈表Line表示該線路。

（1）設計站點的數據結構；endprint

（2）設計線路的數據結構；

（3）設計算法；

（4）程序設計與實現；

（5）選定正常值和邊界值進行測試。

3.3 驗證型實驗與設計型實驗對比分析

我們對驗證型實驗和設計型實驗進行了分析比較，結果如表1所示。

另外，所有設計型實驗均是圍繞市公交系統，相互關聯，為學生的課程設計做準備。

4 課程設計階段的實驗設計

課程設計階段的實驗采用綜合性實驗。

4.1 綜合型實驗樣例

【內容】設計煙臺公交系統。本系統分為三個模塊：乘客查詢模塊、管理模塊和統計模塊。

【要求】三個學生合作完成該系統。對系統進行綜合分析，選擇所用的數據結構和算法。要求用到所學的數據結構至少3個。每個學生選一個模塊，相互測試，共同完成課程設計的實驗報告。

4.2 涉及的數據結構與算法

可選擇的數據結構有：線性表、棧、隊列、稀疏矩陣、二叉樹與樹、圖、查找集合等，以及在這些數據結構上實施的算法。

4.3 設計型實驗和綜合型實驗對比分析

我們對設計型實驗和綜合型實驗進行了分析比較，結果如表2所示。

5 結語

本文論述的數據結構課程實踐環(huán)節(jié)的教學改革設計，于2012年在煙臺大學計算機學院軟件工程專業(yè)和煙臺大學文經學院計算機科學與技術專業(yè)實施。我們將受惠于該設計方案的學生（試驗學生）與其他學生進行了對比，對比結果顯示他們在很多方面表現出優(yōu)勢，見表3。

總之，我們進行的數據結構實踐環(huán)節(jié)的設計是以學生為主體，變學生被動學習為主動學習，重視實踐環(huán)節(jié)中數據結構與算法的設計，強調實驗課階段與課程設計階段的銜接。驗證型、設計型和綜合型三種實驗是由簡單驗證型、構造設計型到綜合分析設計型，循序漸進地培養(yǎng)了學生的實踐能力。兩個年級教學試驗證明其效果良好，值得我們進一步探討、完善，整理出合適的數據結構實踐教材并推廣使用。

注釋

① 張英彥.論實踐教學的理論基礎[J].教育科學，2006.22（4）：34-36.

② 張英彥.論高校實踐教學目標[J].教育研究，2006（5）：46-49.

③ 徐惠.數據結構實踐教程[M].北京：清華大學出版社，2010.

④ 何欽銘，馮雁，陳越.數據結構課程設計.杭州：浙江大學出版社，2007.endprint