前　言

本书基于作者在北京大学用Python讲授相应课程的工作，用Python作为工作语言讨论数据结构和算法的基本问题，其撰写主要有下面几方面考虑：
作为以Python为第一门计算机课程之后相应的数据结构课程的教材。
结合数据结构和算法，讨论Python中重要数据类型的实现情况和性质，帮助读者理解Python语言程序，理解如何写出高效的Python程序。
展示Python的面向对象技术可以怎样运用。书中构造了一批相互关联的数据结构类，前面定义的类被反复应用在后续章节的数据结构和算法中。
基于这些情况，本书不但可以作为数据结构课程的教材，也可以作为学习Python语言编程技术的后续读物（假设读者已经有了Python编程的基本知识）。
由于Python语言的一些优点，近年来，国外已经有不少大学采用它作为第一门计算机科学技术课程的教学语言，包括许多一流大学。国内院校也可能参考这种趋势，出现这种变化。作者在北京大学数学学院开设了基于Python语言的程序设计和数据结构课程，通过亲身实践，发现用Python讲授这两门课程也是一种很好的安排。
用Python学习数据结构，最大的优点就是可以看到复杂的数据结构可以怎样一步步地从基本的语言机制构造起来。在一个章节里定义的数据结构，经常可以在后续章节的算法和数据结构中直接使用，如果不适用，常常可以通过简单的类派生来调整。还可以非常方便地用在各种习题和练习里，或用于解决实际问题。学生可以看到，书中的（或他们自己写的）代码不是玩具，而是切实有用的软件构件。在基于本书的课程中，很容易安排一些有一定规模的面向实际应用的开发课题，使学生得到更好的实际锻炼。
书中标*的节或小节作为选讲内容，或留给学生自己阅读。
本书的成型也得益于作者多年讲授基于C语言的数据结构课程的经验，张乃孝老师的《算法和数据结构》是作者一直使用的教材，本书在编写中也参考了该书的一些体例。此外，北京大学数学学院2013级的同学在学习中提出了许多很好的问题，参加课程辅导工作的刘海洋、胡婷婷、张可和陈晨也提供了很多帮助，在此表示特别的感谢。

目 录

第1章绪论
1.1计算机问题求解
1.2　问题求解：交叉路口的红绿灯安排
1.3算法和算法分析
1.4数据结构
练习
第2章抽象数据类型和Python类
2.1抽象数据类型
2.2Python的类
2.3类的定义和使用
2.4Python异常
2.5类定义实例：学校人事管理系统中的类
本章总结
练习
第3章线性表
3.1线性表的概念和表抽象数据类型
3.2顺序表的实现
3.3链接表
3.4链表的变形和操作
3.5表的应用
本章总结
练习
第4章　字符串
4.1　字符集、字符串和字符串操作
4.1.1　字符串的相关概念
4.1.2　字符串抽象数据类型
4.2　字符串的实现
4.2.1　基本实现问题和技术
4.2.2　实际语言里的字符串
4.2.3　Python的字符串
4.3　字符串匹配（子串查找）
4.3.1　字符串匹配
4.3.2　串匹配和朴素匹配算法
4.3.3　无回溯串匹配算法（KMP算法）
4.4　字符串匹配问题
4.4.1　串匹配/搜索的不同需要
4.4.2　一种简化的正则表达式
4.5　Python正则表达式
4.5.1　概况
4.5.2　基本情况
4.5.3　主要操作
4.5.4　正则表达式的构造
4.5.5　正则表达式的使用
本章总结
练习