“數(shù)據(jù)結(jié)構(gòu)”教學(xué)中提高學(xué)生的編程能力淺談

鄧桂英　高麗萍　李銳　曹春萍　胡德敏

摘 要： 數(shù)據(jù)結(jié)構(gòu)課程主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)進(jìn)行操作的有關(guān)算法。該課程以程序設(shè)計(jì)為基礎(chǔ)，對(duì)學(xué)生進(jìn)行較復(fù)雜程序設(shè)計(jì)的訓(xùn)練，對(duì)學(xué)生編程能力的培養(yǎng)至關(guān)重要。文章著重從如何注重教學(xué)方法、引導(dǎo)學(xué)生學(xué)習(xí)的常用算法、如何進(jìn)行大量程序設(shè)計(jì)實(shí)踐等方面來提高學(xué)生編程能力進(jìn)行了討論。教學(xué)實(shí)踐證明這些教學(xué)方法能很好地提高學(xué)生的編程能力。

關(guān)鍵詞： 編程能力； 教學(xué)方法； 算法； 程序設(shè)計(jì)； 實(shí)踐

中圖分類號(hào)：TP3-0 文獻(xiàn)標(biāo)識(shí)碼：B 文章編號(hào)：1006-8228（2013）08-61-02

0 引言

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)及計(jì)算機(jī)相關(guān)專業(yè)的一門實(shí)踐性較強(qiáng)的軟件基礎(chǔ)課，它內(nèi)容繁多，涉及面廣，主要研究如何把具有一定邏輯關(guān)系的數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)，它是對(duì)數(shù)據(jù)進(jìn)行操作的有關(guān)算法研究的一門學(xué)科[1]，它以程序設(shè)計(jì)為基礎(chǔ)，對(duì)學(xué)生進(jìn)行較復(fù)雜程序設(shè)計(jì)的訓(xùn)練，課程以提高學(xué)生的編程能力培養(yǎng)為主要目標(biāo)。本文對(duì)數(shù)據(jù)結(jié)構(gòu)的教學(xué)方法和實(shí)踐環(huán)節(jié)進(jìn)行探討。

1 注重教學(xué)方法，提高學(xué)生的認(rèn)識(shí)能力

在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)中為了提高學(xué)生的編程能力，應(yīng)注重課堂的教學(xué)方法，使學(xué)生能更好地掌握課程內(nèi)容，理解前人設(shè)計(jì)的算法，為此我們研究了數(shù)據(jù)結(jié)構(gòu)的教學(xué)方法。現(xiàn)代教學(xué)論中，人們把教學(xué)方法歸為兩大類：一類是程序式教學(xué)法，其特點(diǎn)是課堂以教師為中心，有計(jì)劃有步驟地教給學(xué)生教學(xué)大綱上規(guī)定的知識(shí)；另一類是發(fā)現(xiàn)式教學(xué)法，這種教學(xué)法的基本目的不再局限于把前人整理好的知識(shí)傳授給學(xué)生，而是引導(dǎo)、鼓勵(lì)學(xué)生盡可能參與探索知識(shí)的過程，其側(cè)重點(diǎn)在于使學(xué)生領(lǐng)悟和掌握形成知識(shí)的過程和獲取知識(shí)的方法。

