高职计算机专业《数据结构》课程教学设计
中图分类号： G642.4 文献标识码：A 文章编号：1009-3044（2016）03-0174-04
1 前言
《数据结构》课程是高职计算机专业重要的专业基础课。该课程通过学习程序设计中常用的基础数据结构，介绍一些重要的程序设计思想，提高学生的逻辑思维能力和编程技能，培养学生的分析问题、建模与解决问题能力。同时，该课程的学习内容能够促进学生对后继课程的学习内容的理解。例如，高级编程语言C#或Java中有一些库函数实现了对集合元素排序的功能。而这些功能正是以数据结构课中介绍的排序算法为基础的。
根据我们多年的教学经验，在高职计算机专业的课程体系中，数据结构普遍被学生认为是比较困难的一门课程。造成困难的原因大致有以下几个。首先，由于高职计算机专业学生就业的特点，决定了高职学生很少从事基础和底层程序设计，或者从事与数据结构以及程序设计相关的理论研究。因此，数据结构课的学习内容在工作中直接应用的机会很少。这导致部分学生甚至教师对学习数据结构课的必要性存在疑惑，对该课程重视程度不足。其次，数据结构课的概念和算法抽象，理论性强，对学生逻辑思维能力要求高，学习的门槛较高。最后，高职学院学制较短，导致一学期内的专业课程密度高，学生学习时间不足。
现有的高职教材或本科应用型教材例如参考文献[1-4]的内容编排，多沿袭自传统本科数据结构课。一般依线性结构，树结构和图结构的顺序编排，逐次介绍各种数据结构，给出其定义，详细介绍其物理存储结构和基本性质，并穿插其应用的一些例子。其覆盖的知识面广，内容和体系较为完整，条理清晰。但是由于高职计算机专业数据结构课程学时较少，其专业学习的实践性强，学生逻辑思维能力稍弱等特点，这种沿袭自本科教学的授课内容组织方式不完全适合高职学生。虽然针对课时偏少的情况，一般高职课本会对本科课本作一些删减或简化，但其内容构成仍没有本质上的改变。因此，课程内容的选择、组织与编排增加了高职学生学习数据结构课的难度，而未能解决上述造成困难的几个问题。
我们认为，数据结构课程能够训练学生的逻辑思维能力，促进学生深入理解与专业相关的基本编程思想，且其内容与多门后继专业课程相关，因此对计算机专业的学生而言，学习数据结构课的必要性毋庸置疑。而针对高职教育学时少，实践性强的特点，对课程大纲、课程标准、教学内容和教学方式进行改革，使得高职学生能够更好地学习该门课程，改进学习体验，改善学习效果，则势在必行。数据结构课的改革，结合当前高职教育改革的方向，在课程设计方面应该以突出能力培养，以项目为载体，以任务训练岗位职业能力，以及知识理论实践一体化为原则[5-6]。
本文总结了我们在高职计算机专业数据结构课上进行的教学设计改革。我们在课程中引入任务驱动教学方式，设计若干项目供学生在课堂上练习，以项目覆盖课程的各知识点，通过项目引入相关的概念，并作讲解。在课堂教学方式上，以解决问题，完成项目代替抽象的理论教学。由于避免了繁琐的基本概念讲解，缩短了理论教学用时，学生能够投入更多的时间与精力到编程实践练习。而通过练习，能够更好地理解抽象的概念。我们的课程改革，应用于计算机应用专业两届学生的教学实践中，取得了良好的效果。
2 教学项目设计实例
数据结构课程的主要内容大致可以分为三部分，即线性结构、树结构和图结构。其中，线性结构包含了几种重要的数据结构，如栈、队列、数组和串等。树结构的内容一般以最常用的二叉树结构为主。图结构是最为复杂的结构，涉及算法的内容比较多，如图的最短路径算法，图的最小生成树算法和图的连通分支算法等。除此以外，课程还包括查找和排序算法等重要内容，这两类算法同时涉及线性结构和树结构。通常还会介绍递归、指针等重要的编程思想和内容。
我们的教学项目设计思路，是选取相对简单而具有代表性的算法题目，结合一些应用的背景，构成我们的项目，内容力求覆盖基础的数据结构，如线性结构、队列、栈和二叉树等。学生通过完成项目中的一个个任务来学习数据结构的抽象概念。有些方向内容丰富，我们从中选取少量相对简单，然而具备代表性的例子作为任务，使得学生更易上手，尽快建立对一些抽象概念的认知。例如查找和排序操作既可以在线性结构上，也可以在树结构上进行。但我们不考虑树结构，仅仅以线性结构上的问题组成我们项目。又如从图结构的多个算法求解问题中，我们选取容易理解的连通分支求解算法作为教学项目。
作者从事高职计算机应用专业的数据结构课教学。该课程的学时大约为4学时×16周，一般在一年级第二学期开设。根据课时和学生的具体情况，我们在一学期的课程中为学生设计三至四个项目，并主要以学生完成项目的情况作为学期总评的依据。以下以我们为2014级学生设计的项目为例，对课程教学项目设计作一个详细介绍。
我们一共设计了四个项目，具体如下。
迷宫：以一个n×m的{0，1}-矩阵表示一个迷宫。其中，0表示可以通行，1表示有障碍，左上角和右下角均为0，分别表示入口与出口。编写程序判断此迷宫是否存在一条从入口到出口的路径，如存在则输出该路径。
二叉树的构造和遍历：对教师以绘图形式给定的一棵二叉树，编写程序构造该二叉树并输出该二叉树的前序、中序和后序遍历的结果。可以结合一个具体应用进行教学。例如，可采用二叉树的一个典型应用，即表达式的几种表示法。教师输入一个表达式，学生根据其建立一个二叉树，并通过三种遍历方式输出表达式的波兰表示法，逆波兰表示法和中缀表示法。 （1） 查找和排序：对教师给定的一个有序整数序列，编写程序接收用户输入的一个整数，使用二分查找法在序列中查找该整数。对教师给定的一个无序的整数集合，使用插入排序、冒泡排序和选择排序中的至少两种为该集合排序。此问题的一个典型的应用情景是学生的考试分数排序。
（2） 图的连通分支：某班级有n位同学。现组织外出旅游，并拟将全班同学分成若干小组集体行动。现在给定一个图表示本班同学之间的朋友关系。其中以结点表示同学，且若两位同学为朋友关系，则对应的两个结点以边连接。请根据朋友关系将全班同学分成若干个小组，使得有朋友关系的两位同学在都同一个小组中。此题目等价于求朋友关系拓扑图的最大连通分支。
可以看到，这四个项目均具有丰富的理论意义和具体的应用背景。它们覆盖了现有数据结构课本的大部分知识点。表1中列出了数据结构课的大部分知识点以及它们被各个项目覆盖的情况。课程中常见的数据结构，除了串以外，大部分为我们设计的项目所覆盖。同时我们的项目还覆盖了递归，指针，广度优先搜索和深度优先搜索等重要的程序设计思想。
为了引导学生分步完成练习，我们还为比较困难的项目设定预备任务。预备任务不同于一般的习题。它们有一定的独立性，可以提出来作为一个习题，但是又与我们的项目有机地结合在一起，可以认为是相关项目的一项任务。
对于迷宫问题，我们设定以下两个预备任务。
（1.1）写一个栈结构处理程序。每一个栈元素是含有3个整数（这里规定栈元素由3个整数组成，是为了迷宫项目做准备，见下文）的一个结构体。写出栈的初始化，入栈，出栈和判断栈空的操作。在main函数里面建立一个这样的栈，测试它。比如说，入栈若干个元素，例如 （1，1，0） 和 （2，2，0） ，然后出栈，并依照出栈顺序打印这些元素。
（1.2）围障。给定一个以n×m矩阵表示的迷宫，用全一把原迷宫包围起来，创建出一个新的 （n+2）×（m+2） 迷宫。打印出新的迷宫。
迷宫问题采用栈结构存储回溯的结点，每一个栈元素存储迷宫内一个结点的x、y坐标和回到该结点以后下一个可以探索的方向，共3个整数。第一个任务栈处理程序既是一个线性表的练习，也为迷宫问题准备好要使用的栈。我们允许迷宫第一行、最后一行、第一列和最后一列除了出、入口以外，还有其他0元素。但是这些0元素实际上不是在所有的方向上都可以通行。在第二个任务中，我们在迷宫四边添加全1，称之为围障，围障能够使得迷宫求解程序中的一些条件判断大为简化。该任务可以看成一个矩阵练习，并为我们即将探索的迷宫作了初始化。
对于图的连通分支问题，我们也设定了两个预备任务。
（4.1）图的表示。用矩阵表示教师用绘制方式给定的图，并在屏幕上打印出图的结点和边。具体内容包括定义和初始化一个矩阵，表示一个图，输出图的结点列表和图的边的列表。其中，图的结点以数字0，…，n-1 编号，图的每一条边以 （x，y） 的形式表示，x和y是边的两个端点的编号。
（4.2）队列的操作。编程实现一个整数队列的初始化，入队和出队的操作。程序里面定义和初始化一个整数队列；然后入队至少三个元素，按顺序打印出队列里面的所有元素；再出队至少两个元素，又按顺序打印出队列里面的所有元素。
第一个练习非常基本。它完成图在程序中的表示，学生学会把一个图转换为一个矩阵，同时从矩阵中读取出图的顶点和边。第二个练习是为了对图作广度优先遍历时使用队列结构作准备，同时也是一个线性表的练习。
3 教学内容的组织与课堂教学实践
依授课时间顺序，我们的教学内容组织为
一、线性结构；
二、预备任务（1.1）和（4.2）：队列和栈；
三、项目（1）迷宫问题，包括预备任务（1.2）；
四、树结构；
五、项目（2）二叉树遍历；
六、项目（3）查找和排序；
七、图结构；
八、项目（4）图的连通分支，包括预备任务（4.1）。
教学内容的组织以线性结构、树结构到图结构为主线索。
在线性结构部分，对线性表的基本概念作一些介绍后，我们布置预备任务（1.1）和（4.2），通过这两个练习介绍栈和队列的概念。同时，向学生介绍项目（1）迷宫问题和项目（4）图的连通分支，并说明预备任务（1.1）和（4.2）跟这两个项目的关系。在完成了预备任务（1.1）和（4.2）以后，布置项目（1）迷宫问题。迷宫求解问题的讲解，重点要解释清楚深度优先搜索的思想。
接下来是树结构的内容。我们介绍树结构相关的一些概念和重要性质。然后布置项目（2）二叉树遍历。二叉树遍历有先序、中序和后序三种方式。除了树结构内容，我们以递归方式实现二叉树遍历程序，通过这个项目向学生介绍递归思想。所以，此项目教学的重点之一是讲解递归的原理。教师可实现其中一种遍历方式作为例子，而让学生完成其他形式的遍历。如前所述，为了帮助学生更好理解二叉树的思想，可结合二叉树的典型应用，即表达式的三种不同表示方法来讲解。
随后的内容是线性表的查找和排序。完成项目（3）查找和排序方法。其中，查找算法以线性表的二分查找为例，讲解的时候我们与顺序查找作对比。二分查找必须应用于有序数组，而对于无序的数据则只能采用顺序查找，这说明了数据结构对算法设计的影响。
排序算法种类繁多（[7]），其中部分高效算法的时间复杂度能够达到O（nlogn）。但是这些算法对学生而言有相当难度，我们仅选取时间复杂度达到O（n2），而实现思路相对简单的几种算法作为项目的内容，教师可以在课堂上部分或全部实现要求的排序算法，然后让学生再重新自行完成。
最后是图结构部分。我们首先介绍一些和图相关的概念和基本性质。然后以（4）求图的连通分支为教学项目。项目（4）直接以一个实际问题的形式提出，揭示出图算法的强烈应用背景。在求解算法中，我们要求学生掌握使用广度优先搜索来访问图的结点。广度优先搜索的实现需要以队列作为待搜索结点的存储结构。因此，项目又结合队列的设计、实现与应用进行。有助于对理解线性表的相关知识，掌握其应用。 4 小结与展望
在计算机应用专业2013和2014级学生的数据结构课上，我们采用了本文所阐述的教学设计。实践表明，通过课程内容的调整与教学项目的设计实施，数据结构课程的授课和学习效果得到了改进。在课堂上，由于减少了大量抽象概念和性质的讲解，将精力集中于几个项目，使得教师有更多时间为学生分析问题和示范求解。在项目教学时间充足的情况下，教师在课堂上能够向学生演示部分困难的程序代码开发的全过程。对学生而言，通过解决问题而学习的方式更为直观，有助于编程实践能力的增强，对抽象概念的理解也有帮助。难度恰当的任务和老师课堂上充分的教学示范，降低了课程的门槛，提高了学生的自信心。在教学反馈中，学生普遍反映对授课内容和授课方式较能接受。在课后作业中，我们要求学生至少完成三个项目。大部分学生能够完成或超过此要求。
我们的教学项目设计，在教学内容、教学方式和体系结构上根据高职教学的特点进行了一些改革。我们对课程的大量内容进行了删减，挑选出其中的一部分，重新组织成为若干个教学项目。但是，我们所选取的内容仍然基于传统的数据结构课程。在信息技术蓬勃发展的今天，数据结构和算法的应用越来越广泛。数据结构课程的进一步改革，可以引入更多与实际应用相结合的内容，介绍一些新的算法思想，并通过一些精巧设计的例子，部分地实现这些思想。如参考文献[8]介绍了网络搜索的算法，以及由Google的始创者之一，拉里?佩奇提出的网页排序（PageRank）算法。其中以16个网页构成的一个小型网络为例子，说明了网页排序思想。设计和引入更多这一类新型和具有显著应用背景的项目，将会使得数据结构课变得更加生动，增强该门课程的吸引力，开拓学生视野，激发学生对算法设计乃至计算机科学的兴趣。
