案例驅動下數據結構教材的編寫

　　摘要：介紹數據結構的基本概念，討論對數據結構課程的認知，提出教材編寫過程中的幾個要點，強調案例驅動教學模式在教材編寫中的重要性，從而形成教材自身的特色。
　　關鍵詞：數據結構；算法；C++語言；案例驅動
　　
　　1研究背景
　　“數據結構”的概念最早是C.A.R.Hoare于1966年提出的。在他的經典論文《數據結構筆記》中，他首次系統地論述了一組數據結構的構造、表示和操作等問題。1973年，D.E.Knuth在《計算機程序設計技巧》第一卷中給出了關于“信息結構”的系統論述。1976年，N.Wirtnh用“算法+數據結構=程序”這個公式表達了算法與數據結構的聯系和它們在程序中的地位[1]。從此，數據結構確立了在計算機相關專業中的核心基礎課程地位。
　　數據結構是一門關于非數值數據在計算機中表示、變換及處理的課程。這里的數據，實質是指計算機所能表示的各種不同數據對象(性質相同的數據元素的集合)的集合。對于每一具體的數據對象，數據元素之間的關系都不是孤立的。數據元素之間的內在聯系被稱之為結構。從數據元素之間的關系特征分析，各種數據對象的數據元素之間的關系僅呈以下四種結構之一：集合結構、線性結構、樹形結構、圖形結構。
　　數據結構課程的主要內容，是針對以上四種結構，先從邏輯層面討論結構的關系特征及抽象操作；再討論結構在計算機中的存儲表示(映像)；并在存儲表示的基礎上給出相應結構的基本操作及實現；最后討論各種結構的應用。
　　已有教材編寫的思路莫不如此。但許多教材過于抽象而甚少工程背景，原因在于那些教材描述算法所使用的語言工具常是偽代碼指令[2-3]，或在涉及數據結構轉化于應用時往往不能完整地展開。因此，許多剛學完計算機高級語言、編程能力尚且不足的學生為此而深感困惑。
　　在長期的教學過程中，我們認為數據結構是一門兼具理論性與實踐性的課程，也是在掌握程序設計語言后加強與提高學生程序設計能力的課程。因此，我們在編寫數據結構教材時，以基本數據結構的主要內容為主線，在充分討論結構的邏輯特征基礎上給出結構在計算機中經典的存儲表示(映像)，并在存儲表示的基礎上，用C++語言實現結構下的各個基本操作(建立結構的順序類或鏈式類)。我們強調數據結構的應用，以模板的形式給出各種不同數據對象應用數據結構(線性結構、樹形結構、圖形結構、集合結構)的多個實例。每一算法或程序的編寫高效、易讀，并遵循程序設計的規范，從而使學習者將數據結構與工程應用有機結合。
　　2教材編寫的幾個要點
　　2.1教學大綱及教材內容
　　歷經三十多年的發展，數據結構課程的主要討論范疇已基本取得共識。盡管計算機應用領域仍在不斷擴大，并產生了許多新的數據結構和算法，但數據結構最基本、最核心的內容還是各種經典教材中反復強調的最具有代表性的那些知識。2006年，教育部高等學校計算機科學與技術教學指導委員會編制了《高等學校計算機科學與技術專業發展戰略研究報告暨專業規范》[4]，其中，算法與數據結構涉及AL1、AL2、AL3、AL4、AL5、PF2、PF3、PF4等多個知識單元，知識點包括遞歸，面向對象程序設計的基本理論，基本數據結構(棧、隊列、鏈表、串、數組、廣義表、樹、圖、哈希表等)，常用排序算法，常用查找技術，算法分析基礎等。2009年，教育部考試中心制訂了全國碩士研究生入學統一考試關于數據結構的考試大綱。以上內容構成了我們編寫教材的大綱依據。
　　我們編寫的教材[5]共七章，內容如下。
　　1) 第一章：緒論。
　　內容包括數據、數據元素、數據對象、數據結構、數據類型、抽象數據類型、算法的概念、算法時間復雜度和空間復雜度的分析等。
　　2) 第二章：線性表。
　　內容包括線性表的基本概念和類型定義、線性表的順序存儲結構、線性表順序類的實現、線性表的鏈接存儲結構、線性表單鏈表類的實現、循環鏈表及雙向鏈表的存儲結構、線性表的應用等。
　　3) 第三章：其他線性結構。
　　內容包括棧的存儲及操作實現、棧的應用舉例、遞歸、隊列的定義和基本操作、字符串、數組及矩陣的存儲壓縮、廣義表等。
　　4) 第四章：樹型結構。
　　內容包括樹、森林的定義及基本術語、二叉樹的結構定義、二叉樹的存儲結構、二叉樹的遍歷、二叉樹基本操作的實現、樹和森林的遍歷、樹型結構的應用(算術表達式求值、樹與等價問題、赫夫曼樹及赫夫曼編碼)等。
　　5) 第五章：圖。
　　內容包括圖的定義和術語、圖的存儲結構、圖的基本操作、圖的遍歷、圖的應用(最小生成樹、最短路徑、拓撲排序和關鍵路徑、最短路徑)等。
　　6) 第六章：查找。
　　內容包括靜態查找表(順序查找、折半查找、分塊查找)，動態查找表(二叉排序樹、平衡二叉樹、B-樹和B+樹)，哈希查找等。
　　7) 第七章：排序。
　　內容包括插入類排序、分劃類排序、選擇類排序、歸并類排序、基數排序、外部排序介紹等。
　　在教材的編寫過程中，我們注重在體系完整、結構合理、概念清晰的基礎上形成自己的特色。如對于線性表，強調注重在順序及鏈式存儲映像下基本操作的實現，對于棧和隊列等操作上受限制的線性結構，強調注重相關環境下的應用，對于樹、圖等非線性結構，強調注重遍歷及遍歷的應用，對于查找和排序等，強調注重在消化各種經典算法的基礎上時間效率的評估。
　　2.2選擇C++語言描述算法
　　本教材的另一個特點是將面向對象的方法引入到數據結構領域。面向對象技術不僅是一種程序設計方法學，而且是一種認識方法學，數據結構討論的正是數據的描述與處理，與面向對象的認知方法具有天然的聯系。面向對象程序設計語言提供的封裝、繼承、多態和泛型程序設計等機制，為數據結構抽象數據類型的程序實現提供了很好的描述工具。
　　此外，面向對象的最大好處是復用、復用、再復用。數據結構中涉及的各類結構下的基本操作，在實際應用中也是常用的基本操作，而選擇面向對象的高級語言C++作為描述算法的工具，既能將高級語言程序設計與數據結構緊密結合，又能通過數據結構進一步認識C++中的STL(標準模板庫)，從而為實際編程的復用帶來方便。顯然，在數據結構的學習過程中，面向對象的主流語言C++較偽碼語言更值得推崇。
　　2.3典型案例設計及舉例
　　基于案例驅動的教學模式設計是以興趣引導出發、以培養學生的設計能力為宗旨的教學模式，即通過對具體實例的演示、講解，引導學生利用已學的知識，學會分析問題的方法，培養學生解決問題的能力[6]，以達到對問題更高層次的認知。在數據結構教材編寫過程中，我們首先在存儲表示的基礎上，以類的方式實現相應結構的抽象數據類型，然后精心設計案例，通過模板的方式，使用類解決各個不同的應用問題，且對每一案例的解題都附有主函數，以確保應用的完整性。
　　例如，對于二叉樹的學習，遍歷是課程的重點，其重要性不僅在于遍歷操作自身，更重要的是，它還是許多樹形結構應用的基礎。因此，我們設計了算術表達式求值這一案例。在這一案例中，使用二叉樹的先序遍歷次序和中序遍歷次序建立二叉表達式樹，使用二叉樹后序遍歷的思想對表達式求值，通過這一案例的學習，將二叉樹三種重要的遍歷融于一處。
　　圖1是表達式用二叉樹表示的例子。
　　圖1算術表達式二叉樹
　　在實現了用二叉鏈表結構定義的表達式類BinaryExpTree后，利用表達式的前綴式及中綴式建立二叉表達式樹的函數如圖2中的算法1所示。其中
　　
　　ch1為表達式的前綴表示，ch2為表達式的中綴表示，low、high分別為中綴次序的起始和最終位置，本函數根據先序次序和中序次序的形成規律，運用先序遞歸遍歷的思想逐個為先序次序中的第k個元素(k的初值為0)生成二叉鏈表中的結點。
　　在圖3中，設在數組ch1中存有二叉表達式樹的前綴表示，而在數組ch2中存有二叉表達式樹的中綴表示。k指示了當前子樹的根結點位置，在建立了根結點后，查找ch1[k]在ch2 中的位置i，從而形成新的劃分L(low——i-1)、D(i)、R(i+1——high)。
　　K加1，對左右兩部分依次遞歸地建樹，直至某一子序列出現low > high，則子樹建畢。
　　
　　void BinaryExpTree :: _Create ( BTnode*