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

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

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

中圖分類號：TP311.12-4? ? ? 文獻(xiàn)標(biāo)識碼：A 文章編號：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ī)類專業(yè)的專業(yè)基礎(chǔ)課程，又是核心課程。這門課程在計算機(jī)的學(xué)科中起到了承上啟下的作用，既會為后續(xù)學(xué)習(xí)操作系統(tǒng)、算法分析與設(shè)計和軟件工程等課程打下良好的基礎(chǔ)，同時也對培養(yǎng)學(xué)生抽象思維能力、創(chuàng)作力和解決實(shí)際問題的動手操作能力起到一定的指導(dǎo)作用。但是該課程概念繁多、信息量大、抽象性強(qiáng)，一般在低年級開設(shè)，學(xué)生剛開始接觸計算機(jī)，相關(guān)的知識量還很小，所以在教學(xué)過程中，學(xué)生普遍反映算法抽象，很難理解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.5.1? 冒泡排序法

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

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

1.5.2? 歸并排序法

歸并排序使用了分而治之的設(shè)計理念，如圖4所示是插入排序的過程可視化示例圖，灰色柱狀圖是正在進(jìn)行歸并排序的動畫，黑色柱狀圖則是由關(guān)鍵幀組成的靜態(tài)圖。框中的元素為正在排序的元素，其余為待排序的元素。

1.5.3? m著色問題

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

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

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

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

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

1.5.4? 最小生成樹（Kruskal算法）

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

1.5.5? 最短路徑（Dijkstra算法）

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

2? 結(jié)? 論

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

參考文獻(xiàn)：

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

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

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

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

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