基于分层实验和课程答辩的数据结构实践教学改革研究

林丽惠 魏 毅

（武夷学院 数学与计算机学院，福建 武夷山 354300）

“数据结构”是计算机程序设计的重要理论技术基础，是计算机学科的核心课程，其在计算机科学中是一门综合性的专业必修课。[1]“数据结构”课程的重要性可以从其在用计算机解决问题的过程中发挥的作用体现出。用计算机解决问题的过程及数据结构在此过程中发挥的作用如图1所示。

图1 计算机解决问题的过程及数据结构在此过程中发挥的作用Figure 1 The process of solving a problem by computer and the role of data structure in this process

“数据结构”课程的教学要求学生掌握分析计算机要处理的数据的特性，为这些数据选择合适的逻辑结构、存储结构，并设计相应的算法解决实际问题。学生学习“数据结构”课程的过程也是进行复杂程序设计训练的过程。通过“数据结构”课程的学习，学生将具备编写结构清晰、正确易读和符合软件工程规范的程序的能力。[2-3]“数据结构”教学包括理论教学环节和实践教学环节。数据结构的逻辑思想能在理论教学环节中陈述清楚，但是逻辑思想的具体实现则要通过实践教学环节完成。[4]实践教学环节十分重要，通过实践教学环节，可以加强和提升学生对“数据结构”理论教学环节内容的理解。通过为某一种具体数据结构选择合适的存储结构，并设计相应的算法解决问题，真正在计算机上实现某一种数据结构，理解“数据结构”的真谛；同时通过综合型实验，综合运用所学课程知识，选择适当的数据结构，并设计相应算法解决实际问题，进一步锻炼学生进行复杂程序设计的能力，让学生感受软件开发的规范，全面培养学生综合运用知识的能力。

但是长期以来，我们发现“数据结构”实践教学环节并没有达到预期的效果，存在多方面的问题，影响了计算机学科高素质人才的培养。目前实践教学的现状存在以下问题：

（1）“数据结构”实践环节对学生的程序设计能力要求较高，而学生对“数据结构”的先修课程中的程序设计知识点掌握不够扎实，造成学生感觉编写程序困难，对“数据结构”的实践产生畏惧心理。

（2）“数据结构”课程内容的理解比较抽象，“数据结构”实践环节要求将抽象的理论知识通过程序设计实现，而学生不能将数据结构中的逻辑结构与实际在计算机中的存储结构有机结合并设计合适的算法解决问题，造成学生不能正确理解数据结构，从而对“数据结构”的学习丧失积极性和主动性。

（3）“数据结构”实践环节的考核，目前大多是依据实验报告的成绩作为实践环节的考核成绩，而部分学生在“数据结构”实践环节中具有依赖心理，不喜欢动脑思考，不能独立调试程序，依靠抄袭实验报告来应付实践环节的考核，影响了“数据结构”实践环节的教学效果。

因此，我们迫切需要对“数据结构”实践环节的教学进行改革，寻求突破，提高“数据结构”实践教学环节的效果，提高学生进行复杂程序设计的能力[5-6]。

1 实践教学内容改革

合理安排和精心设置实验内容将有助于帮助学生逐步建立编写程序的信心，让学生体会到通过努力克服困难解决问题的成就感，提升学生对“数据结构”课程的理解和兴趣，锻炼学生将数据结构理论转化成编写程序解决实际问题的能力[7]。

1.1 基础知识实验设置

根据多年的教学观察发现，学生在“数据结构”实验编程的薄弱环节主要集中在以下方面的C语言程序设计知识点：描述存储结构时结构体的定义、结构体成员的引用方法，类型定义“typedef”的使用方法，指针、动态内存分配的原理及方法，算法和程序的区别与转换方法，函数返回执行状态的理解，程序组织及代码复用的方法等。针对这部分学生掌握薄弱但是对“数据结构”实验编程又是极其重要的内容，在“数据结构”实践环节的初始，设置基础知识实验，实验内容涵盖上述知识点，对上述知识点内容进行编程集训，起到对C语言程序设计复习巩固和查缺补漏的作用，为学生更好地理解“数据结构”提供先修知识准备，为“数据结构”实验编程消除先修知识上的技术障碍。

1.2 验证型实验设置

