基于工程認(rèn)證的數(shù)據(jù)結(jié)構(gòu)實(shí)踐逆向教學(xué)設(shè)計(jì)

徐燕妮，林曉霞，李環(huán)宇

（山東科技大學(xué)（泰安校區(qū)）信息工程系，泰安271000）

0 引言

作為國際通行的工程教育質(zhì)量保障制度，工程教育專業(yè)認(rèn)證是大勢所趨，國家已經(jīng)全面建立工程專業(yè)認(rèn)證體系[1-2]，各大院校正積極地投入大量精力進(jìn)行工程專業(yè)認(rèn)證的審核。在此大背景下，本文從學(xué)生發(fā)展和社會需求為出發(fā)點(diǎn)，專業(yè)培養(yǎng)目標(biāo)為導(dǎo)向，對《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)課程教學(xué)環(huán)節(jié)進(jìn)行逆向設(shè)計(jì)，助于提升學(xué)生實(shí)踐創(chuàng)新能力，全面提高工程教育人才培養(yǎng)質(zhì)量。

1 數(shù)據(jù)結(jié)構(gòu)課程的培養(yǎng)目標(biāo)

《數(shù)據(jù)結(jié)構(gòu)》課程是計(jì)算機(jī)專業(yè)及相關(guān)專業(yè)的核心課程，在整個課程體系中起了承上啟下的作用，在系統(tǒng)應(yīng)用軟件開發(fā)、無線傳感器網(wǎng)絡(luò)、入侵檢測等領(lǐng)域均有廣泛的應(yīng)用。它全面而又系統(tǒng)地講解了數(shù)據(jù)的組織形式、在計(jì)算機(jī)內(nèi)部的存儲形式以及數(shù)據(jù)相關(guān)運(yùn)算的實(shí)現(xiàn)。著重培養(yǎng)學(xué)生軟件設(shè)計(jì)、算法應(yīng)用、編程調(diào)試和計(jì)算思維的綜合素質(zhì)，提高學(xué)生運(yùn)用所學(xué)專業(yè)知識解決實(shí)際信息技術(shù)問題和自主創(chuàng)新的能力。在工程專業(yè)認(rèn)證的大背景下，《數(shù)據(jù)結(jié)構(gòu)》作為信息專業(yè)的主干課程，其課程目標(biāo)必然與社會需求相適應(yīng)，與培養(yǎng)具有創(chuàng)新思維的高水平IT 工程師的需求相一致。所以，該課程不僅在于讓學(xué)生熟練掌握專業(yè)理論知識，更重要的是培養(yǎng)學(xué)生軟件設(shè)計(jì)能力和創(chuàng)新思維，為其后續(xù)完成的畢業(yè)設(shè)計(jì)和走向工作崗位服務(wù)國家科技行業(yè)奠定良好的基礎(chǔ)。

