“數(shù)據(jù)結(jié)構(gòu)”課程中算法可視化教學(xué)的探索與思考

摘? 要：“數(shù)據(jù)結(jié)構(gòu)”是計(jì)算機(jī)類專業(yè)的核心課程，算法是“數(shù)據(jù)結(jié)構(gòu)”課程中的重點(diǎn)和難點(diǎn)內(nèi)容。由于“數(shù)據(jù)結(jié)構(gòu)”課程一般在低年級(jí)開(kāi)設(shè)，學(xué)生接觸計(jì)算機(jī)相關(guān)的知識(shí)量還不夠多，在教學(xué)過(guò)程中，普遍反映算法抽象，難以理解和應(yīng)用。結(jié)合實(shí)際工作經(jīng)驗(yàn)，開(kāi)發(fā)和利用算法可視化工具，將排序、著色、最短路徑等算法用可視化工具實(shí)時(shí)、動(dòng)態(tài)展示出來(lái)，加深學(xué)生對(duì)算法的直觀認(rèn)識(shí)，可讓學(xué)生更好地理解和使用算法，并提升了教學(xué)效果。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu);算法可視化;教學(xué)方法

中圖分類號(hào)：TP311.12-4? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2019）23-0095-03

Exploration and Thinking of Algorithm Visualization

Teaching in “Data Structure” Course

WANG Han

（School of Mathematics and Computer Science，Guangdong Ocean University，Zhanjiang? 524088，China）

Abstract：“Data Structure” is the core course of computer major，and algorithm is the key and difficult content of “Data Structure” course. The course of “Data Structure” is generally offered in the junior grade，and the amount of knowledge related to computer is not enough. In the teaching process，it generally reflects the abstract algorithm，which is difficult to understand and apply. Combined with practical work experience，the algorithm visualization tools are developed and used to show the sorting，coloring，shortest path and other algorithms in real time and dynamically with the visualization tools，so as to improve students’intuitive understanding of the algorithm，make students better understand and use the algorithm，and improve the teaching effect.

Keywords：data structure;algorithm visualization;teaching methods

0? 引? 言

“數(shù)據(jù)結(jié)構(gòu)”既是計(jì)算機(jī)類專業(yè)的專業(yè)基礎(chǔ)課程，又是核心課程。這門(mén)課程在計(jì)算機(jī)的學(xué)科中起到了承上啟下的作用，既會(huì)為后續(xù)學(xué)習(xí)操作系統(tǒng)、算法分析與設(shè)計(jì)和軟件工程等課程打下良好的基礎(chǔ)，同時(shí)也對(duì)培養(yǎng)學(xué)生抽象思維能力、創(chuàng)作力和解決實(shí)際問(wèn)題的動(dòng)手操作能力起到一定的指導(dǎo)作用。但是該課程概念繁多、信息量大、抽象性強(qiáng)，一般在低年級(jí)開(kāi)設(shè)，學(xué)生剛開(kāi)始接觸計(jì)算機(jī)，相關(guān)的知識(shí)量還很小，所以在教學(xué)過(guò)程中，學(xué)生普遍反映算法抽象，很難理解。

由于算法過(guò)于抽象并且實(shí)踐性較強(qiáng)，造成學(xué)生難以直觀地學(xué)習(xí)和理解算法，以至于在對(duì)算法的學(xué)習(xí)和理解的過(guò)程中耗費(fèi)時(shí)間和精力過(guò)多，造成教學(xué)效率低、學(xué)生難以理解，以及理論和實(shí)際聯(lián)系不夠緊密，出現(xiàn)脫節(jié)等問(wèn)題。為了解決這一問(wèn)題，本文提出如何將復(fù)雜的事物轉(zhuǎn)化為直觀的圖像。利用可視化的方式，將算法所蘊(yùn)含的精髓內(nèi)容轉(zhuǎn)化成易于觀察的圖像進(jìn)行呈現(xiàn)，來(lái)幫助學(xué)生更好地理解和運(yùn)用算法。

1? 算法可視化教學(xué)方法

1.1? 算法可視化的需求與設(shè)計(jì)

