數據結構課程難點講授方法與必備知識

陳燕+屈莉莉+李桃迎

摘要：數據結構是計算機等相關專業重要的專業基礎課，各大高校都十分重視該課程的教學效果。捋順數據結構的先修后繼課程，構建該課程的知識體系結構，凝練線性與非線性兩大分類知識點，有助于形成該課程的系統化教學體系。將理論學習與工程實踐的緊密結合作為講授課程的側重點，提高學生解決實際問題的能力。注重培養學生閱讀和編制程序的技能，將是突破課程難點的重要方法。

關鍵詞：數據結構；知識點；課程體系；程序設計

中圖分類號：G642.41 文獻標志碼：A 文章編號：1674-9324（2015）27-0125-03

一、引言

《數據結構》一直被認為是計算機、信息管理與信息系統、電子商務等專業重要的基礎課程之一。該課程的知識涉及到多學科與多專業，掌握該課程將對學生后續課程的學習起到重要的知識鏈接作用。數據結構課程的主要知識點包括：①線性表的順序存儲結構與鏈式存儲結構及對應算法；②棧的順序存儲與鏈式結構及對應算法；③隊列的順序存儲與鏈式結構及對應算法；④串的順序與鏈式存儲結構及對應算法；⑤數組和廣義表的存儲結構及對應算法；⑥樹和二叉樹的順序與鏈式存儲結構及對應算法；⑦查找方法；⑧排序方法等。為學好這門課程，必須依據課程體系，明確數據結構課程中的概念與術語，靈活運用這些知識點，以達到扎實掌握該課程難點的目的。

二、數據結構的先修后繼課程及知識體系結構

1.掌握數據結構課程的先修與后繼課程。以信息管理與信息系統專業課程體系為例，清晰了解和掌握與數據結構相關聯的先修與后繼課程（如圖1所示）。先修課程主要有：計算機信息處理概論、匯編語言程序設計、高級語言程序設計（C、C++、Java等）、計算機組成原理、離散數學、運籌學、圖論等。后續課程主要有：數據庫原理、信息系統開發方法、編譯原理、信息檢索、數據倉庫與數據挖掘、操作系統、信息集成技術及應用、電子商務與物流信息管理、大數據分析等相關課程。

2.數據結構課程實施框架體系的創新模式。圍繞如下頁圖2所示的數據結構課程實施框架體系的創新模式講授數據結構課程。明確數據結構課程的知識體系和主要知識點。該模式的優勢在于：能夠使學生快速掌握數據結構的概念、術語，客觀世界問題對應在計算機外部的表示方式，在計算機內部的存儲方式，以及如何對它們進行操作（運算）；除此之外，還能夠嚴格按照數據結構課程的各個知識點進行梳理，清楚地歸納出數據結構與其他相關課程的關聯關系。

三、運用歸納總結方法對數據結構課程的知識點進行分類

以嚴蔚敏教授出版的數據結構經典教材為例，將數據結構的知識點進行分類：第一類將第二章“線性表”、第三章“棧與隊列”、第四章“串”、第五章“廣義表”劃分為數據的線性結構部分；第二類將第六章“樹與二叉樹”、第七章“圖”劃分為數據的非線性結構部分。

將自然界的線性問題對應的數據結構實例例舉出來，形成數據結構問題的感性和直觀的認識；然后再由淺入深地掌握其相關的知識點。例如：①為使管理人員快速找到客戶相關信息，用計算機處理該業務應首先確定所使用的數據結構形式，如果希望將電話號碼作為關鍵字，姓名的拼音作為次關鍵字，那么，會容易地查找出“陳”性拼音順序排在“周”性之前的線性關系。②到銀行辦理業務對應的數據結構形式是隊列模式，即滿足“先來先服務，后來后服務”的服務規律。③對字符串進行存儲與處理時，其存儲結構具有緊湊和非緊湊形式，因此需按照形式的不同，進行分類處理后，再對其進行操作（如：插入、刪除、查找、模式串匹配等）。④到圖書館借書時，圖書管理員檢索的模式與圖書的存放形式有關。

與線性結構相比，非線性結構要復雜得多，即線性表的數據結構中數據元素的邏輯結構與物理結構之間存在一一對應的順序關系；而非線性的數據結構中數據元素的邏輯結構與物理結構之間不存在一一對應的順序關系，它們之間的順序是任意的，也就是說非線性的數據結構中數據元素之間不存在前驅和后繼的順序關系，為使初學者掌握其存儲結構對應的操作等相關知識點，必須將數據結構教科書中關于樹與圖的遍歷進行深入而細膩的講授。以二叉樹的遍歷問題為例，說明非線性結構應該著重講授的知識點與教學方式。一般遍歷某二叉樹的原則是：先確定樹根，然后按照樹的遞歸原則進行先序、中序和后序等遍歷，下圖3所示。從三種遍歷的序列可以看出，其每種遍歷的結果序列都有其唯一的前驅和后繼結點。這個規律說明一個道理：任何的非線性結構的結點元素都可以通過先確定遍歷的名稱，然后通過遍歷方便地對其進行訪問，比如：在前序遍歷的序列“-+a*b-cd/ef”仿照線性表的定義找出它們之間的前驅與后繼之間的關系；另外，同樣中序和后繼的遍歷結果也可以仿照線性表的定義找出它們之間的前驅與后繼之間的關系。同時，注意對學生發散性思維的培養，可通過三種遍歷結果，進一步解釋難以理解的概念推理，推論一：若已知一棵二叉樹的前序序列和中序序列，則可以唯一地確定這棵二叉樹；推論二：若已知一棵二叉樹的后序序列和中序序列，則也可以唯一地確定這棵二叉樹。在講授該本課程知識點的同時，應考慮對后繼課程的鋪墊與銜接，上述三種遍歷結果，對后續《編譯原理》課程的前綴碼、中綴碼、后綴碼等概念的理解與掌握將起到重要作用。

