数据结构与算法课程面向实践的教学方法研究

梁 冰，冯 林，杜 猛，李 航

（大连理工大学 创新创业学院，辽宁 大连 116024）

0 引言

数据结构与算法作为计算机专业的核心课程，是计算机专业人才培养的基石，从事计算机学科的信息处理、人工智能、数据库、操作系统、图形图像等方面的研究，都离不开数据结构和算法的应用[1]。随着计算机处理的数据量越来越大，对处理数据的程序效率也提出了更高的需求，计算机专业人才应具有扎实的编码能力和算法知识，并通过程序实现能够让计算机高效、准确地执行人们的想法和构思，这是计算机专业培养的重要目标[2-4]。

数据结构与算法作为一门实践性很强的专业技术基础课程，是培养学生计算思维、算法设计与实现能力的重要课程，包括C语言程序设计、数据结构、算法设计等。采用笔试的传统方式考核学生的知识掌握能力，考试能得高分的学生却不能编写一条简单的程序，这完全背离计算机专业对人才培养的目标，授课教师在理论与实践教学的探索中不断改革创新，培养学生理论素养与实践能力[5-7]。

熟练掌握计算机的经典算法是学生今后从事各方面工作和研究的专业基础[8-10]。IT公司在招聘时，无不把考察学生的算法知识作为重点，尤其在人工智能和大数据的时代，算法在提高程序效率方面起着举足轻重的作用。计算机的经典算法体现着科学家的智慧和思维，通过对经典算法的学习可以培养学生的思维能力和解决问题的能力。更重要的是，对于算法的学习，不仅仅要理解算法的理论，更要能够将算法实现并应用于解决实际问题当中，这才算达到了熟练掌握算法的培养目标[11-12]。

1 理论教学内容与实践教学紧密相连

1.1 按专题讲授经典算法

讲授经典算法时按专题划分，可以较为全面地讲授各类别的经典算法，扩展学生的知识面，培养学生计算机思维，为今后学习与研究打下坚实基础。

数据结构专题，包括栈、队列、二叉树、二叉搜索树、堆、优先队列、图、并查集、线段树、树状数组。

排序算法专题，包括冒泡排序选择排序、插入排序、归并排序、快速排序、计数排序、基数排序。

算法设计类型专题，包括枚举、递推、递归、贪心、分治、模拟、哈希、二分。

搜索算法专题，包括宽度优先搜索、深度优先搜索、剪枝（A*、IDA*）算法。

动态规划（Dynamic Programming，DP）专题，包括背包DP、状态压缩DP、树状DP、概率DP。

图论专题，包括图的最短路算法（Dijkstra、SPFA、Floyd_warshall）、最小生成树算法（Prime、Kruskal）、图的最大流算法（Ford-Fulkerson、Dinic）、二分图匹配算法、最小费用流算法、图的强连通分量分解算法。

字符串专题，包括字符串匹配算法、后缀数组、AC自动机、后缀自动机。

数论专题，包括最大公约数、扩展欧几里得算法、线性方程与同余方程、乘法逆元、中国剩余定理、质数筛法、欧拉函数、高斯消元。

计算几何专题，包括点线形的数据结构表示、线段相交问题、多边形求面积、点与多边形的位置关系、圆、凸包、半平面交。

组合数学专题，包括排列组合母函数、整数拆分、Stirling数和Catalan、容斥原理和莫比乌斯反演、群论和polya定理。

1.2 讲授例题来源于在线评测系统中经典题目

课上每个算法所讲解的例题来自在线评测系统（Online Judge），在线评测系统上的题目一般会综合多个算法知识，从中精选例题进行讲解，有助于学生温故知新、融会贯通。通过可执行C++、Java等代码对算法实现进行讲解，经过课上的学习，课后学生也有兴趣通过在线评测系统实现课上的例题，并在系统上提交。在线评测系统所返回结果可以帮助学生更深入地理解算法的思想，并达到熟练掌握算法的学习目标。

1.3 讲解算法使用C++、Java等语言描述的可执行代码

讲解算法实现时，使用编译通过的可执行代码，可以培养学生读写代码的能力。确保学生能够通过计算机语言将算法原理描述出来，并能够顺利通过编译，使计算机正确的执行。教师应强调只有通过计算机语言正确实现了经典算法的思想，才算真正地掌握算法，完成了算法学习的目标。

