“数据结构”课程强化算法应用的教学实践

王景珊

摘 要：“数据结构”是计算机类专业的核心课程，学习内容抽象难理解，理论教学与实际应用容易脱节，教学中应将抽象的数据类型与现实建立对应，加强学生对理论知识的感性认识。文章以Dijkstra算法和Floyd算法为例，分析强化算法应用的教学实践，同时挖掘算法内涵开展协同育人教学。

关键词：算法应用;Dijkstra算法;Floyd算法;协同育人

0 引言

数据结构是20世纪60年代提出并研究，20世纪70年代科学家Niklaus Wirth的著作《Algorithm+Data Structures=Programs》使得数据结构研究不断深入，20世纪80年代研究日臻成熟，成为一门完整的学科。它是一门介于数学、计算机软件、计算机硬件之间的综合学科，是程序设计的基础。

在知识飞速更新的时代，提高学生获得知识的能力，真正做到“授人以鱼不如授人以渔”，是教师应尽的责任。作为一门理论和实践并重的课程，理论教学讲授算法思想，实践教学实现由抽象到具体的过渡，将不同的数据结构及算法，应用于不同的场景，并优化算法，对提高学生的能力非常重要[1]。

1 分层教学的实施

教学中因材施教，合理进行分层次的教学是有必要的，可使不同层次的同学都能够有所收获，充分调动每个学生的积极性，提高程序设计能力和算法实现的能力，体验成功的快乐。具体开展以下分层次教学。（1）教学内容分层。根据教材内容，总体分为两个部分：一是基础部分，算法相对简单的内容;二是提高部分，相对比较抽象，算法复杂。前一部分内容所有同学都必须掌握，后一部分对学习能力强的同学有很大帮助。（2）课后作业分层。同样分为基础部分和提高部分，把需要完成的作业设置不同的难度系数，学生根据自己的实际能力完成不同难度系统的作业，这样，在他们的能力范围内都有所提高，可增强学生的自信心。当然，不同的难度系数进行考核时其分值是不一样的。（3）实践项目分层。在项目实踐环节，依然是遵循力所能及的原则，而不是强求功能全、难度大的项目，只要同学们用心了，努力了就好[2]。

2 实践教学环节的设计

“互联网+”时代，积极探索改革教学模式，O2O混合式教学模式在本课程的实施中得以充分实现。无论线上线下，实践教学都是由浅入深、由易到难，具体的过程由3步完成：（1）验证性基础实验。教材中已给出的基本算法，比如，线性表的增、删、改、查，二叉树的生成、遍历等，通过上机实践，验证其算法的结果，难度小，提高学生的学习兴趣。（2）综合性实验。完成验证性基础实验之后，掌握了一些基本的算法，为进一步提高学生的分析和应用的能力，要求学生完成一些综合性的实验，比如串的模式匹配算法，教材中一般是精确匹配，我们要求学生使用通配符模糊匹配。         （3）项目设计实验。难度加大，完成一个相对完整的项目设计，提高综合运用能力，培养学生的创新能力。选题的原则是实用，包含较多的知识点，学生可以根据自己的生活学习环境确定，比如，“学生成绩管理软件”不仅包含基本的增、删、改、查，还要求有学生的成绩统计与分析，基本满足教务系统对学生成绩的管理要求;“线下实体书店自助导购软件”通过对图书的管理，让读者能够在一个大型实体书店迅速找到所需要的书籍[3]。

3 强化算法应用的教学案例

数据结构是计算机科学的支柱，程序设计的基础。教学中教师不能只停留在抽象的理论教学层面，一定要强化算法应用才是有效的。本文以最短路径的Dijkstra算法和Floyd算法为例，分析强化算法应用的教学实践。

3.1 将抽象的数据类型与现实建立对应

最短路径是图的最常见的应用之一，图是一种典型的复杂多对多的非线性数据结构。在讲解这部分内容之前，课前布置了预习任务，同学们通过各种线上线下资源，查阅资料，了解图的应用，引导学生的学习兴趣。通过查阅相关资料，就会发现图的应用已经渗入语言学、逻辑学、物理、化学、电信工程及计算机科学与数学学科的其他分支，当今最前沿的科技图神经网络机器学习，都源于图的应用。同学们感叹，学好算法真的是大有用武之地。Dijkstra算法和Floyd算法就从大家生活中非常熟悉的导航系统导入。

3.2 最短路径的概念

