尋楊　柳欣

[摘 要]當(dāng)前，數(shù)據(jù)結(jié)構(gòu)課程受教學(xué)內(nèi)容所限，教師無(wú)法使學(xué)生掌握知識(shí)的全貌。其教學(xué)若不能從后續(xù)課程中提煉數(shù)據(jù)結(jié)構(gòu)并結(jié)合現(xiàn)實(shí)問(wèn)題進(jìn)行分析，則不利于培養(yǎng)學(xué)生根據(jù)問(wèn)題需求選擇適當(dāng)數(shù)據(jù)結(jié)構(gòu)的能力，也容易使學(xué)生產(chǎn)生數(shù)據(jù)結(jié)構(gòu)課程無(wú)用論。文章提出在課程群視域下對(duì)多門(mén)相關(guān)課程進(jìn)行整體教學(xué)設(shè)計(jì)的思想，并且以B+樹(shù)為例設(shè)計(jì)了可應(yīng)用于三門(mén)專(zhuān)業(yè)核心課程的共享案例。這種新的教學(xué)形式有利于打破課程間的知識(shí)壁壘，分階段引導(dǎo)學(xué)生進(jìn)行知識(shí)建構(gòu)，促進(jìn)學(xué)生創(chuàng)新意識(shí)和問(wèn)題解決能力的培養(yǎng)。

[關(guān)鍵詞]數(shù)據(jù)結(jié)構(gòu);B+樹(shù);案例教學(xué);圖解教學(xué);建構(gòu)主義教學(xué)

[中圖分類(lèi)號(hào)] G642 [文獻(xiàn)標(biāo)識(shí)碼] A [文章編號(hào)] 2095-3437（2021）08-0019-03

引言

《國(guó)家中長(zhǎng)期教育改革和發(fā)展規(guī)劃綱要（2010—2020年）》指出，要牢固確立人才培養(yǎng)在高校工作中的中心地位，著力培養(yǎng)信念執(zhí)著、品德優(yōu)良、知識(shí)豐富、本領(lǐng)過(guò)硬的高素質(zhì)專(zhuān)門(mén)人才和拔尖創(chuàng)新人才[1]。數(shù)據(jù)結(jié)構(gòu)既是計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)（簡(jiǎn)稱(chēng)計(jì)算機(jī)專(zhuān)業(yè)）的專(zhuān)業(yè)基礎(chǔ)課程之一，也是培養(yǎng)計(jì)算機(jī)專(zhuān)業(yè)學(xué)生創(chuàng)新意識(shí)和問(wèn)題解決能力的核心課程。該課程的教學(xué)內(nèi)容是圍繞數(shù)據(jù)元素的邏輯關(guān)系、關(guān)系描述以及相互操作而展開(kāi)的[2]。由于教學(xué)內(nèi)容的理論性強(qiáng)，算法底層的邏輯結(jié)構(gòu)較為抽象，復(fù)雜算法的執(zhí)行過(guò)程難以理解等，因此采用傳統(tǒng)教學(xué)方式往往難以取得理想效果[3]。另外，為了培養(yǎng)學(xué)生的創(chuàng)新意識(shí)，也有必要探索新的教學(xué)方法，幫助學(xué)生形成算法思維模式，增強(qiáng)學(xué)生根據(jù)實(shí)際問(wèn)題需要選擇高效數(shù)據(jù)結(jié)構(gòu)并進(jìn)行性能分析的能力[4]。

