文章編號：1672-5913(2008)20-0095-03

摘 要：數(shù)據(jù)結(jié)構(gòu)是一門理論性和抽象性很強(qiáng)的專業(yè)核心課程。本文提出了一種從上至下，從抽象到具體的分層教學(xué)演化模式，符合學(xué)生思維的演化過程，從而降低了該課程的學(xué)習(xí)難度。通過實(shí)踐證明該模式配合內(nèi)容的設(shè)計有較好的教學(xué)效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；教學(xué)模式；層次

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：B

1 引言

數(shù)據(jù)結(jié)構(gòu)是計算機(jī)軟件設(shè)計的重要理論基礎(chǔ)，已成為計算機(jī)專業(yè)及相關(guān)專業(yè)的核心課程。數(shù)據(jù)結(jié)構(gòu)研究的基本問題是數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系在計算機(jī)中的表示，在此基礎(chǔ)上根據(jù)計算機(jī)計算特征開展對數(shù)據(jù)處理方法的探討。采用馮·諾伊曼體系結(jié)構(gòu)計算機(jī)以順序的方式執(zhí)行指令，數(shù)據(jù)用二進(jìn)制形式，從而決定了計算機(jī)處理的數(shù)據(jù)和計算有其獨(dú)有的特點(diǎn)。而學(xué)生具備帶回溯特點(diǎn)的感性和理性思維方式，可處理的數(shù)據(jù)以及思維模式極具多樣性和復(fù)雜性，因此學(xué)生和計算機(jī)能處理的數(shù)據(jù)和計算模式均呈現(xiàn)各自不同特點(diǎn)，從而導(dǎo)致了學(xué)生學(xué)習(xí)該門課程的難度加大。因此找到二者完美的結(jié)合點(diǎn)對于降低該門課程的學(xué)習(xí)難度顯得尤為重要。

要達(dá)到這個目的，必須在教學(xué)模式的選擇、教學(xué)內(nèi)容設(shè)計以及教學(xué)手段的選擇三個方面進(jìn)行提高。本文從教學(xué)模式方面進(jìn)行討論，充分考慮到計算機(jī)與學(xué)生計算特征的異同，采取從抽象到具體、從粗糙到精確的分層教學(xué)方式，將大問題分解為小問題，從而在二者之間架起一座橋梁，起到降低該課程學(xué)習(xí)難度的目的。

2 分層教學(xué)模式

2.1 數(shù)據(jù)結(jié)構(gòu)相關(guān)概念

2.1.1 數(shù)據(jù)結(jié)構(gòu)關(guān)系模型

計算機(jī)面臨的任務(wù)是處理現(xiàn)實(shí)世界提出的需求，其中數(shù)據(jù)結(jié)構(gòu)起著橋梁作用。根據(jù)數(shù)據(jù)結(jié)構(gòu)、現(xiàn)實(shí)世界、計算機(jī)以及算法的關(guān)系，可以構(gòu)建數(shù)據(jù)結(jié)構(gòu)關(guān)系模型(圖1)，該模型由四個部分組成：待求解問題、數(shù)據(jù)結(jié)構(gòu)、計算機(jī)和算法。待求解問題為社會生產(chǎn)活動中的需要計算機(jī)解決的問題；數(shù)據(jù)結(jié)構(gòu)為將待解決問題用計算機(jī)可以理解的數(shù)據(jù)

