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