“數(shù)據(jù)結(jié)構(gòu)”課程強化算法應用的教學實踐

王景珊

摘 要：“數(shù)據(jù)結(jié)構(gòu)”是計算機類專業(yè)的核心課程，學習內(nèi)容抽象難理解，理論教學與實際應用容易脫節(jié)，教學中應將抽象的數(shù)據(jù)類型與現(xiàn)實建立對應，加強學生對理論知識的感性認識。文章以Dijkstra算法和Floyd算法為例，分析強化算法應用的教學實踐，同時挖掘算法內(nèi)涵開展協(xié)同育人教學。

關(guān)鍵詞：算法應用;Dijkstra算法;Floyd算法;協(xié)同育人

0 引言

數(shù)據(jù)結(jié)構(gòu)是20世紀60年代提出并研究，20世紀70年代科學家Niklaus Wirth的著作《Algorithm+Data Structures=Programs》使得數(shù)據(jù)結(jié)構(gòu)研究不斷深入，20世紀80年代研究日臻成熟，成為一門完整的學科。它是一門介于數(shù)學、計算機軟件、計算機硬件之間的綜合學科，是程序設(shè)計的基礎(chǔ)。

在知識飛速更新的時代，提高學生獲得知識的能力，真正做到“授人以魚不如授人以漁”，是教師應盡的責任。作為一門理論和實踐并重的課程，理論教學講授算法思想，實踐教學實現(xiàn)由抽象到具體的過渡，將不同的數(shù)據(jù)結(jié)構(gòu)及算法，應用于不同的場景，并優(yōu)化算法，對提高學生的能力非常重要[1]。

1 分層教學的實施

教學中因材施教，合理進行分層次的教學是有必要的，可使不同層次的同學都能夠有所收獲，充分調(diào)動每個學生的積極性，提高程序設(shè)計能力和算法實現(xiàn)的能力，體驗成功的快樂。具體開展以下分層次教學。（1）教學內(nèi)容分層。根據(jù)教材內(nèi)容，總體分為兩個部分：一是基礎(chǔ)部分，算法相對簡單的內(nèi)容;二是提高部分，相對比較抽象，算法復雜。前一部分內(nèi)容所有同學都必須掌握，后一部分對學習能力強的同學有很大幫助。（2）課后作業(yè)分層。同樣分為基礎(chǔ)部分和提高部分，把需要完成的作業(yè)設(shè)置不同的難度系數(shù)，學生根據(jù)自己的實際能力完成不同難度系統(tǒng)的作業(yè)，這樣，在他們的能力范圍內(nèi)都有所提高，可增強學生的自信心。當然，不同的難度系數(shù)進行考核時其分值是不一樣的。（3）實踐項目分層。在項目實踐環(huán)節(jié)，依然是遵循力所能及的原則，而不是強求功能全、難度大的項目，只要同學們用心了，努力了就好[2]。

2 實踐教學環(huán)節(jié)的設(shè)計

“互聯(lián)網(wǎng)+”時代，積極探索改革教學模式，O2O混合式教學模式在本課程的實施中得以充分實現(xiàn)。無論線上線下，實踐教學都是由淺入深、由易到難，具體的過程由3步完成：（1）驗證性基礎(chǔ)實驗。教材中已給出的基本算法，比如，線性表的增、刪、改、查，二叉樹的生成、遍歷等，通過上機實踐，驗證其算法的結(jié)果，難度小，提高學生的學習興趣。（2）綜合性實驗。完成驗證性基礎(chǔ)實驗之后，掌握了一些基本的算法，為進一步提高學生的分析和應用的能力，要求學生完成一些綜合性的實驗，比如串的模式匹配算法，教材中一般是精確匹配，我們要求學生使用通配符模糊匹配。? ? ? ? ?（3）項目設(shè)計實驗。難度加大，完成一個相對完整的項目設(shè)計，提高綜合運用能力，培養(yǎng)學生的創(chuàng)新能力。選題的原則是實用，包含較多的知識點，學生可以根據(jù)自己的生活學習環(huán)境確定，比如，“學生成績管理軟件”不僅包含基本的增、刪、改、查，還要求有學生的成績統(tǒng)計與分析，基本滿足教務(wù)系統(tǒng)對學生成績的管理要求;“線下實體書店自助導購軟件”通過對圖書的管理，讓讀者能夠在一個大型實體書店迅速找到所需要的書籍[3]。

3 強化算法應用的教學案例

數(shù)據(jù)結(jié)構(gòu)是計算機科學的支柱，程序設(shè)計的基礎(chǔ)。教學中教師不能只停留在抽象的理論教學層面，一定要強化算法應用才是有效的。本文以最短路徑的Dijkstra算法和Floyd算法為例，分析強化算法應用的教學實踐。

3.1 將抽象的數(shù)據(jù)類型與現(xiàn)實建立對應

最短路徑是圖的最常見的應用之一，圖是一種典型的復雜多對多的非線性數(shù)據(jù)結(jié)構(gòu)。在講解這部分內(nèi)容之前，課前布置了預習任務(wù)，同學們通過各種線上線下資源，查閱資料，了解圖的應用，引導學生的學習興趣。通過查閱相關(guān)資料，就會發(fā)現(xiàn)圖的應用已經(jīng)滲入語言學、邏輯學、物理、化學、電信工程及計算機科學與數(shù)學學科的其他分支，當今最前沿的科技圖神經(jīng)網(wǎng)絡(luò)機器學習，都源于圖的應用。同學們感嘆，學好算法真的是大有用武之地。Dijkstra算法和Floyd算法就從大家生活中非常熟悉的導航系統(tǒng)導入。

