《數據結構》課程教學實踐探索

摘 要：討論了《數據結構》課程教學的基本知識框架體系，以問題驅動加深對基礎知識理解，優化課堂教學方法，培養學生學習興趣和創新能力，并以數據元素插入線性表為例，選取合適經典算法講解基本原理， 給出了加強實踐教學方法和改進措施。

關鍵詞：數據結構；算法；教學方法；教學實踐；創新

中圖分類號：G642 文獻標識碼：A 文章編號：1002-7661（2012）12-008-03

《數據結構》是一門重要的綜合性專業基礎課程，數據結構是對計算機內存中的數據的安排，它涉及現實世界數據在計算機中的存儲、表示、組織和處理，以及算法對這些數據結構進行各種處理的初步性能分析技術。

數據結構研究思想和研究方法在計算機科學深度研究領域有著廣泛應用，它是計算機專業人員從事理論研究、應用開發、技術管理工作而必需學習的重要理論基礎。通過各種基本數據結構及相應算法學習，使學生掌握把現實世界的客觀問題轉換為計算機內在表現形式，理解數據結構內在的邏輯關系，數據與關系在計算機中存儲表示，以及在這些數據結構上的運算和算法執行。該課程具有相當的抽象性和動態性，如何學好《數據結構》這門課，讓學生理解教材的理論結構體系需不斷積累教學的經驗，總結科學教學方法，以達到良好的教學效果。

《數據結構》的學習也是程序設計的學習過

程，通過對學生數據抽象能力的培養，使學生掌握軟件工程的規范，能夠編寫正確易讀，結構清楚的程序，具備一定的程序設計能力。本文將從教學方法，教學手段，啟發式案例式教學研究，理論教學和實踐教學的整合幾個方面進行討論。

一、明確數據結構課程的知識體系與教學目標

數據結構的研究涉及到計算機軟、硬件方面，對于編譯程序和操作系統都涉及到數據元素在存儲中的分配問題，硬件的研究的方面涉及到編碼理論、存儲裝置和存取方法，它是介于軟硬件和數學三者之間的核心課程，是設計實現編譯程序、操作系統和數據庫系統等系統程序和大型應用程序的基礎。數據結構作為主要研究數據的各種邏輯結構和存儲結構以及對致據的各種操作的學科，對數據結構的教學應靈活運用與把握數據結構間縱向聯系和縱橫聯系之中。從根本上掌握數據結構理論體系，這是數據結構教學工作做好的必備條件。數據結構課程的教學目標，是使學生學會分析計算機所加工數據的數據結構特性，為程序設計涉及的數據選擇適當的邏輯結構、存儲結構及相應的算法，并初步掌握算法的時間效率分析和空間效率分析的技術。

1、數據結構課程的基本知識體系

一批具有某種邏輯關系的相關數據，按一定的存儲方法被存儲組織于計算機中，并在這些數據上定義了一個運算的集合，即是數據結構，它包括三個方面：邏輯結構、存儲結構和數據的操作運算。數據結構的研究首先應對這三方面有一個清晰的探討，針對每種數據結構均從邏輯結構、存儲結構和操作運算等方面進行研究，是貫穿數據結構研究始終的主線。課程的基本知識模塊是以數據的邏輯結構為主線，介紹線性結構、樹形結構、圖結構和文件結構，在介紹每種數據結構時，再討論其存儲方法以及相關的算法，存儲方法有：順序方法、鏈接方法、索引方法、散列方法。

數據結構課程的基本知識模塊是以數據的邏輯結構為主線，順序介紹線性結構、樹形結構、圖結構和文件結構。在介紹每種數據結構時，再討論其存儲結構以及相關的算法?；灸K教學，從以下幾方面探討：

（1）邏輯結構、存儲結構、操作運算是數據結構間的橫向聯系。邏輯結構的定義、存儲結構的實現、操作運算的實現是對數據結構研究的基本思想，研究數據結構首先應對這三方面進行詳細清晰的探討。

