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

王景珊

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

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

0 引言

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

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

1 分層教學(xué)的實(shí)施

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

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

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

3 強(qiáng)化算法應(yīng)用的教學(xué)案例

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

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

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

3.2 最短路徑的概念

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

3.3? Dijkstra算法思想

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

3.4? Floyd算法思想

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

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

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

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

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

迪杰斯特拉（Dijkastra）算法，源點(diǎn)到其余各點(diǎn)最短距離路徑長(zhǎng)度是按遞增順序一個(gè)一個(gè)求出，就像我們?cè)谌松飞媳仨毲笳鎰?wù)實(shí)，一步一步踏踏實(shí)實(shí)往前走，才能到達(dá)理想的彼岸，尋找屬于自己的最優(yōu)路徑。

4 結(jié)語(yǔ)

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

[參考文獻(xiàn)]

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

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

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

（編輯 王雪芬）