程彩鳳+林德樹

摘 要： 數據結構課程中圖論算法抽象復雜，傳統(tǒng)的板書或PPT演示算法程序語句的教學方法不利于學生理解和掌握。在Visual Studio 2013環(huán)境下，基于MFC平臺研究并設計了一款數據結構課程關于圖論算法動態(tài)智能演示的教學輔助軟件。動態(tài)演示了包括圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法，求最小生成樹的Prim算法和Kruskal算法，最短路徑Dijkastra算法和Floyd算法的執(zhí)行過程。軟件界面簡潔美觀，操作簡單友好，算法執(zhí)行過程一目了然，圖形界面與算法流程、算法數據信息同步顯示。

關鍵詞： 數據結構； 圖論算法； 動態(tài)演示； MFC； CAI

中圖分類號： TN915.5?34； TP39 文獻標識碼： A 文章編號： 1004?373X（2017）18?0040?03

Research on dynamic intelligent demonstration of graph?theoretical

algorithm in data structure

CHENG Caifeng1， LIN Deshu2

（1. College of engineering and technology， Yangtze University， Jingzhou 434020， China；

2. College of Computer Science， Yangtze University， Jingzhou 434023， China）

Abstract： The graph?theoretical algorithm in data structure course is complex. The teaching method of traditional blackboard?writing or algorithm program statements of PPT demonstration is not conducive to the students to understand and master. With the Visual Studio 2013， a teaching assistant software about the graph theory algorithms dynamic intelligent demonstration was designed on the basis of MFC platform. The dynamic intelligent demonstration includes the executing process of the depth?first traversal and the breadth?first traversal algorithm， Prim algorithm and Kruskal algorithm for deriving the minimum spanning tree， and the shortest path Dijkastra algorithm and Floyd algorithm. The software interface is concise and artistic， and its operation is simple and friendly. The executing process of the algorithm is clear at a glance. The graphical interface is synchronically displayed with algorithm flow and algorithm data information.

Keywords： data structure； graph?theoretical algorithm； dynamic demonstration； MFC； CAI

計算機輔助教學（CAI）是目前計算機應用領域的一個新內容，是一種新型的現(xiàn)代化教學手段，也是當前教學手段改革的主要趨勢[1]。

數據結構課程中圖問題始終滲透整個計算機科學，應用非常廣泛。圖論可以應用于電路網絡分析、運籌學、計算機網絡、信息論、控制論等各個領域[2]。而該課程涉及大量深奧、抽象的概念和算法，特別是圖中經典算法的思想涉及到很多遞歸算法，其執(zhí)行過程更為抽象難懂。目前在大多數高校對于算法內容的教學方式，主要以教師板書和PPT演示算法語句為主，沒有將算法在實驗中驗證，這樣的教學方式更增加了學生學習的難度。與這種傳統(tǒng)的教學方法相比，算法動態(tài)智能演示解決了上述問題，它主要是利用可視化技術和多媒體工具，以生動直觀的畫面顯示方式輔助數據結構課程的教學，能夠提高教學效率，有利于培養(yǎng)學生動手實踐的能力、學習和科研的能力[3]。

1 動態(tài)智能演示軟件的總體設計

軟件設計的目的是實現(xiàn)一個動態(tài)智能演示深度優(yōu)先遍歷、廣度優(yōu)先遍歷、最小生成樹和最短路徑問題算法的教學輔助系統(tǒng)，從而幫助學生輕松直觀地學習各種算法。因此簡潔美觀的界面、簡單方便的操作及一目了然的執(zhí)行過程是非常必要的。

1.1 軟件體系結構

數據結構算法的可視化主要是對數據結構的圖形再現(xiàn)，也就是在數據結構變動的同時，圖形界面也要做出同步的變化，進而也就確定了兩者之間的關系，非耦合但在變化邏輯上相關?？紤]到工程量，采用迭代式開發(fā)，整體上就可以分為三層：實體層、算法功能層、圖形繪制層。

在MFC窗體上進行繪制圖形有兩種方案可供選擇，一種是使用文檔視圖類結構，另一種是直接使用對話框類結構；文檔視圖類結構方便文檔的讀取、保存和查看，且架構清晰[4]。但考慮到軟件實際需求無需保存、與文件無關，所以使用更為簡潔的對話框結構，直接在對話框上進行繪制圖形，消除冗余的文檔視圖類結構，簡化軟件的開發(fā)過程。endprint

