基于工程認證的數據結構實踐逆向教學設計

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

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

0 引言

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

1 數據結構課程的培養(yǎng)目標

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

2 逆向實踐教學設計案例

逆向設計的課程教學，不僅打通了實踐環(huán)節(jié)與理論課堂教學環(huán)節(jié)的關系，更加關注學生的應用素質能力的培養(yǎng)[3]。因為篇幅有限，現以最短路徑為例介紹實踐課程的逆向設計過程。

2.1 問題提出：幫“美團騎手”找最快路線

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

2.2 實驗數據

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

圖1 濟南市部分地圖

2.3 數學模型

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

圖2 有向圖

2.4 算法設計及關鍵問題

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

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

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

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

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

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

表1 輔助數組初始化

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

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

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

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

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

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

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

2.5 Dijkstra算法的實現

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

2.6 實驗的實際應用和延伸

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

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

3 實踐內容設計

為了提高學生的學習興趣增強社會實踐能力，設計了坡度型進階實驗。結合工程認證要求構建7 個知識點的實踐教學案例。主要分為基礎型實驗和設計型實驗。基礎型實驗主要包括基本數據結構以及基本算法的實現，屬于驗證性實驗，是學生必做實驗。設計型實驗是在基礎掌握之后，教師為了延伸實踐內容，增加學習興趣，讓學生自行完成一個獨立的實際問題的實驗。設計型實驗難度較大，學生可以選擇性進行分組設計。這種從易到難的實驗設計，不僅鞏固了基礎知識，更讓學生看到了理論知識的實際應用，培養(yǎng)了他們獨立分析問題解決問題的能力和嚴謹的工作作風，為將來走向IT 工作崗位奠定良好的基礎。

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

表3 坡度型實驗表

4 教學效果分析

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

圖3 卷面成績分析

圖4 實驗成績分析

5 結語

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