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

1、“数据结构”课程强化算法应用的教学实践“数据结构课程强化算法应用的教学实践 引言 数据结构是20世纪60年月提出并讨论，20世纪70年月科学家Niklaus Wirth的著作Algorithm+Data Structures=Programs使得数据结构讨论不断深入，20世纪80年月讨论日臻成熟，成为一门完好的学科。它是一门介于数学、计算机软件、计算机硬件之间的综合学科，是程序设计的基础。 在学问飞速更新的时代，提高学生获得学问的能力，真正做到“授人以鱼不如授人以渔，是教师应尽的责任。作为一门理论和实践并重的课程，理论教学讲授算法思想，实践教学实现由抽象到具体的过渡，将不同的数据结构及算法，应

2、用于不同的场景，并优化算法，对提高学生的能力特别重要1。 1 分层教学的实施 教学中因材施教，合理进行分层次的教学是有必要的，可使不同层次的同学都能够有所收获，充分调动每个学生的主动性，提高程序设计能力和算法实现的能力，体验胜利的欢乐。具体开展以下分层次教学。1教学内容分层。依据教材内容，总体分为两个部分：一是基础部分，算法相对简洁的内容;二是提高部分，相对比较抽象，算法冗杂。前一部分内容全部同学都必需把握，后一部分对学习能力强的同学有很大关心。2课后作业分层。同样分为基础部分和提高部分，把需要完成的作业设置不同的难度系数，学生依据自己的实际能力完成不同难度系统的作业，这样，在他们的能力范围内

3、都有所提高，可增添学生的自信念。当然，不同的难度系数进行考核时其分值是不一样的。3实践项目分层。在项目实踐环节，照旧是遵循力所能及的原则，而不是强求功能全、难度大的项目，只要同学们专心了，努力了就好2。 2 实践教学环节的设计 “互联网+时代，主动探究改革教学模式，O2O混合式教学模式在本课程的实施中得以充分实现。无论线上线下，实践教学都是由浅入深、由易到难，具体的过程由3步完成：1验证性基础试验。教材中已给出的基本算法，比方，线性表的增、删、改、查，二叉树的生成、遍历等，通过上机实践，验证其算法的结果，难度小，提高学生的学习兴趣。2综合性试验。完成验证性基础试验之后，把握了一些基本的算法，为

4、进一步提高学生的分析和应用的能力，要求学生完成一些综合性的试验，比方串的模式匹配算法，教材中一般是精确匹配，我们要求学生使用通配符模糊匹配。 3项目设计试验。难度加大，完成一个相对完好的项目设计，提高综合运用能力，培育学生的创新能力。选题的原则是有用，包含较多的学问点，学生可以依据自己的生活学习环境确定，比方，“学生成果治理软件不仅包含基本的增、删、改、查，还要求有学生的成果统计与分析，基本满足教务系统对学生成果的治理要求;“线下实体书店自助导购软件通过对图书的治理，让读者能够在一个大型实体书店快速找到所需要的书籍3。 3 强化算法应用的教学案例 数据结构是计算机科学的支柱，程序设计的基础。教

5、学中教师不能只停留在抽象的理论教学层面，肯定要强化算法应用才是有效的。本文以最短路径的Dijkstra算法和Floyd算法为例，分析强化算法应用的教学实践。 3.1 将抽象的数据类型与现实建立对应 最短路径是图的最常见的应用之一，图是一种典型的冗杂多对多的非线性数据结构。在讲解这部分内容之前，课前布置了预习任务，同学们通过各种线上线下资源，查阅资料，了解图的应用，引导学生的学习兴趣。通过查阅相关资料，就会发觉图的应用已经渗入语言学、规律学、物理、化学、电信工程及计算机科学与数学学科的其他分支，当今最前沿的科技图神经网络机器学习，都源于图的应用。同学们感叹，学好算法真的是大有用武之地。Dijks