1.2 功能模塊

功能模塊主要包括算法介紹和算法演示兩部分：

（1） 算法介紹。主要介紹深度優(yōu)先遍歷、廣度優(yōu)先遍歷算法、Prim算法、Kruskal算法、Dijkastra算法和Floyd算法。

（2） 算法演示。通過具體實例，動態(tài)演示圖的遍歷問題、最小生成樹問題及最短路徑問題的相關算法的執(zhí)行過程和運算結果，以及算法的一些核心操作步驟。

1.3 界面設計

為了程序的清晰和方便管理，采用一個

主對話框作為基本容器，里面可以容納各種算法需要的控件，使用一個tab控件來容納三個無邊框子對話框來作為繪制區(qū)，三個繪制區(qū)相互隔離，功能也相互隔離，方便單個處理和顯示，在主對話框上有著公共的數據控件，三個子對話框通過主對話框指針來各自輸出自己的信息，互不干擾。

2 系統(tǒng)功能模塊的具體實現(xiàn)

2.1 相關技術背景

（1） MFC的GDI類庫[4]。在VS平臺下，借助MFC庫來快速實現(xiàn)Windows窗體上的無向帶權圖的動態(tài)可視化與可交互化，在圖節(jié)點中加入坐標屬性并利用Windows的GDI對象完成可視化，利用強制刷新無效窗口區(qū)域和內存雙緩沖繪圖的原理完成圖的遍歷、最小生成樹、單源最短路徑的動態(tài)生成。

（2） 多線程同步[5]。在軟件演示系統(tǒng)中，為了實現(xiàn)代碼段執(zhí)行的動態(tài)效果和圖形演示動畫同步進行，可以隨時運行和暫停動態(tài)效果，需用到多線程的同步。使得最終運行效果達到圖形界面與算法流程、算法數據信息同步，算法速度可調整、可中斷。

（3） 數據交互。在演示系統(tǒng)中，為了實現(xiàn)人機交互，主要是解決操作者對對象的操作以及該操作能被對象所識別，需要借助鼠標點擊的坐標位置判斷操作者的操作是落在哪個對象的可視范圍內，進而確定操作對象。然后對象反應出相應的操作結果，此結果的產生期間，數據結構與圖形界面的變化是同步的，并有相應的數據信息輸出可供操作者理解算法的流程和步驟。實現(xiàn)方法是使用鼠標右鍵點擊區(qū)域定位和右鍵菜單來實現(xiàn)節(jié)點和邊的交互。

2.2 算法演示模塊

算法演示程序主要采用MFC庫圖對話框來實現(xiàn)算法可視化，主要負責對圖中的節(jié)點、邊及權值進行插入、刪除和更新。在繪制圖形方面，主要算法函數分為界面輔助類算法、圖論算法函數及算法輔助函數、信息輸出函數。相關算法函數的設計如圖1所示。

（1） 深度優(yōu)先遍歷算法。從鼠標右鍵選定的節(jié)點開始訪問當前節(jié)點，然后深度優(yōu)先訪問其鄰接節(jié)點，并設置訪問標識，在圖形界面上就對此節(jié)點進行著色以表示被訪問過，直到當前節(jié)點的相鄰節(jié)點均已被訪問過則退出函數，向上一層回溯。算法程序運行截圖如圖2所示。動態(tài)演示過程中在右側數據顯示區(qū)域動態(tài)顯示遍歷的各節(jié)點值，遍歷結束后在信息輸出區(qū)顯示狀態(tài)及最終遍歷的序列列表。

（2） 廣度優(yōu)先遍歷算法。從鼠標右鍵選定的節(jié)點開始每次訪問一個節(jié)點前先將節(jié)點入隊，然后將隊頭元素出隊，進行訪問著色和設置訪問標識位，然后再將與此節(jié)點相鄰的未被訪問過的節(jié)點入隊，然后再進行循環(huán)操作[6]。算法程序運行截圖如圖3所示。

