新工科教育中以提高程序设计能力为目标的教学设计与实践

章丽玲

（湖北第二师范学院 计算机学院，武汉 430205）

1 引言

当前，新工科教育已成为教育界的热门话题。新工科教育的核心是培养面向新兴产业和新经济需求的工程实践能力强、创新能力强，能够解决复杂工程应用问题且具备国际竞争力的高素质复合型“新工科人才”。[1]程序设计能力是新兴产业如人工智能、大数据等的核心能力，它是衡量计算机类专业学生必备的基础技能，是检验计算机相关专业毕业生质量的重要标准。[2]如何培养具备解决复杂问题的程序设计能力的新工科人才，是目前高校计算机专业教学改革的重点和难点。

数据结构是计算机及相关专业的专业基础课，在整个课程教育体系中起到奠基的作用。该课程学习的好坏直接影响学生的程序设计水平和编程实践能力，并对后续课程的学习产生深远的影响。[3]然而数据结构课程的特点是知识点多，算法抽象不易理解，大多数学生对数据结构的学习有畏难情绪，导致学生学习的信心和动力不足。本文构建以学生为中心，以教师为主导的启发式教学。[4]通过教学设计，采用“读、仿、改、创”的模式，由浅入深进阶式引导学生掌握数据结构相关算法。为了激发学生学习兴趣和学习动力，在教学过程中，精心设计教学问题，引导学生主动思考。通过思路引导、举一反三等方式，让学生真正吃透算法，并能灵活运用算法，做到“授人以渔”。

2 教学设计

传统的数据结构课程看重算法思路的讲解，算法大多以伪代码的形式描述，[5]对学生是否能够编程实践通过没有要求，导致学生只懂算法原理，不能学以致用，更不能基于某个算法进行扩展。最好的办法是设计符合学生认知规律的方式来组织教学，由浅入深进阶式引导学生掌握数据结构核心原理与算法。本文设计的启发式教学模型如图1所示，模型中“读、仿、改、创”四阶段围绕提高程序设计能力这个目标进行。四阶段内容相辅相成，互为前提，形成教学闭环。读：读懂程序代码，分析算法的时间复杂度、空间复杂度。仿：模仿，仿照，在读懂源程序的基础上，能够模仿编写相似的程序，做到触类旁通、举一反三。改：改写，是在模仿程序的基础上，能够完成相似算法的扩展，提高算法的应用。创：创造，创新，是在改写的基础上，有所领悟，思维升华。由于代码是静止的，程序只有运行才有生命。因此，在教学过程中，采用程序驱动的方式[6]，要求学生对每一个算法都能编程实践通过，理论联系实际，才能真正提高学生的程序设计能力。

图1 启发式教学模型

3 教学实践

现以顺序表的应用举例说明。顺序表，顾名思义是采用顺序存储结构，而顺序存储结构的主要特征是，所有的元素按照其逻辑顺序依次存储到对应指定存储位置开始的一块连续的存储空间中，[7]最大的优点是可以随机存储；缺点是为了保证其逻辑顺序不变，在插入、删除等操作的时候，往往伴随大量的移动操作，如果移动操作频繁，往往会降低程序效率。因此，在讲解顺序表的应用的时候，需要跟学生讲透彻——提高顺序表算法效率的核心因素，是尽量地减少移动操作。

实例：请设计一个尽可能高效的算法，按要求将顺序表分成两部分，即以顺序表L 第一个元素为分界线（基准），将所有大于等于它的元素移到该基准的后面，将所有小于它的元素移到基准的前面。[7]假设元素类型ElemType为int整形，算法要求如图2所示：

图2 算法要求示意图

针对这个实例，老师首先提问：“请问，能否用‘重建法’实现，为什么呢？”引导学生思考。根据学生的回答情况，老师对“重建法”的特点给出总结，解析为什么不能用“重建法”的原因。由于算法要求尽可能高效，要求算法的时间复杂度和空间复杂度尽可能低，而重建法，其核心思路是采用赋值的方法按要求将数据拷贝到一个新的顺序表中，因其空间复杂度为O（n），不符合高效算法的要求，接着给出高效算法思路。为了提高效率，减少移动操作，引入两个伪指针i和j。i指向顺序表的第一个元素，j指向顺序表的最后一个元素。以第一个元素为基准，j从右向左找一个小于等于基准的元素x，i从左向右找一个大于基准的元素，将两者交换，直到i大于或等于j。

3.1 读算法

