第1章 Python编程基础

1.1基本程序要素

1.1.1程序和模块

1.1.2 Python程序示例：猜数字

1.1.3编辑、编译并运行Python程序

1.1.4程序注释

1.1.5词法元素

1.1.6拼写和命名惯例

1.1.7语法元素

1.1.8字面值

1.1.9字符串字面值

1.1.10运算符和表达式

1.1.11函数调用

1.1.12 pRInt函数

1.1.13 input函数

1.1.14类型转换函数和混合模式运算

1.1.15 可选的和关键字函数参数

1.1.16变量和赋值语句

1.1.17 Python数据类型

1.1.18 import语句

1.1.19获取关于程序组件的帮助

1.2控制语句

1.2.1条件式语句

1.2.2使用if name__==“_main”

1.2.3循环语句

1.3字符串及其运算

1.3.1运算符

1.3.2格式化字符串以便输出

1.3.3对象和方法调用

1.4内建Python集合及其操作

1.4.1列表

1.4.2元组

1.4.3遍历序列

1.4.4字典

1.4.5搜索一个值

1.4.6对集合应用模式匹配

1.5编写新的函数

1.5.1函数定义

1.5.2递归函数

1.5.3嵌套的函数定义

1.5.4高阶函数

1.5.5使用lambda表达式创建匿名函数

1.6捕获异常

1.7文件及其操作

1.7.1文本文件的输出

1.7.2将数字写入到一个文本文件

1.7.3从文本文件读取文本

1.7.4从文件读取数字

1.7.5使用pickle读写对象

1.8创建新的类

1.9编程项目

第2章 集合概览

2.1集合类型

2.1.1线性集合

2.1.2层级集合

2.1.3图集合

2.1.4无序集合

2.1.5有序集合

2.1.6集合类型的分类

2.2集合上的操作

2.3集合的实现

2.4小结

2.5复习题

2.6编程项目

第3章 搜索、排序和复杂度分析

3.1评估算法的性能

3.1.1度量算法的运行时间

3.1.2统计指令

3.1.3度量算法所使用的内存

3.1.4练习3.1

3.2复杂度分析

3.2.1复杂度的阶

3.2.2大O表示法

3.2.3常量比例的作用

3.2.4练习3.2

3.3搜索算法

3.3.1搜索最小值

3.3.2顺序搜索一个列表

3.3.3最好情况、最坏情况和平均情况的性能

3.3.4有序列表的二叉搜索

3.3.5比较数据项

3.3.6练习3.3

3.4基本排序算法

3.4.1选择排序

3.4.2冒泡排序

3.4.3插入排序

3.4.4再谈最好情况、最坏情况和平均情况的性能

3.4.5练习3.4

3.5更快的排序

3.5.1快速排序简介

3.5.2合并排序

3.5.3练习3.5

3.6指数算法：递归式的Fibonacci

3.7案例学习：算法探查器

3.7.1需求

3.7.2分析

3.7.3设计

3.7.4实现（编写代码）

3.8小结

3.9复习题

3.10编程项目

第4章 数组和链表结构

4.1数组数据结构

4.1.1随机访问和连续内存

4.1.2静态内存和动态内存

4.1.3物理大小和逻辑大小

4.1.4练习4.1

4.2数组的操作

4.2.1增加数组的大小

4.2.2减小数组的大小

4.2.3在数组中插入一项

4.2.4从数组中删除一项

4.2.5复杂度权衡：时间、空间和数组

4.2.6练习4.2

4.3二维数组

4.3.1处理网格

4.3.2创建并初始化网格

4.3.3定义Grid类

4.3.4杂乱的网格和多维数组

4.3.5练习4.3

4.4链表结构

4.4.1单链表结构和双链表结构

4.4.2非连续性内存和节点

4.4.3定义一个单链表节点类

4.4.4使用单链表节点类

4.4.5练习4.4

4.5单链表结构上的操作

4.5.1遍历

4.5.2搜索

4.5.3替换

4.5.4在开始处插入

4.5.5在末尾插入

4.5.6从开始处删除

4.5.7从末尾删除

