数据结构算法设计题的测试程序辅助构建研究

摘要

程序测试是保证程序正确性的重要手段，而测试数据的选择以及测试数据的生成是其核心与关键。然而目前程序测试的测试数据的生成方法多是针对数值型数据，如整型数据、实型数据等，难以直接应用于动态数据结构上，且基本上都是手工生成，一定程度上影响了其发展。因此，研究基于动态数据结构的测试数据和测试程序的生成方法，具有十分重要的意义和广阔的应用前景。
　　 广东工业大学计算机学院吴伟民教授开发的“数据结构算法设计可视化作业系统AnyViewDS”(以下简称AnyViewDS作业系统)是一个数据结构课程编程作业的可视化运行、调试、提交和测试的集成环境，它支持学生在互联网上完成算法设计题型作业。学生只需编辑输入算法的函数体，系统自动对其进行可视化的实时测试。但是，目前其测试数据和测试程序的生成都是教师手工编写的，非常耗费教师的时间和精力。因此，为了提高该系统的实用性，减少教师的工作量，有必要开发一个基于动态数据结构的测试程序生成系统。
　　 基于以上原因，本文以AnyViewDS作业系统中学生提交的作业程序为实验对象，结合动态数据结构的程序测试的相关技术，对数据结构算法设计题的测试程序辅助构建进行系统研究，主要工作如下：
　　 首先分析了AnyViewDS作业系统的不足，提出测试程序生成的需求。在对目前AnyViewDS作业系统中现有的测试程序进行分析与研究的基础上，总结出各个题目对应的测试程序的共同特征，将其抽象为测试程序生成模板，在此基础上提出了一种基于模板填充的测试程序生成方法，并且用于测试数据的构造。为了系统的高耦合性，本文借助测试程序辅助函数库来实现该方法。针对各种不同的数据结构，本文设计并实现了不同的测试程序辅助函数。
　　 其次，在Java Swing技术的基础上，通过人机交互的方式，设计并实现了基于模板填充方法的测试程序生成系统TPGS(Testing Program Generating System)，该系统可以半自动生成AnyViewDS作业系统中需要的测试程序。
　　 最后，为了验证所提出的基于模板填充的测试程序生成方法，将测试程序生成系统TPGS生成的测试程序与AnyViewDS作业系统进行集成，进行实验。实验结果表明所提出的测试程序生成方法达到预期目标。