數(shù)據(jù)結(jié)構(gòu)課程實踐環(huán)節(jié)的設(shè)計

周世平+武秀川+盧云宏

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

關(guān)鍵詞 數(shù)據(jù)結(jié)構(gòu) 實踐環(huán)節(jié) 實驗課 課程設(shè)計

中圖分類號：G424 文獻(xiàn)標(biāo)識碼：A

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

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

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

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

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

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

課程設(shè)計階段采用綜合型實驗，其目的是訓(xùn)練學(xué)生對于比較大的項目能夠進(jìn)行綜合設(shè)計，從項目總體需求設(shè)計數(shù)據(jù)結(jié)構(gòu)和算法，將項目劃分為若干個獨(dú)立的子項目。學(xué)生可借用前期的設(shè)計型實驗，綜合成較大的項目。

3 實驗課階段的實驗設(shè)計

實驗課階段的實驗包含驗證型和設(shè)計型實驗。下面樣例是關(guān)于鏈表的實驗。

3.1 驗證型實驗樣例

【內(nèi)容】鏈表的實現(xiàn)和基本操作。

【要求】定義鏈表結(jié)點，假設(shè)鏈表的元素為int類型數(shù)據(jù)。

（1）程序?qū)崿F(xiàn)鏈表的基本操作

（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（）函數(shù)，給出實例測試各個基本操作。

3.2 設(shè)計型實驗樣例

【內(nèi)容】鏈表的應(yīng)用。

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

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

（1）設(shè)計站點的數(shù)據(jù)結(jié)構(gòu)；endprint

（2）設(shè)計線路的數(shù)據(jù)結(jié)構(gòu)；

（3）設(shè)計算法；

（4）程序設(shè)計與實現(xiàn)；

（5）選定正常值和邊界值進(jìn)行測試。

3.3 驗證型實驗與設(shè)計型實驗對比分析

我們對驗證型實驗和設(shè)計型實驗進(jìn)行了分析比較，結(jié)果如表1所示。

另外，所有設(shè)計型實驗均是圍繞市公交系統(tǒng)，相互關(guān)聯(lián)，為學(xué)生的課程設(shè)計做準(zhǔn)備。

4 課程設(shè)計階段的實驗設(shè)計

課程設(shè)計階段的實驗采用綜合性實驗。

4.1 綜合型實驗樣例

【內(nèi)容】設(shè)計煙臺公交系統(tǒng)。本系統(tǒng)分為三個模塊：乘客查詢模塊、管理模塊和統(tǒng)計模塊。

【要求】三個學(xué)生合作完成該系統(tǒng)。對系統(tǒng)進(jìn)行綜合分析，選擇所用的數(shù)據(jù)結(jié)構(gòu)和算法。要求用到所學(xué)的數(shù)據(jù)結(jié)構(gòu)至少3個。每個學(xué)生選一個模塊，相互測試，共同完成課程設(shè)計的實驗報告。

4.2 涉及的數(shù)據(jù)結(jié)構(gòu)與算法

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

4.3 設(shè)計型實驗和綜合型實驗對比分析

我們對設(shè)計型實驗和綜合型實驗進(jìn)行了分析比較，結(jié)果如表2所示。

5 結(jié)語

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

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

注釋

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

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

③ 徐惠.數(shù)據(jù)結(jié)構(gòu)實踐教程[M].北京：清華大學(xué)出版社，2010.

④ 何欽銘，馮雁，陳越.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計.杭州：浙江大學(xué)出版社，2007.endprint