對(duì)算法進(jìn)行可視化的原理是使用需要可視化的算法對(duì)輸入的數(shù)據(jù)進(jìn)行處理分析，然后根據(jù)需要選擇性地將算法執(zhí)行前、算法執(zhí)行過(guò)程中和算法執(zhí)行完畢后這三個(gè)階段中數(shù)據(jù)的變化進(jìn)行圖形化顯示，以供學(xué)生觀察、分析和理解算法。

算法可視化的架構(gòu)設(shè)計(jì)依托于其要實(shí)現(xiàn)的功能，因此，在了解了算法可視化的原理后，首先需要對(duì)算法可視化的需求進(jìn)行分析，確定所需要實(shí)現(xiàn)的內(nèi)容，隨后再根據(jù)需求分析的結(jié)果，對(duì)算法可視化進(jìn)行模塊劃分。

1.2? 算法可視化的結(jié)構(gòu)設(shè)計(jì)

根據(jù)算法可視化的流程，在對(duì)任何一個(gè)算法進(jìn)行可視化時(shí)，都可以采用MVP模式的結(jié)構(gòu)將其設(shè)計(jì)分為三層，分別是模型層（Model）、視圖層（View）、和控制層（Controller）。如圖1所示。

（1）模型層，也稱作數(shù)據(jù)層，主要負(fù)責(zé)存儲(chǔ)和處理用戶輸入的數(shù)據(jù)以及算法運(yùn)行過(guò)程中產(chǎn)生的中間數(shù)據(jù)，并將處理后的數(shù)據(jù)發(fā)送給視圖層。

（2）視圖層，負(fù)責(zé)顯示相關(guān)的運(yùn)行邏輯，主要負(fù)責(zé)將數(shù)據(jù)進(jìn)行處理轉(zhuǎn)化為圖像，并將圖像輸出到客戶端。

（3）控制層，在這里需要同時(shí)控制數(shù)據(jù)層和視圖層，起到傳遞消息和處理業(yè)務(wù)邏輯的作用。

1.3? 算法可視化系統(tǒng)模塊設(shè)計(jì)

根據(jù)算法可視化的類型，本文將可視化系統(tǒng)的模塊分為2個(gè)，分別是過(guò)程可視化模塊和概念可視化模塊。模塊之間相互獨(dú)立，互不影響，每個(gè)模塊都存在著其所屬類別的算法可視化程序。對(duì)此，算法可視化系統(tǒng)的模塊設(shè)計(jì)如圖2所示。

1.4? 算法演示界面的實(shí)現(xiàn)

系統(tǒng)界面是系統(tǒng)離用戶最近的地方。在技術(shù)快速發(fā)展的當(dāng)下，同一款產(chǎn)品，提供的功能差異不大時(shí)，哪一款產(chǎn)品界面設(shè)計(jì)得更友好，人們就會(huì)傾向于用哪一款。因此，界面設(shè)計(jì)得美觀與否，直接決定產(chǎn)品是否能夠得到用戶的認(rèn)可;除此之外，若界面設(shè)計(jì)得好，不用過(guò)多地引導(dǎo)用戶操作，用戶都會(huì)自己主動(dòng)去探索使用方法。

盡管根據(jù)算法的特點(diǎn)，本系統(tǒng)的界面可能會(huì)有所不同，但其原型都是一樣的。

1.5? 過(guò)程可視化模塊的實(shí)現(xiàn)

過(guò)程可視化模塊主要實(shí)現(xiàn)對(duì)算法程序的執(zhí)行流程，以及中間數(shù)據(jù)的變化用動(dòng)態(tài)圖像配合文字表現(xiàn)出來(lái)。過(guò)程可視化模塊中實(shí)現(xiàn)了過(guò)程可視化的算法分別是：冒泡排序、歸并排序、m著色問(wèn)題、Kruskal算法求最小生成樹(shù)和Dijkstra求最短路徑算法。

1.5.1? 冒泡排序法

冒泡排序算法是排序算法中最容易被理解的算法，其思路簡(jiǎn)單易懂，執(zhí)行過(guò)程中沒(méi)有太大的變化，因此可以直接采用動(dòng)畫(huà)的方式對(duì)冒泡排序的過(guò)程進(jìn)行可視化。

圖3為冒泡排序可視化過(guò)程中的一個(gè)關(guān)鍵幀，圖中黑色柱子是已排序好的數(shù)字，兩個(gè)框中的兩個(gè)柱體是正在相互比較的兩個(gè)數(shù)字，灰色則為未排序的數(shù)字。右側(cè)是交互按鈕和可視化程序執(zhí)行過(guò)程中數(shù)據(jù)的變化細(xì)節(jié)。

