数据结构与算法 Python语言实现PDF电子书下载

第1章 Python入门 1

1.1 Python概述 1

1.1.1 Python解释器 1

1.1.2 Python程序预览 1

1.2 Python对象 2

1.2.1 标识符、对象和赋值语句 2

1.2.2 创建和使用对象 4

1.2.3 Python的内置类 4

1.3 表达式、运算符和优先级 8

1.4 控制流程 12

1.4.1 条件语句 12

1.4.2 循环语句 14

1.5 函数 16

1.5.1 信息传递 17

1.5.2 Python的内置函数 19

1.6 简单的输入和输出 20

1.6.1 控制台输入和输出 21

1.6.2 文件 21

1.7 异常处理 22

1.7.1 抛出异常 23

1.7.2 捕捉异常 24

1.8 迭代器和生成器 26

1.9 Python的其他便利特点 28

1.9.1 条件表达式 29

1.9.2 解析语法 29

1.9.3 序列类型的打包和解包 30

1.10 作用域和命名空间 31

1.11 模块和import语句 32

1.12 练习 34

扩展阅读 36

第2章 面向对象编程 37

2.1 目标、原则和模式 37

2.1.1 面向对象的设计目标 37

2.1.2 面向对象的设计原则 38

2.1.3 设计模式 39

2.2 软件开发 40

2.2.1 设计 40

2.2.2 伪代码 41

2.2.3 编码风格和文档 42

2.2.4 测试和调试 43

2.3 类定义 44

2.3.1 例子：CreditCard类 45

2.3.2 运算符重载和Python的特殊方法 48

2.3.3 例子：多维向量类 50

2.3.4 迭代器 51

2.3.5 例子：Range类 52

2.4 继承 53

2.4.1 扩展CreditCard类 54

2.4.2 数列的层次图 57

2.4.3 抽象基类 60

2.5 命名空间和面向对象 62

2.5.1 实例和类命名空间 62

2.5.2 名称解析和动态调度 65

2.6 深拷贝和浅拷贝 65

2.7 练习 67

扩展阅读 70

第3章 算法分析 71

3.1 实验研究 71

3.2 本书使用的7种函数 74

3.2.1 常数函数 74

3.2.2 对数函数 74

3.2.3 线性函数 75

3.2.4 n-log-n函数 75

3.2.5 二次函数 76

3.2.6 三次函数和其他多项式 77

3.2.7 指数函数 77

3.2.8 比较增长率 79

3.3 渐近分析 79

3.3.1 大O符号 80

3.3.2 比较分析 82

3.3.3 算法分析示例 84

3.4 简单的证明技术 89

3.4.1 示例 89

3.4.2 反证法 89

3.4.3 归纳和循环不变量 90

3.5 练习 91

扩展阅读 95

第4章 递归 96

4.1 说明性的例子 96

4.1.1 阶乘函数 96

4.1.2 绘制英式标尺 97

4.1.3 二分查找 99

4.1.4 文件系统 101

4.2 分析递归算法 104

4.3 递归算法的不足 106

4.4 递归的其他例子 109

4.4.1 线性递归 109

4.4.2 二路递归 112

4.4.3 多重递归 113

4.5 设计递归算法 114

4.6 消除尾递归 115

4.7 练习 116

扩展阅读 118

第5章 基于数组的序列 119

5.1 Python序列类型 119

5.2 低层次数组 119

5.2.1 引用数组 121

5.2.2 Python中的紧凑数组 122

5.3 动态数组和摊销 124

5.3.1 实现动态数组 126

5.3.2 动态数组的摊销分析 127

5.3.3 Python列表类 130

5.4 Python序列类型的效率 130

5.4.1 Python的列表和元组类 130

5.4.2 Python的字符串类 134

5.5 使用基于数组的序列 136

5.5.1 为游戏存储高分 136

5.5.2 为序列排序 138

5.5.3 简单密码技术 140

5.6 多维数据集 142

5.7 练习 145

扩展阅读 147

第6章 栈、队列和双端队列 148

6.1 栈 148

