基于python语言版“数据结构与算法”的教学改革与实践

陈仕军，陶茂虎，王 前

(湖北文理学院 数学与统计学院，湖北 襄阳 441053)

“数据结构与算法”是信息与计算科学专业的重要基础课，具有理论抽象、实践性强、内容多的特点，课程的教与学难度大。对于如何提高该课程的教学质量和提升学生的学习效果，已有一些教学改革的研究和探索。赵芸和徐兴[1]提出基于翻转课堂和成果教学的新模式，提高学生的学习主动性。万晓辉[2]提出了基于雨课堂的混合式教学方式，提升教学效果。王青松等[3]提出以真实问题为导向的教学模式。王曙燕等[4]提出基于“赋能教育”的混合教学模式设计方法，采用线上与线下相结合的教学过程。熊回香和叶佳鑫[5]将信息管理类专业知识与课程教学相结合，对课程教学体系做了改革实践。李禾和柳成行[6]以“少教多学”为理念，强调学生在学习中的主体性作用，进行了全面的教学改革。刘俊杰和胡忠望[7]也提出了线上线下相结合的教学模式，来改善教学效果。任永强等[8]介绍了基于超星学习通移动教学的课程教学体系构建。陈黎黎和国红军[9]提出了基于OBE理念的教学改革实践，取得了较好效果。牛犇等[10]挖掘思政教育资源，融入到课程教学，实现课程的价值引领。廖国富[11]从“教”与“学”两个角度分析了当前数据结构教学中的问题，还提出了问题导入法、演示法等一些有效教学方法。舒清录和廖明梅[12]强调了以培养“计算思维”为核心的课程教学改革。这些教学研究从不同层面进行了探索研究，相关经验和成果值得借鉴，但由于针对的学生群体不同，学生群体的基础和目标不尽相同，而且不同学校采用的程序设计语言也有差别，因此难以有通用的最有效方法。目前，采用最多的程序设计基础语言有C、C++、Java。基于python语言版“数据结构与算法”的课程教学改革与研究，相对比较少。

近年来，省属地方高校办学思路逐渐转变为培养应用型人才，随之而来的课程改革也倾向于开设更多与就业市场关系更紧密的应用性课程。然而，课时总数限制使得“数据结构与算法”等理论基础课的教学课时不断被压缩[11]，教师对于教学成效的压力越来越大。以笔者所在学校信息与计算科学专业为例，以前的“数据结构与算法”课程分为2门课开设，其中“数据结构”为72学时，“算法设计与分析”为54课时，总共126课时。专业课程改革后，2门课合并为“数据结构与算法”，缩短到90个课时。2019年人才培养方案新修订后，进一步压缩课时，调整为80个课时。同时，随着本专业办学越来越侧重于数据分析、人工智能等方向，信息与计算科学专业将python作为本专业的基础程序语言，“数据结构与算法”也转变为采用python版的教材。很多学生对python语言编程掌握不熟练的条件下，就进入“数据结构与算法”的课程学习，如何使绝大多数学生理解并掌握好这门课，教师面临很大的教学压力。为了在总学时有限的条件下，引导学生熟练掌握“数据结构与算法”课程的核心内容，笔者经过近四年的教学实践，探索出一些可行而有效的教学方法。主要有以下几个方面：第一，将“数据存储、操作以及时间复杂度”的核心思想和内容放在中心位置，并将其贯穿于各章节的教学始终；第二，采取“从易到难”的渐进式教学方式，基于重要性和学生的易接受度来选取适合的教学内容和材料；第三，教学过程中，采用“图形化教学、黑板绘图展示”的教学方式，要求学生“动手画图”进行学习，深化对存储和操作的理解；第四，增加实践性教学课时，采用“易于理解和实现的示例”作为实验内容，让学生能真正熟练掌握后，再逐步推广到更加复杂的数据结构与算法示例。

1 强化程序设计基础和数据结构的核心思想

1.1 强化python程序设计基础

首先，重点补充python程序设计的基础知识。引导学生扎实掌握python内置的常用数据结构，如列表list、字符串str、元组tuple的应用。同时，强化学生熟练应用python内置class编程的能力。class适合于描述抽象的数据结构，其中属性对应数据结构的数据及其存储定义，方法对应数据结构中的增加、删除、查找数据等操作。

1.2 将数据结构的核心思想和内容贯穿于教学始终

学习“数据结构与算法”的目标是更高效地存储和组织数据，特别是处理数据的增、删、查、排序等各种操作功能，从而能高效的解决实际问题。如图1所示，数据及数据关系的存储方式(两种存储方式)、数据操作的算法时间复杂度，是该课程的核心思想和内容，将其贯穿于教学始终。

图1 贯穿课程的核心思想和内容

为了让学生深刻掌握该思想和内容，教学中需要强化如下两点。

1)强化对python内置list数据结构的理解，是延伸到其他顺序存储数据类型的基础。python内置多种抽象的数据类型，尤其是属于一种顺序线性表的list，为构造其他复杂数据类型提供了便利。因此，让学生掌握对list的各种操作函数是后续数据结构中应用顺序数据存储的基础。同时，为了让学生理解算法时间复杂度的概念，以list的各种操作为例说明算法复杂度的计算方法，进而掌握for、while等循环程序结构(包括嵌套结构)的算法复杂度。

