《數據結構》課程教學改革探討

亓 璐

(濟寧學院計算機科學系，山東 濟寧 273155)

《數據結構》課程教學改革探討

亓 璐

(濟寧學院計算機科學系，山東 濟寧 273155)

針對《數據結構》課程教學中存在的問題，提出了如下改革措施：運用生活和科研案例，激發學生的學習興趣；使用面向對象的特性，挖掘知識點之間的關系，使學生建立課程的整體知識框架；轉變學生的學習思路，使其重視概念的理解；采用圖解法使程序分析中的抽象問題具體化，幫助學生編寫代碼。實踐表明，采取上述措施和方法，有效地提高了課堂教學效率。

數據結構；面向對象；案例教學；圖解法；實驗教學

《數據結構》是計算機專業課程體系中一門非常重要的基礎課程，其一方面能擴展和深化《離散數學》、《程序設計語言》等課程中的基本理論和方法，另一方面能為學生學習《操作系統》、《編譯原理》和《數據庫》等后續課程奠定堅實的理論與實踐基礎[1]。通過該課程的學習，使學生能從數據結構的角度出發，為現實問題所涉及的數據選擇合適的邏輯結構、存儲結構，設計出合理、可行的算法，并編寫出正確、清晰和高質量的程序，提高算法設計能力和工程實踐能力[2]。由于該課程的傳統課堂教學模式過于注重介紹基本內容和講解習題，忽視對學生實踐能力的培養，導致學生學習該課程時感到枯燥乏味，學習積極性不高。因此，如何激發學生的學習興趣并增強學生解決實際問題的能力，是一個亟待解決的問題。為此，筆者從理論教學和實驗教學2個方面、多個角度對傳統課堂教學方法進行了改革和創新?。

1 《數據結構》理論教學改革

1.1引用生活實例激發學生的學習興趣

《數據結構》課程內容豐富，知識點之間的關系錯綜復雜。要取得好的教學效果，首先要激發學生的學習興趣。由于數據結構是在現實生活中總結出來的，所以在課堂教學中應適當引入生活實例，通過“聯想”式的啟發，將抽象的理論知識轉化成學生容易理解和感興趣的內容，從而調動學生的學習積極性[3]。例如，在講解采用開放定址法解決散列表的沖突時，可以用學生在圖書館占位為例進行說明。當學生來到圖書館選中一個坐位將要坐下時，發現桌上寫著“占位，謝謝合作”，此即散列表中的沖突。如何解決上述問題呢？一種處理方式是觀察右邊的位子是否被占，如果也被占，再觀察右邊下一個位子，依次類推，而往右查看下一個位子就是線性探測法的+1，+2，+3，…。另一種處理方式是先觀察左邊的位子是否被占，再觀察右邊的位子是否被占，此即二次探測再散列的+1和-1。這樣通過列舉與學生生活緊密聯系的實例，可以輕松愉快地理解所學知識。

1.2培養學生面向對象的思維方式

在數據結構中，抽象數據類型充分概括數據結構定義中的數據對象、數據關系和操作3個方面。以往教學時用學生比較熟悉的C語言對抽象數據類型進行描述，由于C語言的局限性，其不能準確、有效地表現抽象數據類型的思想，而C++或Java中類的特性與抽象數據類型的抽象性和封裝性相符合[4]，因此，利用面向對象方法和C++語言來描述數據結構可以提高課堂教學效率。這種改變，不僅有助于挖掘數據結構中隱藏其中的關系，而且能夠培養學生面向對象的思維分析方式以及注重可復用構件的思想。例如，棧是操作受限的線性表，如果把線性表的表頭定義為棧底，表尾定義為棧頂，那么入棧操作等價于在線性表的表尾進行插入操作，出棧操作等價于在線性表的表尾進行刪除操作，因此可以引導學生將線性表理解為基類，將棧作為線性表的派生類對待。在線性表操作的基礎上再實現棧的操作，可以加深學生對程序設計的模塊化和結構化的認識。這樣找到即將講解的棧和已講解的線性表的關系，增強了知識點的連貫性，使學生對新知識更容易理解。

1.3加強整體知識框架的構建

數據結構課程理論知識龐雜、分散，如果知識點的因果關系、內在邏輯關系沒理順的話，學生學習起來會感覺很困難。為此，需要分析各種邏輯結構之間以及各章節知識點之間的關系，采用縱橫對比的方法將分散的的概念和運算納入完整的學科體系中，從而建構起完整知識結構框架[5]。