4.5.8在任何位置插入

4.5.9从任意位置删除

4.5.10复杂度权衡：时间、空间和单链表结构

4.5.11练习4.5

4.6链表的变体

4.6.1带有一个哑头节点的循环链表结构

4.6.2双链表结构

4.6.3练习4.6

4.7小结

4.8复习题

4.9编程项目

第5章 接口、实现和多态

5.1开发接口

5.1.1定义包接口

5.1.2指定参数和返回值

5.1.3构造方法和实现类

5.1.4先验条件、后验条件、异常和文档

5.1.5用Python编写接口

5.1.6练习5.1

5.2开发一个基于数组的实现

5.2.1选择并初始化数据结构

5.2.2先完成容易的方法

5.2.3完成迭代器

5.2.4完成使用迭代器的方法

5.2.5 in运算符和contains方法

5.2.6完成remove方法

5.2.7练习5.2

5.3开发一个基于链表的实现

5.3.1初始化数据结构

5.3.2完成迭代器

5.3.3完成clear和add方法

5.3.4完成remove方法

5.3.5练习5.3

5.4两个包实现的运行时性能

5.5测试两个包实现

5.6用UML图表示包资源

5.7小结

5.8复习题

5.9编程项目

第6章 继承和抽象类

6.1使用继承定制一个己有的类

6.1.1已有类的子类化

6.1.2再谈init方法

6.1.3添加新的contains方法

6.1.4修改已有的add方法

6.1.5 ArraySortedBag的运行时间性能

6.1.6 Python中的类层级

6.1.7练习6.1

6.2使用抽象类去除代码冗余性

6.2.1设计一个AbstractBag类

6.2.2重新编写AbstractBag中的init方法

6.2.3修改AbstractBag的子类

6.2.4将AbstractBag中的add方法泛化

6.3所有集合的一个抽象类

6.3.1将AbstractCollection整合到集合层级中

6.3.2在__eq__方法中使用两个迭代器

6.3.3练习6.2

6.4小结

6.5复习题

6.6编程项目

第7章 栈

7.1栈概览

7.2使用栈

7.2.1栈接口

7.2.2初始化一个栈

7.2.3示例应用程序：匹配括号

7.2.4练习7.1

7.3栈的3种应用

7.3.1计算算术表达式

7.3.2计算后缀表达式

7.3.3练习7.2

7.3.4将中缀表达式转换为后缀表达式

7.3.5练习7.3

7.3.6回溯算法

7.3.7内存管理

7.4栈的实现

7.4.1测试驱动程序

7.4.2将栈添加到集合层级中

7.4.3数组实现

7.4.4链表实现

7.4.5 AbstractStack类的作用

7.4.6两种实现的时间和空间分析

7.4.7练习7.4

7.5案例学习：计算后缀表达式

7.5.1要求

7.5.2分析

7.5.3设计

7.5.4实现

7.6小结

7.7复习题

7.8编程项目

第8章 队列

8.1队列概览

8.2队列接口及其应用

练习8.1

8.3队列的两个应用

8.3.1模拟

8.3.2轮询CPU调度

8.3.3练习8.2

8.4队列的实现

8.4.1队列的链表实现

8.4.2数组实现

8.4.3两种实现的时间和空间复杂度分析

8.4.4练习8.3

8.5案例学习：模拟超市排队结账

8.5.1要求

8.5.2分析

8.5.3用户界面

8.5.4类及其作用

8.6优先队列

练习8.4

8.7案例学习：急症室调度

8.7.1需求

8.7.2分析

8.7.3类

8.7.4设计和实现

8.8小结

8.9复习题

8.10编程项目

第9章 列表

9.1概览

9.2使用列表

9.2.1基于索引的操作

9.2.2基于内容的操作

9.2.3基于位置的操作

9.2.4列表的接口

9.2.5练习9.1

9.3列表的应用

9.3.1堆存储管理

9.3.2组织磁盘上的文件

9.3.3其他集合的实现

9.4列表实现

9.4.1 AbstractList类的角色

9.4.2基于数组的实现

9.4.3链表实现

9.4.4两种实现的时间和空间分析

