程序调试中的数据结构演变可视化方法

doi:10.19678/j.issn.1000-3428.0068265

摘要/Abstract

摘要：

数据结构是程序执行时的重要信息载体, 其演变过程往往较为复杂和抽象。针对程序设计初学者较难理解数据结构演变过程的问题, 提出一种面向程序调试中的数据结构演变可视化方法。在调试开始时, 首先使用组件表达式表示数据结构, 然后通过配置表以及布局函数将组件表达式生成可视化视图。在进行单步调试后, 通过对比单步调试前后的可视化数据方式生成组件演变行为, 运用有限状态机理论构建数据结构演变模型, 该模型的执行使得组件发生演变, 同时生成可视化动作。使用动画单元执行可视化动作, 实现数据结构演变的可视化呈现, 帮助初学者理解数据结构相关程序的执行过程。实验结果表明, 将该方法应用于1个数据结构演变可视化框架StructV, 并应用于1个在线可视化编程实训云平台的研发, 可有效降低初学者理解数据结构演变过程的难度, 并提升编程实训时的程序调试效率。

关键词: 程序调试, 数据结构可视化, 组件演变行为, 有限状态机, 数据结构演变模型

Abstract:

Data structure carries important information regarding program execution in complicated and abstract evolution processes. To address the difficulty encountered by beginners in understanding the evolution process of data structures, this study proposes a method for visualizing the data structure evolution in program debugging. Initially, during debugging, the data structures are represented using component expressions. Subsequently, visual views are generated using configuration tables and layout functions based on component expressions. After single-step debugging, the evolution behavior of the components is determined by comparing the visual data before and after single-step debugging. A data structure evolution model is constructed using the finite state machine theory. The execution of this model causes the components to evolve while generating visual actions. This model uses animation units to perform visual actions and visualize the evolution of data structures, helping beginners understand the execution process of data structure-related programs. The experimental results of applying this method to a data structure evolution visualization framework, StructV, and to the development of an online visualization programming training cloud platform show that this process can effectively reduce the difficulty encountered by beginners in understanding data structure evolution and improve the efficiency of program debugging during programming training.

Key words: program debugging, data structure visualization, component evolution behavior, finite state machine, data structure evolution model

苏庆, 陈建成, 顾国生, 刘冬宁, 黄剑锋. 程序调试中的数据结构演变可视化方法[J]. 计算机工程, 2024, 50(9): 197-207.

SU Qing, CHEN Jiancheng, GU Guosheng, LIU Dongning, HUANG Jianfeng. Visualization Method for Data Structure Evolution in Program Debugging[J]. Computer Engineering, 2024, 50(9): 197-207.

https://www.ecice06.com/CN/Y2024/V50/I9/197

图/表 15

图1 一步DSE调试过程

Fig.1 Debugging process of one-step DSE

图2 组件运算符示意图

Fig.2 Schematic diagram of component operator

图3 组件抽取流程

Fig.3 Procedure of component extraction

图4 检验组件表达式的有限状态机

Fig.4 Finite state machine for checking component expression

图5 组件布局示意图

Fig.5 Schematic diagram of component layout

图6 组件居中布局示意图

Fig.6 Schematic diagram of component centered layout

图7 组件映射过程

Fig.7 Component mapping process

图8 数据结构演变可视化建模过程

Fig.8 Visualization modeling process of the evolution of data structure

图9 数据结构演变模型

Fig.9 Evolution model of data structure

图10 可视化动作执行

Fig.10 Execution of visualization action

图11 StructV总体架构

Fig.11 General architecture of StructV

图12 广义表调试过程及可视化效果

Fig.12 The debugging process and visualization effect of generalized table

图13 不同表示方式在不同数量可视化数据下的性能测试

Fig.13 Performance detection of different representations methods under different amounts of visualized data

参考文献 26

1	HU M J, ASSADI T, MAHROEIAN H. Teaching visualization-first for novices to understand programming[C]//Proceedings of the IEEE International Conference on Engineering, Technology & Education (TALE). Washington D. C., USA: IEEE Press, 2021: 654-660.
2	苏庆, 汤毅豪, 曾永安, 等. 单链结构实时识别及可视化布局算法研究. 计算机工程与应用, 2019, 55(16): 240- 245. doi: 10.3778/j.issn.1002-8331.1804-0291
	SU Q, TANG Y H, ZENG Y A, et al. Research on real-time identification and visualization layout algorithm for single linklist structure. Computer Engineering and Applications, 2019, 55(16): 240- 245. doi: 10.3778/j.issn.1002-8331.1804-0291