表征；算法為待解決問題的解決方案映射為計算機(jī)支持的操作；計算機(jī)為可以在特定數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上執(zhí)行特定操作的機(jī)器。因此數(shù)據(jù)結(jié)構(gòu)本質(zhì)是在算法的約束下將實(shí)際問題解決方案映射為計算機(jī)可處理的解決方案的方法，該方法將待求解問題的數(shù)據(jù)映射為計算機(jī)可支持的數(shù)據(jù)格式，將算法映射為計算機(jī)支持的循環(huán)、順序和選擇等三種計算結(jié)構(gòu)的組合。即假設(shè)待解決問題的數(shù)據(jù)集為D_L，功能需求為R_L，計算機(jī)可以理解數(shù)據(jù)集為D_P，操作集合為R_P，映射f:(D_L， R_L， D_L#9447;R_L)→(D_P， R_P， D_P#9447;R_P)，其中D_L#9447;R_L和D_P#9447;R_P數(shù)據(jù)和功能之間的關(guān)系。

圖1 數(shù)據(jù)結(jié)構(gòu)關(guān)系模型

2.1.2 數(shù)據(jù)結(jié)構(gòu)教學(xué)改進(jìn)

數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)不同的專家學(xué)者提出了多種教學(xué)模式。國內(nèi)外比較著名的現(xiàn)代化教學(xué)模式主要有：(1)掌握學(xué)習(xí)模式。強(qiáng)調(diào)個別化教學(xué)，利用及時反饋和強(qiáng)化作為控制教學(xué)的有效的手段；(2)發(fā)現(xiàn)學(xué)習(xí)模式。通過提出問題，帶著問題意識觀察具體事實(shí)，再上升到一般的概念；(3)范例教學(xué)模式。用特例具體直觀地闡明“個體”的具體特征，根據(jù)范例“個體”的知識推理、分析，掌握整個“類別”事物的特征；(4)最優(yōu)化教學(xué)模式。根據(jù)教學(xué)目的、任務(wù)、學(xué)生學(xué)習(xí)情況、教師自身情況、教學(xué)條件以及教學(xué)質(zhì)量進(jìn)行分析和總結(jié)。這些模式為普適性的教學(xué)模式，但數(shù)據(jù)結(jié)構(gòu)課程有其獨(dú)有的特點(diǎn)，主要是人和計算機(jī)相互適應(yīng)的問題，因此這些模式在當(dāng)前教學(xué)中盡管起到了很好的指導(dǎo)作用，但必須針對數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)對教學(xué)模式進(jìn)行改進(jìn)，根據(jù)圖1主要是：

●明確研究數(shù)據(jù)結(jié)構(gòu)的任務(wù)。務(wù)必讓學(xué)生深刻體會到數(shù)據(jù)結(jié)構(gòu)主要任務(wù)是將現(xiàn)實(shí)世界的信息讓計算機(jī)來處理，從而擴(kuò)展人的能力，達(dá)到提高工作效率的目的。根據(jù)圖1日常的教學(xué)中容易重點(diǎn)關(guān)注2、3、4步，采取各種教學(xué)方法來進(jìn)行強(qiáng)化，使學(xué)生覺得是為了數(shù)據(jù)結(jié)構(gòu)而數(shù)據(jù)結(jié)構(gòu)，沒有目的的學(xué)習(xí)一方面會給學(xué)生帶來疲勞感，另一方面給學(xué)生帶來迷茫，就是學(xué)的比較好的學(xué)生也存在這個問題，如有的學(xué)生問：順序存儲方式和鏈接存儲方式哪個好點(diǎn)？圖中最短距離算法中的課本采用的是鄰接表，學(xué)生就認(rèn)為該算法采取鄰接表是必然的不可改變的。這些問題的出現(xiàn)是由于將數(shù)據(jù)結(jié)構(gòu)孤立起來，不明白研究數(shù)據(jù)結(jié)構(gòu)的任務(wù)而造成的。只有明白研究數(shù)據(jù)結(jié)構(gòu)的任務(wù)，就會知道只要能滿足解決現(xiàn)實(shí)問題的且能被計算機(jī)支持的算法和數(shù)據(jù)結(jié)構(gòu)都是可行的，至于具體采取哪個方案由開發(fā)者和提出問題者協(xié)商和討論，這樣就避免了學(xué)生死讀書，達(dá)到提高學(xué)生分析能力的教學(xué)效果，因此在課堂上要有意識的強(qiáng)調(diào)第1、5步。

