數據結構教學方法的探討
2013-04-12 00:00:00陳燕，屈莉莉，李桃迎
教育教學論壇 2013年49期
摘要：數據結構是計算機相關專業的核心課程。由于該課程涉及到的模型眾多，具有算法難度大、模型不易掌握、編程工作量繁重等特點，因此有效的學習方法對該課程會起到重要作用。本文分析數據結構的特點，闡述了數據結構課程教學過程中存在的問題，設計了數據結構教學的有效方法，對數據結構課程的講授和學習起到指導與幫助作用。
關鍵詞：數據結構；形式化定義；教學方法
中圖分類號：G642.0 文獻標志碼：A 文章編號：1674-9324（2013）49-0082-03
數據結構是計算機、信息管理與信息系統等相關專業的核心基礎課程，涉及多學科知識點。其前驅課程主要包括：計算機信息處理概論、程序設計語言（如：C、C++、Java等）、計算機原理（微機原理）等；其后繼課程主要包括：編譯原理、操作系統、數據庫原理、匯編語言程序設計、管理與決策等。從前驅和后繼課程可以看出，數據結構具有承上啟下的重要性，居于計算機教學的主導地位（如圖1所示）。
隨著計算機和網絡技術的發展，數據處理能力的增強，國內外開設數據結構課程的學校越來越多。該課程覆蓋的專業知識廣，涉及的數學模型多。由于數據結構課程的主要內容涉及對客觀世界問題的建模、數據結構的定義與描述、大量的算法（程序）的實踐環節，本文重點探討如何教授和學習該課程。
一、數據結構特點分析
1.掌握數據結構特點和拓寬專業概念知識。要想學好數據結構，必須詳細掌握數據結構的特點。將客觀世界對應問題的數據結構特點歸納如下：①集合結構：該結構的數據元素間關系是“屬于同一個集合”。②線性結構：該結構的數據元素之間存在一對一先后次序的線性關系。③樹型結構：該結構的數據元素之間存在一對多層次結構的非線性結構關系。④圖形結構：該結構的數據元素之間存在多對多的復雜非線性結構關系，也稱網狀結構。對這四種結構理解的深度將直接影響其與后續課程（數據庫管理、管理信息系統、信息系統分析與設計）的銜接。例如，對數據庫三級模式——外模式、概念模式與內模式的理解方法，可以按照數據結構的知識去理解：外模式稱為用戶級數據庫，它對應用戶看到那部分數據的邏輯結構即用戶視圖；內模式是對數據庫的整體描述。數據庫中數據模型分為三類：層次模型（樹型結構）、網狀模型（圖形結構）和關系模型（集合結構與線性結構，也稱為二維的表格（矩陣）結構）。可見，對數據結構本身結構內涵的理解將直接影響后續課程概念的理解。同時，對數據結構課程的學習應注意與其他課程的連貫和銜接。
2.數據結構特點分析。無論解決問題的原始數據呈現的是集合結構、線性結構、樹型結構還是圖形結構，數據表示的范圍已由原來的數值范圍拓寬到非數值范圍，由原來的結構化數據擴充到非結構化數據。因此，給數據的表示（計算機外部的邏輯表示與計算機內部的存儲方式）帶來了不同的方式。例如，將線性數據結構歸納為：集合與數組的表示與存儲方式；線性表的順序與鏈式表示與存儲方式；棧與隊列的順序與鏈式存儲方式；字符的緊湊（壓縮）與其格式的表示與存儲方式；廣義表的存儲方式。以上五種方式之間是按照問題的特征及其解決問題的目標來劃分的。同樣一組參與運算（操作）的樣本數據，其解決問題的目標不同，則其含義不同。例如：當前某單位有100臺車輛，將這些車輛進行登記，如果到了車輛報廢年限，將該車輛信息刪除掉。以每個車輛的相關信息（車型、排量、車牌號、車主）為數據元素，將這100臺車輛信息運用集合或數組表示為存儲方式即可；車輛入庫和出庫屬于進棧和出棧的后進先出操作；車輛按照大中小型號歸類屬于廣義表的問題；車輛相關性歸類采用樹型的解決方案；求解車輛運輸最短路徑、運輸成本的最小代價等問題屬于圖的數據結構問題。另外，為了查找方便，還可以引入合理排序后的快速查找等問題。因此，對一個問題，數據結構的分析結果直接決定其實現算法的成功與否。
二、數據結構教學過程存在的問題
在教學過程中，根據學生的基礎不同，選擇的教材和講授的內容也不同。但是，還存在如下問題。
1.對數據結構概念、定義及其操作的理解方法問題。數據結構的概念定義有多種方法，如何理解和將一個自然界問題的數據結構提煉出來，并且對其進行科學運算（操作），將是初學者的理解問題的關鍵與難點。
2.選擇實際問題所對應的數據結構。有許多初學者對數據結構的概念模糊，即邏輯思路不清晰，所選擇解決問題的數據結構不恰當，而影響解決問題的效率。
3.對教材與參考資料的配套選擇問題。沒有科學選擇教材，出現學習的錯位現象。應選擇與數據結構相匹配的程序語言設計教材。
4.對遞歸等算法閱讀困難的問題。遞歸是數據結構最為重要的算法和上機實踐環節，以清華大學嚴蔚敏教授編寫的教材為例，如：第三章棧與遞歸、第五章廣義表、第六章樹與第七章圖的算法大多數都涉及到遞歸算法（程序）。
5.算法的邏輯步驟、流程圖、偽代碼、算法與程序之間的區分問題。在大多數數據結構教材中，為了減少篇幅和快速理解數據結構的算法，引入了多種理解和學習數據結構算法的模式，如算法的邏輯步驟、流程圖、偽代碼、算法與程序等模式，但是對初學者來講很難將這些模式進行清晰的界定。
三、數據結構教學方法的探討
針對數據結構教學中經常出現的難點，提出多種教學方法。
1.多視角理解數據結構概念、定義及其操作。根據數據結構概念定義的抽象性，給出如下幾種理解數據結構概念與定義的方法：①針對字面上的含義：數據結構被定義為帶有結構的數據元素的集合，即相互之間存在一種或多種特定關系的數據元素的集合。②針對目標與任務：首先將某實際問題的邏輯結構找出來，然后，再針對該邏輯結構進行科學分析，映射到對應的物理結構，從而形成對應的數據結構，最后對該數據結構進行操作。③從計算機外部與內部來理解數據結構的定義：為解決客觀世界問題，找到運用計算機如何組織和存儲數據的科學方法。其主要目的是描述數據的外部表示方法與內部存儲方式以及如何對這些數據結構進行操作。④關于形式化定義與知識描述：將數據結構的形式化定義為二元組D和R，即DS=（D，R），其中D是數據元素的有限集合，R是D上關系的有限集合。數據結構的形式化定義能非常清楚地描述客觀世界的數據模型的外部表示方式和它對應的內部存儲方式及這些數據之間的結構關系。反之，也可以通過這些數據之間的結構關系來反推出其形式化定義的數據結構。例如圖形數據結構的形式化定義是Graph=（V，R），表示圖Graph是由頂點集V和弧集R構成的數據結構。其中，R={
2.選擇對應實際問題的數據結構。①明確對應的問題是何種數據結構。比如：想設計字符編碼，則將該問題歸結為求最優二叉樹及其對應的編碼問題；求工程處的進度問題，則將該問題歸結為求關鍵路徑問題；銀行辦理業務問題歸結為隊列問題；五叉路口信號燈分配問題歸結為圖論問題等。②注重問題所涉及的參與運算樣本數據的表示方式與存儲方式。如果當前問題屬于鏈式線性表的插入刪除操作，那么該數據元素的結點結構應定義為結構體形式。最后一個結點沒有后繼，它的指針域值為NULL。由于上述鏈表的每個結點只有一個指針域，故稱這種鏈表為單鏈表。單鏈表（以下用LinkList表示）每個數據元素對應結點的（計算機）外部表示形式，數據元素集合=（a1，a2，…，an），指針指出了數據元素ai下一個數據元素ai+1在內存的位置（地址）。
單鏈表結構如圖4所示，其中L為單鏈表的頭指針，它指向表中第一個結點。
對不帶頭結點的單鏈表進行操作：刪除表中的“a2”結點（如圖5所示）。假設在刪除之前，結點a1，a2，...an分別存儲在200，500，300，600...等存儲地址中，每個結點占兩個存儲單元，如：a1結點的信息存放在地址200與201中，a2結點的信息存放在地址500與501中；a3結點的信息存放在地址300與301中；以此類推。這時，各個結點在計算機內部的存儲的實際情況如下：p，q分別作為在單鏈表進行操作的指針變量，其中p代表當前指針位置，即200，q代表當前要刪除的結點指針，假如當前刪除a2結點的信息，則指針q指向a1結點地址的后繼地址即a2結點地址=500。
③注重學生數學建模的訓練。應區分模式與模型的概念：模式作為模型的一個范例。如果將一元一次方程y=ax+b看作是一個模型的話，那么將y=3x+2看作是y=ax+b的一個范例（特例）。在數據結構中如果將非線性結構的“二叉樹”作為一個模型的話，那么“二叉樹”模型包括的模式集合有{滿二叉樹，完全二叉樹，非完全二叉樹，最優二叉樹，線索二叉數，二叉排序數，……，平衡二叉樹}。如果將數據結構的遞歸算法（程序）作為一個模型的話，那么“遞歸算法”模型包括的模式集合有{Hanoi塔遞歸算法（程序），n！算法（程序），Fibonaqi遞歸算法（程序），廣義表的遍歷算法（程序），二叉樹遍歷算法（程序），圖的深度優先搜索算法（程序）……}。“存儲結構”模型包括的模式集合有{順序存儲模式（線性結構），鏈式存儲模式（非線性結構），散列存儲結構模式}。“隊列算法”模型包括的模式集合有{進隊列算法，圖的廣優先搜索算法，銀行隊列動態處理業務系統，計算機操作系統的排隊處理算法……}。“查找算法”模型包括的模式集合有{線性查找，樹型查找，二分查找，靜態樹表查找，索引順序查找，哈希查找……}等。運用對模型與模式的理解，可以將數據結構課程以知識點的方式組織起來，提供一種快速歸納總結的有效方法。
3.閱讀遞歸和圖等難點算法（程序）的方法探討。第一種：閱讀遞歸程序的方法。將計算機執行的所有遞歸程序語句打開一起閱讀，并注重該算法（程序）進入遞歸和退出遞歸當前保存運算參數狀態情況，可收到良好的閱讀效果。比如，閱讀n！遞歸程序時（利用如圖6的圖示法將n！遞歸的邏輯步驟展現出來），需要利用棧來存儲遞歸調用欲返回的語句地址（標號），即將該遞歸語句加上語句序號后，應牢牢記住兩個環節的參數變化情況。第一，當遇到遞歸語句時，計算機都執行哪些操作？每次轉入遞歸時，將其執行步驟細分兩個步驟：①將當前運行的所有參數的狀態保存到地址棧中；②按照當前遞歸調用語句的實參數替換形式參數的原則進行參數的替換，以此新的參數作為下次遞歸調用的參數。第二，當遇到遞歸結束語句時，計算機都執行哪些操作呢？首先，從地址棧中彈出下一步操作的參數；然后按照地址棧頂彈出的參數執行相關（進入遞歸語句時，壓入棧的參數）未被執行的語句。
第二種：閱讀其他難點程序的方法。可采用將每一循環嵌套的循環體進行層次編號的方法閱讀難點程序。例如，在講授圖的廣度優先算法時可利用層次編號方式編寫和閱讀程序，如圖7所示。
第三種：借助算法流程圖來閱讀復雜算法。因數據結構課程要向學生介紹大量的算法，為了讓學生全方位地掌握和學習數據結構的算法理論、模型等知識，在授課中結合程序設計給學生補充上機實驗所必須要掌握的知識。對線性、非線性結構的復雜算法（程序）分為三種結構：順序結構（如：線性表等順序結構）、條件結構和循環結構。而循環程序又分為計數器控制的循環、條件控制的循環和變量控制的循環，還有復合形式的循環程序等。采用算法流程圖來理解算法的邏輯步驟，使學生對實際問題轉換成的算法有清晰的了解，為培養學生獨立編程打下良好的基礎。
4.區分算法的邏輯步驟、流程圖、偽代碼、算法與程序。美國計算機科學家沃思教授認為：Algorithms+Data Structure=Programs。算法與程序的最大區別在于算法是實現程序的邏輯步驟；數據結構描述了解決問題的數學模型、相關數據集合以及數據之間的結構關系集合；程序是為解決實際問題而編制的一組計算機指令集合。如圖8關于計算機解決問題的步驟可以對算法、程序等概念進行區分。
一般針對給出的問題進行定義與描述的方法除了形式化定義外，還采用算法（程序）的先后次序進行描述。如果將這些問題的邏輯步驟寫成算法的話，可以將問題對應的主要變量進行描述，同時還應該將這些邏輯步驟所涉及到的運算模式進行梳理。因此說，從復雜問題的邏輯步驟到算法實現的最好模式就是采用軟件工程上的算法流程圖來詳細給出實現程序的邏輯步驟。為清晰描述復雜的問題和掌握算法，可采用用戶自定義且邏輯上描述清晰的程序。
四、數據結構的發展及應用前景
數據結構課程主要講授對現實問題求解的模型和方法，通過不斷學習、理解與上機實踐，使學生掌握如何針對不同數據的計算機外部表示形式（邏輯表示模式）建立對應的內部存儲方式（物理模式）。隨著數據倉庫的普及和大數據的應用，勢必要解決更為復雜的數據結構問題，包括多維與稀疏的數據結構問題。另外，隨著對自然語言處理能力的增強和信息檢索方法的增多，應對非線性結構、非數值的數據結構問題進行拓寬，以期取得創新成果。
參考文獻：
[1]嚴蔚敏，吳偉民.數據結構（C語言版）[M].北京：清華大學出版社，2011.
[2]譚浩強.C程序設計[M].第四版.北京：清華大學出版社，2010.
[3]遼寧本科教學網的遼寧大學資源共享課→工學→計算機類→數據結構（大連海事大學陳燕教授主講）
http：//sharecourse.upln.cn/pdt/sharecourse/index.html.
