基于Qt的算法可視化框架的設(shè)計*

余　雨　廖　濤　高文勝　李夢濤

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院　淮南　232000)

?

基于Qt的算法可視化框架的設(shè)計*

余雨廖濤高文勝李夢濤

(安徽理工大學(xué)計算機科學(xué)與工程學(xué)院淮南232000)

摘要隨著計算機技術(shù)的飛速發(fā)展和普及，傳統(tǒng)的算法教學(xué)模式已經(jīng)不再適合學(xué)生學(xué)習(xí)比較抽象的算法了。多媒體教學(xué)憑借其自身在教學(xué)方面的優(yōu)勢而在基礎(chǔ)教育中迅速發(fā)展，相對粉筆加黑板的原始教學(xué)，多媒體教學(xué)的優(yōu)勢有以下幾點：程序的執(zhí)行過程更加生動便捷；數(shù)據(jù)演變更加形象直觀；教學(xué)的時間成本和金錢成本都相對較低等；此外，它的靈活性、隨機性以及全方位和立體化的信息展示形式對教育環(huán)境優(yōu)化、提高教學(xué)質(zhì)量起到了極大的作用。論文提出了一種基于Qt的算法可視化框架，利用該框架可以實現(xiàn)算法可視化的開發(fā)。

關(guān)鍵詞算法教學(xué)； 可視化算法框架； Qt

Class NumberTP311

1　引言

在計算機能力的培養(yǎng)中，算法是學(xué)生進行學(xué)習(xí)的一個主要內(nèi)容，算法是一個程序的靈魂，一個好的算法不僅節(jié)約時間、空間還能提高系統(tǒng)的穩(wěn)定性。因此算法在計算機教學(xué)中占有舉足輕重的地位，但同時因為算法的抽象性使學(xué)生難以理解，嚴重影響了學(xué)生的學(xué)習(xí)興趣[1]。算法可視化教學(xué)是一種全新的教學(xué)形式，它以計算機輔助多媒體作為基礎(chǔ)，將抽象復(fù)雜的算法程序通過可視化展現(xiàn)給學(xué)習(xí)者從而起到激發(fā)學(xué)習(xí)者的創(chuàng)造性思維[2]，這種模式在西方發(fā)達國家已經(jīng)取得成功。將學(xué)生從傳統(tǒng)的黑板教學(xué)中解放出來，使學(xué)生的理解力和創(chuàng)新能力得到升華[3]。

本文提出設(shè)計一種基于Qt的算法可視化框架，此框架利用了Qt的強大的GUI和動畫處理功能[4]，可以在此框架的基礎(chǔ)上進行算法可視化軟件的開發(fā)，將復(fù)雜枯燥的算法進行可視化模擬。

2　框架總體設(shè)計思想

本框架設(shè)計工作主要由以下兩部分構(gòu)成： 1) 前期算法的收集和分類。 2) 算法的可視化框架搭建。

2.1算法的收集和分類

算法的收集和分類是進行框架設(shè)計的前期準(zhǔn)備工作，在計算機中算法的種類復(fù)雜繁多，前期需要對算法的種類進行分析估計，然后對算法的共性進行提取，對于不同部分進行抽象化[5]，從而可以給不同的算法提供一個統(tǒng)一的接口調(diào)用。目前該框架主要支持的是數(shù)據(jù)結(jié)構(gòu)教學(xué)和算法教學(xué)中一些基本的排序以及樹的遍歷算法[6]。所以先要對這兩類教學(xué)中常用的算法進行收集整理并加以分析，然后在此基礎(chǔ)上進行接口化工作。

2.2算法可視化框架的搭建

本系統(tǒng)所實現(xiàn)的可視化框架主要由四部分組成，它們分別是算法抽象結(jié)構(gòu)體、演示視圖、演示元素轉(zhuǎn)換、動畫操作。

2.2.1算法抽象結(jié)構(gòu)體

算法抽象結(jié)構(gòu)體中實現(xiàn)了對不同算法的提供了一個統(tǒng)一的接口，通過該接口屏蔽了操作不同算法的實現(xiàn)細節(jié)，再添加新的算法不會影響整體框架的變動。在算法抽象結(jié)構(gòu)體中包含了算法的兩類存儲結(jié)構(gòu)，鏈?zhǔn)饺鐖D1和樹形結(jié)構(gòu)如圖2。

圖1　鏈?zhǔn)浇Y(jié)構(gòu)呈現(xiàn)方式圖

圖2　樹形結(jié)構(gòu)呈現(xiàn)方式圖

2.2.2演示視圖