1.5.2? 歸并排序法

歸并排序使用了分而治之的設(shè)計(jì)理念，如圖4所示是插入排序的過(guò)程可視化示例圖，灰色柱狀圖是正在進(jìn)行歸并排序的動(dòng)畫(huà)，黑色柱狀圖則是由關(guān)鍵幀組成的靜態(tài)圖?？蛑械脑貫檎谂判虻脑兀溆酁榇判虻脑?。

1.5.3? m著色問(wèn)題

m著色問(wèn)題算法的實(shí)現(xiàn)思路大致為：

（1）把一個(gè)圖中的頂點(diǎn)按其角度大小依次減小的次序進(jìn)行排列;

（2）然后用第一種顏色對(duì)第一個(gè)點(diǎn)進(jìn)行上色，并且按照排列好的順序，將與之前的著色點(diǎn)不相鄰的每一點(diǎn)涂上同樣的顏色;

（3）把第二種顏色對(duì)尚未著色的點(diǎn)重復(fù)步驟2，用第三種顏色繼續(xù)，直到所有點(diǎn)全部上色為止。

m著色問(wèn)題的可視化同樣以動(dòng)畫(huà)的方式實(shí)現(xiàn)，不同的是，需要由用戶繪制圖的節(jié)點(diǎn)，然后連接成圖，之后再由對(duì)應(yīng)的程序?qū)著色的算法進(jìn)行可視化。圖5為m著色問(wèn)題算法演示動(dòng)畫(huà)過(guò)程中的其中一幀。

1.5.4? 最小生成樹(shù)（Kruskal算法）

Kruskal生成最小生成樹(shù)算法的可視化，以動(dòng)畫(huà)的方式實(shí)現(xiàn)。需要用戶手動(dòng)繪制一個(gè)圖，之后再由系統(tǒng)程序使用Kruskal算法生成最小生成樹(shù)。圖6為Kruskal算法在演示動(dòng)畫(huà)過(guò)程中的其中一幀。

1.5.5? 最短路徑（Dijkstra算法）

最短路徑Dijkstra算法的可視化，以動(dòng)畫(huà)的形式實(shí)現(xiàn)。需要用戶手動(dòng)繪制一個(gè)圖，之后再由系統(tǒng)程序使用Dijkstra算法生成求出最短路徑的演示動(dòng)畫(huà)。圖7為Dijkstra算法在可視化過(guò)程中的其中一幀。

2? 結(jié)? 論

本文針對(duì)當(dāng)前“數(shù)據(jù)結(jié)構(gòu)”教學(xué)過(guò)程中存在的問(wèn)題，結(jié)合多年的理論教學(xué)經(jīng)驗(yàn)，進(jìn)行教學(xué)改革與探索，開(kāi)發(fā)和利用算法可視化工具，針對(duì)不同算法將其實(shí)時(shí)、動(dòng)態(tài)地展示出來(lái)，以加深學(xué)生對(duì)算法的直觀認(rèn)識(shí)，讓學(xué)生能夠更好地理解和運(yùn)用算法，為教師進(jìn)一步提高課堂教學(xué)效率和教學(xué)水平提供了參考。

參考文獻(xiàn)：

[1] 郭伊.《數(shù)據(jù)結(jié)構(gòu)》課程教學(xué)動(dòng)態(tài)演示系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn) [D].楊凌：西北農(nóng)林科技大學(xué)，2015.

[2] 劉叢.針對(duì)數(shù)據(jù)結(jié)構(gòu)的命令式算法可視化系統(tǒng)設(shè)計(jì)與開(kāi)發(fā) [D].長(zhǎng)沙：湖南大學(xué)，2015.

[3] 熊慧.jQuery技術(shù)在網(wǎng)頁(yè)美工中的應(yīng)用 [J].中國(guó)新通信，2018，20（6）：100.

[4] MCCORMICK H B. Visualization in scientific computing [J].ACM SIGBIO Newsletter，1988，10（1）：15-21.

作者簡(jiǎn)介：王晗（1976.04-），女，漢族，陜西西安人，中級(jí)職稱，本科，研究方向：計(jì)算機(jī)及其應(yīng)用。