●考慮到數(shù)據(jù)結(jié)構(gòu)的橋梁作用。根據(jù)研究數(shù)據(jù)結(jié)構(gòu)的任務(wù)，數(shù)據(jù)結(jié)構(gòu)將在現(xiàn)實(shí)信息世界與計算機(jī)世界之間架起橋梁。因此要求學(xué)生一方面對現(xiàn)實(shí)世界待處理的問題的數(shù)據(jù)特點(diǎn)有充分了解；另一方面對計算機(jī)支持的數(shù)據(jù)規(guī)范和語言規(guī)范要求理解透徹。關(guān)于學(xué)生提出的是否能用自然語言描述數(shù)據(jù)結(jié)構(gòu)相關(guān)問題，對這個問題的回答是肯定的，但要強(qiáng)調(diào)的是用自然語言描述數(shù)據(jù)結(jié)構(gòu)相關(guān)問題是描述的最高境界，因?yàn)樽匀徽Z言的慣性使人們在描述數(shù)據(jù)結(jié)構(gòu)相關(guān)問題的時候容易忽略掉計算機(jī)的數(shù)據(jù)和計算特點(diǎn)，導(dǎo)致該描述向計算機(jī)程序的轉(zhuǎn)換時將會出現(xiàn)困難。因此，在學(xué)生開始學(xué)習(xí)這門課程的時候，一定要按照計算機(jī)的特點(diǎn)分析描述現(xiàn)實(shí)世界的問題，只有達(dá)到可以隨意用計算機(jī)特點(diǎn)整理思路的時候，才可以用自然語言描述數(shù)據(jù)結(jié)構(gòu)相關(guān)問題。

●正視數(shù)據(jù)結(jié)構(gòu)教學(xué)存在的困難。正是由于計算機(jī)能處理的數(shù)據(jù)格式和計算方法嚴(yán)格受限，而人類的思維呈現(xiàn)多樣性和復(fù)雜性，將一個多樣的復(fù)雜的范疇映射到一個受限的數(shù)據(jù)和計算范疇，出現(xiàn)學(xué)習(xí)困難將是必然現(xiàn)象。對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)和理解困難，下文提出了層次教學(xué)模式，將這種困難分解為多個小困難，從而達(dá)到降低學(xué)習(xí)難度的效果。

2.2 教學(xué)模式

2.2.1 原則

“快樂學(xué)習(xí)”是學(xué)習(xí)者和教育者時刻面臨的課題，這里的“快樂”是在學(xué)習(xí)這個范疇內(nèi)的快樂而不是泛指快樂，比如對于有的學(xué)生來說電子游戲是他最大快樂即使最快樂的學(xué)習(xí)也會讓他痛苦不堪。本文提出的分層教學(xué)模式將數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)困難進(jìn)行層次分解，而每個小困難在學(xué)生的容忍范圍之內(nèi)，積小困難的解決為大困難的解決。因此將數(shù)據(jù)結(jié)構(gòu)待解決的問題進(jìn)行層次分解，每分解一次就向計算機(jī)處理特點(diǎn)靠近一步，從而達(dá)到問題影響范圍局部化，問題規(guī)模小型化的原則。

2.2.2 層次教學(xué)模式

層次教學(xué)模式將現(xiàn)實(shí)世界待解決的問題用層次的方式向計算機(jī)可處理的問題演化，見圖2。主要層次為待解決問題、初步解決方案、求精、選擇數(shù)據(jù)結(jié)構(gòu)、多次求精、代碼書寫和優(yōu)化。初步解決方案層較少考慮到計算機(jī)的因素，主要回答如果不采用計算機(jī)處理，人怎么處理待解決問題；求精層盡量用計算機(jī)處理的特點(diǎn)梳理初步解決方案，即用順序、選擇和循環(huán)語句組合描述初步解決方案；選擇數(shù)據(jù)結(jié)構(gòu)層根據(jù)求精層得到的解決方案進(jìn)行數(shù)據(jù)結(jié)構(gòu)選擇，以高效和方便計算機(jī)語句的書寫且有較高的時空效率為原則；再次求精層到第k次求精層為當(dāng)數(shù)據(jù)結(jié)構(gòu)確定后需要對求精層的解決方案進(jìn)行再次求精，以期數(shù)據(jù)結(jié)構(gòu)與解決方案完美結(jié)合，至于k的大小程序員可以根據(jù)具體問題進(jìn)行靈活處置；代碼實(shí)現(xiàn)層將第k次求精層的方案用選定的程序代碼實(shí)現(xiàn)，由于每層的分解是在上一層嚴(yán)格約束下進(jìn)行的，所以代碼層中的實(shí)現(xiàn)代碼顯然是第1層待解決問題的計算機(jī)解決方案；最后仔細(xì)檢查代碼，找到可以在時空方面可進(jìn)行優(yōu)化的地方。

