Python是国际流行的用于教授入门级程序设计课程的语言，国内高校也开始使用。本书是结合国内数据结构课程现状，以Python作为工作语言，编撰的一本数据结构教程。书中结合抽象数据类型结构的思想，基于Python的面向对象机制，讨论了各种基本数据结构的思想、性质、问题和实现，相关算法的设计、实现和特性等。书中还研究了一些数据结构的应用案例。本书要求学习者已有基本Python程序设计的知识和经验，可以作为基于Python的计算机基础课程中的数据结构课程教材，也可以作为学习Python语言基本内容之后的面向对象等高级编程技术的进阶读物。

无

本书基于作者在北京大学用Python讲授相应课程的经验，用Python作为工作语言讨论数据结构和算法的基本问题。撰写过程中主要有以下几方面考虑：
●作为以Python为第一门计算机编程课程之后相应的数据结构课程的教材。
●结合数据结构和算法，讨论Python中重要数据类型的实现情况和性质，帮助读者理解Python语言程序，学习如何写出高效的Python程序。
●展示Python的面向对象技术可以怎样运用。书中构造了一批相互关联的数据结构类，前面定义的类被反复应用在后续章节的数据结构和算法中。鉴于这些情况，本书不但可以作为数据结构课程的教材，也可以作为学习Python语言编程技术的后续读物（假设读者已经有了Python编程的基本知识）。
由于Python语言的一些优点，近年来，国外已经有不少大学（包括许多一流大学）采用它作为第一门计算机科学技术课程的教学语言，国内院校也已经出现这种变化。作者在北京大学数学学院开设了基于Python语言的程序设计和数据结构课程，通过亲身实践，发现用Python讲授这两门课程也是一种很好的安排。
用Python学习数据结构，最大的优点就是可以看到复杂的数据结构怎样一步步地从基本的语言机制构造起来。在一个章节里定义的数据结构，经常可以在后续章节的算法和数据结构中直接使用，如果不适用，常常可以通过简单的类派生来调整。这些数据结构还可以非常方便地用在各种练习里，或用于解决实际问题。学生可以看到书中的（或他们自己写的）代码不是玩具，而是切实有用的软件构件。在基于本书的课程中，很容易安排一些有一定规模的面向实际应用的开发课题，使学生得到更好的实际锻炼。
第2版做了些内容调整，主要是精简了有关Python面向对象的讨论，增加（或者充实）了广义表和数组（3.6节）、等价类和查并集（6.8节）、平衡二叉树的删除操作（8.7.4节）、外存字典（8.8.4节）、外排序问题和算法（9.6节）等方面的内容。本书覆盖了大部分高校数据结构课程（教材）的基本内容和研究生入学考试要求的数据结构知识。
本书的成型源于作者多年讲授基于C语言的数据结构课程的经验，张乃孝老师的《算法与数据结构——C语言描述》是作者一直使用的教材，本书编写时也参考了该书的一些体例。此外，北京大学数学学院2013级的学生在学习中提出了许多很好的问题，参加课程辅导工作的刘海洋、胡婷婷、张可和陈晨也提供了很多帮助。在此表示衷心的感谢。

裘宗燕
2021年9月于北京

计算机\程序设计

目前，Python已经成为世界上广受欢迎的编程语言之一，由于其具有的众多优点，Python正在被越来越多大学用作第一门程序设计课程的语言，更多学校把它作为后续或选修课程的内容。
本书是一本基于Python语言的数据结构教材，旨在结合抽象数据类型结构的思想，基于Python的面向对象机制，阐述各种基本数据结构的想法、性质、问题和实现，讨论一些相关算法的设计、实现和特性，并研究了一些数据结构的应用案例。
本书还加强了一些当前程序设计实践领域特别关注的内容，包括程序和数据结构设计中的安全性问题、正则表达式的概念和使用等。第2版精简了有关Python面向对象的讨论，增加（或者充实）了广义表和数组、等价类和查并集、平衡二叉树的删除操作、外存字典、外排序问题和算法等方面的内容。
本书覆盖高校数据结构课程和研究生入学考试的基本要求，既可以作为基于Python的数据结构课程教材，也可以作为Python语言之后学习面向对象等高级编程技术的进阶读物。

