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