數(shù)據(jù)結(jié)構(gòu)課程側(cè)重于在邏輯層面分析和討論問(wèn)題，所講授的存儲(chǔ)結(jié)構(gòu)僅限于利用高級(jí)程序設(shè)計(jì)語(yǔ)言對(duì)邏輯結(jié)構(gòu)進(jìn)行編碼實(shí)現(xiàn)。該課程對(duì)問(wèn)題的討論并不完整。其教學(xué)內(nèi)容僅限于宏觀層面，而無(wú)法涉及針對(duì)特定數(shù)據(jù)結(jié)構(gòu)（如二叉樹(shù)）在硬盤(pán)中的存儲(chǔ)問(wèn)題以及如何從磁盤(pán)讀入主存等微觀層面上的問(wèn)題。另外，盡管課程講授了線性、樹(shù)型和圖狀結(jié)構(gòu)的抽象數(shù)據(jù)類(lèi)型定義以及相關(guān)算法，但是學(xué)生仍然抱有許多疑問(wèn)，諸如所講授的數(shù)據(jù)結(jié)構(gòu)知識(shí)在今后的專(zhuān)業(yè)課學(xué)習(xí)中能否用到，這些數(shù)據(jù)結(jié)構(gòu)在現(xiàn)實(shí)的軟件系統(tǒng)開(kāi)發(fā)過(guò)程中是否得到使用，等等。計(jì)算機(jī)組成原理是硬件類(lèi)的專(zhuān)業(yè)基礎(chǔ)課程，著重講授計(jì)算機(jī)的硬件工作原理以及數(shù)據(jù)在物理層面上的存儲(chǔ)和運(yùn)算原理。因此，這門(mén)課對(duì)問(wèn)題的討論比較微觀，這就有助于學(xué)生深入理解各類(lèi)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的物理存儲(chǔ)方式。數(shù)據(jù)庫(kù)原理與應(yīng)用是軟件類(lèi)的專(zhuān)業(yè)基礎(chǔ)課程。盡管許多數(shù)據(jù)結(jié)構(gòu)（如多鏈表排序、B+樹(shù)索引等）在商業(yè)數(shù)據(jù)庫(kù)系統(tǒng)的開(kāi)發(fā)過(guò)程中得到應(yīng)用，但是如果教師無(wú)法在教學(xué)中對(duì)這些數(shù)據(jù)結(jié)構(gòu)進(jìn)行提煉，學(xué)生往往會(huì)產(chǎn)生數(shù)據(jù)結(jié)構(gòu)技術(shù)在數(shù)據(jù)庫(kù)領(lǐng)域并未得到應(yīng)用的錯(cuò)覺(jué)。為了了解上述問(wèn)題，應(yīng)當(dāng)組織講授上述課程的教師進(jìn)行專(zhuān)門(mén)研討，精心遴選與現(xiàn)實(shí)應(yīng)用緊密結(jié)合且能滲透于三門(mén)課程教學(xué)內(nèi)容中的綜合性案例，通過(guò)開(kāi)發(fā)共享的教學(xué)案例，實(shí)現(xiàn)專(zhuān)業(yè)基礎(chǔ)知識(shí)的全面貫通。

一、專(zhuān)業(yè)核心課程群視域下的總體教學(xué)設(shè)計(jì)思路

課程群是由多門(mén)教學(xué)內(nèi)容密切相關(guān)的課程構(gòu)成的集合。這些課程適合在更大的框架下進(jìn)行整體建設(shè)，以達(dá)到優(yōu)化教學(xué)資源配置和提高教學(xué)質(zhì)量的效果[5]?？梢曰谡n程群的思路對(duì)密切相關(guān)的專(zhuān)業(yè)核心課程進(jìn)行整體教學(xué)設(shè)計(jì)，開(kāi)發(fā)可以共享的教學(xué)案例。開(kāi)發(fā)共享教學(xué)案例的意義主要有以下幾方面：（1）訓(xùn)練學(xué)生從現(xiàn)實(shí)應(yīng)用中提煉數(shù)據(jù)內(nèi)容和數(shù)據(jù)結(jié)構(gòu)，形成“站在計(jì)算機(jī)角度”進(jìn)行思維的意識(shí)，提高邏輯思維和創(chuàng)新能力。（2）打破相關(guān)課程之間的知識(shí)壁壘，促進(jìn)學(xué)生對(duì)知識(shí)的全面掌握。（3）圍繞復(fù)雜問(wèn)題和復(fù)雜算法設(shè)計(jì)綜合案例，在不同課程中講授案例的某一部分，有利于降低難度，實(shí)現(xiàn)認(rèn)識(shí)水平的螺旋式上升。（4）為地方院校開(kāi)展以“專(zhuān)業(yè)核心課程深度融合和整體建設(shè)”為抓手的系列教學(xué)改革積累經(jīng)驗(yàn)，為后期開(kāi)展工程教育專(zhuān)業(yè)認(rèn)證奠定基礎(chǔ)。

