案例驅(qū)動下數(shù)據(jù)結構教材的編寫

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