圖2 層次教學(xué)模式

3 實(shí)例研究

3.1 問題

非線性關(guān)系的且有先后次序的頂點(diǎn)關(guān)系呈有向圖結(jié)構(gòu)，對于有向圖如果有一個頂點(diǎn)的線性序列且不改變頂點(diǎn)的在圖中的先后次序，該序列為拓?fù)湫蛄校枰鉀Q的問題是研究怎樣得到拓?fù)湫蛄械姆椒?，即拓?fù)渑判蛩惴ā?/p>

3.2 層次教學(xué)模式應(yīng)用

(1) 待解決的問題

一個拓?fù)湫蛄惺茿OV(Active of Vertex)網(wǎng)中頂點(diǎn)的線性序列，使得對有向圖中任意二個頂點(diǎn)i和j，若在網(wǎng)中，i領(lǐng)先于j，則在線性序列中i是j的前驅(qū)結(jié)點(diǎn)。

(2) 初步解決方案

1、在圖中尋找一個入度為零的頂點(diǎn)，輸出之；

2、從圖中刪除該頂點(diǎn)及其所有出邊；從圖中刪除一個頂點(diǎn)及其所有出邊時，會產(chǎn)生新的入度為0的頂點(diǎn)；

3、重復(fù)1、2，直到所有頂點(diǎn)都輸出，或圖中剩下的頂點(diǎn)再也沒有入度為零的頂點(diǎn)(存在有向回路)為止。

(3) 求精

1、計算圖中每個頂點(diǎn)的入度；

2、將入度為0的頂點(diǎn)放進(jìn)專門的數(shù)據(jù)結(jié)構(gòu)；

3、輸出一個入度為0的頂點(diǎn)，刪除它的所有出邊；

4、將新產(chǎn)生的入度為0的頂點(diǎn)放入專門的數(shù)據(jù)結(jié)構(gòu)；

5、重復(fù)執(zhí)行3、4，直到n-1次或者沒有新的入度為0的頂點(diǎn)。

(4) 選擇數(shù)據(jù)結(jié)構(gòu)

1、選擇一維數(shù)組保存每個頂點(diǎn)的入度，Indegree[n]；

2、選擇整型棧保存入度為0的頂點(diǎn)，S；

3、由于沒輸出一個入度為0的頂點(diǎn)，均要刪除它的所有的出邊，因此選擇圖的鄰接表存貯方式。

(5) 再次求精

1、計算每個頂點(diǎn)的入度，分別寫入數(shù)組Indegree[n]；

2、檢查每個頂點(diǎn)的入度，如果為0，將S該頂點(diǎn)壓入棧；

3、執(zhí)行n-1次

3.1 如果沒有入度為0的頂點(diǎn)，有環(huán)路，返回；

3.2 從S中取一個頂點(diǎn)，輸出之；

3.3 將該頂點(diǎn)的所有的出邊頂點(diǎn)的入度減1；如果產(chǎn)生新的入度為0的頂點(diǎn)，則壓入棧S

4、結(jié)束

(6) 實(shí)現(xiàn)代碼

如果學(xué)生對計算機(jī)語言的數(shù)據(jù)規(guī)范和語句規(guī)范很熟悉，那么到這一步很容易以處理了，因?yàn)?6)的每一句幾乎可以單獨(dú)來思考，黑體字為考慮到計算機(jī)特點(diǎn)的語句。以