二、支撐性的教學(xué)理論及其內(nèi)涵

我們的教學(xué)改革是在案例教學(xué)、圖解教學(xué)和建構(gòu)主義教學(xué)理論指導(dǎo)下開(kāi)展的。（1）案例教學(xué)法起源于哈佛大學(xué)，其基本思想是將相關(guān)的案例引入課堂教學(xué)，通過(guò)設(shè)置案例展示和案例討論環(huán)節(jié)，幫助學(xué)生理解抽象知識(shí)，并且展示它們?cè)趯?shí)踐中的具體運(yùn)用[6]。開(kāi)展案例教學(xué)的目的在于創(chuàng)設(shè)情境以及引導(dǎo)學(xué)生深入思考，從而達(dá)成“知識(shí)+應(yīng)用”的教學(xué)目標(biāo)。（2）開(kāi)展數(shù)據(jù)結(jié)構(gòu)教學(xué)的難點(diǎn)在于如何展現(xiàn)抽象的邏輯結(jié)構(gòu)、邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的對(duì)應(yīng)關(guān)系、復(fù)雜算法的求解過(guò)程以及如何將問(wèn)題求解思路轉(zhuǎn)換為代碼描述。對(duì)此，一種行之有效的辦法是使用結(jié)構(gòu)圖[7]。通過(guò)圖解，可以直觀地展示問(wèn)題求解過(guò)程中數(shù)據(jù)邏輯結(jié)構(gòu)的演進(jìn)變化及其與代碼描述之間的關(guān)系。鼓勵(lì)學(xué)生進(jìn)行算法的圖解，有助于促進(jìn)學(xué)生的思維訓(xùn)練，加深學(xué)生對(duì)存儲(chǔ)結(jié)構(gòu)的理解，提高學(xué)生解決問(wèn)題的能力。（3）建構(gòu)主義教學(xué)理論強(qiáng)調(diào)以學(xué)生的內(nèi)在經(jīng)驗(yàn)和知識(shí)為基礎(chǔ)，通過(guò)創(chuàng)設(shè)教學(xué)情境引發(fā)知識(shí)沖突，以促進(jìn)學(xué)生實(shí)現(xiàn)自我知識(shí)建構(gòu)[8]。斯皮羅等人提出隨機(jī)進(jìn)入式教學(xué)的觀點(diǎn)[9]。其基本思想是為了幫助學(xué)生全面掌握事物的內(nèi)在性質(zhì)以及事物間的聯(lián)系，利用不同的途徑與方式，在不同的時(shí)間進(jìn)入同一教學(xué)內(nèi)容的學(xué)習(xí)。但是，所謂的“多次進(jìn)入”并不意味著相同內(nèi)容的簡(jiǎn)單重復(fù)，而是每次進(jìn)入著眼于問(wèn)題的不同側(cè)面，進(jìn)而使學(xué)生通過(guò)多次學(xué)習(xí)認(rèn)識(shí)事物的全貌，實(shí)現(xiàn)認(rèn)識(shí)上的飛躍。

三、共享案例教學(xué)設(shè)計(jì)——以B+樹(shù)索引為例

（一）案例選取