四、運用靈活的教學方式講授難點章節

由于數據結構課程設計到多學科（專業）知識點，因此，教與學的過程中，難免存在難點、“瓶頸”問題和難以理解的算法。為解決此問題，在教學中應注重選用具有代表性的例子，如：在第七章的許多工程類例子與運籌學的例子非常相似，因此，在講授此章節時，注重教材例子與運籌學學習的重點，但不同專業基礎課程的側重點不同。

1.非線性數據結構的講授方法。以第七章為例，該章的相關知識內容有：圖論、數據的邏輯結構及其對應的物理結構、算法實現的技巧與方法、優化問題、非線性問題的映射方法。主要存在如下難點：①非線性問題的邏輯表示方法。根據工程類例子的實際需求，找出該問題的邏輯表示方法是解決問題的核心。如：將符合多種方案選擇的工程類的工序問題（如：排課問題、具有先后時間次序的問題），運用有向圖的知識點將該問題表示清晰；應該標明該數據元素屬于鄰接表還是順序存儲形式。②非線性問題的物理表示方法。通過問題的邏輯表示方法可以將工程類的工序問題轉換成有向圖的存儲方式，然后再選擇圖的存儲結構，如：數組（順序）存儲、鄰接表（鏈式）存儲等方式。③如何編制實現解決非線性問題的算法（程序）。上述的邏輯結構確定了之后，再根據實際問題的要求進行實現程序的核心部分即算法的編制工作，當算法太復雜時，則先設計算法流程圖然后再編寫實現算法的程序。endprint

2.非線性數據結構的上機實踐方法。最為有效的方法是選擇學生日常生活中與工程類算法處理流程相近的例子。如在拓撲排序的上機實踐選擇的題目是給某專業課程進行排序，這個例子的選課過程正好符合工程類工序（周期）施工排序的案例；設計報文或字符編碼時，按照第六章中的哈弗曼樹的存儲結構對報文進行編碼；選擇順序線性表的上機例子是在一張學生登記表中進行插入和刪除運算；選擇鏈式線性表的上機例子是在一張按照拼音順序進行插入和刪除運算的線性表。

五、閱讀程序的技巧與必備知識

數據結構的大量算法都要靠其對應的程序來驗證，那么，如何針對數據結構經典算法來編程并且閱讀這些經典的算法（程序）呢？這也是學好數據結構這門課程的關鍵。

1.讓學生通過閱讀程序，了解如何科學選取一個好的程序（算法）。由于程序是依靠“算法+數據結構”實現的，對一個實際問題來說，可以有不同的程序來實現。僅以一個簡單的例子說明，如：運用計算機進行n的平方計算，有3種方法：n的平方=n n；n的平方=1+3+…+2n-1；高級語言自帶的求平方函數，如double pow（n，2）。上述算法一個采用乘法，一個采用加法，一個是高級語言自帶的，究竟哪種方法好呢？主要還是看其運算精度、算法的復雜度和空間復雜度等綜合指標。

2.讓學生通過閱讀程序，了解和掌握相關知識點。應補充程序設計分類的相關知識。程序包括：直接程序設計，條件控制的程序，循環控制的程序（計數器控制的循環結構程序的算法、條件控制的循環結構程序的算法、變量控制的循環結構程序的算法）。還應該向學生介紹算法轉換為運行程序的經驗，如：數據的初始化如何處理；程序中的循環計數器與判斷條件以及檢驗結果如何檢驗；遞歸程序中的出口條件判斷問題；邏輯變量、精度、機器零、數值零、文本非結構化等歸一問題。

3.快速閱讀程序的必備知識。按照數據結構的課程要求，必須在讀懂經典算法的基礎上，才能夠編制一個邏輯結構嚴謹的程序。但是，在教學中發現，有的學生學習方法不當，導致閱讀程序的能力低而不能系統掌握數據結構課程的知識點。為了解決這一“瓶頸”問題，在講授數據結構第一章緒論內容中，增加了程序設計方法、編制算法流程圖的標準與規定、算法與程序的區分、如何選用大O來計算算法的時間復雜度和空間復雜度等知識點。遞歸程序的閱讀是數據結構中較難掌握的內容。為讓學生順利閱讀遞歸程序，必須在閱讀遞歸算法之前，補充相關的知識，如：計算機原理“中斷”的概念；程序設計中的過程調用的步驟和閱讀方法；遞歸程序本身的特點，以及遞歸過程與一般過程的區別等。

六、小結

數據結構課程是計算機相關專業重要的基礎課程之一，但課程學習難度較大，為提高該課程的教學質量和教學效果，本文梳理了數據結構的先修后繼課程，構建了課程的知識體系結構，提煉出數據結構知識點分類的線性與非線性兩條主線，強調將理論學習與工程實踐的有機結合，提出實現程序設計與具備閱讀程序的技巧是解決課程難點的重要手段。

參考文獻：

[1]嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，2011.

[2]陳燕，等.數據結構[M].北京：科學出版社，2014.

[3]陳志珍，等.數據結構算法應用—基于Floyd算法的醫院選址問題求解[J].教育教學論壇，2014，（36）：280-281.

[4]陳燕，等.數據結構教學方法的探討[J].教育教學論壇，2013，（49）：82-84.endprint