(6).3為例說明：

3.執(zhí)行n-1次

[for (i=0;i

3.1.如果沒有入度為0的頂點(diǎn)，有環(huán)路，返回；

[如果棧S為空，則沒有入度為0的頂點(diǎn)，返回有回路;]

3.2.從S中取一個頂點(diǎn)，輸出之；

[S出棧頂點(diǎn)j，cout<

3.3.將該頂點(diǎn)的所有的出邊頂點(diǎn)的入度減1；

[for (p=a[j];p;p=p->nextArc) k=p->adjVex; InDegree[k]--;]

/*因?yàn)閳D用鄰接點(diǎn)表示，j的所有的出邊都保存在以a[j]為表頭的鏈接表中*/

3.4 . 如果產(chǎn)生新的入度為0的頂點(diǎn)，則壓入棧S。

[如果頂點(diǎn)入度為0，則將k入棧S]

(7) 代碼的書寫和檢查

黑體字非常容易轉(zhuǎn)換成標(biāo)準(zhǔn)的計算機(jī)程序語言，根據(jù)學(xué)生選擇的計算機(jī)語言進(jìn)行轉(zhuǎn)化；然后進(jìn)入檢查和編譯調(diào)式階段。

(8) 優(yōu)化

對于入度為0的頂點(diǎn)，在Indegree數(shù)組中的位置已經(jīng)空閑，所以可以將這些位置連接起來，其中一個頂點(diǎn)序號為頭保存在top中，一個頂點(diǎn)為尾Indegree值為-1，另外頂點(diǎn)在Indegree中存放下個入度為0頂點(diǎn)序號而不是入度值，這樣就不需要專門保存入度為0頂點(diǎn)的棧S。3.4可以修改為：

如果產(chǎn)生新的入度為0的頂點(diǎn)，則壓入棧S。

[如果頂點(diǎn)k入度為0，InDegree[k]=top;top=k;]

/*在k沒加入之前，入度為0頂點(diǎn)的頭為top，k加入后，k成入度為0頂點(diǎn)新的頭，而k的Indegree值為剛被替換的頭，即InDegree[k]=top ， top=k*/

4 結(jié)論

將現(xiàn)實(shí)世界待處理問題的數(shù)據(jù)和功能需求映射到計算機(jī)可處理的數(shù)據(jù)和操作是研究數(shù)據(jù)結(jié)構(gòu)的根本意義所在，由于兩者的數(shù)據(jù)和操作呈現(xiàn)不同的特點(diǎn)，如現(xiàn)實(shí)世界的問題存在二義性、回溯性和多樣性等特點(diǎn)，計算機(jī)呈無二義性、順序性、數(shù)據(jù)格式和語言規(guī)范簡單性等特點(diǎn)，因此學(xué)生學(xué)習(xí)理解這種映射關(guān)系會感到困難。本文提出的分層教學(xué)模式，將現(xiàn)實(shí)世界待解決的問題的解決方案到計算機(jī)解決方案的一次性映射分解為多個層次映射，這樣達(dá)到了降低理解映射難度的目的，呈現(xiàn)出良好的教學(xué)效果。另外在理解其他的比較難的映射情況下，將一次性映射分解為分層映射不失為有助于理解和交流的好辦法，因此該方法具有一般性。

參考文獻(xiàn)

[1] 陳慧南．?dāng)?shù)據(jù)結(jié)構(gòu)-使用C++語言描述[M]．北京：人民郵電出版社，2006.

[2] 顧紅生，曲娟．關(guān)于數(shù)據(jù)結(jié)構(gòu)課堂教學(xué)模式的研究[J]．遼寧廣播電視大學(xué)學(xué)報，2007，(4):44-45.

[3] 吳偉民．?dāng)?shù)據(jù)結(jié)構(gòu)和算法的可視化教學(xué)研究與實(shí)踐[J]．高等教育研究學(xué)報，1999，(3):35-37.