数据结构(Python语言描述)(第2版)电子书

版 权

版权声明

内容提要

作者简介

致 谢

前 言

服务与支持

第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 print函数

1.1.12 input函数

1.1.13 类型转换函数和混合模式操作

1.1.14 可选和关键字函数参数

1.1.15 变量和赋值语句

1.1.16 Python的数据类型

1.1.17 import语句

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

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.2.1 所有多项集类型中的基本操作

2.2.2 类型转换

2.2.3 克隆和相等性

2.3 迭代器和高阶函数

2.4 多项集的实现

2.5 章节总结

2.6 复习题

2.7 编程项目

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

3.1 衡量算法的效率

3.1.1 衡量算法的运行时

3.1.2 统计指令数

3.1.3 衡量算法使用的内存

3.2 复杂度分析

3.2.1 复杂度的阶

3.2.2 大O表示法

3.2.3 比例常数的作用

3.3 搜索算法

3.3.1 最小值搜索

3.3.2 顺序搜索列表

3.3.3 最好情况、最坏情况以及平均情况下的性能

3.3.4 基于有序列表的二分搜索

3.3.5 比较数据元素

3.4 基本的排序算法

3.4.1 选择排序

3.4.2 冒泡排序

3.4.3 插入排序

3.4.4 再论最好情况、最坏情况以及平均情况下的性能

3.5 更快的排序

3.5.1 快速排序

3.5.2 归并排序

3.6 指数复杂度的算法：递归斐波那契

将斐波那契转换为线性算法

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.2 数组的操作

4.2.1 增大数组的尺寸

4.2.2 减小数组的尺寸

4.2.3 将元素插入增大的数组

4.2.4 从数组里删除元素

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

4.3 二维数组（网格）

4.3.1 使用网格

4.3.2 创建并初始化网格

4.3.3 定义Grid类

4.3.4 参差不齐的网格和多维数组

4.4 链接结构

4.4.1 单向链接结构和双向链接结构

4.4.2 非连续内存和节点

4.4.3 定义单向链接节点类

4.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.6 链接上的变化

4.6.1 包含虚拟头节点的环状链接结构

4.6.2 双向链接结构

4.7 章节总结

4.8 复习题

4.9 编程项目

第5章 接口、实现和多态

5.1 开发接口

5.1.1 设计包接口

5.1.2 指定参数和返回值

5.2 构造函数和类的实现

5.2.1 前置条件、后置条件、异常和文档

5.2.2 在Python里编写接口

5.3 开发基于数组的实现

5.3.1 选择并初始化数据结构

5.3.2 先完成简单的方法

5.3.3 完成迭代器

5.3.4 完成使用迭代器的方法

5.3.5 in运算符和__contains__方法

5.3.6 完成remove方法

5.4 开发基于链接的实现

5.4.1 初始化数据结构

5.4.2 完成迭代器

5.4.3 完成clear和add方法

5.4.4 完成remove方法

5.5 两种包实现的运行时性能

5.6 测试包的两种实现

5.7 使用UML绘制包资源

5.8 章节总结

5.9 复习题

5.10 编程项目

第6章 继承与抽象类

6.1 使用继承定制已经存在的类

6.1.1 已有类的子类

6.1.2 修改__init__方法

6.1.3 添加新的contains方法

6.1.4 修改已有的add方法

6.1.5 修改已有的__add__方法

6.1.6 ArraySortedBag的运行时性能

6.1.7 Python里类的层次结构的解释

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.4 多项集的专家级框架

6.5 章节总结

6.6 复习题

6.7 编程项目

第7章 栈

7.1 栈的概述

7.2 使用栈

7.2.1 栈接口

7.2.2 栈的实例化

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

7.3 栈的3个应用程序

7.3.1 算术表达式的求值

7.3.2 计算后缀表达式

7.3.3 把中缀表达式转换为后缀表达式

7.3.4 回溯算法

7.3.5 内存管理

7.4 栈的实现

7.4.1 测试驱动

7.4.2 将栈添加到多项集的层次结构

7.4.3 栈的数组实现

7.4.4 栈的链接实现

7.4.5 抽象栈类的作用

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

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.3 队列的两个应用

8.3.1 计算机模拟

8.3.2 CPU的轮询调度

8.4 队列的实现

8.4.1 队列的链接实现

8.4.2 队列的数组实现

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

8.5 案例研究：超市收银排队的模拟

8.5.1 案例需求

8.5.2 案例分析

8.5.3 用户交互接口

8.5.4 类和它们的职责

8.6 优先队列

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.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.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.7.1 类Lisp列表的基本操作

9.7.2 类Lisp列表的递归遍历

9.7.3 创建类Lisp列表

9.7.4 类Lisp列表的内部结构

9.7.5 使用__repr__在IDLE里输出类Lisp列表

9.7.6 列表和函数式编程

9.8 章节总结

9.9 复习题

9.10 编程项目

第10章 树

10.1 树的概述

10.1.1 树的术语

10.1.2 普通树和二叉树

10.1.3 树的递归定义

10.2 用树结构的原因

10.3 二叉树的形状

10.4 二叉树的遍历

10.4.1 前序遍历

10.4.2 中序遍历

10.4.3 后序遍历

10.4.4 层次遍历

10.5 二叉树的3种常见应用

10.5.1 堆

10.5.2 二叉查找树

10.5.3 表达式树

10.6 开发二叉查找树

10.6.1 二叉查找树接口

10.6.2 链接实现的数据结构

10.6.3 二叉查找树的复杂度分析

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.10 堆的实现

10.11 章节总结

10.12 复习题

10.13 编程项目

第11章 集合和字典

11.1 使用集合

11.2 Python的集合类

11.2.1 使用集合的交互示例

11.2.2 集合的应用

11.2.3 集合和包之间的关系

11.2.4 集合与字典之间的关系

11.2.5 集合的实现

11.3 集合的数组实现和链接实现

11.3.1 AbstractSet类

11.3.2 ArraySet类

11.4 使用字典

11.5 字典的数组实现和链接实现

11.5.1 Entry类

11.5.2 AbstractDict类

11.5.3 ArrayDict类

11.5.4 字典的数组实现和链接实现的复杂度分析

11.6 哈希策略

11.6.1 冲突与密度的关系

11.6.2 非数字键的哈希

11.6.3 线性探测法

11.6.4 二次探测法

11.6.5 链式法

11.6.6 复杂度分析

11.7 案例研究：分析哈希策略

11.7.1 案例需求

11.7.2 案例分析

11.7.3 案例设计

11.7.4 案例实现

11.8 集合的哈希实现

11.9 字典的哈希实现

11.10 有序集合和有序字典

11.11 章节总结

11.12 复习题

11.13 编程项目

第12章 图

12.1 使用图的原因

12.2 图的术语

12.3 图的存储方式

12.3.1 邻接矩阵

12.3.2 邻接表

12.3.3 两种存储方式的分析

12.3.4 对运行时的进一步思考

12.4 图的遍历

12.4.1 通用遍历算法

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

12.4.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 Floyd算法

12.7.7 分析

12.8 开发图多项集

12.8.1 图多项集的用法示例

12.8.2 LinkedDirectedGraph类

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 编程项目