数据结构核心算法可视化系统设计与实现

慕岩磊，耿耀君

（西北农林科技大学信息工程学院，咸阳712100）

0 引言

《数据结构》是电子信息类专业一门十分重要的专业课，是《操作系统》、《计算机网络》等诸多课程的先修课。编写程序时，选择优良的数据结构，可以提高算法效率以及系统质量。如今我国的数据结构教学，主要还是以“课本+PPT”的形式进行，不仅枯燥而且使学生难以理解相关概念。故需要一种更加直观有关的方法来帮助学生学习数据结构。

1 系统实现

相比于文字，人们对图形和动画有着更加直观的理解。利用它们来进行学习，可以极大地提高学习效率。数据结构核心算法可视化系统正好给学生及广大计算机爱好者提供了一个这样的学习数据结构的良好环境。学生可以在该系统中选择需要学习的数据结构，通过观看系统内的标准算法的动画演示进行学习，也可以自己动手编写程序，观看自己所写程序的运行过程的动画来学习。

如图1 所示，该系统主要由界面和逻辑功能代码两个模块组成。

界面模块主要功能如下：

（1）接收用户请求。

（2）对用户请求做出响应，进行相应的动画演示。

图1 系统模块图

逻辑功能代码模块主要功能如下：

（1）通过编译器对程序进行词法分析和语法分析，如出现词法或语法错误则报错。

（2）对无语法错误的程序进行语义分析，生成绘图指令系列的中间代码。

（3）绘图指令解析程序对绘图指令进行解析，调用相应的绘图函数进行动画演示。

通过使用本系统，能将传统的“课堂+多媒体”的数据结构学习方式，转变为“动画展示+自主动手编程”的模式。对于学生来说既能够方便学生学习，又能够提高学习者的动手编程能力。

2 实现方法

本系统开发将基于面向对象程序设计方法，采用增量迭代方式开发。

2.1 简易编译器

数据结构计算机存储、组织数据的方式，本质上为一组抽象的概念，可以使用任何一种编程语言实现。本项目采用C 语言编译器进行开发。

编译器主要负责对程序进行词法分析和语法分析，报告程序存在的词法和语法错误。编译器的开发遵循C89 标准，采用Flex+Bison+C++的技术。以下是具体被调用的相关内容及步骤。

（1）词法分析：系统后端接收到前端传过来的程序源码，对其进行扫描，根据词法规则识别单词。若存在无法识别的单词，则为词法错误，需向前端发送错误消息。若不存在错误，则将该单词转化为指定的字符序列。

（2）语法分析：词法分析得到的字符序列根据文法规则转换为语法树。遍历语法树，不符合C 语言文法结构的部分将报告给前端界面。

（3）语义分析：审查每个语法成分的语义。若语义正确，则生成对应的绘图指令序列，否则向前端报错。

编译器开发过程如下：

（1）简化C 语言词法和文法

完整的C 语言所包含的内容比较庞大复杂，开发完整的C 编译器工作量大，且也没有必要。根据系统需求，对C 语言进行了适当简化，词法部分去除了auto、extern 等16 个关键字，保留了余下的16 个关键字。此外，去除了>>、&等不常用运算符。文法部分，删减并修改了部分C 文法。如删除了文法

abstract_declarator->pointer|direct_abstract_declara -tor|pointer direct_abstract_declarator，

将struct_declarator_list->struct_declarator|struct_declarator_list‘,’struct_declarator

修改为struct_declarator_list->declarator|struct_declarator_list‘,’declarator。

（2）词法分析

通过使用Flex 语言，将C 语言的词法规则用正规表达式编写，得到对应词法规则文件。由Flex 翻译器将该文件翻译成一个C 语言源文件，之后将该文件由g++编译，得到词法分析器。词法分析器能够识别用户源程序，将其转换为指定的字符序列。如用户程序存在词法错误，如标识符以数字开头，则进行报告。

（3）语法分析

将C 语言文法根据巴科斯范式（BNF）进行编写，定义规约方式。编译完成后交由Bison 编译器编译得到y.tab.h 和y.tab.c 文件。词法分析得到的字符序列可由编译得到的C 语言程序转化为语法树。遍历语法树通过C++语言程序实现。若出现语法错误则向用户报告错误。

（4）语义分析

语义分析程序采用C++语言开发，通过再次遍历语法树，进而分析程序语义。生成的类汇编语言的绘图指令序列以C 语言字符串的形式输出。

2.2 绘图指令