1.4 注重讲解算法复杂度的分析以及算法的优化方法

图论中很多经典算法的讲授需要详细讲解复杂度，比如同样是图的最短路算法，Bellman-Ford算法的复杂度是O(|V||E|)，而Dijkstra算法的复杂度是O(|E|log|V|)，后者更高效地计算最短路的长度；图中的网络流算法，Ford-Fulkerson算法的复杂度为O(F|E|)，而Dinic算法复杂度为O(|E||V|2)，后者在实际应用中速度非常快。如果解决问题的算法不是最优的，那么在线评测系统是不会通过的，系统会返回Time Limit Exceeded（TLE）：程序运行时间超出了题目的规定。对于解决问题的算法只有满足时间复杂度和空间复杂度的情况，系统才会返回通过：“Accepted（AC）：在规定的时间内不超出内存限制的条件下得出满足题目要求的结果”。

2 面向实践的教学方法

2.1 讲授算法时以现实中遇到的实际问题为切入点

教师鼓励学生在课后阅读相关的算法在实际生产和生活中应用的文献资料，学生能够更好地理解算法的功能和意义，加深理解算法，提升学生学习算法的热情。如，将快速幂求模算法运用于著名的RSA公钥加密方法中，鼓励学生课后查找RSA公钥加密方法的相关资料进行学习。最大流最小割算法应用于优化图像分割方法，像Photoshop、美图秀秀等基于交互式分割得到目标的功能基本源于图像分割。字符串匹配算法Boyer-Moore用于文本编辑器的“查找”功能、论文查重等。

2.2 引导学生主动学习与自学

计算机领域需要学习的经典算法非常多，如果不能引导学生自己深入的学习，教师在有限的课堂时间内是无法将所有的经典算法传授给学生的，并且单一的讲授效果并不好，不能调动学生积极的思考。因此，提纲挈领地讲授经典算法的思想和精髓，调动起学生的兴趣，通过主动学习与实现更多的相关算法是有限课堂时间内的首要任务。如栈和队列的应用和实现方式上有很多相似的原理，可以讲授栈的实现方式，而队列的实现方式留给学生自学，一是提升学生学习的主动性，积极思考；二是避免相似内容讲解时学生精神不集中。

2.3 采用引导式及互动式教学

在授课时，教师准备好可以和学生积极互动的知识点，调动学生积极思考，调动起学生学习的兴趣。一些知识点的讲解也很合适与学生互动，如在讲解算法的时间复杂度时，教师以快速幂运算算法为例，对于逐次相乘的算法，需要循环n次，才能获得结果，因此算法复杂度是O(n)，而将n次幂用二进制表示之后，算法又需要循环多少次便可以得到计算结果？有了这样的启发，可以激发学生思考、师生进行互动。

2.4 答疑与探讨

教师将每一个经典算法介绍之后，会给学生一个提问和探讨的机会：学生有什么知识点没有听明白，这样可以了解学生理解问题困难的点，下次授课可以详细介绍；学生也会提出教师没有深入讲授的知识点，完善教学讲授的要点，实现教学相长。

3 基于在线评测系统的实验平台建设与实验教学开展

3.1 在线评测系统的课程实验平台建设的必要性

建设在线评测系统（Online Judge，OJ）实验平台对提升程序设计类课程的实验效果是非常有效的。在没有在线评测系统之前，对数据结构与算法实验课程中学生实验结果的可行性考核是不强的，编译系统对程序的考察只是编译结果是否正确，对于算法的时间复杂度和空间复杂度的考核没有一个严格的标准，教师对班级每位学生程序的验证所耗费的时间是不可估量的。

3.2 在线评测系统的特点和性能

在线评测系统是ACM-ICPC国际大学生程序设计竞赛的比赛系统，OJ系统的应用使比赛结果公平、公正、公开，不受人为因素影响，这项赛事吸引了全球大学生的积极参与，也使得ACM国际大学生程序设计竞赛成为全球最具影响力的大学生程序设计竞赛[13-14]。在线评测系统能够自动评判代码的正确性，并将评判结果返回参赛选手。自动评测系统只反馈以下结果。