引导学生认真读算法的每一条语句，理解算法的设计思路、算法的逻辑执行步骤，分析算法的时间复杂度、空间复杂度。算法的代码如下：

通读上面的算法，理解算法的思路。该算法首先把基准元素L-＞data[0]保存到临时变量tmp中，然后给两个伪指针i，j附初值，i=0。i的初始值为顺序表的最小下标，j=L-＞length-1，j的初始值为顺序表的最大下标，j从右向左找一个小于基准元素，i从左向右找一个大于基准的元素，然后将两个元素交换，直到i＜j为假，循环结束。将L-＞data[0]与L-＞data[i]交换，通过分析，该算法的时间复杂度为O（n），空间复杂度为O（1），性能优于重建法。为了提高学生的编程能力，要求学生在DevC++编程环境中，在main（）函数调用该算法，并给出相关的数据实例测试通过，测试数据为：3 8 2 7 1 5 3 4 6 0。测试显示运行结果如下图3所示：

图3 实例1运行结果

3.2 仿算法

通过读算法，学生能够理解算法的思路，但还不会灵活运用。因此，第二步就是引导学生模仿算法，即在原算法的基础上作很小的扩充调整，目的是指导学生能够对算法思路进行灵活运用，做到举一反三。

调整一。如果把题目的要求改为：将所有的奇数移动到偶数之前。调整后，编程的整体思路不变，同样设置两个伪指针i，j。j的初始值为顺序表的最大下标，j从右向左找一个奇数元素；i的初始值为顺序表的最小下标，i从左向右找一个偶数元素，然后将两个元素交换，直到i＜j。算法的整体框架不变，无需设置临时变量tmp，只需要将判断条件改为判断是奇数还是偶数即可。修改部分的代码如下：

同样要求学生通过DevC++编程环境编译通过，给出尽量多的测试用例测试通过。

举一反三。可以把基准设计为任何整数x，不再固定为顺序表的第一个元素，也不固定为奇数或偶数。如要求学生调整算法使所有小于x（任意值）的元素放在所有大于等于x 的元素的前面，按照实际的要求将顺序表分为两部分。通过仿算法，学生可以掌握类似相似的问题，发散了学生编程思维，提高学生编程实践能力。

3.3 改算法

原算法的思路只涉及到将一个顺序表拆分为两个部分，如果把算法要求改为将顺序表拆分为符合条件的三部分，引导学生思考。如何修改算法才能实现呢？以荷兰国旗问题为例：设有一个条块序列，每个条块为红（0）、白（1）、蓝（2）三种颜色中的一种。[8]设计一个尽可能高效的算法，使得这些条块即按红、白、蓝的顺序排成荷兰国旗图案，假设该序列采用顺序表存储。

思路引导。拆分两部分需要用2个伪指针，那么拆分三部分需要3个伪指针，用不同的伪指针指向不同的区间，伪指针i，j，k。初始的时候，i=-1，j=0，k=L-＞length。将0～i 表示0 区间（红色），k～n-1 表示2 区间（蓝色），中间部分为1区间（白色）。i和j指针从左往右移，k指针从右往左移，指针j从头开始扫描顺序表L中的所有元素。针对j所指向的元素，如果j指向元素0：说明它属于前部，i增1（扩大0元素区间），将i、j位置的元素交换，j++。j指向元素2：说明它属于后部，k减1（扩大2元素区间），将j、k位置的元素交换，此时j位置的元素可能还要交换到前部，所以j不前进。j指向元素1：说明它属于中部，保持不动，j++。

程序代码如下：

思路扩展。可以将荷兰国旗问题扩充到任一顺序表，按照一定的条件将顺序表划分三个区间，而不是固定为相同的元素。解决的思路与上面类似，程序的框架不变，只需要修改中间的判断条件即可。

举一反三。问题：就地循环位移，设将n（n＞1）个整数存放在一维数组R中。设计仅用O（1）辅助空间，将数组R 中保存的序列循环左移p（0＜p＜n）个位置，即将R 中的数据由（X0，X1…..Xn-1）变换为（Xp，Xp+1，…..Xn-1，X0，X1，……Xp-1）。

由于要求O（1）的辅助空间，因此仍然不能用“重建法”，需要引导学生如何减少移动的操作。

算法思路如下：

1：将数组R（X0，X1…，Xn-1）看成顺序表，将其分成两部分（X0，X1，……，Xp-1）和（Xp，Xp+1，…..，Xn-1）。