隨著數(shù)據(jù)規(guī)模的日益擴(kuò)大，數(shù)據(jù)查詢效率成為影響數(shù)據(jù)庫(kù)性能的關(guān)鍵因素之一。索引機(jī)制是提高數(shù)據(jù)查詢效率的有效辦法，B+樹(shù)是一種在數(shù)據(jù)庫(kù)索引領(lǐng)域得到廣泛應(yīng)用的樹(shù)型結(jié)構(gòu)。利用該結(jié)構(gòu)的索引文件，有利于減少磁盤(pán)讀取次數(shù)和提高內(nèi)存的利用率[10]。鑒于B+樹(shù)索引具有較大的現(xiàn)實(shí)意義且該項(xiàng)內(nèi)容適合在數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)組成原理和數(shù)據(jù)庫(kù)原理與應(yīng)用這三門(mén)課程中進(jìn)行講授，因此我們選取該項(xiàng)內(nèi)容進(jìn)行共享案例設(shè)計(jì)。該案例的設(shè)計(jì)目標(biāo)是通過(guò)分階段實(shí)施案例教學(xué)，將這三門(mén)課程涉及的十個(gè)左右的知識(shí)點(diǎn)貫穿起來(lái)（如表1所示），激發(fā)學(xué)生學(xué)習(xí)興趣，促進(jìn)學(xué)生深入思考，實(shí)現(xiàn)讓學(xué)生從微觀與宏觀的角度全面掌握相關(guān)知識(shí)的目標(biāo)。

（二）共享案例詳細(xì)的教學(xué)設(shè)計(jì)

根據(jù)這三門(mén)課程的先修后修關(guān)系，我們將整個(gè)案例的實(shí)施過(guò)程分為以下三個(gè)階段。

第一個(gè)階段是在數(shù)據(jù)結(jié)構(gòu)教學(xué)過(guò)程中完成的。在講授完二叉排序樹(shù)、B-樹(shù)和B+樹(shù)之后，教師給出一個(gè)有關(guān)B+樹(shù)應(yīng)用的綜合案例，通過(guò)對(duì)相關(guān)邏輯結(jié)構(gòu)進(jìn)行性質(zhì)比較，幫助學(xué)生加深對(duì)知識(shí)的理解。案例問(wèn)題描述如下：給定一組關(guān)鍵字，要求學(xué)生構(gòu)造三種面向動(dòng)態(tài)查找法的樹(shù)型結(jié)構(gòu)，即二叉排序樹(shù)、B-樹(shù)和B+樹(shù)（如圖1所示），用結(jié)構(gòu)圖畫(huà)出三種樹(shù)型結(jié)構(gòu)的構(gòu)造過(guò)程，并且對(duì)它們的查找效率進(jìn)行比較。在構(gòu)造過(guò)程中，教師提示學(xué)生注意二叉排序樹(shù)構(gòu)造過(guò)程中的平衡調(diào)整問(wèn)題，以及在B-/B+樹(shù)構(gòu)造過(guò)程中的結(jié)點(diǎn)分裂問(wèn)題等。在效率比較過(guò)程中，教師提示學(xué)生將平均查找長(zhǎng)度作為三種結(jié)構(gòu)效率比較的重要依據(jù)。在案例總結(jié)階段，教師引導(dǎo)學(xué)生得出以下結(jié)論：（1）對(duì)于給定關(guān)鍵字key，查找過(guò)程的效率取決于“從根結(jié)點(diǎn)到結(jié)點(diǎn)key的路徑上”的結(jié)點(diǎn)個(gè)數(shù)（即比較次數(shù)）。（2）對(duì)于B-/B+樹(shù)，可以將查找過(guò)程中的比較次數(shù)表示為logd[（N+1）/2]+1（N表示關(guān)鍵字總數(shù)，d表示內(nèi)部結(jié)點(diǎn)的度數(shù)）。（3）與二叉排序樹(shù)和B-樹(shù)相比，B+樹(shù)支持的查找方式更為靈活，即除了可以從根結(jié)點(diǎn)出發(fā)，“從上至下”進(jìn)行查找，還可以在最底層沿水平方向進(jìn)行查找。上述案例的教學(xué)目標(biāo)是使學(xué)生在宏觀層面上深入理解三種結(jié)構(gòu)的特點(diǎn)，掌握基于平均查找長(zhǎng)度的查找效率分析方法。