Accepted（AC），在规定的时间内不超出内存限制的条件下得出满足题目要求的结果。

Presentation Error（PE），在规定的时间内不超出内存限制的条件下得出结果，但是同正确的结果相比结果的格式存在问题。

Time Limit Exceeded（TLE），程序运行时间超出了题目的规定。

Memory Limit Exceeded（MLE），程序在编译或者运行期间向操作系统申请的内存超出了题目的规定。

Wrong Answer（WA），在规定的时间内不超出内存限制的条件下得出结果，但是同正确的结果相比存在较大差别。

Runtime Error（RE），程序运行期间访问非法内存。

Output Limit Exceeded（OLE），程序输出结果文件过大，超出评测系统限制。

Compile Error（CE），程序编辑错误。

评测系统不仅能够评测程序的正确性，更重要的是可以对程序的时间复杂度和空间复杂度进行评测，如果程序虽然能够通过编译，但时间复杂度或空间复杂度高于题目要求，是不能通过的。正是评测系统这一功能的设定使学生对算法的复杂度有了前所未有的重视，加强了学生对算法的理解和学习的深度。

3.3 基于在线评测系统的实验课程开展方法

按照课堂教学中讲授的每个算法，为学生在OJ中设定相应的经典题目作为实验内容。教师可以根据OJ对学生提交题目的判定结果总结出学生在代码编写中常常出现的错误，从而重点讲解，及时纠正学生常犯的错误。

评测系统对程序及时详细的反馈，对学生的学习是一种积极的鼓励与促进，更是杜绝了学生在学习算法时的浅尝辄止，因为一知半解学习所得到的结果不会是最优的。在线评测系统返回给学生不同类型的判定结果，培养了学生对算法精益求精、深入研究、理解透彻的学习习惯，这对学生是受益终生的。

4 课程考核方式改革

在总成绩中加大编码和算法实现成绩所占的比例，引导学生重视编码能力的锻炼：①将实验课程的成绩和课后OJ系统中所留的作业成绩纳入到期末总成绩；②期中考试采取线上OJ题目考核的方式，考核学生的实践编码能力；③期末考试采用笔试的方式。

课程总成绩各项所占比例：①实验成绩15%；②作业 15%；③期中线上考试1成绩20%；期中线上考试2成绩20%；④期末成绩，期末采用笔试的方式，占30%。其中，实验、作业、期中竞赛在OJ上完成。

从课程总成绩中实践考核内容所占的比例可以看出，计算机专业的学生如果不重视本课程的实践特性，不能一点一滴的提升自己的编程能力，课程是很难获得高分的。课程的最终成绩能够客观反映学生的编码能力和程序设计能力，避免出现试卷能够获得高分却无法实现一些简单算法的现象。学生在学习这门实践性很强的课程时，单纯的笔试考核方式容易造成学生学习方法和学习重点的方向上的错误，因此，通过在线评测系统加大客观评估学生实际编程能力的上机考核方式，使学生在课程学习中，重视上机调试程序和算法的实现与应用。

5 结语

数据结构与算法课程讲授了非常重要和实用的计算机算法，能将算法灵活应用的基础就是不仅能够掌握算法的思想，更要能够编码实现算法。笔者提出的面向实践的教学方法，引导学生在学习这门课时重视理论与实践相结合，不仅是学习算法的理论，更重要的是编码实现算法及算法在解决实际问题中的应用，而且算法在实践中应用更能加深学生对算法思想的理解，相辅相成。

面向实践的教学方法经过多年在理论教学和实验教学的应用，在计算机人才培养上取得了明显的效果，学生具有编程能力强、算法知识面广且扎实、专业素质高的特点，因此在保研和就业中具有很强的竞争力。知名高校和企业越来越看重学生的算法能力，考核学生的算法能力是很重要的一项。在目前大数据和人工智能的环境下，没有算法的程序已不能满足实际应用的需求了，学生的编程能力和算法实现能力，无时无刻不在科研和研发中发挥着重要的作用。因此，具有编程能力强、算法基础扎实的计算机专业学生成为名校和名企的抢手人才，大连理工大学的毕业生获得了来自清华、北大、上海交通大学、美国加州大学等名校的保研资格以及来自谷歌、微软等知名IT企业的Offer。