演示視圖是基于Qt的圖形視圖框架，該框架提供一個surface來實現(xiàn)對大陸的圖形項進行管理操作，提供了三個體系架構(gòu)場景、視圖和圖形項。本框架的演示視圖正是在此基礎(chǔ)上進行封裝，框架每次演示之前，將先創(chuàng)建一個視圖，視圖中包含的就是進行演示的區(qū)域，同時將一個場景綁定到視圖，因為場景提供了一個對大量圖形項進行操作的接口，所以框架就可以同時對算法中大量的圖形項進行操作。該部分最主要的問題就是怎樣把算法演示的數(shù)據(jù)轉(zhuǎn)換為Qt視圖中所支持的圖形項，這樣每一個元素其實轉(zhuǎn)換之后就對應(yīng)于一個圖像元素，軟件在模擬算法的時候就對該元素進行操作，反映到界面上也就是每個圖形元素的操作。

2.2.3演示元素轉(zhuǎn)換

演示元素轉(zhuǎn)換是針對需要進行算法演示的數(shù)據(jù)對象，將數(shù)據(jù)對象轉(zhuǎn)換為圖形添加到場景中。算法對數(shù)據(jù)的操作反映到演示中的是演示元素的動畫[7]。演示開始將先開辟一個場景空間，對場景的寬度和高度進行設(shè)置。因為本框架支持兩種算法存儲結(jié)構(gòu)，所以在開辟兩個數(shù)據(jù)元素空間，保存到QMap容器中，該容器可以提供key和value存儲方式，在該框架中保持的就是數(shù)據(jù)項對應(yīng)的圖形項。然后遍歷所有的圖形項，讓其在界面顯示。本框架對圖形項的另一個主要的操作就是數(shù)據(jù)改變反映到視圖中就是圖像項的改變，這里主要通過將原始數(shù)據(jù)經(jīng)過算法處理之后，再將每一步的變化結(jié)果保存到QMap中。然后再對QMap進行遍歷，從而實現(xiàn)算法的動態(tài)模擬。

2.2.4動畫操作

框架對Qt原有的動畫操作進行封裝，在對不同的算法進行演示的時候可以使用同一套動畫方案。所有的動畫操作均是針對不同算法的公共演示操作。例如：元素平移、交換、添加等動畫操作。動畫操作其最主要的就是將要進行操作的動畫添加到QParallelAnimationGroup中，然后設(shè)置該動畫所需要播放的時間，開始位置以及結(jié)束的位置，之后調(diào)用start()就可以保持演示動畫的并行運行。另外Qt還提供了眾多的動畫屬性設(shè)置，可以呈現(xiàn)豐富的動畫效果，Qt中有個動畫操作的類[8]如表1所示。

表1　Qt動畫框架類

3　框架待優(yōu)化方面

計算機中的算法是多種多樣的，而且算法的復(fù)雜度也不盡相同，為了加深學(xué)生對算法的理解，這樣就必須使學(xué)生能夠自己調(diào)試演示程序或者通過編寫自己的算法演示程序。這樣框架中就必須加入編譯調(diào)試單元，對于學(xué)生自己輸入的算法進行編

譯顯示，讓軟件更加智能化。另外還可以考慮加入提問機制[9]，使學(xué)生在進行算法演示的時候系統(tǒng)可以根據(jù)學(xué)生的的情況來提出和該算法相關(guān)的問題[10]，從而更能幫助學(xué)生對算法的深度理解。

4　結(jié)語

本框架為算法可視化教學(xué)研究中的一次全新探索，隨著可視化教學(xué)輔助系統(tǒng)的不斷發(fā)展，促使在算法設(shè)計等專業(yè)基礎(chǔ)課程體系的教學(xué)中增加了新的教學(xué)手段。本框架結(jié)合目前先進的GUI庫，利用其強大的圖形顯示能力，進一步探索開發(fā)，力求通過該框架開發(fā)出簡便、高效的算法可視化系統(tǒng)，在傳統(tǒng)的算法教學(xué)中融入可視化教學(xué)，使得學(xué)生從枯燥乏味的算法中解脫出來，提高了學(xué)生的學(xué)習(xí)興趣，也提高了教學(xué)的趣味性和實用性[11]。初步通過該框架設(shè)計的系統(tǒng)較為令人滿意，在今后的優(yōu)化和修改中將繼續(xù)對該框架進行完善。

參 考 文 獻

[1] 劉亞琴.基于三層結(jié)構(gòu)模型的算法可視化教學(xué)研究與實踐[D].長沙:湖南師范大學(xué),2007.