（2）數據結構間的縱向聯系。以簡單數據結構為基礎實現對較復雜數據結構的研究，教學中讓學生知道遍歷操作對樹、圖結構是非常重要的運算。雖然從樹、圖的遞歸定義能設計出樹、圖遍歷的遞歸算法，但從線性結構到樹、圖的發展是數據結構從簡單到復雜的逐步發展過程。對于較復雜的數據結構樹、圖的遍歷可用較簡單的線性結構棧和隊列來實現，這體現了數據結構間的縱向聯系。

（3）數據結構間縱橫聯系。運用把握這種縱橫聯系，對從抽象數據類型（ADT）的角度進行數據結構的學習與研究有著重要的意義。ADT的操作就是實現對象的封裝，把ADT和面向對象技術和抽象數據類型結合起來，更容易理解一些。和面向對象結合起來講， ADT繼續發展就是Object， ADT的操作就是對象的方法， STL(C++ Standard Template Library)是ADT的經典實現，介紹STL的實現讓學生知道ADT究竟是如何被操作使用實現的。

2、課程教學目標

通過學習數據結構的概念、各種數據結構與算法的實現方式，不同數據結構和算法的特點比較。使學生能夠提高用計算機解決實際問題的能力。

基本數據結構和基本算法分析技術部分，對常用基本數據結構的ADT 及其應用介紹，包括線性結構（線性表、串、棧和隊列）、二叉樹、樹、圖等；針對遍歷二叉樹這一教學內容，首先從遍歷的概念講起，引導學生掌握概念并理解遍歷的本質就是非線性結構的線性化。

同時基于各種數據結構所實施的運算討論算法分析的基本技術，掌握時間和空間權衡的原則。排序、檢索和索引技術部分主要討論插入排序、Shell 排序、堆排序、快速排序、歸并排序、基數排序等常用的各種排序算法及其時間和空間開銷，并介紹文件管理（數據在外存中的組織形式）和外排序技術，以及自組織線性表、散列表、倒排文件、B/B+樹等常見的檢索和索引技術，及其各自相應的時間和空間開銷。

本課程的學習將使學生基本掌握數據結構和算法的設計分析技術，提高程序設計的能力；根據所求解問題的性質，選擇合理的數據結構并對時間空間復雜性進行必要的控制。

二、創新課堂教學方法，培養學生學習興趣

1、基于任務問題教學，實施啟發式教學

主要數據結構包括棧、隊列、列表、字符串、表、樹、圖、排序、查找等； 在數據結構的討論中滲透典型的算法策略: 分治法、回溯法、貪心法、遞歸技術等； 使用典型的分析方法: 漸進分析法、緩沖分析技術等進行算法分析。數據結構課堂教學應以問題求解為導向，培養和提高學生理論、抽象、設計的能力。例如XMLDOM 樹解析器、后綴樹、搜索引擎等。激發學生的學習興趣，培養學生的創新思維能力。

通過新的教學方法訓練學生的數據結構思維，使其認識到數據結構的內在有趣，問題驅動的教學方法體現如下：掌握結構化問題解決技術和數據抽象原則；從架構師和設計師兩個角度解決具體與抽象之間的難度；教授精巧數據結構給程序所帶來的巨大改善；概括性地評價一個數據結構和程序的成本方法；數據結構來解決實際問具體應用。例如，搜索引擎問題詢問，通過程序設計來實現搜索引擎會用到哪些數據結構，使用何種數據結構更有效。我們先嘗試不用任何數據結構，發現無法構建搜索引擎；在用了簡單的數組結構后可以構建搜索引擎，但效率很低；因此我們需要一步步引入構建更為精巧的矢量結構、樹結構、索引表、哈希表結構等。再如教材管理問題，首先要考慮教材的各種信息，一般的方法是建立一個表，如表1所示，實際上，它就是1種稱為線性表的數據結構。借助一個問題，圍繞搜索引擎程序設計的實現，串起一系列的數據結構，學生看到了各種數據結構不是抽象的空的，而是因實際問題驅動、經過邏輯上的逐次演進推理而出現，從而幫助學生更加有趣地學習數據結構。邏輯上的數據結構反映數據成分之間的邏輯關系，物理上的數據結構反映數據成分在計算機內的存儲安排。數據結構是數據存在的形式，以問題為驅動，以應用為軸線，對每一種數據結構的出現動機、發展邏輯、表示方式進行演繹，闡述如何從一種想法轉換為一種設計，又如何從設計轉化為具體程序，對每種數據結構都輔以程序設計中的實際應用，從而化抽象為具體，幫助學生利用數據結構思維解決實際問題。