第二個(gè)階段是在計(jì)算機(jī)組成原理課程教學(xué)過(guò)程中完成的。介紹完硬盤(pán)存取原理和主存工作原理之后，教師再次向?qū)W生提出上述案例，并且將討論重點(diǎn)轉(zhuǎn)向以下內(nèi)容。首先，介紹上述三種結(jié)構(gòu)的現(xiàn)實(shí)應(yīng)用是作為數(shù)據(jù)庫(kù)索引文件的組織形式。然后，介紹三種索引文件在硬盤(pán)中的存儲(chǔ)方法以及將位于硬盤(pán)上的結(jié)點(diǎn)讀入內(nèi)存的過(guò)程。在此階段，教師需要引導(dǎo)學(xué)生深入思考以下問(wèn)題：（1）每讀入一個(gè)結(jié)點(diǎn)（即執(zhí)行1次I/O操作）需要多少時(shí)間。（2）如何從微觀角度理解B+樹(shù)索引的檢索過(guò)程（如圖2所示），以及如何對(duì)檢索過(guò)程的時(shí)間效率進(jìn)行分析。在案例總結(jié)階段，教師引導(dǎo)學(xué)生得出以下結(jié)論：在關(guān)鍵字檢索過(guò)程中，每訪問(wèn)一個(gè)內(nèi)部結(jié)點(diǎn)/葉結(jié)點(diǎn)，就需要執(zhí)行1次I/O操作。因此，索引文件的檢索效率取決于檢索過(guò)程中的I/O操作次數(shù)。通過(guò)上述案例教學(xué)過(guò)程，學(xué)生會(huì)在微觀層面上對(duì)這三種樹(shù)型結(jié)構(gòu)產(chǎn)生新的認(rèn)識(shí)。

第三個(gè)階段是在數(shù)據(jù)庫(kù)原理與應(yīng)用課程教學(xué)過(guò)程中完成的。在介紹完索引原理之后，教師第三次提出上述案例，并對(duì)案例的描述做出以下調(diào)整：假設(shè)員工信息表包含“工號(hào)”和“姓名”兩個(gè)字段。為了提高查找效率，要求基于二叉排序樹(shù)、B-樹(shù)和B+樹(shù)技術(shù)分別構(gòu)造索引文件，并且利用結(jié)構(gòu)圖畫(huà)出員工信息表與三種索引文件的存儲(chǔ)結(jié)構(gòu)。在圖解過(guò)程中，教師指導(dǎo)學(xué)生設(shè)計(jì)結(jié)構(gòu)圖，著重體現(xiàn)索引與數(shù)據(jù)庫(kù)記錄的對(duì)照關(guān)系（如圖3所示），并介紹選取B+樹(shù)作為商業(yè)數(shù)據(jù)庫(kù)（如MySQL）索引的原因。

在此階段，教師需要引導(dǎo)學(xué)生深入思考以下問(wèn)題：（1）如何統(tǒng)計(jì)三種索引結(jié)構(gòu)在查找過(guò)程中的比較次數(shù)？（2）假設(shè)關(guān)鍵字總數(shù)為N，且d表示B-/B+樹(shù)中每個(gè)內(nèi)部結(jié)點(diǎn)的度數(shù)，為何B+樹(shù)索引優(yōu)于另外兩種索引（如表2所示）？在案例總結(jié)階段，教師引導(dǎo)學(xué)生得出以下結(jié)論：在B-/B+樹(shù)中，查找過(guò)程的關(guān)鍵字比較次數(shù)約為[logdN]。