6.1.1 栈的抽象数据类型 148

6.1.2 简单的基于数组的栈实现 149

6.1.3 使用栈实现数据的逆置 152

6.1.4 括号和HTML标记匹配 152

6.2 队列 155

6.2.1 队列的抽象数据类型 155

6.2.2 基于数组的队列实现 156

6.3 双端队列 160

6.3.1 双端队列的抽象数据类型 160

6.3.2 使用环形数组实现双端队列 161

6.3.3 Python collections模块中的双端队列 162

6.4 练习 163

扩展阅读 165

第7章 链表 166

7.1 单向链表 166

7.1.1 用单向链表实现栈 169

7.1.2 用单向链表实现队列 171

7.2 循环链表 173

7.2.1 轮转调度 173

7.2.2 用循环链表实现队列 174

7.3 双向链表 175

7.3.1 双向链表的基本实现 177

7.3.2 用双向链表实现双端队列 179

7.4 位置列表的抽象数据类型 180

7.4.1 含位置信息的列表抽象数据类型 182

7.4.2 双向链表实现 183

7.5 位置列表的排序 186

7.6 案例研究：维护访问频率 186

7.6.1 使用有序表 187

7.6.2 启发式动态调整列表 188

7.7 基于链接的序列与基于数组的序列 190

7.8 练习 192

扩展阅读 195

第8章 树 196

8.1 树的基本概念 196

8.1.1 树的定义和属性 196

8.1.2 树的抽象数据类型 199

8.1.3 计算深度和高度 201

8.2 二叉树 203

8.2.1 二叉树的抽象数据类型 204

8.2.2 二叉树的属性 206

8.3 树的实现 207

8.3.1 二叉树的链式存储结构 207

8.3.2 基于数组表示的二叉树 212

8.3.3 一般树的链式存储结构 214

8.4 树的遍历算法 214

8.4.1 树的先序和后序遍历 214

8.4.2 树的广度优先遍历 216

8.4.3 二叉树的中序遍历 216

8.4.4 用Python实现树遍历 217

8.4.5 树遍历的应用 220

8.4.6 欧拉图和模板方法模式 223

8.5 案例研究：表达式树 227

8.6 练习 230

扩展阅读 235

第9章 优先级队列 236

9.1 优先级队列的抽象数据类型 236

9.1.1 优先级 236

9.1.2 优先级队列的抽象数据类型的实现 236

9.2 优先级队列的实现 237

9.2.1 组合设计模式 237

9.2.2 使用未排序列表实现优先级队列 238

9.2.3 使用排序列表实现优先级队列 239

9.3 堆 241

9.3.1 堆的数据结构 241

9.3.2 使用堆实现优先级队列 242

9.3.3 基于数组的完全二叉树表示 244

9.3.4 Python的堆实现 246

9.3.5 基于堆的优先级队列的分析 248

9.3.6 自底向上构建堆 248

9.3.7 Python的heapq模块 251

9.4 使用优先级队列排序 252

9.4.1 选择排序和插入排序 253

9.4.2 堆排序 254

9.5 适应性优先级队列 255

9.5.1 定位器 256

9.5.2 适应性优先级队列的实现 256

9.6 练习 259

扩展阅读 263

第10章 映射、哈希表和跳跃表 264

10.1 映射和字典 264

10.1.1 映射的抽象数据类型 264

10.1.2 应用：单词频率统计 266

10.1.3 Python的MutableMapping抽象基类 267

10.1.4 我们的MapBase类 267

10.1.5 简单的非有序映射实现 268

10.2 哈希表 269

10.2.1 哈希函数 270

10.2.2 哈希码 271

10.2.3 压缩函数 274

10.2.4 冲突处理方案 274

10.2.5 负载因子、重新哈希和效率 276

10.2.6 Python哈希表的实现 278

10.3 有序映射 281

10.3.1 排序检索表 282

10.3.2 有序映射的两种应用 286

10.4 跳跃表 288

10.4.1 跳跃表中的查找和更新操作 289

10.4.2 跳跃表的概率分析 292

