数据结构经典算法实验平台的设计与开发

张 岩, 娄 久, 李秀坤, 刘 扬, 王春宇

(哈尔滨工业大学， 计算机科学与技术学院， 黑龙江 哈尔滨 150001)



数据结构经典算法实验平台的设计与开发

张 岩, 娄 久, 李秀坤, 刘 扬, 王春宇

(哈尔滨工业大学， 计算机科学与技术学院， 黑龙江 哈尔滨 150001)

为更好地满足数据结构与算法课程教学需求，设计实现了一个以数据结构经典算法为主体的双边教学实验平台，可以支持教师的算法动态教学演示和学生的自学推导。该平台通过图形化、虚拟化的方法逐步展示经典数据结构与算法分析和计算过程。同时为便于学生理解算法，避免界面化技术产生的工程代码对算法代码的干扰，该平台提供控制台代码展示功能，学生可以通过控制台和界面实现双向输入或输出。该实验平台可以帮助学生理解数据结构课程中经典算法的设计思想，设计策略，时空复杂性以及实现过程，使学生更好地掌握数据结构与算法课程的教学内容，提高课堂教学效率和学生的自学创新能力。

实验教学； 实验平台； 数据结构； 算法

0 引 言

“数据结构与算法”是计算机学科的基础骨干核心课程，是本科教学的重中之重[1]。但由于课程内容本身具有高度抽象性和较强的理论性，在学习时，学生会感到有些枯燥和单调，不容易理解[2-4]。因此，需要通过实验教学促进学生对理论教学的理解，从而达到培养具有实践创新能力人才的目的。然而，为达到这一目的不仅需要在教学模式和教学方法上进行改革[5-6]，还需要借助于图形化、虚拟化等信息技术构建适应教学需求的实验平台[7-8]。

本文研究并设计了一种数据结构经典算法实验平台，旨在对经典数据结构和算法进行归纳、分类、编码和展示，教师可以用图形化方式直观地演示算法流程和代码，学生可以通过该平台学习和推演算法，这将加深学生对教学内容的理解深度，有利于教学效率的提高和课后学生自学创新能力的培养。

1 实验平台的总体设计

本实验平台是双边实验平台，即要求平台不仅能够支持教师的教学演示需求，还需要满足辅助学生学习的需求。因此，平台物理框架共为三层，即用户层、应用层和文件层，具体如图1所示。从图中可以看出，在用户层中用户可通过前端界面，选择想要学习的算法或相应的功能。如果用户选择的是算法学习，则用户可根据所选择的算法提供输入，程序有简单的容错能力，如果输入有误，程序会在一定范围内给予提示和改正；在应用层，程序会根据用户提供的输入和选择的算法进行运算，然后将运算结果返回给前台，用户即可查询浏览；在文件层，支持代码查询功能，如果用户选择的是代码查询功能，则系统会根据用户选择的算法，从文件中读取相应内容，显示到前台。

图1 平台的物理架构图

1.2 功能模块设计

通过实际调研和分析发现，学生在进行数据结构与算法课程的学习过程中，主要难点集中于非线性数据结构、查找、排序算法以及数据结构的综合应用[9]。因此，为满足教学需求，平台设计了四个功能模块，树及树的应用模块、图及图的应用模块、查找及排序模块和综合应用模块，具体包含内容如图2所示。平台可以展示基于树和图等基本数据结构的经典算法代码；展示基本数据结构的查找、排序流程；能够直观地展示算法的运行过程；并能够分析算法效率。此外，用户还能够根据已完成的算法和界面，实现一个小的应用。

数据结果经典算法的分析及应用 树及树的应用模块 图及图的应用模块树的存储及遍历(包含各种存储方式及遍历方式)哈夫曼树选择树判定树BST树AVL树图的存储及遍历(包含各种存储方式及遍历方式)Prim算法Kruskal算法BellmanFord算法Dijkstra算法Floyed算法查找排序模块综合应用模块线性查找二分查找选择排序 插入排序 冒泡排序堆排序 希尔排序 快排序 归并排序代码展示流程图展示启动界面算法综合应用模块

图2 平台的功能结构图

2 实验平台的开发

2.1 树及树的应用模块开发

树及树的应用包含树的经典存储方式及遍历方法，如哈夫曼树(含哈夫曼编码)、胜者树[10]、判定树[11]、BST树[12]、AVL树[13]。在主属性页上方看到所有的算法信息，复选框高亮的部分为选择的算法的信息，图3～6分别给出哈夫曼树、判定树、选择树和BST树的实例展示。

