基于Python的数据结构课程

裘宗燕

（北京大学数学学院，北京100871）

0 引言

越来越多的高校开设了Python编程课程，国际上已有很多学校将Python作为第一门计算机科学技术课的语言，讲授基本编程的思想、概念和技术。这种做法不可避免地带来一个问题：这门课程怎样与后续课程衔接，首先是怎样与数据结构课程衔接。我们使用Python语言讲授过几次计算机基础课，包括基本编程课和数据结构课，并编写出版了相关教材[1]，发现用Python讲授数据结构课程的现实情况：与原来基于C语言等的课程相比，该课程有哪些优势，又有哪些需要特别关注和解决的问题。

1 Python与数据结构

数据结构课程大约于20世纪70年代从发达国家的计算机科学系起步，最初使用伪代码讨论和分析，相关教学和教材很大程度上受到文献[2]的影响。随着高级语言的广泛使用，数据结构课程的教学逐渐转向以高级语言作为讨论工具。文献[3]中提出的观点被广泛接受，对数据结构课程的发展产生了很大影响。一时之间，绝大多数数据结构课程都转向采用Pascal语言。后来，抽象数据类型（ADT）的思想逐渐被数据结构教材和课程所采用。20世纪90年代以后，随着C语言的使用日益广泛和Pascal日渐衰落，越来越多的国内外高校改用C语言教授数据结构课程，而后又有其他语言逐渐加入。目前，数据结构课程使用的主要语言包括C、C++、Java等。

随着越来越多的高校开始使用Python讲授第一门程序设计课程，用Python讨论数据结构的问题也被提上议事日程。为了深入探讨有关情况，我们首先回答几个经常听到的问题，网上对于这些问题也有许多讨论。

第1个常见的问题：Python的表和字典就是数据结构课程中讨论的典型数据结构，学习Python编程之后就已经会用了，还需要学习数据结构课程吗？我们的回答是，当然需要。一方面，数据结构是计算机科学知识体系中最重要的环节之一，其核心问题是讨论数据组织和管理的思想和技术、计算复杂性的概念和分析等，这些都是计算机科学技术领域最重要的基础知识，而表、字典等只是传播上述核心知识和技术的媒介，是课程所讨论的典型实例，Python的程序设计基础和相关课程既不能提供上述重要知识和相关技术，又不可能代替数据结构课程；另一方面，要用好Python语言并发挥其作用，必须理解数据结构的一般性知识和Python的特殊情况，编程语言是非常复杂的工具，编程是最复杂的工作，缺乏对所用语言的理解是做不好编程的，数据结构课程则能帮助学生深入理解Python的表、字典等组合类型。因此，基于Python的数据结构课程教学需要兼顾这两方面的需求。

第2个常见的问题：用Python语言讨论数据结构的可行性。依据我们的理解和经验来判断，这种做法确实可行。目前，国际上已经出版了许多使用Python语言讲授数据结构相关内容的教材，如在亚马逊网站上可以查到文献[4-6]，但是国内至今未出版中文翻译版本。我们已经使用Python讲授过几次数据结构课程，并编写出版了相关教材[1]。此外，还可以找到国外同行研究这个问题的论文，如文献[7]，也可以找到国外一些知名高校发布的有关使用Python讲授CS2的消息[8]。这些情况都说明，使用Python讲授数据结构课程的做法是可行的。当然，不同语言有各自的特点，应用于同一门课程时，也需要考虑其特点，扬长避短。如前所述，这门课程应该是数据结构基础知识和Python的结合，用Python讲授数据结构既有优势，又有劣势。

第3个常见的问题：学习数据结构课程对于使用Python开发程序（软件）有特殊意义吗，特别是使用Python语言讨论的课程？对此，我们的回答是肯定的。因为除了讲授计算机科学技术的一般性作用之外，这门课程还对提升学生使用Python工作的能力产生重要影响，主要体现在以下3个方面。

（1）有助于学生理解Python程序的行为，理解怎样写好Python程序。

（2）帮助学生在使用Python编程的过程中作出正确的设计选择，并为这些选择提供本质性的判断根据。例如，保存一批数据时，选用标准类型的表或字典，还是自己开发专门结构，并知悉原因；向表中加入元素应该用哪个操作等。

（3）有助于识别程序中的效率陷阱。Python程序中很容易创建各种复杂数据对象，这种便利如果使用不当，很可能严重影响程序的效率和可用性。

2 用Python讲授数据结构课程的目标、优势和困难

基于Python的数据结构课程的教学目标应包含以下3方面。

（1）清晰介绍数据结构课程的基本理论内容。这些内容与具体语言无关，包括数据结构和算法的基本概念，相应的理论问题（复杂性等），数据结构的基本构造技术，各种典型数据结构的原理、性质、基本使用和基本实现技术等。

（2）基于Python语言讨论数据结构的实现技术，既要体现一般的数据结构技术，又要充分发挥Python的优点，展示有用的设计和Python编程技术，还应说明在Python程序里使用数据结构解决问题时可能遇到的问题、分析和思考的方法、解决问题的方法等。

