孫 悅，蘇利敏，江 靜

(北京聯合大學智慧城市學院，北京 100101)

0 引言

數據結構課程既涉及硬件存儲又涉及軟件算法，對學生抽象思維及編程能力要求較高[1]。目前其教學方式以教師講授為主，講授內容為基本概念和基本算法，教師將大部分時間投入到內容的講解中，而學生處于被動接收地位，其主動研究、探索的機會受到很大限制。而且數據結構這門課程教學上缺少實例，不能使學生融會貫通，當面對具體問題時，不知該如何運用學過的知識給出切實可行的解決方案。如何改善數據結構課程的教學效果，提高學生學習興趣，是目前任課老師要迫切解決的問題。本文主要考慮學生編程能力的一般情況，轉變傳統(tǒng)的教學模式，對案例式教學方法展開探討。

1 存在問題

1.1 學生基礎薄弱

目前我校使用的數據結構課程教材以類C語言為描述工具，多數普通高校的學生，沒有編程基礎，大學一年級只修了C 語言程序設計這一門高級語言課程，由于教學計劃等原因，C語言的課時安排往往不夠用，通常只有48 學時理論，16 學時上機實驗，多數學生學完后僅達到入門水平。另外，C 語言程序設計和數據結構這兩門課程通常由不同任課教師擔任，導致兩門課程在教學內容上出現知識銜接的斷層。數據結構課程對C語言中的結構體和指針等知識涉及較多，而這部分內容在C語言課程授課過程中由于學時有限，往往被一筆帶過，學生對該部分內容無法熟練應用，例如當遇到大量的C語言偽代碼時，學生就會覺得難懂，生出畏難情緒，給授課教師也帶來重重困難。

1.2 學時設置

目前，大多數高校數據結構課程的上機實踐學時短缺，學生實踐機會偏少，教學是以利用偽代碼描述數據結構和算法為主，以編程實踐為輔，實踐教學不能支撐起理論教學，上機實踐過少，學生在理解算法時只停留在表面[2]。本校數據結構課程開設學時數為64 學時，其中理論48 學時，實驗16 學時，另外設置課程設計1 周。如果依靠課內理論學時，是沒有辦法既講解數據結構基本概念和算法，又講解足夠的案例，不得已需要借助課外學時及實踐學時來彌補，而在學生主動性不夠的情況下，需要老師做出合理的安排和引導，準備的完整案例程序來講解，幫助學生盡快補足所缺知識。

2 各章案例選擇

教師選擇典型且難度適宜的案例，引導學生利用已有的知識背景，在實現案例的過程中發(fā)現問題、分析問題和解決問題。通過案例式教學緊緊圍繞所學知識點，借助項目案例使理論和實踐緊密結合，不但提高學生學習興趣，幫助學生理解相關知識點，而且提高學生編程能力，培養(yǎng)學生解決實際問題能力，讓學生在學完本課程后不僅僅是知道幾種數據結構的特點，了解一些算法，而是能做到學以致用，解決問題。

2.1 案例選擇要求

根據學生水平差異，設置難度級別不同的案例，將難度較高的案例留給學生課后完成。在這里，案例選擇時應該滿足以下條件。

⑴案例要能最大限度地調動學生的參與度，接近學生生活，讓學生很容易進入案例情景。

⑵案例要具有代表性，與準備講解的知識點高度相關。

⑶案例要有助于學生深刻理解數據結構模型，并引起學生的探究和思考，能對所學數據結構加以變形應用。

⑷案例難易程度和學生水平相當，學生學習后，能夠獨立實現該案例。

⑸授課過程中，注意課程的銜接性，適當選用后續(xù)課程中會應用到的數據結構類型相關案例，以此提升學生的關注度。

2.2 各章案例選擇注意事項

⑴線性表