10.5 集合、多集和多映射 294

10.5.1 集合的抽象数据类型 294

10.5.2 Python的MutableSet抽象基类 295

10.5.3 集合、多集和多映射的实现 297

10.6 练习 298

扩展阅读 302

第11章 搜索树 303

11.1 二叉搜索树 303

11.1.1 遍历二叉搜索树 303

11.1.2 搜索 305

11.1.3 插入和删除 306

11.1.4 Python实现 307

11.1.5 二叉搜索树的性能 311

11.2 平衡搜索树 312

11.3 AVL树 316

11.3.1 更新操作 318

11.3.2 Python实现 320

11.4 伸展树 322

11.4.1 伸展 322

11.4.2 何时进行伸展 323

11.4.3 Python实现 324

11.4.4 伸展树的摊销分析 325

11.5 （2，4）树 328

11.5.1 多路搜索树 328

11.5.2 （2，4）树的操作 330

11.6 红黑树 334

11.6.1 红黑树的操作 335

11.6.2 Python实现 341

11.7 练习 343

扩展阅读 348

第12章 排序与选择 349

12.1 为什么要学习排序算法 349

12.2 归并排序 349

12.2.1 分治法 349

12.2.2 基于数组的归并排序的实现 351

12.2.3 归并排序的运行时间 353

12.2.4 归并排序与递归方程 354

12.2.5 归并排序的可选实现 355

12.3 快速排序 357

12.3.1 随机快速排序 361

12.3.2 快速排序的额外优化 362

12.4 再论排序：算法视角 364

12.4.1 排序下界 365

12.4.2 线性时间排序：桶排序和基数排序 366

12.5 排序算法的比较 367

12.6 Python的内置排序函数 369

12.7 选择 370

12.7.1 剪枝搜索 370

12.7.2 随机快速选择 371

12.7.3 随机快速选择分析 371

12.8 练习 372

扩展阅读 376

第13章 文本处理 377

13.1 数字化文本的多样性 377

13.2 模式匹配算法 378

13.2.1 穷举 378

13.2.2 Boyer-Moore算法 379

13.2.3 Knuth-Morris-Pratt算法 382

13.3 动态规划 385

13.3.1 矩阵链乘积 385

13.3.2 DNA和文本序列比对 386

13.4 文本压缩和贪心算法 389

13.4.1 霍夫曼编码算法 390

13.4.2 贪心算法 391

13.5 字典树 391

13.5.1 标准字典树 391

13.5.2 压缩字典树 394

13.5.3 后缀字典树 395

13.5.4 搜索引擎索引 396

13.6 练习 397

拓展阅读 400

第14章 图算法 401

14.1 图 401

14.2 图的数据结构 405

14.2.1 边列表结构 406

14.2.2 邻接列表结构 407

14.2.3 邻接图结构 408

14.2.4 邻接矩阵结构 409

14.2.5 Python实现 409

14.3 图遍历 412

14.3.1 深度优先搜索 413

14.3.2 深度优先搜索的实现和 416

扩展 416

14.3.3 广度优先搜索 419

14.4 传递闭包 421

14.5 有向非循环图 424

14.6 最短路径 426

14.6.1 加权图 427

14.6.2 Dijkstra算法 428

14.7 最小生成树 434

14.7.1 Prim-Jarnik算法 435

14.7.2 Kruskal算法 438

14.7.3 不相交分区和联合查找结构 442

14.8 练习 445

扩展阅读 451

第15章 内存管理和B树 452

15.1 内存管理 452

15.1.1 内存分配 452

15.1.2 垃圾回收 453

15.1.3 Python解释器使用的额外内存 455

15.2 存储器层次结构和缓存 456

15.2.1 存储器系统 456

15.2.2 高速缓存策略 456

15.3 外部搜索和B树 460

15.3.1 （a，b）树 460

15.3.2 B树 462

15.4 外部存储器中的排序 462

15.5 练习 464

拓展阅读 465

附录A Python中的字符串 466

附录B有用的数学定理 469

参考文献 474