LIU Yaqin. Research and practice of visual teaching based on the three layer structure model[D]. Changsha: Hunan Normal University,2007.

[2] 李曉鴻,劉叢,駱嘉偉.面向計算思維訓(xùn)練的算法可視化教學(xué)系統(tǒng)研究[J].計算機教育,2014(21):78-81.

LI Xiaohong, LIU Cong, LUO Jiawei. Research on the visual teaching system for computing oriented thinking training[J]. Computer Education,2014(21):78-81.

[3] W. Pierson, S. Rodger. Web-based animation of data structures using JAWAA[C]//Proceedings of the 29th SIGCSE Technical Symposium on Computer Science Education, Atlanta, GA, USA, ACM,1998:267-271.

[4] 霍亞飛.Qt及Qt Quick開發(fā)實戰(zhàn)精解[M].北京:北京航空航天大學(xué)出版社,2012:202-224.

HUO Yafei. Qt and Qt Quick development of combat[M]. Beijing: Beihang University Press,2012:202-224.

[5] 楊政,王強.算法圖形演示框架構(gòu)建方案研究[J].科技信息(學(xué)術(shù)研究),2007,20:092.

YANG Zheng, WANG Qiang. Research on the construction scheme of the algorithm graphic demonstration frame[J]. Scientific and Technological Information(Academic Research),2007,20:092.

[6] 孫凌宇,冷明,郭愷強,等.計算機算法知識領(lǐng)域的計算過程可視化教學(xué)研究[J].高等財經(jīng)教育研究,2014,4(S1):6-8.

SUN Lingyu, LENG Ming, GUO Kaiqiang, et al. Research on Visualization Teaching of computer algorithm in the field of computing algorithm[J]. Research on Higher Education of Finance and Economics,2014,4(S1):6-8.

[7] Reif I, Orehovacki T. ViSA: Visualization of sorting algorithms[C]//MIPRO, 2012 Proceedings of the 35th International Convention. IEEE,2012:1146-1151.

[8] 霍亞飛.Qt Creator快速入門[M].北京:北京航空航天大學(xué)出版社,2012:243-282.

HUO Yafei. Qt Creator quick start[M]. Beijing: Beihang University Press,2012:243-282.

[9] Wong Y F, Sideris A. Learning convergence in cerebellar model articulation controller[J]. IEEE Trans on Neural Networks,1992,3(1):115-121.

[10] Choristos Foutsitzis, Stavros Demetriadis. AlCoLab. Architecture of Algorithm Visualization System[D]. Thessaloniki: Aristotle University of Thessaloniki,2008:172-174.

[11] 趙慧臣,王淑艷.知識可視化應(yīng)用于學(xué)科教學(xué)的新觀點[J].開放教育研究,2014,20(2):4-10.

ZHAO Huicheng, WANG Shuyan. Knowledge visualization applied to new perspectives of subject teaching[J]. Open Education Research,2014,20(2):4-10.

收稿日期:2015年10月9日,修回日期:2015年11月27日

基金項目:安徽理工大學(xué)大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目(編號：AH201410361068)；安徽理工大學(xué)2013年度校級重大教學(xué)改革研究項目“多媒體教學(xué)中算法可視化交互式教學(xué)的研究和實現(xiàn)”資助。

作者簡介:余雨，女，碩士研究生，研究方向：軟件編程、人工智能、物聯(lián)網(wǎng)技術(shù)。廖濤，男，博士，副教授，研究方向：Web數(shù)據(jù)挖掘、人工智能。高文勝，男，碩士，研究方向：人工智能、智能信息處理、軟件編程。李夢濤，男,研究方向：物聯(lián)網(wǎng)工程等。

中圖分類號TP311

DOI:10.3969/j.issn.1672-9722.2016.04.039

Design of Algorithm Visual Frame Based on Qt

YU YuLIAO TaoGAO WenshengLI Mengtao

(School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan232000)

AbstractWith the rapid development and popularization of computer technology, the traditional algorithm teaching mode is no longer suitable for students to learn more abstract algorithm. Multimedia teaching has a rapid development in basic education with its own teaching advantages, compared with the original teaching of the relative chalk and blackboard, multimedia teaching has the following advantages: procedures for the implementation of more vivid and convenient, data evolution is more intuitive, time cost and cost of money are relatively low. In addition, it has a great effect on the optimization of educational environment and the improvement of the quality of teaching. In this paper, a visualization framework is proposed based on Qt, this framework can be used to realize the visualization of the algorithm.

Key Wordsalgorithm teaching, visualization algorithm framework, Qt