论文部分内容阅读
摘 要：“数据结构”是计算机类专业的核心课程，学习内容抽象难理解，理论教学与实际应用容易脱节，教学中应将抽象的数据类型与现实建立对应，加强学生对理论知识的感性认识。文章以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]<dist[i]，则修改dist[i]，使dist[i]=dist[w]+arcs[w][i]。④重复步骤②和③共n-1次，数组dist记录了从源点到图中其余各顶点的最短路径。⑤由此求得从源点到其余各顶点的最短距离是依次路径长度递增的序列。 3.4 Floyd算法思想
Floyd是求任意顶点对之间的最短路径算法。在给定的有向网中，依然假定用带权的邻接矩阵来表示有n个顶点的带权有向图。初始状态是，若<vi，vj>存在，则存在一条长度为arcs[i][j]的路径{vi，vj}，若<vi，vj>不存在，则为∞（表示时用INF），最短路径长度（用dist[]表示）初值为dist[i][j]=arcs[i][j]。因为该路径不一定是最短路径，然后进行n次试探，具体步骤如下。①首先试探从vi到vj是否有以顶点v1为中间点的路径，若<vi，v1>，<v1，vj>存在，则有路径{vi，v1，vj}，距离为<vi，v1>，<v1，vj>长度之和，与最初的最短距离比较，取较短者为当前最短路径。②再添加顶点2为中间点，添加顶点3为中间点，……，依次类推，添加顶点n为中间点，每次添加后总是取路径较短者为当前最短路径，即在n次的试探过程中，如果存在一个k，使得dist[i][k]+dist[k][j]<dist[i][j]，则将vk添加到vi到vj的路径中。③每次替换更新后的n阶方阵分别用D（-1），D（0），D（1），……，D（k），……，D（n-1）（存放最短距离），P（-1），P（0），P（1），……、P（k），……，P（n-1）（存放最短路径）。
在最短路径的理论教学过程中，重点分析讲解Dijkstra算法和Floyd算法的思想，再引导同学写出相应的算法代码，最后在实践教学过程中完成一个功能较为完善的交通咨询系统，交通网络区域可以大，也可以小，但一定要使用实际数据，这样才能把算法应用落实到实处。
3.5 算法思想的协同育人教学
“数据结构”课程蕴含着丰富的育人资源，正确引导学生，把树立“中国梦”的理想与“专业梦”的规划有效结合起来，挖掘算法的思想内涵，开展协同育人教学。
学习了最短路径的Dijkstra算法和Floyd算法之后，激发学生“时不我待、舍我其谁”的爱国热情。图神经网络是近年来倍受大家关注的前沿科技，AI是未来重要的发展方向，引导学生发现其中蕴含的机遇与挑战，从而教育学生一定要有认真、仔细、严谨、求真、求实的学习态度，担当起科技强国的使命和责任。
迪杰斯特拉（Dijkastra）算法，源点到其余各点最短距离路径长度是按递增顺序一个一个求出，就像我们在人生路上必须求真务实，一步一步踏踏实实往前走，才能到达理想的彼岸，寻找属于自己的最优路径。
4 结语
“数据结构”课程的理论知识看似抽象枯燥，但其应用无处不在，加强算法应用的教学十分重要。新时代的教师要成为学生学习的引导者，不断进行教学理论的研究，设计好每一个教学过程，体现以“教师为主导，学生为主体”的教学理念，同时牢记教书育人的职责，实现知识教育与价值教育的内在契合，开展协同育人教学。
[参考文献]
[1]霍清华.应用型人才培养下的数据结构与算法课程改革[J].电脑知识与技术，2018（14）：209-210.
[2]严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2018.
[3]周蓓.数據结构与算法（C语言版）[M].北京：清华大学出版社，2019.
（编辑 王雪芬）
关键词：算法应用;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]<dist[i]，则修改dist[i]，使dist[i]=dist[w]+arcs[w][i]。④重复步骤②和③共n-1次，数组dist记录了从源点到图中其余各顶点的最短路径。⑤由此求得从源点到其余各顶点的最短距离是依次路径长度递增的序列。 3.4 Floyd算法思想
Floyd是求任意顶点对之间的最短路径算法。在给定的有向网中，依然假定用带权的邻接矩阵来表示有n个顶点的带权有向图。初始状态是，若<vi，vj>存在，则存在一条长度为arcs[i][j]的路径{vi，vj}，若<vi，vj>不存在，则为∞（表示时用INF），最短路径长度（用dist[]表示）初值为dist[i][j]=arcs[i][j]。因为该路径不一定是最短路径，然后进行n次试探，具体步骤如下。①首先试探从vi到vj是否有以顶点v1为中间点的路径，若<vi，v1>，<v1，vj>存在，则有路径{vi，v1，vj}，距离为<vi，v1>，<v1，vj>长度之和，与最初的最短距离比较，取较短者为当前最短路径。②再添加顶点2为中间点，添加顶点3为中间点，……，依次类推，添加顶点n为中间点，每次添加后总是取路径较短者为当前最短路径，即在n次的试探过程中，如果存在一个k，使得dist[i][k]+dist[k][j]<dist[i][j]，则将vk添加到vi到vj的路径中。③每次替换更新后的n阶方阵分别用D（-1），D（0），D（1），……，D（k），……，D（n-1）（存放最短距离），P（-1），P（0），P（1），……、P（k），……，P（n-1）（存放最短路径）。
在最短路径的理论教学过程中，重点分析讲解Dijkstra算法和Floyd算法的思想，再引导同学写出相应的算法代码，最后在实践教学过程中完成一个功能较为完善的交通咨询系统，交通网络区域可以大，也可以小，但一定要使用实际数据，这样才能把算法应用落实到实处。
3.5 算法思想的协同育人教学
“数据结构”课程蕴含着丰富的育人资源，正确引导学生，把树立“中国梦”的理想与“专业梦”的规划有效结合起来，挖掘算法的思想内涵，开展协同育人教学。
学习了最短路径的Dijkstra算法和Floyd算法之后，激发学生“时不我待、舍我其谁”的爱国热情。图神经网络是近年来倍受大家关注的前沿科技，AI是未来重要的发展方向，引导学生发现其中蕴含的机遇与挑战，从而教育学生一定要有认真、仔细、严谨、求真、求实的学习态度，担当起科技强国的使命和责任。
迪杰斯特拉（Dijkastra）算法，源点到其余各点最短距离路径长度是按递增顺序一个一个求出，就像我们在人生路上必须求真务实，一步一步踏踏实实往前走，才能到达理想的彼岸，寻找属于自己的最优路径。
4 结语
“数据结构”课程的理论知识看似抽象枯燥，但其应用无处不在，加强算法应用的教学十分重要。新时代的教师要成为学生学习的引导者，不断进行教学理论的研究，设计好每一个教学过程，体现以“教师为主导，学生为主体”的教学理念，同时牢记教书育人的职责，实现知识教育与价值教育的内在契合，开展协同育人教学。
[参考文献]
[1]霍清华.应用型人才培养下的数据结构与算法课程改革[J].电脑知识与技术，2018（14）：209-210.
[2]严蔚敏.数据结构（C语言版）[M].北京：清华大学出版社，2018.
[3]周蓓.数據结构与算法（C语言版）[M].北京：清华大学出版社，2019.
（编辑 王雪芬）