線性表是數據結構課程引入的第一個數據結構類型，也是最基礎的，針對順序表，保證學生能夠熟練地操作數組元素，鏈表部分由于會涉及大量指針操作，要重點講解。作為初學章節(jié)，此章案例不易過難，以多項式求和及合并有序表為例即可，要求完成線性表的創(chuàng)建、插入、刪除和遍歷等基本操作。本部分教學是解決學生基礎薄弱的關鍵一步，太難的案例會讓學生產生挫敗感，甚至因實現困難而再次放棄學習。所以，理論課學時部分可以補充結構體和指針相關知識點，案例實現時需要給學生完整程序，并詳細講解所有語句，或者實踐課上帶著學生做，讓學生在原有C語言基礎上，對數組、結構體和指針等知識點能夠完全掌握，保證后面教學的正常進行。

⑵棧和隊列

棧與隊列，在計算機教學過程中是比較常用的兩個數據結構。借此章節(jié)，進一步鞏固對線性表的操作，同時強調這兩個數據結構的特點。棧最大的特點是先進后出，逆序輸出是棧經常用到的一個應用場景。其他主要應用包括數值轉換、括號匹配、表達式求值和迷宮求解等，前兩個案例較為簡單，只講算法即可?？梢赃x取表達式求值為完整實現案例，后面介紹二叉樹內容時，用創(chuàng)建表達式樹的內容與之相呼應。另外，要重點介紹棧在函數調用過程中的作用和棧在遞歸調用中的作用，如果學生對遞歸算法不是很熟悉，選擇一個案例，采用遞歸和非遞歸兩種方法來實現，闡明遞歸存在的缺點，以及用棧來實現遞歸的方法。隊列是一種特殊的線性表，遵循先進先出的原則。凡是用到先進先出的場合，比如日常生活中各種采用先來先服務的場合都可以采用隊列。其中較為特殊的是循環(huán)隊列的應用，后續(xù)操作系統(tǒng)課程教學過程中涉及的生產者與消費者問題，使用循環(huán)隊列解決循環(huán)使用緩沖區(qū)，這里可以提前引入講解。除此以外，在計算機領域，編譯器中表達式的處理、函數的調用要用到棧；操作系統(tǒng)中的作業(yè)和進程排隊、內存分配、設備管理均要用到隊列；數據庫中使用線性表、索引表等進行數據管理[3]。這些應用和后續(xù)課程密切相關，可以在舉例時提出，提高學生的興趣。

⑶樹

樹結構本身是遞歸定義的，對二叉樹的各種操作也是在遍歷過程中實現的，所以這一章的重點內容是二叉樹的遍歷算法，此章案例可選取一些簡單的遞歸算法幫助學生進一步理解遞歸，比如：統(tǒng)計葉子結點個數、計算樹的深度等，課內學時就可以實現。實際應用中，課內教學多數教材以哈夫曼編碼為重點[4-5]，因此，可以選擇哈夫曼樹的創(chuàng)建、哈夫曼編碼和譯碼為典型案例，介紹整體實現，這樣更有助于學生加深對哈夫曼樹的創(chuàng)建和編碼譯碼過程的理解。這個案例相對規(guī)模較大，學生學到這一章時，編程能力應該已經有較大提高，可以編制一些更為復雜的案例。其他與樹結構相關的應用主要是查找和排序，查找算法中有二叉排序樹的創(chuàng)建和查找，排序算法中有堆排序。后續(xù)課程中樹結構的典型應用主要用于文件系統(tǒng)。

⑷圖

圖結構中以遍歷圖的兩種算法作為重點，即深度優(yōu)先搜索和廣度優(yōu)先搜索。深度優(yōu)先搜索算法類似樹的先序遍歷，本質上也是使用棧實現，常用于解決類似迷宮的問題，此處可結合前面的迷宮算法。廣度優(yōu)先算法的原理類似于樹的層次遍歷，并且算法使用了隊列。所以這部分案例的實現，可以結合前面所學內容，進行對比，并且嘗試將不同數據結構的應用統(tǒng)一到一個案例中。拓撲排序的應用包括課程選修的先決條件、檢測死鎖、計算作業(yè)的流水線、解析電子表格中的公式等[6]，可以選擇學生最熟悉的課程選修的先決條件案例。最短路徑算法的應用包括查找一個地方到另一個地方的最快方式，查找一個城市到另一個城市的最便宜交通方式或類似問題[6]，可選擇應用廣泛的最短路徑問題。工程關鍵路徑相關問題難度較高，可安排學生課后選擇完成。

