數(shù)據(jù)結(jié)構(gòu)中圖論算法動態(tài)智能演示的研究

程彩鳳+林德樹

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

關(guān)鍵詞： 數(shù)據(jù)結(jié)構(gòu)； 圖論算法； 動態(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

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

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

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

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

1.1 軟件體系結(jié)構(gòu)

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

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

1.2 功能模塊

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

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

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

1.3 界面設(shè)計

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

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

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

2.1 相關(guān)技術(shù)背景

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

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

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

2.2 算法演示模塊

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

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

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

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

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

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

3 結(jié) 論

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

參考文獻

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

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

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

[4] 連遠峰.基于MFC的可視化數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2014.

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

[6] CORMEN T H， LEISERSON C E， RIVEST R L， et al.算法導(dǎo)論[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] 嚴蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：人民郵電出版社，2015.

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

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

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