在教學(xué)過程中，我們將這兩種方法相結(jié)合，在講解數(shù)據(jù)結(jié)構(gòu)理論基礎(chǔ)知識(shí)時(shí)主要采用程序式教學(xué)法，始終抓住什么是“數(shù)據(jù)結(jié)構(gòu)”這根主線，按照數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算和運(yùn)算的實(shí)現(xiàn)這四步逐層展開討論，做到教學(xué)思路清晰、邏輯性強(qiáng)，引導(dǎo)學(xué)生理解程序的運(yùn)行原理和過程，并且對(duì)于不同層次的學(xué)生具體采用不同的方法。在講解數(shù)據(jù)結(jié)構(gòu)算法的實(shí)現(xiàn)時(shí)，我們發(fā)現(xiàn)有些班的學(xué)生對(duì)編程普遍懷有恐懼感，針對(duì)這種情況教師與學(xué)生一起按常人的邏輯思維方式考慮解決問題的方法，歸納出解決問題的方法和步驟，按方法和步驟與學(xué)生一起一步一步地寫出程序，然后回過去重讀一遍程序，并將不夠理想的地方加以改進(jìn)，使學(xué)生知道原來教師考慮問題的思路和自己的思路基本是一樣的，這樣引導(dǎo)學(xué)生編程的過程可使學(xué)生獲益匪淺，再經(jīng)過大量地由淺入深地訓(xùn)練后，學(xué)生消除了恐懼感，增強(qiáng)了信心，對(duì)編程逐漸也產(chǎn)生了興趣。

數(shù)據(jù)結(jié)構(gòu)中的內(nèi)容很豐富，為使學(xué)生更好地掌握，我們將教學(xué)重點(diǎn)放在使用廣泛的數(shù)據(jù)結(jié)構(gòu)上，精講最基本的概念與方法，并在這基礎(chǔ)上例舉一些綜合的算法例子，通常借助于發(fā)現(xiàn)式教學(xué)法的思想進(jìn)行教學(xué)，提供背景材料，講透算法思想，提出問題，鼓勵(lì)學(xué)生思考、分析，舉一反三，讓學(xué)生自己設(shè)計(jì)出多種算法。例如，在講解數(shù)據(jù)結(jié)構(gòu)中的遞歸算法時(shí)，由于遞歸算法是數(shù)據(jù)結(jié)構(gòu)中最難掌握的內(nèi)容之一，學(xué)生一般不能很快接受，因此講解遞歸算法的方法很重要。我們先從學(xué)生較易接受的數(shù)學(xué)函數(shù)計(jì)算入手，進(jìn)而引入非數(shù)值的遞歸算法，為了使學(xué)生了解嵌套調(diào)用、層層返回等概念，畫出遞歸運(yùn)行的狀態(tài)圖和棧的變化圖，告訴學(xué)生嵌套調(diào)用和返回的含義，概括出“遞歸進(jìn)入一層，則進(jìn)棧，遞歸退出一層，則退?！钡姆椒?，使學(xué)生一目了然。在掌握了基本遞歸算法及運(yùn)行過程后，進(jìn)一步例舉稍難的遞歸算法，使學(xué)生從多個(gè)方面加深對(duì)遞歸算法的理解，這對(duì)數(shù)據(jù)結(jié)構(gòu)后續(xù)內(nèi)容中的樹、圖、查找和排序算法設(shè)計(jì)的學(xué)習(xí)是很有幫助的。

2 注重常用的、經(jīng)典算法的學(xué)習(xí)，以激起探索研究的愿望

在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)過程中我們強(qiáng)調(diào)基本的編程方法和常用的算法的介紹，并指導(dǎo)學(xué)生積累常用算法，積累經(jīng)典的好算法，例如查找算法、排序算法、遍歷算法和圖操作算法等，這樣使學(xué)生在解決復(fù)雜問題之前掌握可使用的基本方法，可借鑒好算法的思想來拓展自己的思路。