2)强化对节点和链表概念的理解，它们是后续延伸到其他链式数据结构的基础。除了顺序存放数据采用list实现外，链式存储是另一种关键的数据存储方式。链式存储中，单个数据均存储于节点中，各数据之间的前后或父子等关系，通过节点中的“链接”属性来表达。因此，以单链表为例，引导学生掌握节点和链式存储的概念，然后拓展到双链表、循环链表。对于单链表的数据结构，特别强调头节点的设置与作用。要求学生在学习和实践中，多思考从各种操作的算法时间复杂度，不断理解和掌握顺序线性表和链表的本质、优缺点和适用场景。

2 精简教学内容，按难度渐进式教学，强化知识模块的关联性

2.1 精简教学内容，按难度渐进式教学

从以往的教学实践经验中发现，学生不必学习太多内容，但务必要能扎实掌握，以便增强自信心，提高学习兴趣。学生如果能真正掌握几种相对简单的数据结构与算法，则不难推广和学习更复杂的数据结构与算法。同时，教学选材要兼顾知识点的渐进深入和上机实践的难度。笔者通过近四年的教学与实践，考虑从易到难，探索出按照如下的教学内容模块顺序进行，基本能达到较好的教学效果。

在图2中，单向实心箭头表示讲授知识模块的顺序，而带虚线的反向箭头表示与前面所学知识点相关联，这样使学生逐渐形成更加系统化的数据结构知识体系。例如，对二叉树进行深度搜索和广度搜索时，适合于应用前面的栈和队列解决问题，从而进一步深化对栈和队列的理解与应用。在讲授平衡二叉搜索树时，加深对前面搜索和排序算法的理解，通过算法分析与比较，能进一步加深对算法复杂度的认识。同时也体会到平衡二叉树与前面的list和链表的本质差别。

图2 渐进式教学内容分步图

2.2 强化知识模块的渐进性和关联性

1)栈和队列的概念与实践。栈和队列的概念相对比较简单，但仍有部分学生在学习栈和队列时，不能理解栈和队列的增加、删除数据等操作过程。为此，需要强调栈属于“后进先出”的功能性数据结构，并采用一些简单的示例说明其适用场景。例如，将十进制数转化为二进制数，采用除以2取余数法，将所得余数进行倒置，则得到二进制数。利用栈的“后进先出”原理，这一过程容易理解和实现，也体现了栈的特点；再以约瑟夫环问题为例，说明利用队列的“先进先出”性质解决此类问题的便捷性。后期在学习二叉树和图的节点遍历搜索时，强化学生对于栈和队列应用场景的理解。

2)递归与二叉树。二叉树属于非线性结构，其数据关系和相关操作比线性结构更复杂，所需的基础知识和扩展内容也更多，包括递归、深度遍历、广度遍历、栈和队列的应用、各种特定的二叉树结构及应用等。同时，这些知识内容的编程实现过程也要复杂很多。考虑到课时限制和大部分学生的知识接受能力有限，讲授时必须有所取舍。因此，在前期学习时，重点引导学习递归、二叉树的遍历、完全二叉树、堆的概念及操作，后期学有余力时再延伸到平衡二叉树。

首先，以简易小问题为例，例如阶乘、单链表求长度、汉诺塔盘片移动问题等，引导学生掌握递归的基本思想和程序实现方法。然后在此基础上，讲解二叉树的数据结构和常用深度遍历方法，强化递归应用的思维训练。对于完全二叉树，通过分析节点数和层数的关系，说明其线性存储的优点。再由完全二叉树推广到堆的概念，引导学生掌握堆实现优先队列、操作与实现方法，加深对二叉树应用的理解。对于平衡二叉树，不仅操作更加复杂，而且会用到搜索和排序的知识，因此先只讲授基本概念，后期学有余力时再加深理解。

3)简单搜索和排序算法。搜索(或查找、遍历)是解决很多问题的基础操作。对于线性的数据结构进行顺序搜索，直观易理解，学生都能轻松掌握。对于有序线性结构的二分搜索，采用以方程求根的二分搜索算法举例，说明其相似性。同时，要让学生理解查找和搜索的区别与联系，并了解其方法具有多样性。

排序算法比较多，由于学时有限，有必要做精简，要求学生学会2种排序算法：冒泡排序与快速排序。冒泡排序的原理简单直观，是学习排序算法的基础，也是和其他排序进行复杂度对比时常用的算法。由于前期的“python语言程序设计”课程中会介绍冒泡排序，因此难度相对较低，只要再简单复习，学生能够熟练掌握。再从算法复杂度角度分析，说明冒泡排序是一种效率不高的排序算法(O(n*n))。而快速排序具有高效率的特点，时间复杂度低(O(n*logn))，但其算法实现过程稍显复杂。讲解时多分配学时，让学生真正理解，并能编程实现。在此基础上，其他排序算法(插入排序、希尔排序、归并排序)，均可以通过自学理解。