四、結(jié)束語(yǔ)

本文 在專(zhuān)業(yè)核心課程群視域下，研究了對(duì)數(shù)據(jù)結(jié)構(gòu)課程與后續(xù)的計(jì)算機(jī)組成原理課程和數(shù)據(jù)庫(kù)原理與應(yīng)用課程進(jìn)行整體教學(xué)設(shè)計(jì)的問(wèn)題。選取B+樹(shù)作為聯(lián)系這三門(mén)課程的教學(xué)內(nèi)容，并且基于建構(gòu)主義教學(xué)理論，圍繞B+樹(shù)的相關(guān)知識(shí)進(jìn)行“分階段多次進(jìn)入”的共享案例教學(xué)設(shè)計(jì)。同時(shí)，利用結(jié)構(gòu)圖技術(shù)對(duì)二叉排序樹(shù)、B-樹(shù)和B+樹(shù)的復(fù)雜邏輯結(jié)構(gòu)進(jìn)行直觀展示。本文提出的案例有利于幫助學(xué)生從宏觀和微觀層面全面掌握B+樹(shù)相關(guān)知識(shí)，培養(yǎng)邏輯思維和問(wèn)題解決能力。

[ 參 考 文 獻(xiàn) ]

[1] 教育部.國(guó)家中長(zhǎng)期教育改革和發(fā)展規(guī)劃綱要（2010—2020年）[EB/OL]. （2010-07-29）[2020-04-02].http：//old.moe.gov.cn/publicfiles/business/htmlfiles/moe/info_list/201407/xxgk_171904.html

[2] 張銘，耿國(guó)華，陳衛(wèi)衛(wèi)，等. 數(shù)據(jù)結(jié)構(gòu)與算法課程教學(xué)實(shí)施方案[J].中國(guó)大學(xué)教學(xué)，2011（3）：56-60.

[3] 柳欣，張斌，張波.復(fù)雜算法的案例教學(xué)設(shè)計(jì)[J].計(jì)算機(jī)時(shí)代，2020（2）：109-111+116.

[4] 羅麗燕，鄧小芳，林樂(lè)平.“雙一流”建設(shè)背景下數(shù)據(jù)結(jié)構(gòu)課程教學(xué)初探[J].大學(xué)教育，2020（3）： 80-82.

[5] 張映輝， 陶霞. 地方本科院校數(shù)學(xué)與應(yīng)用數(shù)學(xué)專(zhuān)業(yè)課程群建設(shè)的理論與實(shí)踐[J]. 湖南理工學(xué)院學(xué)報(bào)（自然科學(xué)版）， 2016（1）： 92-94.

[6] 錢(qián)明輝，李天明，舒詩(shī)雅，等.教學(xué)案例開(kāi)發(fā)框架模型的構(gòu)建及其應(yīng)用[J].管理案例研究與評(píng)論，2018（2）：210-220.

[7] 農(nóng)國(guó)才. 淺談圖示在數(shù)據(jù)結(jié)構(gòu)教學(xué)中的應(yīng)用[J]. 廣西民族師范學(xué)院學(xué)報(bào)，2013（3）：70-72.

[8] 李雪珊. 基于建構(gòu)主義理論的教學(xué)策略初探：以《高等數(shù)學(xué)》課程教學(xué)為例[J]. 西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014（2）：152-155.

[9] 李曉波，劉磊. 建構(gòu)主義理論及其在《數(shù)據(jù)結(jié)構(gòu)》教學(xué)中的應(yīng)用探索[J]. 濰坊學(xué)院學(xué)報(bào)，2008（6）：155-156.

[10] 施恩，顧大權(quán)，馮徑，等. B+樹(shù)索引機(jī)制的研究及優(yōu)化[J].計(jì)算機(jī)應(yīng)用研究， 2017（6）：1766-1769.

[責(zé)任編輯：龐丹丹]