周世平+武秀川+盧云宏

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)課階段的實(shí)驗(yàn)設(shè)計(jì)

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

3.1 驗(yàn)證型實(shí)驗(yàn)樣例

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

【要求】定義鏈表結(jié)點(diǎn)，假設(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）插入一個(gè)元素 LinkedListInsert（LinkedList L，int i， Elemtype x）

（f）刪除一個(gè)元素 LinkedListDelete（LinkedList L，int i）

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

（2）編寫main（）函數(shù)，給出實(shí)例測(cè)試各個(gè)基本操作。

3.2 設(shè)計(jì)型實(shí)驗(yàn)樣例

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

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

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

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

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

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

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

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

3.3 驗(yàn)證型實(shí)驗(yàn)與設(shè)計(jì)型實(shí)驗(yàn)對(duì)比分析

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

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

4 課程設(shè)計(jì)階段的實(shí)驗(yàn)設(shè)計(jì)

課程設(shè)計(jì)階段的實(shí)驗(yàn)采用綜合性實(shí)驗(yàn)。

4.1 綜合型實(shí)驗(yàn)樣例

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

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

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

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

4.3 設(shè)計(jì)型實(shí)驗(yàn)和綜合型實(shí)驗(yàn)對(duì)比分析

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

5 結(jié)語

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

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

注釋

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

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

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

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