9.4.5练习9.2

9.5实现列表迭代器

9.5.1列表迭代器的角色和作用

9.5.2设置和实例化一个列表迭代器类

9.5.3列表迭代器中的导航方法

9.5.4列表迭代器中的修改器方法

9.5.5链表列表的列表迭代器的设计

9.5.6列表迭代器实现的时间和空间分析

9.6案例学习：开发一个有序的列表

9.6.1要求

9.6.2分析

9.6.3设计

9.6.4实现（代码）

9.7小结

9.8复习题

9.9编程项目

第10章 树

10.1树的概览

10.1.1树的术语

10.1.2普通的树和二叉树

10.1.3树的递归定义

10.1.4练习10.1

10.2为什么要使用树

10.3二叉树的形状

练习10.2

10.4二叉树的3种常见应用

10.4.1堆

10.4.2二叉搜索树

10.4.3表达式树

10.4.4练习10.3

10.5二叉树的遍历

10.5.1前序遍历

10.5.2中序遍历

10.5.3后序遍历

10.5.4层序遍历

10.6开发二叉搜索树

10.6.1二叉搜索树接口

10.6.2链表实现的数据结构

10.6.3二叉搜索树的复杂度分析

10.6.4练习10.4

10.7递归的后代解析和编程语言

10.7.1语法简介

10.7.2在语言中识别、解析和解释句子

10.7.3词法分析和扫描器

10.7.4解析策略

10.8案例学习：解析和表达式树

10.8.1要求

10.8.2分析

10.8.3节点类的设计和实现

10.8.4解析器类的设计和实现

10.9二叉树的数组实现

练习10.5

10.10实现堆

练习10.6

10.11小结

10.12复习题

10.13编程项目

第11章 集和字典

11.1使用集

11.2 Python的set类

11.2.1集的一个示例会话

11.2.2集的应用

11.2.3集和包的关系

11.2.4集和字典的关系

11.2.5集的实现

11.2.6练习11.1

11.3集的基于数组和链表的实现

11.3.1 AbstractSet类

11.3.2 ArraySet类

11.4使用字典

11.5基于数组和基于链表的字典实现

11.5.1 Item类

11.5.2 AbstractDict类

11.5.3 ArrayDict类

11.5.4集和字典的基于数组和列表的实现的复杂度分析

11.5.5练习11.2

11.6哈希策略

11.6.1冲突和密度的关系

11.6.2非数字键的哈希

11.6.3线性探测

11.6.4二次探测

11.6.5链化

11.6.6复杂度分析

11.6.7练习11.3

11.7案例学习：探查哈希策略

11.7.1需求

11.7.2分析

11.7.3设计

11.8集的哈希实现

11.9字典的哈希实现

练习11.4

11.10有序的集和字典

11.11小结

11.12复习题

11.13编程项目

第12章 图

12.1图的术语

练习12.1

12.2为什么使用图

12.3图的表示

12.3.1相邻矩阵

12.3.2 邻接表

12.3.3两种表示的分析

12.3.4运行时间的进一步考虑

12.3.5练习12.2

12.4图的遍历

12.4.1泛型遍历算法

12.4.2广度优先遍历和深度优先遍历

12.4.3图区域

12.4.4练习12.3

12.5图中的树

12.5.1生成树和森林

12.5.2最小生成树

12.5.3最小生成树的算法

12.6拓扑排序

12.7最短路径问题

12.7.1 Dijkstra算法

12.7.2初始化步骤

12.7.3计算步骤

12.7.4无限的表示和用法

12.7.5分析

12.7.6练习12.4

12.7.7 Floyd算法

12.7.8分析

12.8开发一个图集合

12.8.1使用图集合的示例

12.8.2 LinkedDirected-Graph类

12.8.3 LinkedVertex类

12.8.4 LinkedEdge类

12.9案例学习：测试图算法

12.9.1需求

12.9.2分析

12.9.3 GraphDemoView类和GraphDemoModel类

12.9.4实现（代码）

12.10小结

12.11复习题

12.12编程项目

附录 供Python程序员使用的集合框架