云计算在《数据结构》实验环节中的应用

2018-11-17朱洁黄海平陈兴国张毅

现代计算机 2018年29期

朱洁，黄海平，陈兴国，张毅

（1.南京邮电大学计算机学院，南京210023；2.南京理工大学计算机科学与工程学院，南京210094）

0 引言

《数据结构》主要研究各种数据的抽象表示、实现方法和算法的设计过程，是计算机软件设计的重要理论和实践基础课程，该门课程也是面向非计算机专业学生的全校跨专业选修课之一。该课程先修课程为《高级语言程序设计》和《高等数学》，后续课程有《操作系统》和《算法分析与设计》等。在南京邮电大学《数据结构》大纲中规定，针对计算机相关专业的学生，该课程的课程目标包括：（1）使学生掌握数据结构的基本概念，熟悉合理组织数据的基本方法，培养学生运用计算思维分析计算机领域的相关工程问题的能力，为本专业后续课程学习及进一步的软件开发打下良好的理论基础；（2）能够运用计算思维分析问题和解决问题，针对具体问题，分析数据元素的组成和逻辑关系，设计灵活高效的数据存储结构，实现所需的运算，针对计算机领域复杂工程问题设计可行的研究方案；（3）能综合运用数据结构的基本理论和设计方法，研究针对计算机领域复杂工程问题自主设计数据结构，并能对研究方案的可行性进行论证。与之对应地，当面向非计算机专业学生时，该课程的授课目标专注于使学生掌握数据结构的基本概念，熟悉合理组织数据的基本方法，培养学生运用计算思维进行问题分析与简单算法设计的能力。可以看出，无论是面向计算机专业还是非计算机专业，该门课程的核心目标是培养学生的抽象思维能力、逻辑推理能力、和综合运用所学分析问题和解决问题的能力。

1 《数据结构》课程教学现状

该课程的难点是针对实际应用问题选择合适的数据结构及设计有效的算法并实现，需要重视并强化上机实践教学环节，提高学生的独立编程能力。《高级语言程序设计》（即C语言课程）作为该门课程的先修课程，是全校各专业必修的通识课程，在学生大一下学期开始学习。而《数据结构》则是在大二上或大二下分别面向计算机或非计算机专业学生进行授课。众所周知，大二学生（即使是计算机专业）的编程能力非常有限，大多数学生仅仅能做到通过《高级语言程序设计》考试，真正可以做到不被编程语法所束缚、做到具备“自由的理解数据结构思想”能力的学生非常少。作为《数据结构》授课教师，对学生的预期是：学生在学习先修课程《高级语言程序设计》时，能够在课外花费相对于课题授课5倍甚至更多的时间去进行各种编程实践，做好充分的实践准备；然后在《数据结构》课程学习过程中，利用编程实践手段来辅助理解数据逻辑表达内涵，从而提高分析与解决复杂工程问题的能力，为后续理论课程《算法分析与设计》和实践课程《算法与数据结构设计》打下坚实基础。也就是说，在《数据结构》学习过程中，编程是加深对理论理解的重要手段（但不是唯一手段）。但是，大多数学生都没有做好这样充分的准备工作，即使在授课过程中对书上的每一个编程案例进行逐行讲解，仍然有很多学生都觉得这门课程难度太高，一边要恶补编程，一边又要充分发挥逻辑推导与抽象思维能力，还要兼顾考试题目的各种花样，学习负担与心理负担都非常重。

《数据结构》试卷出题情况一般包括80%的理论题（考核对数据结构概念、定理与应用理解，包括选择题、填空题和简答题）和20%的实践题（算法设计或编程填空）。针对这样公开的出卷规律，存在一部分学生在学习《数据结构》课程时，完全放弃实践环节，主攻80%的理论分。通过最近几年试卷分析我们发现了一个规律：理论题得分率在80%以上的学生，实践题得分率基本上不低于80%，这说明了卷面成绩达到良好及以上的学生，都具备较强的算法设计能力。这也进一步表明，《数据结构》课程要想学好，不能放弃实践环节。针对该试卷分析结论，课程组教师进行了较为激烈的讨论，在无法改变学生语言基础薄弱的现实情况下，如何能够尽可能提高学生对本课程的学习兴趣与信心，尽可能理解和掌握数据结构思想，是课程组讨论的核心议题。根据讨论结果，建议全体授课教师调整教学方法，将理论教学授课重点放在学生逻辑推理与抽象思维能力的培养上，在一定程度上弱化代码的讲解，让学生不会对编码望而生畏；通过画图、动画等手段展示数据结构的各种算法过程与逻辑结构，先从理论上给学生一个鲜明而形象的印象，趁着学生兴趣较浓的时候，适当地引入代码实现，不建议逐行讲解程序，而是在代码上用各种色彩分块，简单地讲一下代码实现过程模块，重点讲解核心代码。扫除学生对编程的心理障碍，激发兴趣，反而能够使得学生愿意在学有余力之余挑战编程。