验证型实验主要是上机实现数据结构课程各个章节中涉及的相关基础算法，使学生进一步领会其原理和验证算法的正确性。验证型实验的实验内容主要是实现各种数据结构采用不同存储结构时的基本操作，包括建立、查找、插入、删除等基本操作。学生通过做验证型实验，可以加深和巩固对不同数据结构不同操作的理解，深刻体会同一种数据结构采用不同存储结构时有哪些不同的特点及操作方法的异同之处，同时也为后续的设计型实验和综合型实验打下扎实的理论和实验基础。[8]验证型实验还能检测学生的基础编程能力，学生也可以在验证型实验的过程中对编程知识进行补缺补漏，提高基础编程能力。同时，通过验证型实验编程实现的算法可以保留，提供给后续的设计型实验和综合型实验调用。这样，在后续的设计型实验和综合型实验中，学生就可以不要纠结在一些细小的编程问题，可以将精力用在更高层次的数据结构和算法的设计上。做好验证型实验能够激发学生学习“数据结构”的兴趣和信心。验证型实验的实验内容设置如表1。

表1 验证型实验的内容Table 1 The content of verification experiment

例如，在验证型实验“线性表的基本操作”中，要求学生编写程序分别实现顺序表和链表的整体建表算法和各种基本运算，并在此基础上设计一个主程序，完成建立顺序表和链表以及插入元素、删除元素、输出顺序表和链表元素的功能。通过做这个实验，能够增进学生对“数据结构”本质的理解，使学生能够掌握非数值计算的程序设计问题中计算机的操作对象以及对象之间的关系的表示方法，能够掌握对这些操作对象进行各种操作的方法，同时也能够更加深刻地理解“数据结构+算法=程序设计”这个有关程序设计的经典名句。

1.3 设计型实验设置

设计型实验通过采用数据结构的基本方法，分析并且选择某种数据结构，采用某种存储结构，设计合适的算法并加以实现来求解问题。[9]通过设计型实验，学生才能真正理解如何应用“数据结构”来解决实际的问题，真正理解学习“数据结构”课程的意义。设计型实验通常还具有一定的实用性和趣味性，可以增进学生对实验课的兴趣。因此，根据教学目标，精心设置出适当难度和规模的设计型实验是非常重要的。

例如，针对队列的应用，设置“猴子选大王”这个设计型实验。给出“猴子选大王”的问题描述如下：n只猴子（n不超过50）围成一个圈。从某一只开始依次给猴子们编号，从1到n。然后从第一只猴子开始依次报数，从1数到m，报到m的猴子离开此圈。离开此圈的猴子的下一只猴子再开始从1报数，报到m的猴子再离开此圈。以此循环，直到圈中剩下最后一只猴子,这只猴子就是大王。要求编程实现，输入n和m，依次输出离开圈子的猴子编号，然后输出大王的编号。[10]对于此问题的解决,首先要求学生对问题进行分析,选择合适的数据结构。根据问题描述，n只猴子围成一个圈，正好对应数据结构里的循环链表，每只猴子为循环链表的一个结点。“从某一只开始依次给猴子们编号，从1到n。”的操作即为：给循环链表的结点编号，从某个结点开始编号，从1到n。“从第一只猴子开始依次报数，从1数到m，报到m的猴子离开此圈”的操作相当于从循环链表中删除一个结点。经过分析可知，该问题的程序编写包括以下实现过程：建立单链表；报数利用do-while循环实现猴子的出列 （即删除结点操作）；判断循环链表是否最终剩下一个结点，剩下的一个结点即为大王。

综上，学生做设计型实验的过程实际上就是进行了包括分析、设计、编码和调试等一系列操作的训练。因此，学生通过做设计型实验，能够更加深刻地理解和掌握数据结构的选择和应用、数据结构的存储表示方法，并且通过设计合适的算法巩固并提高分析问题、解决实际问题的能力。

设计型实验的实验内容设置如表2。

1.4 综合型实验设置

综合型实验是综合运用“数据结构”课程中多个相关知识点求解比较复杂的问题，或者同一个问题用多种方法求解，能够提升学生对“数据结构”的整体认识，提高学生分析解决复杂问题的能力。综合型实验的题目有很多，常见的综合型实验题目有：通讯录管理系统问题、停车场管理系统问题、校园导航系统问题、八皇后问题等。