2、結合實際問題，加強課堂互動

數據結構是反映數據的內部構成，即由哪些數據成分構成，構成方式，呈什么結構，也就是指相互之間存在一種或多種特定關系的數據元素的集合，數據結構是數據存在的形式。數據結構有邏輯上的數據結構和物理上的數據結構之分。目前國內較好的教材有清華大學出版社的嚴尉敏著《數據結構- C 語言描述》及其配套的《數據結構題集- C 語言描述》，殷人昆編著清華大學出版社出版的《數據結構( 用面向對象方法的C++ 描述)》等，Preiss 著《數據結構與算法- 面向對象的C+ + 設計模式》以及電子工業出版社的Clifford A. Shaffer著《數據結構與算法分析》都是很好的教學參考書。

課堂教學是教學有效的關鍵，課堂教學

中結合許多實際的講解，如棧和車庫停車、隊列和火車站等地方的順序服務； 樹和人類的族譜、各種社會組織機構； 圖和哥德斯堡七橋問題、四色定理等。結合現實問題，可以一定程度地提升教學效果。同時要充分進行課堂互動。講解一個知識點時，而是要加強啟發式引導，讓學生接話，之后再重復強調如何理解。這樣既能促進學生的思考，又能使學生加深理解課堂授課內容。

三、選擇合適經典算法，科學講授基本原理

1、選取經典算法算例

表1

計算機科學家N.沃斯提出“程序=數據結構+算法”，說明算法是對合理數據結構的操作(運算)，是數據處理的核心。《數據結構》課程中介紹的基本數據結構有線性表、堆棧、隊列、數組、樹、二叉樹、圖以及相應的算法。一個算法是建立在某種數據結構的基礎上，一個算法不可能脫離數據結構而孤立存在。只有通過學習算法，才能真正掌握某種數據結構。學習《數據結構》的過程基本上是學習各種算法的過程，典型算法見表1。

在眾多的算法中如何選擇少量的典型算法進行分析講解，往往能起到以點帶面的關鍵作用。通過典型算法的分析，一方面讓學生加深對數據結構基本理論的理解，另一方面讓學生學習程序設計方法。例如在講授線性表順序存儲教學內容時，可利用典型算法說明其存儲特征，線性表的優點能對每個數據元素隨機訪問，其存儲密度高，其缺點是插人、刪除操作時需要移動大量的數據元素，操作效率低?？衫谩跋蛴行?由小到大或由大到小)的線性表(順序存儲)插人一個新的數據元素”，這一典型算法反映線性表順序存儲的特點。

算例：將一個值為X的數據元素插人到有序(由小到大或由大到小)的線性表(順序存儲)中，可以分兩步進行，首先查找到值為X的數據元素在線性表中應有的位置，采用從頭到尾循環比較的方法確定其位置I，然后，將第I個以后的全部數據元素向后移動一個存儲單元，最后將值為X的數據元素存放到第I個位置上，線性表元素個數增1。線性表的元素插人(對數據的操作或算法)在線性表中進行元素插人，其示意圖見圖1所示：

圖1

L= (a1，…a i-1，a i ， ai+1，…，an) 中的第i(1≤i≤n)個位置上插入一個新數據元素e，使其成為線性表 : L=( a1，…a i-1， e， a i ， ai+1，…，an)，除非i=n+1，否則必須將第i個到第n個數據元素均向后移動1個位置，然后將e存人第I個位置。

算法1

PROCEDURE INSERT(V，m，n，X)

//將值為X的數據元素插人到V數組中，(線性表順序存貯在V中)m為最多元素個數，n為當前實際元素個數

IF (m = n)