2 逆向?qū)嵺`教學(xué)設(shè)計(jì)案例

逆向設(shè)計(jì)的課程教學(xué)，不僅打通了實(shí)踐環(huán)節(jié)與理論課堂教學(xué)環(huán)節(jié)的關(guān)系，更加關(guān)注學(xué)生的應(yīng)用素質(zhì)能力的培養(yǎng)[3]。因?yàn)槠邢蓿F(xiàn)以最短路徑為例介紹實(shí)踐課程的逆向設(shè)計(jì)過程。

2.1 問題提出：幫“美團(tuán)騎手”找最快路線

當(dāng)我們在美團(tuán)網(wǎng)上點(diǎn)了一份外賣，美團(tuán)的快遞師傅接到訂單之后，就會借助百度地圖等工具找到最快的線路，爭取最快的速度送達(dá)到客戶手中，那百度地圖是怎樣找到最短路線的呢？

2.2 實(shí)驗(yàn)數(shù)據(jù)

選取濟(jì)南市山東大學(xué)周邊區(qū)域地圖，如圖1 所示。以千佛山風(fēng)景區(qū)為快遞出發(fā)點(diǎn)，以山東大學(xué)、濟(jì)南大學(xué)、濟(jì)南技師學(xué)院、濟(jì)南護(hù)理職業(yè)學(xué)院和濟(jì)南城市建設(shè)職業(yè)學(xué)院為運(yùn)送目的地。

圖1 濟(jì)南市部分地圖

2.3 數(shù)學(xué)模型

將圖中地點(diǎn)看做圖的頂點(diǎn)，把兩個地點(diǎn)的道路看做圖中的弧，把道路的長度看做弧上的權(quán)值，就為這個問題建立了一個數(shù)據(jù)模型——有向圖，如圖2 所示。美團(tuán)騎手找最短路線問題就轉(zhuǎn)換為在這個有向圖中從源點(diǎn)S 到其余各目標(biāo)點(diǎn)的單源點(diǎn)最短路徑問題。

圖2 有向圖

2.4 算法設(shè)計(jì)及關(guān)鍵問題

求單源點(diǎn)最短路徑問題采用著名的Dijkstra 算法[4-5]，算法思想為：

（1）初始化：將源點(diǎn)v0加到S 集合中；將v0到各個終點(diǎn)的最短路徑長度初始化為權(quán)值，即D[i]=G.arcs[v0][vi]；如果v0和頂點(diǎn)vi有弧，則將vi的前驅(qū)置為v0。在這一步中需要解決三個關(guān)鍵問題。

關(guān)鍵問題1：如何來表示S 集合？可以采用一維數(shù)組S[]，若置為true，表示該頂點(diǎn)屬于S 集合，false 屬于V-S 集合。

關(guān)鍵問題2：如何存放最短路徑的長度？可以采用一維數(shù)組dist[]來保存。其初值為：如果源點(diǎn)v0到vi有弧，則D[i]為弧上的權(quán)值，否則為∞。

關(guān)鍵問題3：如何存放最短路徑？可以采用一維數(shù)組path[]來保存前驅(qū)頂點(diǎn)。其初值為：如果源點(diǎn)v0到vi有弧，則path[i]為v0，否則為-1。

有向圖圖2 的輔助數(shù)組初始化情況，如表1 所示。

表1 輔助數(shù)組初始化

（2）在D[]中選擇最短路徑的終點(diǎn)vk，使得D[k]=Min{D[i]|vi∈V-S}。

（3）將vk加入到S 中，并置S[vk]=true。

（4）更新從v0出發(fā)到集合V-S 上任一頂點(diǎn)的最短路徑的長度，同時更改vi的前驅(qū)為vk。

若S[i]=false 且D[k]+G.arcs[k][i]

（5）重復(fù)（2）～（4）n-1 次，即可按照路徑長度的遞增順序，逐個求得從v0到其余各頂點(diǎn)的最短路徑。

有向圖圖2 在求解過程中各參量的變化如表2所示。

表2 求解過程中各參量的變化

2.5 Dijkstra算法的實(shí)現(xiàn)

程序分為三個模塊：一是輸入模塊，二是處理模塊，三是輸出模塊。下面給出Dijkstra 算法的實(shí)現(xiàn)部分。

2.6 實(shí)驗(yàn)的實(shí)際應(yīng)用和延伸

（1）一方面在物流運(yùn)輸中的應(yīng)用，隨著網(wǎng)絡(luò)購物的普及，物流逐漸興起，如何選擇距離最短或者時間最短的路徑成了物流關(guān)注的主要問題。因此，最短路徑算法的應(yīng)用與改進(jìn)是物流企業(yè)經(jīng)濟(jì)效益來源的主要因素之一。另一方面在日常出行中的應(yīng)用，在我們?nèi)粘３鲂兄幸呀?jīng)習(xí)慣應(yīng)用百度地圖或者汽車GPS 為我們選擇一條最優(yōu)路線，而最優(yōu)路線的選擇就是采用的最短路徑算法。另外，在房地產(chǎn)選址、城市公交系統(tǒng)、城市資源配置都有最短路徑算法的應(yīng)用。

（2）Dijkstra 算法是求靜態(tài)的單源點(diǎn)到各個頂點(diǎn)的最短路徑。而在一些對抗游戲如敵人或障礙物不斷移動的情況下，動態(tài)路徑的最短路徑是隨著外界環(huán)境不斷發(fā)生變化的，此時應(yīng)采用的D*算法，美國火星探測器采用的核心尋路算法就是采用的D*算法。

3 實(shí)踐內(nèi)容設(shè)計(jì)

為了提高學(xué)生的學(xué)習(xí)興趣增強(qiáng)社會實(shí)踐能力，設(shè)計(jì)了坡度型進(jìn)階實(shí)驗(yàn)。結(jié)合工程認(rèn)證要求構(gòu)建7 個知識點(diǎn)的實(shí)踐教學(xué)案例。主要分為基礎(chǔ)型實(shí)驗(yàn)和設(shè)計(jì)型實(shí)驗(yàn)。基礎(chǔ)型實(shí)驗(yàn)主要包括基本數(shù)據(jù)結(jié)構(gòu)以及基本算法的實(shí)現(xiàn)，屬于驗(yàn)證性實(shí)驗(yàn)，是學(xué)生必做實(shí)驗(yàn)。設(shè)計(jì)型實(shí)驗(yàn)是在基礎(chǔ)掌握之后，教師為了延伸實(shí)踐內(nèi)容，增加學(xué)習(xí)興趣，讓學(xué)生自行完成一個獨(dú)立的實(shí)際問題的實(shí)驗(yàn)。設(shè)計(jì)型實(shí)驗(yàn)難度較大，學(xué)生可以選擇性進(jìn)行分組設(shè)計(jì)。這種從易到難的實(shí)驗(yàn)設(shè)計(jì)，不僅鞏固了基礎(chǔ)知識，更讓學(xué)生看到了理論知識的實(shí)際應(yīng)用，培養(yǎng)了他們獨(dú)立分析問題解決問題的能力和嚴(yán)謹(jǐn)?shù)墓ぷ髯黠L(fēng)，為將來走向IT 工作崗位奠定良好的基礎(chǔ)。

為了更好地實(shí)施實(shí)驗(yàn)教學(xué)，我們編寫了數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)大綱、實(shí)驗(yàn)教材，定制了實(shí)驗(yàn)報(bào)告格式，充分利用浙江大學(xué)PTA 平臺。以社會實(shí)際問題和培養(yǎng)目標(biāo)為導(dǎo)向，從數(shù)據(jù)的邏輯結(jié)構(gòu)設(shè)計(jì)、物理結(jié)構(gòu)設(shè)計(jì)到算法的分析與實(shí)現(xiàn)，全面提升學(xué)生解決實(shí)際問題的能力。實(shí)驗(yàn)設(shè)計(jì)內(nèi)容如表3 所示。

表3 坡度型實(shí)驗(yàn)表

4 教學(xué)效果分析

以計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)17-1 班和18-1 班為分析數(shù)據(jù)，17 級為實(shí)驗(yàn)教學(xué)改進(jìn)前的班級，18 級為改進(jìn)后的班級。他們的卷面成績和實(shí)驗(yàn)成績分析如圖3、圖4 所示。從圖中可以看出，卷面成績和實(shí)驗(yàn)成績80 分以上均由42%提高到57%，成績大幅度提高。從實(shí)驗(yàn)課堂來看，低頭族越來越少，學(xué)生提問發(fā)言的次數(shù)增多，課堂比較活躍，學(xué)生學(xué)習(xí)興趣度大大提高。

圖3 卷面成績分析

圖4 實(shí)驗(yàn)成績分析

5 結(jié)語

在工程教育專業(yè)認(rèn)證的大背景下，如何設(shè)計(jì)教學(xué)環(huán)節(jié)以適應(yīng)社會發(fā)展的需要是每個教師必須要考慮的重要問題。本文以社會需求和培養(yǎng)目標(biāo)為導(dǎo)向，逆向設(shè)計(jì)了數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程的教學(xué)環(huán)節(jié)，給出了完整的實(shí)踐教學(xué)案例，取得良好的實(shí)踐效果，當(dāng)然也存在很多不足之處，例如案例的選擇是否典型、欠缺課程的監(jiān)管機(jī)制等，在以后的教學(xué)過程中將進(jìn)一步加以完善，使得教學(xué)成效螺旋上升。