3 教學實施過程

講授每個數據結構時，通過講解一個完整的案例，分析如何利用所學知識解決實際問題，具體的實施過程可按照“案例引入——數據結構及其操作——案例分析與實現”的思路來展開教學，通過案例式教學強化學生對該知識體系的認識，從而降低學習的難度。課程的學習過程也是學生進行復雜程序設計的訓練過程，從而達到培養(yǎng)學生分析解決實際問題的能力，切實提高學生利用所學數據結構編制復雜算法程序的水平。

3.1 案例引入

每類數據結構引入時使用一個有趣的“問題案例”開頭，由該案例逐步引入新的數據結構，然后給出該數據結構的存儲表示及各種基本操作的實現，對重點難點和抽象的內容增加圖示進行講解，突出其結構的實用性和應用性。教師把事先選擇好的案例實現要求發(fā)給學生，讓學生帶著案例所提出的問題去理解和運用教材中的理論知識，這樣不僅提高了學生分析問題和解決問題的能力，而且激發(fā)了學生的學習熱情。講解這些案例時，首先分析需要實現的功能，然后選擇并構造數據結構，使用與特定數據結構相應的算法來實現具體功能。案例的分析解決過程，就是一個實踐軟件工程思想的過程。

3.2 數據結構及其操作

傳統(tǒng)的數據結構教學方法主要注重數據結構的基本概念和各種數據結構相關的常用算法，引入案例式教學方法后，這部分仍然是教學的重點，并且要結合案例實現，分析需要用到的算法，有針對性地引入，作為重點部分先介紹。還可以考慮案例的特殊性，補充一些通用的操作算法。

3.3 案例分析與實現

從解決實際問題出發(fā)，精選實用案例，注重學以致用，案例實現采用定義規(guī)范、流程清楚、可讀性強、具備參考價值的代碼案例，促使學生養(yǎng)成良好的編程習慣。教師針對精選的案例，分析解決方案，引導學生積極思考，最后對案例進行實現，將這部分內容作為教學中的重點部分，通過對典型案例的講授，教給學生解決實際問題的方法，解決學生基礎薄弱問題，幫助學生找到突破口，通過自己的努力完成實踐任務，改進教學效果，提高學生解決實際問題的能力。

實施過程中采用課前引入、課堂講授和課下實現的方式。充分利用實踐教學環(huán)節(jié)和課外時間，解決學時緊張問題，利用實踐學時補充講解案例，利用課外學時督促學生完成案例。根據學生水平，給出不同案例，如果學生整體水平較低，可以在實驗課上詳細講解，帶著學生完成一部分內容，其余的要求學生充分利用課外時間完成，為保證完成的效果，課上要進行檢查，并安排部分案例由學生獨立完成。

教學過程中采用循序漸進的方式，除了前面兩章的內容講解完整案例外，后面的案例不再給出完整程序，只需提供程序框架，將數據結構的表示、構建和操作實現的程序框架搭建好提供給學生，根據學生編程能力進展程度，選擇合適時機布置完全由學生獨立完成的案例。

4 結束語

數據結構的教學內容較為抽象，所以對于課程中比較抽象的概念可以盡量先從學生熟知的案例講起，老師引導學生討論案例，通過案例分析引入相關知識，并用所學知識解決案例，最后通過實踐環(huán)節(jié)完成案例。通過實踐過程中真正實現不同的案例，才能讓學生在學習過程中不再是簡單的閱讀算法，擺脫水中看月的感覺，最終使得學生在軟件開發(fā)的過程中，能夠為求解的具體問題選擇合理的數據結構，能夠應用高級語言編寫和實現結構清晰、正確、易讀的有效算法，達到學習數據結構課程的目標。