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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻：

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

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

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

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

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