橫向對比方面，以線性表為例，可從線性表的順序存儲結構和鏈式存儲結構2個方面出發，分析算法的優缺點，從而弄清楚知識點的前因后果，將順序表、單鏈表、循環鏈表和雙向鏈表“串聯”起來。當在線性表的順序存儲(順序表)中插入、刪除一個數據元素操作時，“驚動”了其他許多數據元素，因而需要移動大量數據元素。為了解決順序表動態操作效率低的問題，可引入鏈式存儲。鏈式存儲中的單鏈表通過指針“順藤摸瓜”找到下一個數據元素，但無法找到其直接前驅元素，為此引入循環鏈表。循環鏈表雖然能夠實現找到任何一個數據元素的前驅結點，但是時間復雜度比較大，為此通過改進結點，增加指向前驅的指針域，進而形成雙向鏈表。雙向鏈表的2個指針域可以容易地找到任何一個數據元素的前驅和后繼，時間復雜度都降為O(1)。這并不能說明雙向鏈表是十全十美的，也存在不足，存儲密度不緊密就是其中一個方面。順著該線索，引導學生發現順序表的優點。經過深入分析，使學生對各種存儲方式做到“心中有數”，這樣在處理實際問題時才能“揚長避短”。

縱向對比方面，以線性結構和樹形結構為例，對上述2種原本不相干的結構進行分析，發現它們存在相似的地方：線性結構除了首元素外具有唯一的前驅，樹形結構除了根結點外具有唯一的雙親；線性結構除了尾元素外具有唯一的后繼，樹形結構除了葉子結點外具有多個孩子。因此，線性結構的前驅相當于樹形結構的雙親，線性結構的后繼相當于樹形結構的孩子。這樣，樹形結構中形式上只有左孩子或只有右孩子的單支二叉樹，本質上其實是線性結構。

1.4注重基本概念的理解

2 《數據結構》實驗教學改革

由于《數據結構》是一門理論與實踐緊密結合的課程，因而要求學生既能掌握基本的理論知識，還能上機編程實現算法。為了提高學生的程序設計能力，可以采用算法自然語言、C++語言并配合相應示意圖的教學方式，具體內容如下。

2.1示意圖法在隊列初始化中的應用

隊列是操作受限的線性表，在隊頭出隊列、在隊尾入隊列。在實現隊列初始化時，首先明確目標，即最終形成空隊列(見圖1)；然后將算法自然語言描述“翻譯”成C++語言，畫出對應的示意圖。每更新一次示意圖，都要與圖1對照，找出差異，完善程序，步驟如下：

1)生成一個結點：Node *front=new Node；(見圖2)。

2)指針域為空： front->next=Null(見圖3)。

3)隊尾指向頭結點：rear=front；(見圖4)。

最后將算法最終生成圖與圖1對比，如果兩者相同，則程序完成；如果兩者不相同，找出差別，完善程序，直到與圖1完全相同為止。

圖1 空隊列 圖2 生成結點 圖3 設置指針域 圖4 設置隊尾指針

2.2示意圖法在順序表初始化中的應用

順序表是指用一組地址連續的存儲空間依次存放線性表中的數據元素，其包含以下重要信息：開辟一塊地址連續的存儲空間；開辟空間大??；將數據元素放入其中；放入數據元素的個數。據此建立對應類，elem為開辟存儲空間的首地址，listsize為空間大小，length為存放數據元素的個數。因此建立類list為：

Class list{

private

int length;

int listsize;

圖5 開辟空間 圖6 空間為100

T *elem;

}

順序表的初始化就是實現順序表概念的4個方面，即為類中3個變量賦值：

1)開辟地址連續的空間：elem=new T[listsize];(見圖5)。

2)空間大小為100：listsize=100;(見圖6)。

3)初始狀態不存放數據元素：length=0。

3 結 語

為了提高《數據結構》課程教學質量，筆者提出一些針對性的改革措施。教學實踐表明，采取教學改革措施后，提高了課堂教學效率，明顯改善教學效果，因而受到學生的認可。今后，應在培養學生的編程能力方面繼續探索，從而進一步提高學生的實踐創新素質。

[1]劉馨月,張憲超,于紅.數據結構與算法核心課程建設[J].計算機教育,2011(6):65-68.

[2] 張小剛,李向陽.《數據結構》課程教學改革探討與實踐[J].塔里木大學學報,2008,20(2)：93-95.

[3] 陳越,何欽銘,馮雁.“數據結構”綜合性課程設計教學探索與實踐[J].計算機教育,2008(8):54-55.

[4] 殷人昆.數據結構(用面向對象和 C++描述)[M]. 北京:清華大學出版社,2007.

[5] 青宇航.關于《數據結構》現代教學方法的探索[J].教育與職業,2007,59(8):151-152.

[編輯] 李啟棟

10.3969/j.issn.1673-1409(N).2012.11.062

N4

A

16731409(2012)11N18603