日常出行，选择的是路程最短（通常路程与时间成正比）。如果路程较短的道路比较拥堵，需要花费较长时间，我们会选择实际时间短的线路，有的可能考虑的是交通费用最少。交通的便利给人们带来了更多的选择。所以，首先明确最短路径问题，不能狭义认为只是距离最短，可以是距离，可以是时间，也可以是其他，是解决关于有向带权图的问题。最短路径问题有两大类：第一，从某个源点到其余各顶点的最短路径，用一维数组表示源点到其余各顶点的最短距离;第二，任意两个顶点之间的最短距离，用二维数组表示任意两个顶点之间的最短距离。

3.3  Dijkstra算法思想

Dijkstra是单源最短路径算法，用于计算一个顶点（称源点）到其他所有顶点的最短路径。对于给定的有向网，把所有顶点分成两组，第一组是已求出最短路径的顶点集合S，其初值为源点（顶点v）;第二组是尚未确定最短路径的顶点集合T（即V-S），T的初值包含除源点之外的所有顶点。具体步骤：① 假设用带权的邻接矩阵来表示有n个顶点的带权有向图。arcs[i][j]表示弧上的权值，若不存在，则为∞（表示时用INF），最短路径长度（用dist[]表示）初值为dist[i]=arcs[v][i]。②从T集合中选择w，使得dist[w]=MIN{dist[i]|Vi∈V-S}，就是当前求得的一条从v出发最短路径的终点。从T集合中删除w，并入S集合，令S=S∪{w}。③修改从v出发到T集合中各顶点的最短路径长度。如果dist[w]+arcs[w][i]

3.4  Floyd算法思想

Floyd是求任意顶点对之间的最短路径算法。在给定的有向网中，依然假定用带权的邻接矩阵来表示有n个顶点的带权有向图。初始状态是，若存在，则存在一条长度为arcs[i][j]的路径{vi，vj}，若不存在，则为∞（表示时用INF），最短路径长度（用dist[]表示）初值为dist[i][j]=arcs[i][j]。因为该路径不一定是最短路径，然后进行n次试探，具体步骤如下。①首先试探从vi到vj是否有以顶点v1为中间点的路径，若，存在，则有路径{vi，v1，vj}，距离为，长度之和，与最初的最短距离比较，取较短者为当前最短路径。②再添加顶点2为中间点，添加顶点3为中间点，……，依次类推，添加顶点n为中间点，每次添加后总是取路径较短者为当前最短路径，即在n次的试探过程中，如果存在一个k，使得dist[i][k]+dist[k][j]

在最短路径的理论教学过程中，重点分析讲解Dijkstra算法和Floyd算法的思想，再引导同学写出相应的算法代码，最后在实践教学过程中完成一个功能较为完善的交通咨询系统，交通网络区域可以大，也可以小，但一定要使用实际数据，这样才能把算法应用落实到实处。

3.5  算法思想的协同育人教学

“数据结构”课程蕴含着丰富的育人资源，正确引导学生，把树立“中国梦”的理想与“专业梦”的规划有效结合起来，挖掘算法的思想内涵，开展协同育人教学。

学习了最短路径的Dijkstra算法和Floyd算法之后，激发学生“时不我待、舍我其谁”的爱国热情。图神经网络是近年来倍受大家关注的前沿科技，AI是未来重要的发展方向，引导学生发现其中蕴含的机遇与挑战，从而教育学生一定要有认真、仔细、严谨、求真、求实的学习态度，担当起科技强国的使命和责任。

迪杰斯特拉（Dijkastra）算法，源点到其余各点最短距离路径长度是按递增顺序一个一个求出，就像我们在人生路上必须求真务实，一步一步踏踏实实往前走，才能到达理想的彼岸，寻找属于自己的最优路径。

4 结语

“数据结构”课程的理论知识看似抽象枯燥，但其应用无处不在，加强算法应用的教学十分重要。新时代的教师要成为学生学习的引导者，不断进行教学理论的研究，设计好每一个教学过程，体现以“教师为主导，学生为主体”的教学理念，同时牢记教书育人的职责，实现知识教育与价值教育的内在契合，开展协同育人教学。

[参考文献]

[1]霍清华.应用型人才培养下的数据结构与算法课程改革[J].电脑知识与技术，2018（14）：209-210.

[2]严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2018.

[3]周蓓.数據结构与算法（C语言版）[M].北京：清华大学出版社，2019.

（编辑 王雪芬）