3	李彦龙, 李国强, 董笑菊. 树比较可视化方法综述. 软件学报, 2016, 27(5): 1074- 1090. URL
	LI Y L, LI G Q, DONG X J. Survey on visualization of tree comparison. Journal of Software, 2016, 27(5): 1074- 1090. URL
4	苏庆, 黎智洲, 刘添添, 等. 程序调试中的树形结构演变可视化模型. 计算机科学, 2021, 48(5): 68- 74. URL
	SU Q, LI Z Z, LIU T T, et al. Tree structure evaluation visualization model for program debugging. Computer Science, 2021, 48(5): 68- 74. URL
5	BACH B, PIETRIGA E, FEKETE J D. GraphDiaries: animated transitions and temporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics, 2014, 20(5): 740- 754. doi: 10.1109/TVCG.2013.254
6	CHEONG S H, SI Y W, WONG R K. Online force-directed algorithms for visualization of dynamic graphs. Information Sciences, 2021, 556, 223- 255. doi: 10.1016/j.ins.2020.12.069
7	GOROCHOWSKI T E, DI BERNARDO M, GRIERSON C S. Evolving enhanced topologies for the synchronization of dynamical complex networks[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2010, 81(5 Pt 2): 056212.
8	BANSAL A, SHAH P, SHAH S. Eye: program visualizer for CS2[EB/OL]. [2023-07-15]. http://arxiv.org/abs/2101.12089.
9	汤毅豪. 数据结构实时调试可视化技术的研究与应用[D]. 广州: 广东工业大学, 2020.
	TANG Y H. Research and application of data structure realtime debugging visualization technology[D]. Guangzhou: Guangdong University of Technology, 2020. (in Chinese)
10	LIN J, ZHANG H. Data structure visualization on the web[C]//Proceedings of the IEEE International Conference on Big Data (Big Data). Washington D. C., USA: IEEE Press, 2020: 3272-3279.
11	BURLINSON D, MEHEDINT M, GRAFER C, et al. BRIDGES: a system to enable creation of engaging data structures assignments with real-world data and visualizations[C]//Proceedings of the 47th ACM Technical Symposium on Computing Science Education. New York, USA: ACM Press, 2016: 18-23.
12	PERHÁČ P, ŠIMOŇÁK S. Interactive system for algorithm and data structure visualization[J]. Computer Science Journal of Moldova, 2022, 30(1): 28-48.
13	BECK F, BURCH M, DIEHL S, et al. A taxonomy and survey of dynamic graph visualization. Computer Graphics Forum, 2017, 36(1): 133- 159. doi: 10.1111/cgf.12791
14	原恺涓, 傅四维, 葛晓东, 等. 动态图序列演变模式的可视化. 计算机辅助设计与图形学学报, 2020, 32(10): 1655- 1662. URL
	YUAN K J, FU S W, GE X D, et al. Understanding evolution patterns in multiple sequences of dynamic graphs. Journal of Computer-Aided Design & Computer Graphics, 2020, 32(10): 1655- 1662. URL
15	刘真, 吴向阳, 郑秋华. 动态网络可视化与可视分析综述. 计算机辅助设计与图形学学报, 2016, 28(5): 693- 701. doi: 10.3969/j.issn.1003-9775.2016.05.001
	LIU Z, WU X Y, ZHENG Q H. A survey of dynamic network visualization and visual analysis. Journal of Computer-Aided Design & Computer Graphics, 2016, 28(5): 693- 701. doi: 10.3969/j.issn.1003-9775.2016.05.001
16	THOMPSON J, LIU Z, LI W, et al. Understanding the design space and authoring paradigms for animated data graphics. Computer Graphics Forum, 2020, 39(3): 207- 218. doi: 10.1111/cgf.13974
17	MASHIMA D, KOBOUROV S G, HU Y F. Visualizing dynamic data with maps. IEEE Transactions on Visualization and Computer Graphics, 2012, 18(9): 1424- 1437. doi: 10.1109/TVCG.2011.288
18	RUFIANGE S, MCGUFFIN M J. DiffAni: visualizing dynamic graphs with a hybrid of difference maps and animation. IEEE Transactions on Visualization and Computer Graphics, 2013, 19(12): 2556- 2565. doi: 10.1109/TVCG.2013.149
19	黄剑锋, 苏庆, 刘添添, 等. 可视化WebIDE编程实训系统的构建与教学实践. 实验技术与管理, 2021, 38(7): 166- 171. URL
	HUANG J F, SU Q, LIU T T, et al. Construction and teaching practice on visual WebIDE programming training system. Experimental Technology and Management, 2021, 38(7): 166- 171. URL
20	PAI T V, JAYANTHILA DEVI A, AITHAL P S. A systematic literature review of lexical analyzer implementation techniques in compiler design. International Journal of Applied Engineering and Management Letters, 2020, 285- 301. doi: 10.47992/IJAEML.2581.7000.0087
21	李琳, 毋国庆, 黄勃, 等. 基于行为模型的需求可视化研究. 计算机学报, 2013, 36(6): 1312- 1324. URL
	LI L, WU G Q, HUANG B, et al. Behavioral model based requirements visualization method. Chinese Journal of Computers, 2013, 36(6): 1312- 1324. URL
22	GE T, ZHAO Y, LEE B, et al. Canis: a high-level language for data-driven chart animations. Computer Graphics Forum, 2020, 39(3): 607- 617. doi: 10.1111/cgf.14005
23	KIM Y, HEER J. Gemini: a grammar and recommender system for animated transitions in statistical graphics. IEEE Transactions on Visualization and Computer Graphics, 2021, 27(2): 485- 494. doi: 10.1109/TVCG.2020.3030360
24	CHALBI A. Understanding and designing animations in the user interfaces[D]. Lille, Franch: Université lille1, 2018.
25	FRANZ M, LOPES C T, HUCK G, et al. Cytoscape. js: a graph theory library for visualisation and analysis. Bioinformatics, 2016, 32(2): 309- 311. doi: 10.1093/bioinformatics/btv557
26	BOSTOCK M, OGIEVETSKY V, HEER J. D³: data-driven documents. IEEE Transactions on Visualization and Computer Graphics, 2011, 17(12): 2301- 2309. doi: 10.1109/TVCG.2011.185

[1]	王文斌, 钱振江, 靳勇, 孙高飞, 邢晓双, 苏超, 孙天琦. 基于Isabelle/HOL的文件系统形式化设计与验证[J]. 计算机工程, 2024, 50(4): 277-285.
[2]	林伟建,王伦耀,夏银水. 有限状态机的双逻辑面积优化[J]. 计算机工程, 2016, 42(5): 282-287.
[3]	马殷元,王虎军,张伟. 机电系统中实时控制软件状态图模型扩展及实现[J]. 计算机工程, 2016, 42(3): 94-97.
[4]	李明哲,陈君,王劲林,陈晓. 基于状态机的HTTP Chunked流并发解析[J]. 计算机工程, 2015, 41(1): 256-260.
[5]	曹文, 郭帆, 余敏, 张磊. 基于哈希树和有限状态机的XSS检测模型[J]. 计算机工程, 2013, 39(6): 154-157,161.
[6]	黄鹏，刘箴. 一种基于动机理论的人群行为模型[J]. 计算机工程, 2013, 39(12): 290-293.
[7]	谭貌, 段斌, 彭邦伦, 张建和. 云制造环境下协同工作流控制模型研究[J]. 计算机工程, 2012, 38(24): 21-26.
[8]	黄晓玲, 陈桂林, 赵生慧. 基于云计算的并行测试方案设计与实现[J]. 计算机工程, 2012, 38(24): 27-31.
[9]	张依依, 祝跃飞, 高翔. 针对BGP路由器的DDoS攻击及防范措施[J]. 计算机工程, 2012, 38(19): 103-106.
[10]	袁佳琳, 高建华. 基于改进FSM的RBAC测试集约简方法[J]. 计算机工程, 2012, 38(17): 42-45,48.
[11]	翟琰, 魏振春, 韩江洪, 卫星. 基于脚本语言建模的汽车ECU测试系统设计[J]. 计算机工程, 2012, 38(15): 260-263.
[12]	张之武, 娄建安, 常小龙, 李川涛. 基于信息论的时序电路演化设计[J]. 计算机工程, 2012, 38(10): 288-290.
[13]	闵华松, 刘冬, 王田苗. 智能机器狗的语音控制模型研究[J]. 计算机工程, 2012, 38(01): 188-191.
[14]	南洋, 秦贵和, 董劲男, 高洋. 基于FSM模型的车载MOST网络管理系统[J]. 计算机工程, 2011, 37(18): 91-93.
[15]	张菁. 基于有限状态机的UDP传输设计[J]. 计算机工程, 2011, 37(17): 52-54.

选择文件类型/文献管理软件名称

选择包含的内容