图3 哈夫曼树实例展示

图4 判定树实例展示

(1) 哈夫曼树实例展示。图3展示了哈夫曼树及编码过程，用户可在输入栏中输入任何英文文章，不限内容和字数。然后可点击建立哈夫曼树按钮，会弹出树已建立提示，而后用户可点击哈夫曼编码，就会在下方区域显示具体的编码。如果用户对原有文章进行修改，则需要重新建立树，再次点击哈夫曼编码按钮时，可重新编码，用户可比较修改后的结果和原有结果的不同。

(2) 判定树实例展示。图4展示了以八硬币问题为例的判定树演示界面。用户首先在属性页资源上选择判定树，这样进入判定树页面，可以修改图中任何一个硬币的重量，而后点击判定按钮，则会在对话框上显示假硬币重量，并告知用户假硬币较真硬币是轻是重。所有硬币初始值10 g，用户可重复操作。

(3) 选择树实例展示。图5为胜者树展示界面。用户首先在属性页资源上选取胜者树按钮，进入胜者树页面，而后输入需归并的数量，再次输入归并段内容，每个归并段以‘ ’号分隔，数据输入完成后击建立选择树按钮，可看到排序后的结果，并且在页面的最下方给出了算法的时间复杂度分析。

公司的经营绩效通过盈利能力、营运能力、偿债能力、成长能力等来表现，其中代表盈利能力的指标如净资产收益率、总资产收益率等，代表营运能力的指标如总资产周转率，代表偿债能力的指标如资产负债率、流动比率等，代表成长能力的指标如营业总收入同比增长率等。

图5 选择树的实例展示

(4) BST树实例展示。图6为BST树的建立过程，首先用户需在属性页上选择BST 树资源，进入BST算法展示，而后用户在输入对话框中输入节点信息，同时，用户可随时点击插入、删除、查找按钮对BST树进行增删改操作。最后可用中序输出这个BST树，由于树的性质，中序输出是一个递增序列。

图6 BST树的实例展示

2.2 图及图的应用模块的开发

从图2中可以看出，图及图的应用模块主要包含经典的图的建立与遍历算法的展示，图7～9分别为图的建立及遍历，BellmanFord算法[14]和Floyed[15]算法的实例展示。

(1) 图的建立与遍历实例展示。图7展示了图的建立和最基本遍历算法，用户可在界面最顶层输入定点数和边数，而后在第二行输入顶点信息，在第三行输入边信息。当用户点击建立图按键时，系统可提示图是否建立正确，如图正确建立，则用户点击深度优先或广度优先按钮时，可查询深度优先和广度优先结果。

(2) BellmanFord算法实例展示。图8展示了利用BellmanFord算法求单源最短路径的过程，用户可在本系统中输入任意个图，输入方法和上例相同，而后点击建立图按钮，如果图正确建立，点击BellmanFord算法按钮，系统将用中文输出运行结果。

图7 图的建立及遍历实例展示

图8 BellmanFord算法的实例展示

(3) Floyed算法实例展示。图9展示了利用Floyed算法求所有节点最短路径的过程，在本实验平台，用户只需输入想要遍历的图，点击建立图，程序就会自动进行迭代，将输出的结果保存在距离矩阵中，用户可在对话框内随便输入两节点编号，点击Floyed算法，将会给出两节点的最短路径。

图9 Floyed算法的实例展示

2.3 查找部分的开发

查找排序部分所涉及的算法最多，但由于功能单一，这里只给出堆排序和二分搜索的实例展示界面。

(1) 堆排序算法实例展示。图10为堆排序算法，用户需输入堆的大小和堆的内容，点击建立堆。同时用户可通过点击向堆中添加元素按钮向堆中添加元素。当用户点击堆排序按钮时。系统会在最后一个对话框中以递减的顺序展示排序结果。

图10 堆排序展示

(2) 二分搜索算法实例展示。图11为二分搜索算法，用户首先输入数组大小和数组内容，注意此处数组内容要是一个有序序列，在查找项窗口中输入待查找项，而后点击查找按钮，系统此时会显示查找结果，如果存在则显示数组下标，不存在则显示-1。

图11 二分搜索展示

2.4 综合应用模块的开发