（3）认真分析Python语言中的各种组合数据结构（作为理论数据结构的具体实现）的想法、具体设计和实现，各方面的实际性质、优缺点、使用时需要注意的问题等。

用Python讲授数据结构课程有许多优势，最重要的优势来自Python语言设计的很多特征可以在数据结构课程中发挥作用。

（1）Python的面向对象机制可以作为ADT（抽象数据类型）的具体体现，用于实现各种数据结构和支持封装。类定义中的实例方法可用于实现数据结构操作；继承用于扩充已定义的部件，实现扩充（或部分修改）的新数据结构等。

（2）Python的生成器函数可用于实现各种容器结构都需要的遍历操作，使自定义的容器类型可以平滑地纳入Python语言的基本编程模型。

（3）Python变量、参数和对象属性都没有类型限制，因此Python里定义的函数和对象方法都具有通用性，能操作任何满足需要的对象且只要求被操作对象提供所需操作，自定义数据结构能保存任何类型的数据元素。

（4）由于上述通用性，教科书里、课堂上和学生工作中开发的各种组件，如函数、类等，只要定义合适，就能作为辅助性数据结构直接用于后续工作，用于实现更复杂的数据结构和操作，或直接支持数据结构的应用。这使学生能看到从简单到复杂的软件开发过程，看到自己编写的程序能真正得到应用，更有成就感。

用Python讲授数据结构也存在一些困难，主要困难源自Python语言的高级和抽象。做算法（程序）的复杂性分析时，首先要确定基本操作和基本数据单元，它们必须具有O(1)复杂性。在C语言等较低级的语言里，基本操作都是O(1)操作；Python作为比较高级的语言，屏蔽了重要的实现细节，表面上看似很简单的操作，内部实现可能很复杂，如==判断、整数加法等，都不一定是O(1)操作。组合数据类型的广泛使用，进一步增加了复杂性分析的难度，用Python讲授课程时需要特别注意这些问题。

3 用Python讲授数据结构课程的实践和体会

我们用自己编写的材料讲授了几次数据结构课程，教学效果总体上是非常正面的：学生反应比较积极，做作业也很有兴趣，完成了不少有一定复杂性的工作。

与基于C语言的课程相比，有关数据结构理论的抽象讨论可以基本照搬。有关抽象数据类型的介绍可以更有针对性，ADT描述可以参考Python类定义做些调整，如增加self参数等。前面章节实现的数据结构可以直接用于后面数据结构或应用问题，看到做出的东西有实用性，学生也觉得更亲切。如果出现基本数据结构不能满足需要的情况，也很容易扩充调整，如实现哈夫曼树时，要比较两棵二叉树根数据的大小，可以用优先队列保存二叉树要检查队列元素个数。实现这种功能的基础是面向对象的继承，以及函数和数据结构的通用性。

目前，数据结构教材上讨论的内容和习题，用Python来解决大多比较方便，程序代码比用C语言要短，概念和结构更清晰，尤其是能更好地反映算法的精髓，有利于学生学习。数据结构课程中一些不好用C语言处理的问题，在基于Python的课程中则能很自然地处理，如操作错误的处理——栈空时弹出可以用Python异常机制描述，符合软件实践的需要，既规范又方便。

4 关于课程中几个具体问题的考虑和建议

数据结构课程的内容和结构成型于20世纪70～80年代，且在那之后没有太大变化，国内也出版了一些使用比较广泛的教材。随着软件领域研究和实践的发展，有些过去不受重视的问题现在变得非常重要，一些理论观点和方法也需要得到重视。

4.1 正则表达式和模式匹配

数据结构课程应该加入有关正则表达式的讨论。实际上，正则表达式才是当前业界广泛使用的模式匹配概念的基础，而且已成为实际软件开发中的重要工具。正则表达式这个概念特别应该纳入专业教学，且比较适合放入数据结构课程，它既有数据结构问题，又有算法问题。我们编写的教材中，“字符串”一章里介绍了正则表达式。在Python里处理这个问题比较方便，我们首先应该推广模式匹配概念，引进正则表达式的概念，先介绍简化的正则表达式的匹配算法，再介绍Python的正则表达式包re。通过介绍这个典型正则表达式包的各个细节，帮助学生了解实际软件开发中使用的正则表达式及其模式匹配功能。

4.2 动态顺序表

现有教材大多采用固定大小的数组实现元素个数可变的数据结构，如顺序表。在C语言里这样做，主要原因是做法比较简单，但是在实际应用中，能随着元素增加而自动增大容量的“动态顺序表”已是当前各种基本类型库的标准配置。Python标准类型list就是动态顺序表，动态增长规则和性质也是与数据结构有关的重要知识。