微观上看，数据结构算法的原子操作为：为数据申请内存、释放内存空间、移动指针、访问数组元素等。绘图指令与这些原子操作相对应，在底层将用户自编的数据结构算法程序规范化，便于后续绘图操作的统一处理。

绘图指令序列是编译器的输出，它是标准程序和用户自定义程序的另一种表示，目的是便于后续的绘图操作。在绘图指令中包含两种指令：控制指令和绘图指令。控制指令代表源程序中的分支和循环结构。

绘图指令借鉴汇编语言编写，一条C 语言语句对应多条绘图指令，代表算法中的产生绘图语义的原子操作。

2.3 绘图指令解析程序

绘图指令解析程序由C++语言编写。该程序借鉴Win32 消息处理模型，实现绘图指令到绘图函数的对应关系。

当其接收到编译器编译生成的绘图指令序列之后，绘图指令解析程序对指令进行识别，决定所需要调用的绘图函数。为了加快绘图指令解析的速度，将采用哈希表等数据结构来组织绘图指令及绘图函数。

2.4 界面动画

绘图动画采用并行机制，系统调用绘图函数进行图形绘制，对算法的执行情况进行展示。动画演示的同时，将当前动画所对应的核心代码行也在代码窗口标注出来，代码与动画同时展示。每执行一行代码，都有相应的动画演示对其进行解释，二者同步，不出现延迟或超前的现象。

无论哪种数据结构，其中包含大量结点。由于需要对数据结构进行动态演示，所以需要对结点进行统一的操作和管理。自己定义数据结构去管理这些结点是非常困难的，无法达到预期目的。故需要一种较为方便的方式来完成。通过使用Qt 的GraphicsView 框架，利用对模型和视图结构的图形管理，从而实现对结点的管理。此外，GraphicsView 框架提供坐标变换和图元组等多种方便的功能，为对结点的操作提供便利。

对于一种数据结构来说，选择合适的结点表现形式能产生更好的绘制效果。对于顺序表、链表等，选择矩形绘制结点较好。而对于树和图等，则选择圆形来进行绘制。故我们采用两个类：ball 类和rect 类对结点进行管理和操作。其中ball 为圆形类，rect 为矩形类。

我们可以在不同的数据结构上执行不同的操作，故将一种数据结构封装为一个类，由该类对其进行管理和操作。类中的一个函数对应一种操作。

GraphicsView 框架结构主要包含三个类：QGraphicsScene（容器）、QGraphicsView（视图）和QGraphicsItem（图形项）。QGraphicsView 提供一个可视的窗口，用于显示场景中的项目，一个场景中可以有多个视口。QGraphicsScene 通过与之相连的QGraphicsView类来与外界进行互操作。QGraphicsItem 是场景中各个项目的基础类。ball 类和rect 类为QGraphicsItem 的子类，Item 类及其子类可以处理鼠标点击、移动、释放等事件。一种数据结构的算法动画为一个函数，由一个场景QGraphicsScene 对象以及若干个Item 子类对象完成。在函数内通过在适当位置创建Item 类对象并将其加入场景中，配合定时器进行展示。

2.5 用户界面

界面由功能选择菜单、动态的图形演示、同步的算法程序代码显示、算法说明等部分组成。界面上方为功能选择菜单，左侧为算法选择区，右下方为算法程序代码同步演示区。正在执行的语句以高亮显示。随着算法的执行，高亮部分逐行移动算法图形动态演示区的显示区也跟着变化。中央区域为算法动画演示区，它根据算法的执行过程显示对应的动画。界面下方为动画速度调节，可以调整算法演示的速度。

用户界面采用Qt 技术进行开发。通过使用信号/槽机制，当用户发出请求时，相应组件发出信号。与该信号建立的连接槽，则可以接收该信号并做出回应，完成对用户请求的反馈。

3 结语

本文介绍了一种基于自制编译器和Qt 的数据结构核心算法可视化系统的设计与开发。该系统包含了简易C 语言编译器、绘图指令解析程序、用户界面等组成部分。用户可以观看系统内的标准程序的运行动画来学习，亦可自己动手编写程序，观看其动画来。系统通过自制编译器来将程序转化为自定义指令，利用Qt中GraphicsView 框架来进行绘图动画操作，出色地完成了预期功能。在《数据结构》课程中使用本系统，可以把“学与练”结合起来，提高学生的学习兴趣，降低学习难度。此软件在经过后期的一些细节优化后，即将投入到以后的《数据结构》课程中，相信它可以使本来抽象难懂的数据结构变得简单易学起来，成为学生们在学习过程中的良师益友。