作者介绍
裘宗燕，北京大学数学学院信息科学系教授。长期从事计算机软件与理论、程序设计语言和符号计算方面的研究与教学工作。已出版多部著作和译著，包括《程序设计语言基础》（译著，北京大学出版社，1990），《Mathematics数学软件系统的应用与程序设计》（编著，北京大学出版社，1994），《C++程序设计语言（特别版）》（译著，机械工业出版社，2002），《C++语言的设计和演化》（译著，机械工业出版社，2002），《程序设计语言——概念和结构》（合译，机械工业出版社，2002），《从问题到程序——程序设计与C语言引论》（编著，机械工业出版社，2005年第1版，2011年第2版）等。

裘宗燕：
裘宗燕: 北京大学数学学院信息科学系教授。长期从事计算机软件与理论、程序设计语言和符号计算方面的研究和教学工作。已出版多部著作和译著，包括《程序设计语言基础》（译著，北京大学出版社，1990），《Mathematica数学软件系统的应用与程序设计》（编著，北京大学出版社，1994），《计算概论（上）》（合著，高等教育出版社，1997），《从问题到程序—程序设计与C语言引论》（编著，北京大学出版社，1999）等；自2000年以来，他先后为机械工业出版社华章分社翻译了《程序设计实践》（2000），《C++程序设计语言（特别版）》（2001），《C++语言的设计和演化》（2002），《程序设计语言——概念和结构》（2002），《从规范出发的程序设计》（2003），《计算机程序的构造和解释》（2004）等一系列经典著作，他认真的工作作风、严谨的治学态度，以及所做出的巨大贡献，赢得广大读者的好评。 在北京大学教授的主要课程：计算概论（一年级本科生，主要内容为C语言程序设计），程序设计技术与方法（本科生），程序设计语言原理（研究生），算法和数据结构（本科生），算法设计与分析（本科生和研究生），数理逻辑（本科生）等。 点击进入[URL=http://www.math.pku.edu.cn/teachers/qiuzy/]作者主页[/URL]。

前言
第1章　绪论1
　1.1　计算机问题求解1
　　1.1.1　程序开发过程1
　　1.1.2　一个简单例子3
　1.2　问题求解：交叉路口的红绿灯安排4
　　1.2.1　问题分析和严格化5
　　1.2.2　图的顶点分组和算法6
　　1.2.3　算法的精化和Python描述7
　　1.2.4　讨论8
　1.3　算法和算法分析10
　　1.3.1　问题、问题实例和算法10
　　1.3.2　算法的代价及其度量13
　　1.3.3　算法分析19
　　1.3.4　Python程序的计算代价（复杂度）21
　1.4　数据结构24
　　1.4.1　数据结构及其分类24
　　1.4.2　计算机内存对象表示27
　　1.4.3　Python对象和数据结构30
　练习32
第2章　抽象数据类型和Python类34
　2.1　抽象数据类型34
　　2.1.1　数据类型和数据构造34
　　2.1.2　抽象数据类型的概念36
　　2.1.3　抽象数据类型的描述37
　2.2　Python的类和面向对象编程39
　　2.2.1　类的定义和使用39
　　2.2.2　继承44
　　2.2.3　异常类和自定义异常48
　　2.2.4　本书采用的ADT描述形式50
　总结50
　练习51
第3章　线性表53
　3.1　线性表的概念和表抽象数据类型53
　　3.1.1　表的概念和性质53
　　3.1.2　表抽象数据类型53
　　3.1.3　线性表的实现：基本考虑55
　3.2　顺序表56
　　3.2.1　基本实现方式56
　　3.2.2　顺序表基本操作的实现57
　　3.2.3　顺序表的实现结构61
　　3.2.4　Python的list64
　　3.2.5　顺序表的简单总结65
　3.3　链接表66
　　3.3.1　线性表的基本需要和链接表66
　　3.3.2　单链表67
　　3.3.3　单链表类的实现72
　3.4　链表的变形和操作75
　　3.4.1　单链表的简单变形75
　　3.4.2　循环单链表78
　　3.4.3　双链表79
　　3.4.4　两个链表操作81
　　3.4.5　在顺序表里实现“链表”85
　　3.4.6　不同链表的简单总结86
　3.5　表的应用87
　　3.5.1　Josephus问题和基于数组概念的解法87
　　3.5.2　基于顺序表的解88
　　3.5.3　基于循环单链表的解88
*3.6　广义表和数组　本书中标星号的小节为选学/选讲内容。89
　　3.6.1　广义表89
　　3.6.2　数组92
　　3.6.3　矩阵94
　总结97
　练习98
第4章　字符串102
　4.1　字符集、字符串和字符串操作102
　　4.1.1　字符串的相关概念102
　　4.1.2　字符串抽象数据类型104
　4.2　字符串的实现104
　　4.2.1　基本实现问题和技术104
　　4.2.2　实际语言里的字符串105
　　4.2.3　Python的字符串106
　4.3　字符串匹配（子串查找）107
　　4.3.1　字符串匹配问题107
　　4.3.2　串匹配和朴素匹配算法108
　　4.3.3　无回溯串匹配算法（KMP算法）110
　4.4　字符串匹配问题115
　　4.4.1　串匹配/搜索的不同需要115
　　4.4.2　一种简化的正则表达式117
*4.5　Python正则表达式119
　　4.5.1　正则表达式标准库包re119
　　4.5.2　基本情况119
　　4.5.3　主要操作120
　　4.5.4　正则表达式的构造121
　　4.5.5　正则表达式的使用127
　总结127
　练习128
第5章　栈和队列130
　5.1　概述130
　　5.1.1　栈、队列和数据使用顺序130
　　5.1.2　应用环境131
　5.2　栈：概念和实现131
　　5.2.1　栈抽象数据类型131
　　5.2.2　栈的顺序表实现132
　　5.2.3　栈的链接表实现134
　5.3　栈的应用134
　　5.3.1　简单应用：括号匹配问题135
　　5.3.2　表达式的表示、计算和变换137
　　5.3.3　栈与递归144
　5.4　队列149
　　5.4.1　队列抽象数据类型149
　　5.4.2　队列的链接表实现150
　　5.4.3　队列的顺序表实现150
　　5.4.4　队列的list实现152
　　5.4.5　队列的应用155
　5.5　迷宫求解和状态空间搜索156
　　5.5.1　迷宫求解：分析和设计156
　　5.5.2　求解迷宫的算法159
　　5.5.3　迷宫问题和搜索161
　5.6　几点补充166
　　5.6.1　与栈或队列相关的几种结构166
　　5.6.2　顺序实现和链接实现166
　总结167
　练习168
第6章　二叉树和树170
　6.1　二叉树170
　　6.1.1　概念和性质170
　　6.1.2　抽象数据类型175
　　6.1.3　遍历二叉树176
　6.2　二叉树的list实现177
　　6.2.1　设计和实现178
　　6.2.2　二叉树的简单应用：表达式树179
　6.3　优先队列182
　　6.3.1　概念182
　　6.3.2　基于线性表的实现183
　　6.3.3　树形结构和堆185
　　6.3.4　优先队列的堆实现186
　　6.3.5　堆的应用：堆排序189
　6.4　应用：离散事件模拟190
　　6.4.1　通用的模拟框架191
　　6.4.2　海关检查站模拟系统192
　6.5　二叉树的类实现196
　　6.5.1　二叉树结点类197
　　6.5.2　遍历算法198
　　6.5.3　二叉树类202
　6.6　哈夫曼树203
　　6.6.1　哈夫曼树和哈夫曼算法203
　　6.6.2　哈夫曼算法的实现204
　　6.6.3　哈夫曼编码205
　6.7　树和树林207
　　6.7.1　实例和表示207
　　6.7.2　定义和相关概念208
　　6.7.3　抽象数据类型和操作210
　　6.7.4　树的实现211
　　6.7.5　树的Python实现212
*6.8　等价类和查并集214
　　6.8.1　概念和问题214
　　6.8.2　朴素实现215
　　6.8.3　用树表示集合215
　　6.8.4　优化结构217
　总结219
　练习220
第7章　图224
　7.1　概念、性质和实现224
　　7.1.1　定义和图示224
　　7.1.2　图的一些概念和性质225
　　7.1.3　图抽象数据类型228
　　7.1.4　图的表示和实现228
　7.2　图的Python实现231
　　7.2.1　邻接矩阵实现232
　　7.2.2　压缩的邻接矩阵（邻接表）实现233
　　7.2.3　小结235
　7.3　基本图算法235
　　7.3.1　图的遍历236
　　7.3.2　生成树238
　7.4　最小生成树240
　　7.4.1　最小生成树问题240
　　7.4.2　Kruskal算法240
　　7.4.3　Prim算法243
　*7.4.4　Prim算法的改进246
　　7.4.5　最小生成树问题247
　7.5　最短路径247
　　7.5.1　最短路径问题248
　　7.5.2　求解单源点最短路径：Dijkstra算法248
　　7.5.3　求解所有顶点之间的最短路径：Floyd算法251
　　7.5.4　最短路径问题254
　7.6　AOV网/AOE网及其算法254
　　7.6.1　AOV网、拓扑排序和拓扑序列255
　　7.6.2　拓扑排序算法256
　　7.6.3　AOE网和关键路径258
　　7.6.4　关键路径算法258
　总结261
　练习261
第8章　字典和集合264
　8.1　数据存储、检索和字典264
　　8.1.1　数据存储和检索264
　　8.1.2　字典实现的问题266
　8.2　字典的线性表实现268
　　8.2.1　基本实现268
　　8.2.2　有序顺序表和二分法检索269
　　8.2.3　线性表字典总结271
　8.3　散列和散列表272
　　8.3.1　散列的思想和应用272
　　8.3.2　散列函数274
　　8.3.3　冲突的内消解：开地址技术276
　　8.3.4　外消解技术279
　　8.3.5　散列表的性质279
　8.4　集合281
　　8.4.1　集合的概念、运算和抽象数据类型281
　　8.4.2　集合的实现283
　　8.4.3　特殊实现技术：位向量实现284
　8.5　Python的标准字典类dict和集合类set285
　8.6　二叉排序树和字典286
　　8.6.1　二叉排序树287
　　8.6.2　最佳二叉排序树294
　　8.6.3　一般情况的最佳二叉排序树296
　8.7　平衡二叉树301
　　8.7.1　定义和性质302
　　8.7.2　AVL树类303
　　8.7.3　插入操作303
　*8.7.4　删除操作309
　　8.7.5　几种二叉排序树的对比312
　8.8　动态多分支排序树和外存字典313
　　8.8.1　多分支排序树313
　　8.8.2　B树314
　　8.8.3　B＋树316
　*8.8.4　外存字典317
　总结319
　练习320
第9章　排序322
　9.1　问题和性质322
　　9.1.1　问题定义322
　　9.1.2　排序算法323
　9.2　简单排序算法325
　　9.2.1　插入排序326
　　9.2.2　选择排序327
　　9.2.3　交换排序329
　9.3　快速排序331
　　9.3.1　快速排序的表实现331
　　9.3.2　程序实现332
　　9.3.3　复杂度分析333
　　9.3.4　另一种简单实现334
　9.4　归并排序335
　　9.4.1　顺序表的归并排序示例335
　　9.4.2　归并算法的设计和实现336
　　9.4.3　算法分析337
　9.5　其他排序方法和问题338
　　9.5.1　分配排序和基数排序338
　　9.5.2　一些情况340
　　9.5.3　Python系统的排序算法342
*9.6　外排序问题和算法343
　　9.6.1　外存数据的排序问题343
　　9.6.2　基本外存排序算法343
　　9.6.3　多路归并345
　总结347
　练习348
参考文献350