數(shù)據(jù)結(jié)構(gòu)中有很多經(jīng)典的好算法，它們是著名的計(jì)算機(jī)科學(xué)家的成果。我們不僅要學(xué)習(xí)算法的設(shè)計(jì)思想，還要學(xué)習(xí)算法設(shè)計(jì)的思維方式，以提高學(xué)生的邏輯思維能力。以最小生成樹兩種方法為例，①普里姆（Prim）算法以圖中的點(diǎn)為主，通過點(diǎn)朝最小邊權(quán)伸張出去的方式來求解，其時(shí)間復(fù)雜度為O（n2）（n為圖的頂點(diǎn)個(gè)數(shù)），它與圖中的邊數(shù)無關(guān)，因此適用于求邊稠密的圖的最小生成樹，但在如何判斷加入一條邊而不形成回路的問題上就遇到了困難；②克魯斯卡爾（Kruskal）求最小生成樹算法以邊為主，容易判斷加入新頂點(diǎn)是否產(chǎn)生回路的問題，其時(shí)間復(fù)雜度為O（eloge）（e為圖中邊的個(gè)數(shù)），因此適合求邊稀疏的圖的最小生成樹。求解同一個(gè)問題時(shí)，不同的算法具備不同的特點(diǎn)，適應(yīng)不同的范圍，這樣分析討論，可使學(xué)生思路暢通，激發(fā)起探研的愿望。再例，數(shù)據(jù)結(jié)構(gòu)中的排序算法可分類討論，由個(gè)別到一般，由具體到抽象形成算法的設(shè)計(jì)，并進(jìn)行算法的初步分析，其中有些算法的分析并未得到完整的答案，例如，希爾排序的分析就是一個(gè)復(fù)雜的問題，因?yàn)樗臅r(shí)間復(fù)雜度是所取“增量”序列的函數(shù)，只是得出一些局部的結(jié)論。雖然我們不一定要引導(dǎo)學(xué)生去專門鉆研這些難題，但是，提出并分析這些問題至少可以提高學(xué)生的學(xué)習(xí)興趣，形成研究問題的情景，對(duì)數(shù)據(jù)結(jié)構(gòu)中的許多問題留下思考和探索的空間，從中啟發(fā)出今后需要深入研究的問題，這樣有利于對(duì)學(xué)生能力的培養(yǎng)。

3 加強(qiáng)實(shí)驗(yàn)環(huán)節(jié)，以提高學(xué)生的編程能力

數(shù)據(jù)結(jié)構(gòu)是一門理論和實(shí)踐性都很強(qiáng)的課程，學(xué)習(xí)它的主要目的是提高學(xué)生的編程能力，而學(xué)會(huì)編程、提高編程的能力并不是輕而易舉的，要通過長時(shí)間的實(shí)踐鍛煉，要學(xué)生自己多動(dòng)手去體驗(yàn)，有些問題只有通過實(shí)踐后才能明白，也只有實(shí)踐才能把教師和書本上的知識(shí)變成自己的。因此我們?cè)诮虒W(xué)過程中針對(duì)每個(gè)環(huán)節(jié)都布置一定數(shù)量的上機(jī)實(shí)踐題目，有基礎(chǔ)題、有綜合題，還有結(jié)合實(shí)際的綜合應(yīng)用題。例如基礎(chǔ)題有順序表、鏈表的創(chuàng)建、查找、插入、刪除；棧、隊(duì)列的操作；二叉樹的遍歷；圖的存儲(chǔ)實(shí)現(xiàn)；查找；排序等。綜合題有一種結(jié)構(gòu)上的綜合操作題如兩個(gè)鏈表的合并操作就是查找、插入和刪除基本操作的綜合，還有多種結(jié)構(gòu)上的綜合操作題，如圖的遍歷搜索演示實(shí)驗(yàn)，它可綜合考查學(xué)生對(duì)字符串、鏈表、棧、隊(duì)列、圖的遍歷和遞歸算法等的理解和綜合應(yīng)用能力，這種實(shí)驗(yàn)題知識(shí)點(diǎn)覆蓋了數(shù)據(jù)結(jié)構(gòu)的絕大部分內(nèi)容，具有較強(qiáng)的綜合性。我們舉幾個(gè)結(jié)合實(shí)際應(yīng)用的例題。

例1：用二叉排序樹與單鏈表相結(jié)合來實(shí)現(xiàn)學(xué)生成績管理。

用二叉排序樹存放成績，用鏈表存放學(xué)生信息，相同成績的學(xué)生連在一個(gè)鏈表中并由二叉排序樹相應(yīng)結(jié)點(diǎn)指向，具體鏈表結(jié)點(diǎn)形式：

