“數據結構”教學中提高學生的編程能力淺談

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

摘 要： 數據結構課程主要研究數據的邏輯結構和數據的存儲結構，以及對數據進行操作的有關算法。該課程以程序設計為基礎，對學生進行較復雜程序設計的訓練，對學生編程能力的培養至關重要。文章著重從如何注重教學方法、引導學生學習的常用算法、如何進行大量程序設計實踐等方面來提高學生編程能力進行了討論。教學實踐證明這些教學方法能很好地提高學生的編程能力。

關鍵詞： 編程能力； 教學方法； 算法； 程序設計； 實踐

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

0 引言

數據結構是計算機專業及計算機相關專業的一門實踐性較強的軟件基礎課，它內容繁多，涉及面廣，主要研究如何把具有一定邏輯關系的數據在計算機中存儲，它是對數據進行操作的有關算法研究的一門學科[1]，它以程序設計為基礎，對學生進行較復雜程序設計的訓練，課程以提高學生的編程能力培養為主要目標。本文對數據結構的教學方法和實踐環節進行探討。

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

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

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

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

2 注重常用的、經典算法的學習，以激起探索研究的愿望

在數據結構課程教學過程中我們強調基本的編程方法和常用的算法的介紹，并指導學生積累常用算法，積累經典的好算法，例如查找算法、排序算法、遍歷算法和圖操作算法等，這樣使學生在解決復雜問題之前掌握可使用的基本方法，可借鑒好算法的思想來拓展自己的思路。

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

3 加強實驗環節，以提高學生的編程能力

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

例1：用二叉排序樹與單鏈表相結合來實現學生成績管理。

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

二叉樹結點形式：

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

例2：用棧解決算術表達式求值演示。根據算符優先關系，實現算術四則混合運算表達式的求值，演示在求值中運算符棧、操作數棧、輸入字符和主要操作的變化過程。

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

例4：用圖進行上海導游咨詢。以圖中頂點表示上海各主要景點，存放景點名稱、代號、簡介等，以邊表示路徑，存放路徑長度等相關信息，程序具有為游客提供各景點相關信息的查詢，有查詢任意兩個景點之間的最短路徑等功能。

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

4 結束語

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

參考文獻：

[1] 嚴蔚敏，吳偉民.數據結構（C語言版）[M].清華大學出版社，2011.

[2] 許自龍.關于《數據結構》的教學實踐和體會[J].信息技術教學與研究，2012.4.

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

[4] 嚴蔚敏，吳偉民.數據結構題集[M].清華大學出版社，2011.

[5] 嚴蔚敏，陳文博.數據結構及應用算法教程[M].清華大學出版社，2009.