（3） Prim算法函數。Prim算法對連通圖生成一個最小生成樹，先選擇一個起點節(jié)點，每次選擇與當前最小生成樹相鄰的節(jié)點中權值最小的點加入最小生成樹中，直到所有節(jié)點都被加入生成樹中為止[2，6]。由于采用的是鏈表結構存儲圖，所以圖的節(jié)點可以動態(tài)變化，靈活性很強，但是在進行此類算法時，使用鏈表效率會稍稍降低，不能像矩陣那樣進行隨機存儲和讀取[7]。

在這個算法內部要用到兩個容器，一個是節(jié)點容器，用來保存最小生成樹的節(jié)點指針，另一個是邊容器，用來保存最小生成樹的邊指針[8?9]。最開始是將選定節(jié)點加入最小生成樹的節(jié)點容器中，然后對其進行訪問和著色。接下來，從節(jié)點容器中進行遍歷，找出各個節(jié)點相鄰未訪問過的節(jié)點中邊權值最小的一個，然后將這個節(jié)點和連接此節(jié)點的邊加入容器中去，并進行訪問和著色。算法程序運行截圖如圖4所示。

（4） Dijkastra算法函數。加入一個鏈表轉矩陣的函數，將現(xiàn)有的鏈表結構轉換成相應的矩陣存儲形式，然后對矩陣執(zhí)行算法，還要加入一個處理矩陣和鏈表對應關系的函數，即根據索引獲取節(jié)點指針和根據指針獲取節(jié)點索引函數[10?11]。算法執(zhí)行完畢后輸出路徑向量和距離向量中的值。算法程序運行截圖如圖5所示。在右側數據顯示區(qū)域動態(tài)顯示算法執(zhí)行過程中源點到各節(jié)點的距離。

3 結 論

針對目前數據結構中圖算法實現(xiàn)過程可視化的問題，在分析圖論遍歷問題、生成樹問題和最短路徑問題算法的概念和原理的基礎上，提出了一種基于MFC的動態(tài)繪制圖形的方法，能智能動態(tài)地演示圖論復雜的算法執(zhí)行過程。通過軟件實驗演示，使用該教學輔助軟件改進了原有的板書、PPT演示文稿的教學模式，降低了教師的講解難度，增加了學生的興趣，提高了教學效率。結果驗證了動態(tài)智能演示軟件的有效性和實用性。程序中采用的算法具有高效性、可行性，設計的動態(tài)智能演示軟件能滿足數據結構課堂演示的要求。

參考文獻

[1] 徐新黎，胡磊.智能搜索算法在線教學實驗平臺的設計與實現(xiàn)[J].實驗技術與管理，2012，29（5）：112?117.

[2] 周忠玉，方歡，方賢文.圖論最短路徑算法的圖形化演示及系統(tǒng)設計[J].電腦知識與技術，2016，12（18）：159?160.

[3] 趙靜.算法演示在“數據結構”課程教學中的應用探討[J].黑龍江生態(tài)工程職業(yè)學院學報，2010（1）：109?110.

[4] 連遠峰.基于MFC的可視化數據結構[M].北京：清華大學出版社，2014.

[5] 曹偉，劉風華，陳秋平.VC++環(huán)境下數據結構演示系統(tǒng)開發(fā)[J].科協(xié)論壇，2010（2）：54?55.

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al.算法導論[M].王剛，鄒恒明，殷建平，等譯.3版.北京：機械工業(yè)出版社，2013：362?391.

[7] WEISS M A. Data structures and algorithm analysis in C++ [M]. 3rd ed. BeiJing： Posts & Telecom Press， 2015.

[8] DROZDEK Adam. Data structures and algorithms in C++ [M]. 2nd ed. Beijing： Tsinghua University Press， 2003： 340?349.

[9] 嚴蔚敏，李冬梅，吳偉民.數據結構（C語言版）[M].北京：人民郵電出版社，2015.

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

[11] 王玢玥，李冬梅，李華穎，等.數據結構算法演示系統(tǒng)的設計[J].教育教學論壇，2016（28）：167?168.

[12] 李一春，王效東.兩種UHF RFID標準標簽數據結構差異對讀寫器設計的影響[J].物聯(lián)網技術，2014，4（10）：15?16.endprint