数据结构算法演示系统的设计与实现

刘鹤　王佳欣　段云鹏等

关键词：算法；Python; GUI

中图法分类号：TP311 文献标识码：A

1引言

近年来，随着国内互联网市场的快速发展，尤其在移动互联网市场已经领先全球的大背景下，国内各大院校争先开设计算机专业及软件工程专业。而对于刚踏人大学的计算机专业的学生来说，“如何学习‘数据结构课程”就可能影响他们对本专业的学习态度，甚至是影响未来一生工作选择的重大问题。之所以很多学生认为“数据结构”课程中的许多算法晦涩难懂，一方面是大学教材中对于算法的解释多数只有让人摸不着头脑的代码和算不上通俗的文字讲解，另一方面大多数的学生并不能脚踏实地地去理解代码中的逻辑。换言之，采用通过思考从而模拟的方式去“运行”代码显然不适合刚接触计算机专业的大学生。反而，“数据结构”这门需要大量计算机基础并且是计算机学习体系中的基础课程将许多学生推向了学习编程的反面。因此，如何让学生以简单易懂的方式去学习算法，就成为每个开设计算机专业的院校需要研究的课题。

2系统设计

2.1概要设计

在概要设计阶段，首先要解决的是系统如何实现的问题。之后，将系统的主要内容进行划分，即划分出系统的结构。坏的系统结构在模块之间耦合度较高的情况下，甚至会导致原本只需要做一行的修改，结果却出现涉及上百个模块的情况。有经验的开发者都知道，前期的混乱会在开发时拖自己的后腿。但是，开发者又背负着期限的压力，所以只好继续在混乱的系统设计中继续制造混乱。在具有较好的系统结构后，无论是对系统进行开发或是维护的效率都将大大提高。

2.2系统功能结构设计

通过对需要完成的算法进行分析，可以大致将系统分为图、排序、二叉树三个模块，本文以图的存储结构及遍历算法来表示与实现，图算法子系统模块内容如图1所示。

对单个算法实现的GUI程序分解成类似于MVC模式的结构，以及针对几个小题，在不同的Python文件中解决。

（1）GUI界面：每个算法都会有一个独立的GUI界面Python文件作为UI的显示。

（2）Paint类：继承了PyQt4库中的QtGui.QGraphicsScene类，其中封装了绘制开发需要的动画的方法，以及动画运行的逻辑方法。

（3）Text类：主要用于控制在GUI界面显示的文本，并且对正在执行的语句进行背景色变红的高亮显示。

（4）Data类：用于封装在算法运行过程中使用的数据，以及改变数据的方法。

2.3系统功能模块描述

针对本系统的四个算法，每一个算法都有其子算法，每一个子算法都有些许不同的设计。图的存储结构及遍历算法模块如下。

（1）邻接矩阵的插入：点击新建图按钮，将数据清空并初始化界面：勾选有向图并点击新建图，将得到有向图的邻接矩阵，使用数组表示数据元素和元素之间的关系；在动画演示窗口双击，可以生成一个新的顶点；在输入弧顶点的文本框中输入弧名，再点击插入弧按钮就会生成弧。

（2）图的广度优先遍历：点击新建图按钮，将数据清空并初始化界面；勾选有向图并点击新建图，将得到有向图的邻接矩阵；在动画演示窗口双击，可以生成一个新的顶点；点住图中的某一个顶点，再将鼠标拖拽到另一个顶点，就可以生成两个顶点之间的边（弧）；在输入遍历开始的顶点的文本框中输入顶点名，点击开始遍历按钮，就可以对当前的图进行遍历。

（3）图的深度优先遍历：步骤同图的广度优先遍历。

3系统实现

系统的每个子界面都是根据要实现的算法内容所设计的，每个算法的数据结构不同使得算法动画也不同，且控制面板上的各种控制按钮的功能也各不相同。

3.1图的算法

在图的算法模块中，圆圈代表图的顶点，圆圈之间的直线代表无向图中顶点之间的弧，带箭头的线代表有向图中顶点之间的弧。图的算法下有三个子界面，分别是邻接矩阵、图的深度优先遍历、图的广度优先遍历。邻接矩阵界面有如下几个功能。

只要在动画演示窗口内双击，就会自动生成新的顶点，如图2所示。

在该界面下的文本“输入弧的顶点”右侧输入要生成的弧的两个顶点名，再点击插入弧按钮，就会自动生成对应的弧，并改变动画演示窗口中的图形和邻接矩阵窗口中的数组，如图3所示。

若新建图，则把原先的数据清除重置，而将“有向图”勾选后，再点击新建图，就会生成一个有向图。此时插入弧，在动画演示窗口就会显示为一个带箭头的弧，右侧显示邻接矩阵的同时，也会显示对应的数值，如图4所示。

3.2深度优先遍历的功能

与邻接矩阵界面一样，深度优先遍历也能够在动画演示窗口点击生成顶点。但是，与邻接矩阵页面又有所不同，在该界面可以通过用鼠标点住一个顶点，再拖拽到另一个顶点，从而生成弧，如图5所示。

在文本输入框输入遍历开始的结点后，点击开始遍历按钮，可以自动进行深度优先遍历动画，并将访問过的顶点和进入栈显示在数据演示窗口，如图6所示。

深度优先遍历同样可以通过新建图清除重置数据，也可以通过勾选有向图来创建有向图进行深度优先遍历，如图7所示。

3.3广度优先遍历的功能

广度优先遍历的功能基本与深度优先遍历相同，但其算法运行的过程及结果与深度优先遍历有所不同，如图8所示。

4结束语

该系统是一个图形化用户界面程序，使用的语言为Python和PyQt4库，并且使用py2exe将py文件转换成可执行文件（.exe），实现的功能主要有动画与文本的同步演示、用户交互式输入数据、动画执行及单步执行等，实现的算法包括图（Graph）、排序、哈夫曼编码、二叉树。在经过程序的动画演示后，这些复杂而又难以理解的算法也能够被大部分学生所接受，达到提高学习效率的目的。

对于一个用于学习的工具来说，仅实现功能远远不够，它需要的是真正被学生所使用、所接受。为此，必须从学生处获取关于使用体验的调查报告，再将调查报告转换成需求和代码。而本系统基于Python，拥有较好的可读性与可修改性，在面临需要对其进行扩展、增加部件的情况下，本系统的子系统之间相互独立，因此也表现出极好的可扩展性。所以，该系统程序的开发将不会就此停滞，未来也会以开发新模块并将其加入系统中和完善旧模块为目标继续前进。

作者简介：

刘鹤（1979—），硕士，副教授，研究方向：计算机教育。