4)以二叉树为例，掌握深度遍历和广度(或宽度)遍历的思想与方法，加深对递归、栈以及队列的理解与应用。引导学生从线性结构的遍历，延伸到非线性结构的遍历。二叉树和图作为两种典型的非线性结构，遍历其节点时，采用深度遍历或者广度遍历算法。利用画图方式，逐步展示两种算法的区别。在程序实现时，考虑两种编程方法，即递归和非递归。采用递归方式，更加直观，但需要对递归有较深的认识。采用非递归方式，则需要对栈和队列有熟练理解。对二叉树的深度遍历和广度遍历的练习，能让学生加深对递归、栈和队列等内容的理解。

5)学会图的基本存储与操作、图节点的遍历与搜索、最小生成树和最短路问题。图数据结构是相对较复杂的数据结构，但又是解决很多与网络相关复杂问题的基础。首先，要掌握图的存储和操作，然后从二叉树的遍历方法推广到图的遍历方法，使得学生理解图的深度搜索和广度搜索算法的思想和方法，这是对图操作的基础。图的应用内容非常多，根据实际情况，让学生掌握最小生成树和最短路问题的算法及其代码实现。

6)平衡二叉树和哈希表。这部分数据结构相对更加抽象、操作更复杂，不管理论还是实践都是难度最大的部分。因此，在学生前期基础掌握比较扎实的情况下，再进行讲解，学生更容易接受。在学习平衡二叉树(重点是二叉查找树)时，对比前面已学的查找算法，从时间复杂度体会二叉查找树的高效率。学习哈希表时，进一步体会其查找效率的优势，并掌握其适用场景。其他内容，如哈夫曼树、字符串匹配算法等，根据学生掌握情况和课时剩余情况，进行引导学习即可。

3 教学方法与教学过程的改进

3.1 图形化教学、黑板绘图展示，要求学生草稿纸上绘图、理解

传统采用PPT教学的方法，课程内容进度较快，不能详细演示，学生对内容掌握不牢固。教师采用黑板上“边讲解、边绘图”的教学方法，会具有更好的效果。“好记性赶不上烂笔头”，要求学生带草稿纸，绘图体会数据结构的数据存储方式和操作过程。在对数据结构的理论掌握的基础上，再进行实验实践。事实证明，这种“脑子想、纸上画”的教学学习方法，能让学生更容易理解和掌握。

3.2 教学过程与教学环节设计改进

1)以问题为导向，以易理解和操作的示例为主线，增加实验课时，强调学生的实践能力。传统的实验课程示例，一般规模较大，操作复杂，程序代码长，一次实验难以完成，使得学生体会不到数据结构编程的乐趣和成就感。为此，基于近些年的实践教学经验，构建出一些学生易理解、易操作的教学实践示例。例如，以学生信息中的单科成绩排序为例，说明python的list和sort函数的使用方法；为掌握递归的思路和方法，以n阶乘、汉诺塔以及二叉树的遍历的算法为例，体会递归的不同适用场景；以十进制转二进制为例，让学生体会栈的操作与应用；进一步拓展到将栈应用于迷宫问题。

2)应用多种数据结构进行对比，让学生深刻体会到操作时间复杂度的差异。为此，也构造出一些易于理解和实现的示例。例如，利用自然数1、2、…、n求和，体会程序循环累加和数学公式计算之间的计算效率差别，进而说明计算时间复杂度的重要性；以约瑟夫问题为例，采用list、循环链表、队列，来从时间复杂度角度体会不同数据结构的优缺点；以优先队列为例，采用list实现和采用堆实现进行对比，体会堆具有时间复杂度低的优点；利用冒泡排序和快速排序进行对比，体会不同排序算法之间的效率差异；以数据的插入、删除和查找为例，分别比较list和二叉查找树之间的效率差异。

4 近四年来的教学成效

通过近四年的教学改革与实践，学生学习数据结构与算法课程的积极性有明显提升，对基础数据结构与算法的理解和掌握程度，也越来越深。在试卷难度不变的条件下，最近四年的期末考试成绩如表1所示。

表1 近四年的“数据结构与算法”期末考试成绩

从近四年的期末考试成绩看，考试卷面平均分、总成绩平均分、优秀占比，总体上均有一定幅度的稳步提升。教学效果，有了明显的改善。同时，总成绩的不及格比例也呈下降趋势。在后期，在教学实践改革中，要进一步精选知识点和示例，引入更多图形化展示方法，更加生动展示课程特点，提升教学效果。

5 结语

通过近四年的“数据结构与算法”教学实践经验，提出了一些课程内容与方法的改进措施。主要是精简教学内容，采用由易到难渐进式教学、图形化教学展示，以容易理解和实现的示例作为实验重点，不断提高学生的学习兴趣。从近几届学生的反馈和期末成绩来看，教学改革与实践具有较好的成效。近些年，互联网发展迅猛，网络课堂也是线下教学的重要补充。对于如何合理利用好网络资源和网络教学，做好“数据结构与算法”课程的线上和线下相结合，还需要不断探索和实践，以进一步提高教学质量。