例如，“停车场管理系统”的问题描述如下：有一个只有一个大门可以进出的狭长停车场，可以停放n辆汽车。最早进入停车场的车停放在狭长停车场的最靠里面的车位，其它车辆按到达时间依次从里往外停放。如果停车场车位已满，后面到达的车辆依次在停车场大门外的便道上停放等待。如果停车场有车辆要离开，排在这辆车后面进入停车场的车辆都要先退出停车场，等待这辆车离开后，再依原来的次序依次开进停车场停放。一旦停车场有空余的车位，排在便道上的车辆依次开进停车场停放。每辆车都依据其在停车场内停放的时间长度交费。在便道上停放的车辆不收费。要求编制一程序实现对停车场的管理。对于此问题的解决,首先要求学生对问题进行分析,选择合适的数据结构。根据问题描述，可以设计两个堆栈，分别用来模拟狭长停车场和临时停车场。当狭长停车场有车辆要离开时，排在这辆要离开的车后面进入停车场的车辆都先退出到临时停车场，为要离开的车让路。选择堆栈来模拟狭长停车场和临时停车场是因为堆栈具有“后进先出”的特点，这与停车场车辆进出的顺序要求是相符的。同时，使用一个链队列来模拟当停车场车位已满时需要停放车辆的停车场大门外的便道。选择队列来模拟便道，是因为这个便道上的车辆将具有“先进先出”的特点。一旦停车场有空余的车位，排在便道上的第一辆车离开便道，开进停车场停放，便道上原来的第二辆车成为便道上的第一辆车。这个操作就是删除链队列的队头元素，并将这个队头元素插入到狭长停车场这个堆栈中。以上“停车场管理系统”问题同时使用到了栈和链式队列两种数据结构。

设计数据结构的过程，首先要求设计逻辑结构，然后再设计存储结构，最后是在此基础上设计算法，解决问题。这过程中每个环节都对问题求解的性能有重要影响。这就要求学生对特定的问题不仅能够设计出相应的数据结构和算法，还要对所设计的算法的相关性能（包括时间性能和空间性能等）进行分析比较,然后给出最合适的选择。因此，综合型实验还要求学生能够对同一个问题用多种方法求解，再根据实际情况选择一种最优的解决方法。

综上，通过做综合型实验，能够增强学生综合运用课程中的知识与方法的能力，能够提升学生对给定的问题设计出合适的数据结构和算法并解决实际问题的综合实践能力。

2 实践教学模式改革

在实践教学中，循序渐进地安排实验内容，从验证型实验，到设计型实验，再到综合型实验。每个章节的实验内容均按由浅入深、由易到难的原则设计不同层次的实验。验证型实验和设计型实验属于必做实验，综合型实验属于选做实验，以满足不同层次的学生需求。

为增强教学效果，教师应提前布置实验任务，要求学生课前预习实验内容，带着问题参加实验。在实验课上，教师重点讲解实验中比较关键的内容，采用启发式的方式辅助学生解决问题。在实验课结束前，对实验内容和出现的问题进行总结。并且在课后加强与学生交流沟通，通过课程网站和教师主页进行课后答疑，切实保证学生能真正掌握实验所要求的内容，切实保障实践教学应有的教学效果[11]。

3 实践教学考核改革

对于实践教学考核，除了提交实验报告，增设课程答辩环节。答辩时主要采用学生讲解、演示测试过程、老师提问和小组讨论的方式，以便深入了解学生对实验内容的掌握情况。实践教学考核的成绩为实验报告成绩和课程答辩成绩的综合成绩。实践教学考核增设课程答辩环节后，部分偷懒的学生就不能再依靠抄袭实验报告来应付实践环节的考核，激发他们必须通过努力扎实掌握实验内容，[12]切实保障实践教学应有的教学效果。

4 结论

本研究从实践教学内容、实践教学模式和实践教学考核等方面进行数据结构实践教学改革研究，提出一个基于分层实验和课程答辩的数据结构实践教学改革方案。在实践教学内容上，循序渐进地设计基础知识实验、验证型实验、设计型实验、综合型实验等不同层次的实验，以满足不同层次的学生需求。在实践教学模式上，加强实验课课前和课后的辅导。要求学生课前预习实验内容，带着问题参加实验，通过课程网站和教师主页进行课后答疑。实践教学考核增设课程答辩环节。使用本研究提出的数据结构实践教学改革方案，经过对连续四届计算机科学与技术专业的《数据结构》实践教学进行改革探索，教学实践表明本研究实施的教学改革方案能够切实保障数据结构实践教学取得应有的教学效果。主要体现在对《数据结构》这门课程，学生学习的积极性和主动性提高了，综合应用数据结构的知识编写程序的能力也提高了。