數(shù)據(jù)結(jié)構(gòu)課程案例式教學(xué)方法探討＊

孫 悅，蘇利敏，江 靜

(北京聯(lián)合大學(xué)智慧城市學(xué)院，北京 100101)

0 引言

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

1 存在問題

1.1 學(xué)生基礎(chǔ)薄弱

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

1.2 學(xué)時(shí)設(shè)置

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

2 各章案例選擇

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

2.1 案例選擇要求

根據(jù)學(xué)生水平差異，設(shè)置難度級(jí)別不同的案例，將難度較高的案例留給學(xué)生課后完成。在這里，案例選擇時(shí)應(yīng)該滿足以下條件。

⑴案例要能最大限度地調(diào)動(dòng)學(xué)生的參與度，接近學(xué)生生活，讓學(xué)生很容易進(jìn)入案例情景。

⑵案例要具有代表性，與準(zhǔn)備講解的知識(shí)點(diǎn)高度相關(guān)。

⑶案例要有助于學(xué)生深刻理解數(shù)據(jù)結(jié)構(gòu)模型，并引起學(xué)生的探究和思考，能對(duì)所學(xué)數(shù)據(jù)結(jié)構(gòu)加以變形應(yīng)用。

⑷案例難易程度和學(xué)生水平相當(dāng)，學(xué)生學(xué)習(xí)后，能夠獨(dú)立實(shí)現(xiàn)該案例。

⑸授課過程中，注意課程的銜接性，適當(dāng)選用后續(xù)課程中會(huì)應(yīng)用到的數(shù)據(jù)結(jié)構(gòu)類型相關(guān)案例，以此提升學(xué)生的關(guān)注度。

2.2 各章案例選擇注意事項(xiàng)

⑴線性表

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

⑵棧和隊(duì)列

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

⑶樹

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

⑷圖

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

3 教學(xué)實(shí)施過程

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

3.1 案例引入

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

3.2 數(shù)據(jù)結(jié)構(gòu)及其操作

傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)教學(xué)方法主要注重?cái)?shù)據(jù)結(jié)構(gòu)的基本概念和各種數(shù)據(jù)結(jié)構(gòu)相關(guān)的常用算法，引入案例式教學(xué)方法后，這部分仍然是教學(xué)的重點(diǎn)，并且要結(jié)合案例實(shí)現(xiàn)，分析需要用到的算法，有針對(duì)性地引入，作為重點(diǎn)部分先介紹。還可以考慮案例的特殊性，補(bǔ)充一些通用的操作算法。

3.3 案例分析與實(shí)現(xiàn)

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

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

教學(xué)過程中采用循序漸進(jìn)的方式，除了前面兩章的內(nèi)容講解完整案例外，后面的案例不再給出完整程序，只需提供程序框架，將數(shù)據(jù)結(jié)構(gòu)的表示、構(gòu)建和操作實(shí)現(xiàn)的程序框架搭建好提供給學(xué)生，根據(jù)學(xué)生編程能力進(jìn)展程度，選擇合適時(shí)機(jī)布置完全由學(xué)生獨(dú)立完成的案例。

4 結(jié)束語

數(shù)據(jù)結(jié)構(gòu)的教學(xué)內(nèi)容較為抽象，所以對(duì)于課程中比較抽象的概念可以盡量先從學(xué)生熟知的案例講起，老師引導(dǎo)學(xué)生討論案例，通過案例分析引入相關(guān)知識(shí)，并用所學(xué)知識(shí)解決案例，最后通過實(shí)踐環(huán)節(jié)完成案例。通過實(shí)踐過程中真正實(shí)現(xiàn)不同的案例，才能讓學(xué)生在學(xué)習(xí)過程中不再是簡單的閱讀算法，擺脫水中看月的感覺，最終使得學(xué)生在軟件開發(fā)的過程中，能夠?yàn)榍蠼獾木唧w問題選擇合理的數(shù)據(jù)結(jié)構(gòu)，能夠應(yīng)用高級(jí)語言編寫和實(shí)現(xiàn)結(jié)構(gòu)清晰、正確、易讀的有效算法，達(dá)到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程的目標(biāo)。