“數據結構”課程中算法可視化教學的探索與思考

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

關鍵詞：數據結構;算法可視化;教學方法

中圖分類號：TP311.12-4? ? ? 文獻標識碼：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? 引? 言

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

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

1? 算法可視化教學方法

1.1? 算法可視化的需求與設計

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

算法可視化的架構設計依托于其要實現的功能，因此，在了解了算法可視化的原理后，首先需要對算法可視化的需求進行分析，確定所需要實現的內容，隨后再根據需求分析的結果，對算法可視化進行模塊劃分。

1.2? 算法可視化的結構設計

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

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

（2）視圖層，負責顯示相關的運行邏輯，主要負責將數據進行處理轉化為圖像，并將圖像輸出到客戶端。

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

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

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

1.4? 算法演示界面的實現

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

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

1.5? 過程可視化模塊的實現

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

1.5.1? 冒泡排序法

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

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

1.5.2? 歸并排序法

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

1.5.3? m著色問題

m著色問題算法的實現思路大致為：

（1）把一個圖中的頂點按其角度大小依次減小的次序進行排列;

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

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

m著色問題的可視化同樣以動畫的方式實現，不同的是，需要由用戶繪制圖的節(jié)點，然后連接成圖，之后再由對應的程序對m著色的算法進行可視化。圖5為m著色問題算法演示動畫過程中的其中一幀。

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

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

1.5.5? 最短路徑（Dijkstra算法）

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

2? 結? 論

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

參考文獻：

[1] 郭伊.《數據結構》課程教學動態(tài)演示系統(tǒng)的設計與實現 [D].楊凌：西北農林科技大學，2015.

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

[3] 熊慧.jQuery技術在網頁美工中的應用 [J].中國新通信，2018，20（6）：100.

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

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