數據結構課程教學模式的研究

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

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

關鍵詞：數據結構；教學模式；層次

中圖分類號：G642 文獻標識碼：B

1 引言

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

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

2 分層教學模式

2.1 數據結構相關概念

2.1.1 數據結構關系模型

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

表征；算法為待解決問題的解決方案映射為計算機支持的操作；計算機為可以在特定數據結構基礎上執行特定操作的機器。因此數據結構本質是在算法的約束下將實際問題解決方案映射為計算機可處理的解決方案的方法，該方法將待求解問題的數據映射為計算機可支持的數據格式，將算法映射為計算機支持的循環、順序和選擇等三種計算結構的組合。即假設待解決問題的數據集為D_L，功能需求為R_L，計算機可以理解數據集為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數據和功能之間的關系。

圖1 數據結構關系模型

2.1.2 數據結構教學改進

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

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

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

●正視數據結構教學存在的困難。正是由于計算機能處理的數據格式和計算方法嚴格受限，而人類的思維呈現多樣性和復雜性，將一個多樣的復雜的范疇映射到一個受限的數據和計算范疇，出現學習困難將是必然現象。對于數據結構的學習和理解困難，下文提出了層次教學模式，將這種困難分解為多個小困難，從而達到降低學習難度的效果。

2.2 教學模式

2.2.1 原則

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

2.2.2 層次教學模式

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

圖2 層次教學模式

3 實例研究

3.1 問題

非線性關系的且有先后次序的頂點關系呈有向圖結構，對于有向圖如果有一個頂點的線性序列且不改變頂點的在圖中的先后次序，該序列為拓撲序列，需要解決的問題是研究怎樣得到拓撲序列的方法，即拓撲排序算法。

3.2 層次教學模式應用

(1) 待解決的問題

一個拓撲序列是AOV(Active of Vertex)網中頂點的線性序列，使得對有向圖中任意二個頂點i和j，若在網中，i領先于j，則在線性序列中i是j的前驅結點。

(2) 初步解決方案

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

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

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

(3) 求精

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

2、將入度為0的頂點放進專門的數據結構；

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

4、將新產生的入度為0的頂點放入專門的數據結構；

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

(4) 選擇數據結構

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

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

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

(5) 再次求精

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

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

3、執行n-1次

3.1 如果沒有入度為0的頂點，有環路，返回；

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

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

4、結束

(6) 實現代碼

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

(6).3為例說明：

3.執行n-1次

[for (i=0;i

3.1.如果沒有入度為0的頂點，有環路，返回；

[如果棧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 . 如果產生新的入度為0的頂點，則壓入棧S。

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

(7) 代碼的書寫和檢查

黑體字非常容易轉換成標準的計算機程序語言，根據學生選擇的計算機語言進行轉化；然后進入檢查和編譯調式階段。

(8) 優化

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

如果產生新的入度為0的頂點，則壓入棧S。

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

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

4 結論

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

參考文獻

[1] 陳慧南．數據結構-使用C++語言描述[M]．北京：人民郵電出版社，2006.

[2] 顧紅生，曲娟．關于數據結構課堂教學模式的研究[J]．遼寧廣播電視大學學報，2007，(4):44-45.

[3] 吳偉民．數據結構和算法的可視化教學研究與實踐[J]．高等教育研究學報，1999，(3):35-37.