为了便于学生自学和实践开发，平台设计了综合应用模块，该模块可以帮助学生通过图形界面来实现算法演绎推理。图12～15为图的建立、遍历以及最短路径演绎结果。用户首先通过鼠标的点击在对话框上建立图的节点，然后通过鼠标右键点击两个节点的圆心，建立图的边，边的权值为两个节点相距的像素值。在图建立完成后，可选择点击深度优先搜索或广度优先搜索按钮，深度优先是通过蓝色点闪烁实现的，广度优先搜索是通过粉色点闪烁实现的。当用户点击查找按钮时，即选择一个源点，再随便点击一个已经建立好的点，则系统会按照最短路径算法，用橙色的点标定出路径。

图12 图的建立

图13 单源最短路径展示

图14 深度优先算法

图15 广度优先算法

3 结 语

数据结构经典算法实验平台是一个双边教学实验平台。教师利用该实验平台展示算法流程及代码，将抽象化的算法直观化；学生通过参数设置、码演示、流程演示和综合开发等环节，参与到教学实践中，加深了对授课内容的理解并提高了自身实践创新的能力。同时，该平台具有一定的通用性与扩展性，可以对大规模数据进行树、图等的运算。因此，该平台可以作为科学研究的基础平台，具有一定的推广价值。

[1] 李晓鸿，骆嘉伟，季 洁.“数据结构与算法分析”研究型实践教学的探索[J]. 实验室研究与探索，2012，31(1)：121-125.

[2] 邹恒明. 分而治之为上策：数据结构课程的反思与变革[J]. 中国大学教学，2011(6)：53-56.

[3] 杜小坤，涂 韬. 数据结构教学方法探讨[J]. 计算机教育，2014(18)：46-48.

[4] 曹春萍，陈 平. 问题驱动法在“数据结构”教学中的应用探讨[J].中国电力教育，2014(23)：78-79.

[5] 徐 翀. 微课在数据结构课程中的应用[J]. 中国教育信息化，2014(11)：37-39.

[6] 娄 久，李秀坤，张 茹. 软件设计与开发实践课程探讨分析[J].实验技术与管理，2012，29(4)：186-188.

[7] 刘小晶，钟 琦，张剑平. 翻转课堂模式在“数据结构”课程教学中的应用研究[J]. 中国电化教育，2014，331：106-110.

[8] 林瑜华. 云计算环境下高校实验教学模式的创新与实践[J]. 实验室研究与探索，2011，30(8)：271-274.

[9] 鹿 旸. 数据结构与算法课程教学方法的思考[J]. 计算机教育，2010(5)：88-90.

[10] 裴 松，武 彤. 扩展哈弗曼前缀编码实现XML数据与关系数据转换[J].微型机与应用，2013，32(17)：56-59.

[11] 维 斯. 数据结构与算法分析——C语言描述[M].北京：机械工业出版，2010：186-188.

[12] Horowitz E，Sahni S，Rajas-ekaran S. Computer Algorithms [M]. Silicon Press，2008： 773-775.

[13] 郑丽英. 数据结构Trie及其应用[J].现代计算机，2004，193：20-22.

[14] 李汉兵，喻建平，黄建雄,等. 基于时延限制的Bellman Ford算法[J]. 西安电子科技大学学报，2000，27(3)：330-334.

[15] Clifford A Shaffer. Data Structure and Algorithms(C++)[M]. Electronic Industry Press，2013：214-218.

Design and Development Experimental Platform for Data Structure Classical Algorithm

ZHANGYan，LOUJiu，LIXiu-kun，LIUYang，WANGChun-yu

(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001，China)

In order to meet the needs of the teaching of data structures and algorithms, a bilateral teaching experiment platform that can support teachers teaching and students self-teaching is designed and implemented for classic data structures and algorithms. It used graphical and visual technologies to gradually show the classic data structures and algorithms analysis and calculation processes. Meanwhile, in order to facilitate the students' understanding of algorithms and avoiding interface technology project code generated by the interference of the algorithm code, the platform provides console code display function, students can achieve bidirectional input or output via the console and interface. The experimental platform can greatly help students understand the data structures course in classical algorithm design, design strategy, time and space complexity and implementation process, it not only enables students to better grasp the teaching curriculum content of data structures and algorithms, but also improves the efficiency of classroom teaching and students' self-learning and innovative ability.

experiment teaching； experiment platform； data structure； algorithms

2015-01-08

2014年黑龙江省高等教育教学改革项目(JG2014010704)

张 岩(1965-)，男，黑龙江穆棱人，副教授，主要研究方向：数据库、信息可用性管理、算法理论等。

Tel.:0451-86413341; E-mail:zhangy@hit.edu.cn

TP 30

A

1006-7167(2015)08-0127-04