6、tra算法和Floyd算法就从大家生活中特别熟识的导航系统导入。 3.2 最短路径的概念 日常出行，选择的是路程最短通常路程与时间成正比。假如路程较短的道路比较拥堵，需要花费较长时间，我们会选择实际时间短的线路，有的可能考虑的是交通费用最少。交通的便利给人们带来了更多的选择。所以，首先明确最短路径问题，不能狭义认为只是距离最短，可以是距离，可以是时间，也可以是其他，是解决关于有向带权图的问题。最短路径问题有两大类：第一，从某个源点到其余各顶点的最短路径，用一维数组表示源点到其余各顶点的最短距离;第二，任意两个顶点之间的最短距离，用二维数组表示任意两个顶点之间的最短距离。 3.3 Dijkstr

7、a算法思想 Dijkstra是单源最短路径算法，用于计算一个顶点称源点到其他全部顶点的最短路径。对于给定的有向网，把全部顶点分成两组，第一组是已求出最短路径的顶点集合S，其初值为源点顶点v;第二组是尚未确定最短路径的顶点集合T即V-S，T的初值包含除源点之外的全部顶点。具体步骤： 假设用带权的邻接矩阵来表示有n个顶点的带权有向图。arcsij表示弧上的权值，若不存在，则为表示时用INF，最短路径长度用dist表示初值为disti=arcsvi。从T集合中选择w，使得distw=MINdisti|ViV-S，就是当前求得的一条从v出发最短路径的终点。从T集合中删除w，并入S集合，令S=Sw。修改

8、从v出发到T集合中各顶点的最短路径长度。假如distw+arcswidisti，则修改disti，使disti=distw+arcswi。重复步骤和共n-1次，数组dist记录了从源点到图中其余各顶点的最短路径。由此求得从源点到其余各顶点的最短距离是依次路径长度递增的序列。 3.4 Floyd算法思想 Floyd是求任意顶点对之间的最短路径算法。在给定的有向网中，照旧假定用带权的邻接矩阵来表示有n个顶点的带权有向图。初始状态是，若vi，vj存在，则存在一条长度为arcsij的路径vi，vj，若vi，vj不存在，则为表示时用INF，最短路径长度用dist表示初值为distij=arcsij。因为

9、该路径不肯定是最短路径，然后进行n次试探，具体步骤如下。首先试探从vi到vj是否有以顶点v1为中间点的路径，若vi，v1，v1，vj存在，则有路径vi，v1，vj，距离为vi，v1，v1，vj长度之和，与最初的最短距离比较，取较短者为当前最短路径。再添加顶点2为中间点，添加顶点3为中间点，依次类推，添加顶点n为中间点，每次添加后总是取路径较短者为当前最短路径，即在n次的试探过程中，假如存在一个k，使得distik+distkjdistij，则将vk添加到vi到vj的路径中。每次替换更新后的n阶方阵分别用D-1，D0，D1，Dk，Dn-1存放最短距离，P-1，P0，P1，、Pk，Pn-1存放最短

10、路径。 在最短路径的理论教学过程中，重点分析讲解Dijkstra算法和Floyd算法的思想，再引导同学写出相应的算法代码，最终在实践教学过程中完成一个功能较为完善的交通咨询系统，交通网络区域可以大，也可以小，但肯定要使用实际数据，这样才能把算法应用落实到实处。 3.5 算法思想的协同育人教学 “数据结构课程蕴含着丰富的育人资源，正确引导学生，把树立“中国梦的理想与“专业梦的规划有效结合起来，挖掘算法的思想内涵，开展协同育人教学。 学习了最短路径的Dijkstra算法和Floyd算法之后，激发学生“时不我待、舍我其谁的爱国热情。图神经网络是近年来倍受大家关注的前沿科技，AI是将来重要的进展方向，引导学生发觉其中蕴含的机遇与挑战，从而教育学生肯定要有仔细、认真、严谨、求真、求实的学习看法，担当起科技强国的使命和责任。 迪杰斯特拉Dijkastra算法，源点到其余各点最短距离路径长度是按递增顺序一个一个求出，就像我们在人生路上必需求真务实，一步一步踏踏实实往前走，才能到达理想的彼岸，查