數(shù)據(jù)結(jié)構(gòu)課程教學(xué)模式的研究

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

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

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

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

1 引言

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

要達(dá)到這個目的，必須在教學(xué)模式的選擇、教學(xué)內(nèi)容設(shè)計以及教學(xué)手段的選擇三個方面進(jìn)行提高。本文從教學(xué)模式方面進(jìn)行討論，充分考慮到計算機與學(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)系模型

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

表征；算法為待解決問題的解決方案映射為計算機支持的操作；計算機為可以在特定數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)上執(zhí)行特定操作的機器。因此數(shù)據(jù)結(jié)構(gòu)本質(zhì)是在算法的約束下將實際問題解決方案映射為計算機可處理的解決方案的方法，該方法將待求解問題的數(shù)據(jù)映射為計算機可支持的數(shù)據(jù)格式，將算法映射為計算機支持的循環(huán)、順序和選擇等三種計算結(jié)構(gòu)的組合。即假設(shè)待解決問題的數(shù)據(jù)集為D_L，功能需求為R_L，計算機可以理解數(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í)模式。強調(diào)個別化教學(xué)，利用及時反饋和強化作為控制教學(xué)的有效的手段；(2)發(fā)現(xiàn)學(xué)習(xí)模式。通過提出問題，帶著問題意識觀察具體事實，再上升到一般的概念；(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)課程有其獨有的特點，主要是人和計算機相互適應(yīng)的問題，因此這些模式在當(dāng)前教學(xué)中盡管起到了很好的指導(dǎo)作用，但必須針對數(shù)據(jù)結(jié)構(gòu)的特點對教學(xué)模式進(jìn)行改進(jìn)，根據(jù)圖1主要是：

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

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

●正視數(shù)據(jù)結(jié)構(gòu)教學(xué)存在的困難。正是由于計算機能處理的數(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)行層次分解，每分解一次就向計算機處理特點靠近一步，從而達(dá)到問題影響范圍局部化，問題規(guī)模小型化的原則。

2.2.2 層次教學(xué)模式

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

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

3 實例研究

3.1 問題

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

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

(1) 待解決的問題

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

(2) 初步解決方案

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

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

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

(3) 求精

1、計算圖中每個頂點的入度；

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

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

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

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

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

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

2、選擇整型棧保存入度為0的頂點，S；

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

(5) 再次求精

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

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

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

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

3.2 從S中取一個頂點，輸出之；

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

4、結(jié)束

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

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

(6).3為例說明：

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

[for (i=0;i

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

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

3.2.從S中取一個頂點，輸出之；

[S出棧頂點j，cout<

3.3.將該頂點的所有的出邊頂點的入度減1；

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

/*因為圖用鄰接點表示，j的所有的出邊都保存在以a[j]為表頭的鏈接表中*/

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

[如果頂點入度為0，則將k入棧S]

(7) 代碼的書寫和檢查

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

(8) 優(yōu)化

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

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

[如果頂點k入度為0，InDegree[k]=top;top=k;]

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

4 結(jié)論

將現(xiàn)實世界待處理問題的數(shù)據(jù)和功能需求映射到計算機可處理的數(shù)據(jù)和操作是研究數(shù)據(jù)結(jié)構(gòu)的根本意義所在，由于兩者的數(shù)據(jù)和操作呈現(xiàn)不同的特點，如現(xiàn)實世界的問題存在二義性、回溯性和多樣性等特點，計算機呈無二義性、順序性、數(shù)據(jù)格式和語言規(guī)范簡單性等特點，因此學(xué)生學(xué)習(xí)理解這種映射關(guān)系會感到困難。本文提出的分層教學(xué)模式，將現(xiàn)實世界待解決的問題的解決方案到計算機解決方案的一次性映射分解為多個層次映射，這樣達(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é)研究與實踐[J]．高等教育研究學(xué)報，1999，(3):35-37.