2：分别对这两部分中的元素进行原地逆置，中间结果为（Xp-1，Xp-2，......X1，X0），（Xn-1，Xn-2，......Xp-1，Xp）

3：再对整个数组进行逆置，最终实现算法要求，结果为（Xp，Xp+1，…..Xn-1，X0，X1……Xp-1）。

该题思路的核心是数组逆置，而数组逆置算法同样可以采用上面类似的顺序表的算法思路，即设计两个伪指针i，j，i的初始值为数组的起始下标，j的初始值为数组的最大下标，i和j对应的元素循环交换，i从左往右移，j从右往左移，循环条件为i＜j。详细代码如下：

最后同样需要在编程环境中实现通过。

分析该算法的时间复杂度为O（n），空间复杂度为O（1），属于高效的算法。

3.4 创新

在前面读、仿、改的基础上，最后的目标是引导学生对所学到的和所领悟的知识进行归纳和总结，形成自己的知识体系，并且能够在所悟的基础上进行创新，提高自己的思维创新能力。如上文读的实例中，引导学生进一步优化算法，读算法中调用了交换函数，而一次交换函数，需要执行3 次赋值操作，能否直接赋值呢？要求学生回答，而结果肯定是可以的，因为基准已经暂存在临时变量tmp中，可以采用赋值语句，从而进一步提高运行效率。代码修改非常简单，只需将while循环体内部改为下面的代码即可。

改进后算法的思路其实就是经典算法“快速排序”的一趟划分过程。[9]如果需要对n个元素的顺序表进行递增排序，需要对产生的两部分分别重复上述过程，这就是典型的递归的分而治之的思想，即将大的问题分解为两个相似的小问题，直到每个小问题内只有一个元素或空为止。简而言之，每趟使表的第一个元素放入适当的位置，将表划分为两个子表，对子表按递归方式继续这种划分，直至划分的子表的长为1或0。将上述算法作简单的修改，就是经典的快速排序算法了。

通过DevC++编程环境编译通过，采用原先的测试数据，运行结果快速排序算法结果如图4：

图4 综合运行结果

最后对快速排序进行简单的算法分析，最好的情况是每一次划分都将n 个元素划分为两个长度差不多的子区间，这样的递归树的高度为O（log2n）。而每一趟划分的时间复杂度为O（n），因此，此算法的时间复杂度为O（nlog2n），空间复杂度为O（log2n）。相对于简单的冒泡排序，其算法的平均复杂度从O（n2）提高到O（nlog2n），算法的效率得到提高[10]。

总结顺序表进行拆分的应用实例，不管是以某一个数为基准，还是按照某种特征进行拆分，为了减少移动操作的次数，都可以设置两个伪指针。一个指向顺序表的初始位置，一个指向顺序表的末尾位置。通过比较两个指针对应的值进行相关的操作。采用这种方法，可以提高顺序表的运行效率。通过对算法的总结归纳，使学生渐渐形成了对复杂问题进行分而治之的思维方式，对今后类似的算法设计都有很大的帮助。

4 小结

上文以顺序表的应用为实例，在教学中采用理论与实践相结合的方式，通过“读、仿、改、创”四个阶段由浅入深循序渐进地进行启发式教学。这种教学模式和方法可推广到其他的典型数据结构，如单链表、二叉树和图等。通过问题导入、思路引导、思维扩展的方式，引导学生思考，使学生能够做到举一反三，触类旁通，提高了学生学习动力，挖掘了学生的学习潜能。通过“改”和“创”两个步骤，引导学生进行思维升华，学会归纳和总结，并进行创新。采用程序驱动的方式，提高了学生学习的成就感，促进了学生的程序设计能力和编程实践能力的提高。

5 成果展示

通过20级计科两个班进行教学实践，对照19级计科两个班学生期末成绩，采用算法设计题得分率和期末成绩平均分进行比较分析。比较结果如表1所示，从表一数据可以看出，算法设计题1、算法设计题2和期末平均分的增长率均超过了10%。另外，在刚刚公示的第十三届蓝桥杯软件设计大赛全国决赛获奖名单中，20级学生在本次全国总决赛中，共获一等奖1项，二等奖3项，三等奖3项，优秀奖6项，创造了近年来最佳成绩。由此可知，按照“读、仿、改、创”四个阶段进行启发式教学，提高了学生的程序设计能力。该教学方法不仅适合《数据结构》课程，同时也适应所有的程序设计类课程，具有一定的推广价值。

表1 19计科和20计科数据结构成绩对照表