T HEN( \"OVERFLOW\"；RETURN}

FOR I =1TO n DO

IF ( X (V (D) THEN BREAK

FOR J=nTO I BY-1 DO V(J+1)=V(J)

V(I)=X

n= n + 1

RETURN

該算法的優點是簡單，便于理解，缺點是循環體內有提前退出語句，不利于結構化程序設計；確定新數據元素位置和移動數據元素分兩步進行，有重復操作，那么可將兩步合并一步以改進，即將循環比較與移動數據元素同時進行。從線性表的尾部開始向前循環比較，比新數據元素大者后移，直到小于等于時停止。

[算法2]

PROCEDURE INSERT(V，m，n，X)

IF(m= n) THEN( \"OVERFLOW\"；RETURN}

I= n

WHILE(I)=1)AND(V(I))X)DO (V(I+1)=V(I)；I=I-1}

V (I+1)=X

n= n + l

RETURN

算法2中循環條件，當循環結束后I=0或V(I)(=X，新數據元素的位置為I+l，C算法1的時間復雜度為0(2n)，而算法2的時間復雜度為0(n)，循環結構采用結構化程序設計，該算法要歸納循環條件是關鍵，可改進推廣應用。

[類C插人算法(數組的下標從0開始的)]

#define MAXLEN線性表可能達到的最大長度

Typedef struct

Elem type elem[MAXLEN]； Int length；

}Sqlist；

Sta tus Listin sert(SqlistL，inti， Elemtype e )

{//在線性表L中第i個元素之前插人新的元素e

//i的合法值為0≤i≤List Length(L )

if ( i< 0 I {i>L..length‖L .length>=

MAX LEN) return ERROR；

for (q=L.length-1；q≧i；q--)L.elem[q+1〕=L.elem[q]；

//將第i個元素及其后的元素后移

L.elem [i-1〕二e；//插人元素

L.le ngth++；//線性表長度增1

return OK；

通過對算法的分析要有助于程序設計能力的提高，有助于學生理解線性表的數據結構。還可使用流程圖描述算法，進一步幫助學生更好地直觀地理解算法。

3.2 優化實踐教學，培養創新能力

數據結構課程，上機實習題的設計、學生的實習訓練的數量和質量對學習效果都非常重要。通過適當的實習訓練，使得學生深刻理解和掌握課程知識體系中的理論和抽象概念，以及各類設計實現方法，提高在復雜軟件系統中的實踐能力。以學生自主探究和開發活動為主體，培養學生學習的興趣和能力。強化創新意識和創新能力，相應地提高理論聯系實際能力、實踐動手能力和科研能力，也能提高學生的學習和研究積極性，學生通過文獻調研、開題、項目分析、項目設計、成果匯報、總結評價展開設計訓練，可以把理論課上的很多算法得以實現，并且進行深入的數據結構和算法時間、空間效率討論，達到理論與實踐水平共同提高目的。

四、結語

本文針對數據結構課程進行了教學方法上的探討，從廣度和深度上把握課程的知識體系，了解基本數據結構和經典算法，掌握理論、抽象和設計方法進行探討。以期為本課程的教學提供借鑒。文中討論選取實際問題，選擇合適的數據模型，選擇經典算法，剖析重要數據結構與算法思想方法，突破常規教學方法，研究設計教學案例，通過這些例題讓學生知道利用所學知識的對實際問題問題求解，助學生理解數據結構原理和算法技術，這樣才能充分培養學生學習本課程的興趣。

參考文獻

[1] 嚴蔚敏，吳偉民. 數據結構(C語言版)[M] 北京:清華大學出版社，2006:156-163.

[2] 陳雪剛. 數據結構課程教學改革與實踐[J] 計算機教育，2011 (4):34-37.

[3] 楊利英. 數據結構課程的教學方法探討，2011 6 (24):131-133.

[4] Shaffer，A.數據結構與算法分析(C + + 版)[M] 2 版.北京:電子工業出版社，2010.

[5] 龐曉瓊. 案例驅動的《數據結構》課程設計教學改革實踐.計算機教育[J]，2009.1:53~64.

[6] 沙宗堯，邊馥苓. 圖示教學法在數據結構與算法教學中的應用［J］.計算機教育，2009(18):80-82.

[7]張立，王偉嘉. 基于學習興趣開展數據結構教學 計算機教育[J]，2010 13 10:95~97.

[8] Thomas H Cormen，etc Introduction to Algorithms (2ndedition)[M] 北京:高等教育出版社，2005.