2 云计算在实验环节中的应用设计

2.1 《数据结构》实验环节内容

在学生基本掌握数据结构理论知识后，通过上机实践，一方面使学生加深对课内所学各种数据逻辑结构、存储表示和运算基本内容的理解，学习如何运用所学的数据结构和算法知识处理应用问题的方法；另一方面，在程序设计方法、C语言编程环境以及程序的调试和测试等方面得到必要的训练。上机实践教学环节要求学生能设计结构清晰的算法和程序，学习分析所设计算法的时间和空间复杂度，选择足够的测试用例进行测试，并在实验结束后认真完成实验报告，整理所编写源程序代码和可执行程序，递交实验报告和程序。南京邮电大学《数据结构》课程教学大纲中设定的实践环节包括4个实验[1]：

实验一：线性表的基本运算及多项式的算术运算（2学时）；该实验主要考核学生在线性表的顺序存储结构和链表结构上的各种操作，其核心代码包括：顺序表上的插入、删除操作和单链表上插入、删除操作；

实验二：二叉树的基本操作及哈夫曼编码译码系统的实现（2学时）；该实验主要考核学生对二叉树数据结构的操作，其核心代码包括：二叉树的构造和拆解操作，二叉树先序、中序和后续遍历递归算法的实现与应用；

实验三：图的基本运算及飞机换乘次数最少问题（2学时）；该实验主要考核学生在图的邻接表数据结构上的各种操作，其核心代码包括：图的邻接表存储结构的构造、图的深度/宽度优先遍历算法的实现；

实验四：各种内排序算法的实现及性能比较（2学时）；该实验主要考核各种排序算法的实现，其核心代码包括：简单选择排序的选择操作、插入排序的插入操作、冒泡排序的冒泡操作、快速排序算法的划分操作、两路合并算法的合并操作和堆排序算法的调整操作等。

2.2 《数据结构》实验环节实施现状

实践环节首要是为了加强学生对理论知识的理解，其次才是对学生编程能力的锻炼。要求学生能够独立完成程序开发环境的搭建（如果采用非实验室已安装开发工具语言）、完整的程序开发（文件头、核心代码、测试代码）和调试工作。如要在2个学时之类完成上述工作，需要学生具备较为扎实的开发基础或至少在实验课之前快速熟悉开发工具，而这对于大二学生而言仅是一种理想状态，仅有少数学生可以达成，更不用说非计算机专业学生。实际的实验环节实施过程中存在问题包括：

（1）一半以上的学生第一次实验时耗费大量时间熟悉开发工具，即使是在《高级语言程序设计》课程学习中已经使用过的开发工具；

（2）书上仅提供算法主要方法，学生语法基础较差，不能正确补全程序的其他部分，如头文件定义、main函数中主要方法的调用、测试程序的开发；

（3）在main函数中写入固定测试数据，或需要学生手动输入特定格式的输入数据，不能多角度地展示算法效果，也增加任课教师课后验收学生实验结果的难度；更有甚者，在程序中伪造实验结果，产生虚假的演示效果；

（4）实验验收时，存在拷贝他人程序直接演示的情况，不能正确回答针对算法核心代码的问题；

（5）实验报告抄袭严重。

每学期仅有约10%的学生能够完整地在实验课时间完成实验环节的验收工作，而大部分学生无法在课堂完成程序开发，更不用说达到加强对理论知识的理解目的。对于任课教师来说，实验课的2学时时间大部分用于帮助学生调试程序，而造成程序开发工作停滞不前的主要原因是一些小的语法错误，而非与数据结构本身相关的问题。这对学生而言，不能充分利用教师的指导时间，其实也是一种资源浪费。从学生心理角度而言，在课后完成实验其氛围不如集体上机，而且很容易产生消极态度和惰性，这也导致了实验程序和报告存在大量抄袭现象。而部分态度认真的学生，在课后继续实验，但是因为不能和任课教师实时互动，导致遇到困难无法及时解决。

因此，如何能够让学生在实验上机时专注于数据结构和算法核心代码编写与测试（尤其是针对非计算机专业学生），减轻学生对编程语法问题的畏惧感，提高实践环节效率，达成实验目的，是《数据结构》课程实践环节所面对的最大难点。

2.3 云计算在《数据结构》实践环节的应用