3.2 最短路徑的概念

日常出行，選擇的是路程最短（通常路程與時間成正比）。如果路程較短的道路比較擁堵，需要花費較長時間，我們會選擇實際時間短的線路，有的可能考慮的是交通費用最少。交通的便利給人們帶來了更多的選擇。所以，首先明確最短路徑問題，不能狹義認為只是距離最短，可以是距離，可以是時間，也可以是其他，是解決關(guān)于有向帶權(quán)圖的問題。最短路徑問題有兩大類：第一，從某個源點到其余各頂點的最短路徑，用一維數(shù)組表示源點到其余各頂點的最短距離;第二，任意兩個頂點之間的最短距離，用二維數(shù)組表示任意兩個頂點之間的最短距離。

3.3? Dijkstra算法思想

Dijkstra是單源最短路徑算法，用于計算一個頂點（稱源點）到其他所有頂點的最短路徑。對于給定的有向網(wǎng)，把所有頂點分成兩組，第一組是已求出最短路徑的頂點集合S，其初值為源點（頂點v）;第二組是尚未確定最短路徑的頂點集合T（即V-S），T的初值包含除源點之外的所有頂點。具體步驟：① 假設(shè)用帶權(quán)的鄰接矩陣來表示有n個頂點的帶權(quán)有向圖。arcs[i][j]表示弧上的權(quán)值，若不存在，則為∞（表示時用INF），最短路徑長度（用dist[]表示）初值為dist[i]=arcs[v][i]。②從T集合中選擇w，使得dist[w]=MIN{dist[i]|Vi∈V-S}，就是當前求得的一條從v出發(fā)最短路徑的終點。從T集合中刪除w，并入S集合，令S=S∪{w}。③修改從v出發(fā)到T集合中各頂點的最短路徑長度。如果dist[w]+arcs[w][i]

3.4? Floyd算法思想

Floyd是求任意頂點對之間的最短路徑算法。在給定的有向網(wǎng)中，依然假定用帶權(quán)的鄰接矩陣來表示有n個頂點的帶權(quán)有向圖。初始狀態(tài)是，若存在，則存在一條長度為arcs[i][j]的路徑{vi，vj}，若不存在，則為∞（表示時用INF），最短路徑長度（用dist[]表示）初值為dist[i][j]=arcs[i][j]。因為該路徑不一定是最短路徑，然后進行n次試探，具體步驟如下。①首先試探從vi到vj是否有以頂點v1為中間點的路徑，若，存在，則有路徑{vi，v1，vj}，距離為，長度之和，與最初的最短距離比較，取較短者為當前最短路徑。②再添加頂點2為中間點，添加頂點3為中間點，……，依次類推，添加頂點n為中間點，每次添加后總是取路徑較短者為當前最短路徑，即在n次的試探過程中，如果存在一個k，使得dist[i][k]+dist[k][j]

在最短路徑的理論教學過程中，重點分析講解Dijkstra算法和Floyd算法的思想，再引導同學寫出相應的算法代碼，最后在實踐教學過程中完成一個功能較為完善的交通咨詢系統(tǒng)，交通網(wǎng)絡(luò)區(qū)域可以大，也可以小，但一定要使用實際數(shù)據(jù)，這樣才能把算法應用落實到實處。

3.5? 算法思想的協(xié)同育人教學

“數(shù)據(jù)結(jié)構(gòu)”課程蘊含著豐富的育人資源，正確引導學生，把樹立“中國夢”的理想與“專業(yè)夢”的規(guī)劃有效結(jié)合起來，挖掘算法的思想內(nèi)涵，開展協(xié)同育人教學。

學習了最短路徑的Dijkstra算法和Floyd算法之后，激發(fā)學生“時不我待、舍我其誰”的愛國熱情。圖神經(jīng)網(wǎng)絡(luò)是近年來倍受大家關(guān)注的前沿科技，AI是未來重要的發(fā)展方向，引導學生發(fā)現(xiàn)其中蘊含的機遇與挑戰(zhàn)，從而教育學生一定要有認真、仔細、嚴謹、求真、求實的學習態(tài)度，擔當起科技強國的使命和責任。

迪杰斯特拉（Dijkastra）算法，源點到其余各點最短距離路徑長度是按遞增順序一個一個求出，就像我們在人生路上必須求真務(wù)實，一步一步踏踏實實往前走，才能到達理想的彼岸，尋找屬于自己的最優(yōu)路徑。

4 結(jié)語

“數(shù)據(jù)結(jié)構(gòu)”課程的理論知識看似抽象枯燥，但其應用無處不在，加強算法應用的教學十分重要。新時代的教師要成為學生學習的引導者，不斷進行教學理論的研究，設(shè)計好每一個教學過程，體現(xiàn)以“教師為主導，學生為主體”的教學理念，同時牢記教書育人的職責，實現(xiàn)知識教育與價值教育的內(nèi)在契合，開展協(xié)同育人教學。

[參考文獻]

[1]霍清華.應用型人才培養(yǎng)下的數(shù)據(jù)結(jié)構(gòu)與算法課程改革[J].電腦知識與技術(shù)，2018（14）：209-210.

[2]嚴蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學出版社，2018.

[3]周蓓.數(shù)據(jù)結(jié)構(gòu)與算法（C語言版）[M].北京：清華大學出版社，2019.

（編輯 王雪芬）