在C语言里实现动态顺序表并不难，但是代码比较繁琐；采用动态增长技术改造所有可能受容量限制的数据结构，也会带来一些麻烦。在基于Python的课程或教材中，这个问题则比较容易处理，这主要得益于Python标准类型的内在功能。

4.3 分偿（平摊，amotized）复杂性

传统数据结构课程只讨论一次数据结构操作的复杂性，但在当前的软件领域，一系列操作的平均复杂性也是很重要的概念。这个概念被称为平摊复杂性，典型例子是对动态顺序表的尾端插入。如果采用正确的容量扩大策略，大多数操作只有O(1)开销，高代价操作越来越稀少，而平摊复杂性仍然是O(1)。按目前数据结构课程的讨论，在动态顺序表的尾部插入操作，最坏情况时间复杂性是O(n)，但是这样不仅不能很好地反映该操作的性质，还不能将其与其他插入区分开。平摊复杂性已成为当前软件领域考查数据结构实现的重要指标，课程中应加入这方面内容。此外，学习Python的数据结构也必须理解平摊复杂性的概念。

4.4 错误处理

专业基础课应该教给学生正确的编程理念，现有课程在某些问题上没有很好地给予处理。当前最受重视的问题之一是程序安全，其中最主要的问题就是正确处理程序运行中的错误，数据结构中操作失败是典型的运行时错误。对于这个问题，传统C语言教材采用的方式或是不理会，或是输出信息报错，又或是直接调用exit(1)之类语句终止，这些都是错误做法，实际程序操作中不能采用。要在C语言中贯彻一套正确并合理的错误处理理念，会遇到许多困难，也太繁琐。新型语言，如Python的异常机制支持处理运行时错误，而且很容易使用，能给学生传播正确的理念和技术。

4.5 面向对象技术的作用

一方面，我们应该在数据结构的设计和构造中充分展示面向对象编程技术的作用，说明基于已有的类扩充，通过继承、扩充、方法覆盖等，可以非常简单方便地解决遇到的问题，而不需要重新定义。很多新数据结构可以定义为已有数据结构的扩充，在需要某种辅助性数据结构，而已有结构不能完全满足需要时，可以很方便地予以调整。例如，继承简单链接表，定义带尾指针的链接表；继承简单链接表，定义循环链接表；继承简单链接表及其结点，定义双向链接表的结点和双向链接表等。

另一方面，课程中应该尽可能实现通用算法，一种数据结构的不同实现尽可能采用公共接口，这样能使一组算法应用于不同的数据结构实现。例如，图的最常见表示是邻接矩阵和邻接表，一种合理的做法是定义两个表示图的类，它们的内部实现分别采用不同技术，但是提供统一的接口；开发图算法时，所有算法都基于图类的公共接口来定义，使这些算法能应用于采用不同内部表示的图。采用面向对象技术，既方便开发实例，又可以展示面向对象技术的威力和Python语言的能力，Python的通用性本质也起到重要作用。

5 结语

Python语言正越来越多地应用在计算机科学技术基础课程甚至是第一门课程中，这种安排必然会对计算机专业的其他课程产生影响。在研究Python语言的教学使用和生态培育时，必须关注这些问题。如果我们把Python作为计算机科学技术专业第一门课程的工作语言，就必须研究如何用Python教授数据结构课程；如果采用其他语言，数据结构的课程只能推后，还须补充其他语言的知识，这也会对整个专业教育产生影响。我们基于教学经验和思考，讨论了基于Python的数据结构课程的内容设计和教学目标，研究了以Python作为数据结构课程基础的实际可行性和实施中的主要关注点，分析了用Python开设数据结构课程的优势和难点，以及一些重要问题的处理方法。

国内各院校在使用C语言教授数据结构课程方面已经有了很多积累，包括被广泛使用的教材、练习题目以及各种教学支持系统的建设。改用Python教授基础课程时，这些方面基本是空白。如果有更多院校选择这样的课程体系，就需要更多人力和物力的投入；开展相关建设，需要更多人参与，课程内容和教材也需要进一步建设、修改和完善。

[1]AhoAV,HopcroftJE,JeffreyD.Ullman:Thedesignandanalysisofcomputeralgorithms[M].Boston:Addison-Wesley,1974.

[2]WirthN.Algorithms+datastructures=programs[M].UpperSaddleRiver:Prentice-Hall,1976.

[3]MillerBN,RanumDL.ProblemsolvingwithalgorithmsanddatastructuresusingPython[M].2ed.Franklin:Beedleamp;Associates,2011.[4]BakaB.Pythondatastructuresandalgorithms[M].Birmingham:PacktPublishing,2017.

[5]LeeKD,HubbardS.DatastructuresandAlgorithmswithPython(undergraduatetopicsincomputerscience)[M].Berlin:Springer,

20 15.

[6]裘宗燕.数据结构和算法:Python语言描述[M].北京:机械工业出版社,2016.

[7]AgarwalKK.PythonforCS1,CS2andbeyond[J].ConsortiumforComputingSciencesinColleges,2005,20(4):262-270.