云计算是一种基于互联网的计算新方式，通过互联网上异构、自治的服务为个人和企业用户提供按需即取的计算[2]。著名咨询机构Gartner将云计算定义为“云计算是利用互联网技术来将庞大且可伸缩的IT能力集合起来作为服务提供给多个客户的技术”[3]。云计算的应用之一就是开发测试云。开发测试总是繁琐、易错和耗时的过程，特别是在准备测试环境上面，还有会遇到诸如测试资源管理混乱，难于重现问题发生的环境和缺乏压力测试所需要的强大计算能力等棘手问题。而开发测试云能有效解决上面这些问题，其通过友好的Web界面，可以预约、部署、管理和回收整个开发测试的环境，通过预先配置好（包括操作系统，中间件和开发测试软件）的虚拟镜像来快速地构建一个个异构的开发测试环境，通过快速备份/恢复等虚拟化技术来重现问题，并利用云的强大的计算能力来对应用进行压力测试。

所做实验是课内实验，一般是随着理论教学进度情况进行实验安排，四个实验不具备连续性，间隔至少2周以上。一般高校计算机实验室网络环境较好，但是出于安全考虑，电脑会定期还原。因此，仅为某个课程在计算机实验室内部进行开发测试私有云平台的部署，不太符合实验室的实际情况。而租赁公有云进行实验，费用不菲。考虑到以上情况，设计以下基于云计算技术的实验环节实施方案（如图1所示）：

图1 实验环节实施过程

准备工作阶段：课程组教师提供台服务器，按照数据中心管理软件搭建私有云数据中心；课程组教师创建初始虚拟机，在该虚拟机上部署实验开发环境（主要指开发工具软件和数据库软件）和实验报告撰写工具（Office软件），创建四个初始项目分别对应四个实验内容；初始项目包含所有必须头文件、库函数、配置文件、核心方法空白的主要代码文件（需具有大量注释）、数据读写接口（即数据库操作的主要方法已经给出）；数据库配置完成并导入多个测试实例用于算法验证；虚拟机设置成无网卡模式；课程组教师为申请使用云开发模式进行实验的学生（因为还是存在一些学生愿意挑战项目编程开发工作的全部过程），创建初始虚拟机副本；

实验课时内实施阶段：课程组教师为学生启动虚拟机副本，提供给学生虚拟机IP地址和初始密码；向学生简单演示实验开发过程、数据读写接口的调用方法和实验测试方式；学生通过实验室台式机远程访问虚拟机，利用开发工具启动初始项目，根据项目内文件注释进行核心代码的开发工作；遇到问题和与任课教师实时沟通，及时解决问题；

实验课时外实施阶段：学生在课外可以在同一个开发环境下继续开发工作，如遇到问题无法解决，可及时给任课教师在线留言（一般任课教师都会给学生提供在线答疑途径），任课教师可以登录特定虚拟机帮助学生定位问题，找到解决方案；学生必须在虚拟机指定目录下的模板上进行实验报告撰写工作；

实验验收阶段：任课教师可以登录各台服务器，检查学生项目完成情况，并给出实验成绩。

3 应用实施与效果

课程组准备4台惠普2U机架式服务器，配置为8核、16G内存、3TB硬盘；服务器安装XenServer构建私有云数据中心；初始虚拟机配置为：1CPU、2G内存、20G硬盘，安装 Windows Visual Studio 2010、Windows Office软件、MySQL、初始四个实验项目和实验报告模板；每台服务器上可同时启动8台虚拟机，共计32台虚拟机，能够满足大部分学生申请。

该方案可以一定程度上缓解或解决该课程实践环节所遇到的一些问题，在应用效果上具有以下优点：

（1）学生在实验室可以专注核心代码的调试，达成实验环节的首要目的，即加强对数据结构理论知识的理解；

（2）便于了解学生实际开发的参与情况，并可进行少量限制（无网卡或网络设限模式，无法使用USB，不能进行拷贝和文件传输），一定程度上降低学生仅用简单代码拷贝蒙混过关的情况；

（3）课程组教师所需要进行的准备工作较为简单，不涉及新系统的开发；

（4）学生可共享测试平台资源，无需实验室提供任何软件安装、备份或维护工作；

（5）可实现快速的课后代码验收工作，任课教师只需要查看数据库中的实验结果记录即可了解学生代码的正确性，也可以快速执行指定路径下的可执行文件，演示学生所开发程序；

（6）学生很难拷贝他人实验报告。

但是也存在以下不足之处，尚待改进：

（1）实验代码和报告的收集，需要任课教师在验收阶段逐台机器去收集；因为项目代码和实验报告都在指定目录下，可以开发简单的收集小程序进行批量收集；

（2）代码验收目前还是需要教师手动检查数据库中的计算结果；可以开发简单验证程序，进行自动化的检验；

（3）因为硬件资源数量不足，该实施方案不能覆盖所有学生，后期将考虑租赁公有云服务器。