二叉樹結(jié)點(diǎn)形式：

程序具有前序、中序、后序遍歷瀏覽所有信息功能、有各信息查詢功能、有統(tǒng)計(jì)成績功能、有鏈表結(jié)點(diǎn)插入和樹結(jié)點(diǎn)插入功能，有鏈表結(jié)點(diǎn)刪除和樹結(jié)點(diǎn)刪除等功能，對(duì)編程基礎(chǔ)好的學(xué)生還要求將二叉排序樹改為平衡樹來完成。

例2：用棧解決算術(shù)表達(dá)式求值演示。根據(jù)算符優(yōu)先關(guān)系，實(shí)現(xiàn)算術(shù)四則混合運(yùn)算表達(dá)式的求值，演示在求值中運(yùn)算符棧、操作數(shù)棧、輸入字符和主要操作的變化過程。

例3：用棧隊(duì)列進(jìn)行停車場管理。以棧模擬停車場，以隊(duì)列模擬車場外的通道，從輸入的數(shù)據(jù)序列進(jìn)行模擬管理。

例4：用圖進(jìn)行上海導(dǎo)游咨詢。以圖中頂點(diǎn)表示上海各主要景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等，以邊表示路徑，存放路徑長度等相關(guān)信息，程序具有為游客提供各景點(diǎn)相關(guān)信息的查詢，有查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑等功能。

為了達(dá)到預(yù)期實(shí)驗(yàn)效果，在做每個(gè)實(shí)驗(yàn)時(shí)，要求學(xué)生上機(jī)運(yùn)行所編程序，教師認(rèn)真檢查程序運(yùn)行結(jié)果及程序的測試數(shù)據(jù)，必要時(shí)查看學(xué)生所編寫的程序，了解他們的編程思想；將編程風(fēng)格好、解決方案好的程序作為例子給學(xué)生講解，鼓勵(lì)他們多觀察、分析、比較、積累，遇到問題時(shí)多想幾種解決方案；通過分析這些程序，培養(yǎng)學(xué)生良好的編程習(xí)慣，讓他們明白編程風(fēng)格的好壞在很大程度上影響程序的質(zhì)量。良好的編程風(fēng)格可以使程序結(jié)構(gòu)清晰合理，且使程序代碼便于維護(hù)。我們經(jīng)過這樣大量的上機(jī)實(shí)踐，使學(xué)生的編程能力、上機(jī)調(diào)試能力得到很大的提高。

4 結(jié)束語

本文探討了提高學(xué)生編程能力的具體教學(xué)措施，這些措施需要結(jié)合教學(xué)方法靈活地加以運(yùn)用。我們積累了大量的教學(xué)實(shí)驗(yàn)用例，幫助學(xué)生開闊視野，增強(qiáng)學(xué)習(xí)的動(dòng)力，進(jìn)而提高學(xué)生學(xué)習(xí)的自覺性，使他們的學(xué)習(xí)過程走向良性循環(huán)的軌道。我們經(jīng)過幾年的數(shù)據(jù)結(jié)構(gòu)教學(xué)實(shí)踐，學(xué)生的編程能力普遍提高，證明了上述教學(xué)方法是有效的。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].清華大學(xué)出版社，2011.

[2] 許自龍.關(guān)于《數(shù)據(jù)結(jié)構(gòu)》的教學(xué)實(shí)踐和體會(huì)[J].信息技術(shù)教學(xué)與研究，2012.4.

[3] 呂國英.算法設(shè)計(jì)與分析（第二版）[M].清華大學(xué)出版社，2011.

[4] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)題集[M].清華大學(xué)出版社，2011.

[5] 嚴(yán)蔚敏，陳文博.數(shù)據(jù)結(jié)構(gòu)及應(yīng)用算法教程[M].清華大學(xué)出版社，2009.