PYTHON数据结构与算法（第3版）

《Python 数据结构与算法（第 3 版）》是一本面向初级及中级 Python 开发者与学生的专业技术书籍，聚焦数据结构与算法在 Python 中的实战应用。书中系统介绍了 Python 基础数据类型（如数值、布尔、序列、字典、集合）及集合模块（命名元组、双端队列等），深入解析链表、栈、队列、树、堆、哈希表、图等核心数据结构的原理与实现，并涵盖冒泡排序、快速排序、二分搜索、KMP 算法等经典算法的原理、Python 代码实现及性能分析。

全书以 “理论 案例 实操” 为框架：通过对比数组与链表的特性、演示树的遍历逻辑、图解图的最小生成树算法等，帮助读者理解复杂概念；结合动态规划、分治法、贪婪算法等设计范式，解析算法优化思路；穿插字符串匹配、优先级管理等实际场景案例，展现数据结构与算法在提升应用程序性能、处理大规模数据中的关键作用。此外，书中提供各章练习答案，并附赠树算法扩展内容（可通过链接下载），助力读者巩固知识、深化实践。

无论是零基础入门数据结构，还是进阶优化算法设计，本书均以简明的步骤说明与丰富的代码示例，帮助读者掌握高效存储数据、设计可扩展程序的核心能力，适用于软件开发、算法课程学习及技术提升等场景。

第1章Python数据类型与结构1

1.1Python 3.10简介2

1.2Python安装2

1.2.1Windows操作系统2

1.2.2Linux操作系统2

1.2.3Mac操作系统3

1.3设置Python开发环境3

1.3.1通过命令行设置3

1.3.2通过Jupyter Notebook进行设置3

1.4数据类型和对象5

1.5基本数据类型6

1.5.1数值类型6

1.5.2布尔类型7

1.5.3序列类型7

1.5.4成员运算符、身份运算符和逻辑运算符12

1.5.5元组16

1.6复杂数据类型17

1.6.1字典17

1.6.2集合20

1.7Python的集合模块23

1.7.1命名元组24

1.7.2双端队列24

1.7.3有序字典25

1.7.4默认字典25

1.7.5ChainMap26

1.7.6计数器对象27

1.7.7UserDict27

1.7.8UserList28

1.7.9UserString28

1.8总结29

第2章算法设计导论30

2.1算法简介30

2.2算法的性能分析31

2.2.1时间复杂度32

2.2.2空间复杂度33

2.3渐进符号34

2.3.1θ符号35

2.3.2O符号36

2.3.3Ω符号38

2.4平摊分析40

2.5组合复杂度类别40

2.6计算算法的运行时间复杂度42

2.7总结44

练习44

第3章算法设计技术和策略46

3.1算法设计技术46

3.2递归47

3.3分治法48

3.3.1二分查找48

3.3.2归并排序50

3.4动态规划54

3.5贪婪算法58

3.6总结71

练习71

第4章链表73

4.1数组73

4.2链表简介74

4.3单链表76

4.3.1创建和遍历77

4.3.2追加元素78

4.3.3查询列表84

4.3.4删除元素85

4.4双链表89

4.4.1创建和遍历90

4.4.2追加项91

4.4.3查询列表97

4.4.4删除元素98

4.5循环链表102

4.5.1创建和遍历103

4.5.2添加元素104

4.5.3查询列表106

4.5.4删除循环链表中的元素106

4.6链表的实际应用110

4.7总结110

练习110

第5章栈和队列112

5.1栈112

5.1.1通过数组实现栈114

5.1.2使用链表实现栈117

5.1.3推入操作118

5.1.4弹出操作120

5.1.5查看操作121

5.1.6栈的应用122

5.2队列124

5.2.1Python的基于列表的队列125

5.2.2基于链表的队列128

5.2.3基于栈的队列131

5.2.4队列的应用136

5.3总结139

练习139

第6章树140

6.1术语140

6.2二叉树142

6.2.1节点的实现143

6.2.2树的遍历144

6.2.3表达式树150

6.3二叉搜索树154

6.3.1二叉搜索树的操作155

6.3.2二叉搜索树的优点166

6.4总结168

练习168

第7章堆和优先队列169

7.1堆169

7.1.1插入操作171

7.1.2删除操作174

7.1.3删除堆中特定位置的元素178

7.1.4堆排序180

7.2优先队列181

7.3总结186

练习186

第8章哈希表188

8.1简介188

8.1.1哈希函数189

8.1.2完美哈希函数191

8.2解决冲突192

8.3实现哈希表195

8.3.1在哈希表中存储元素196

8.3.2扩展哈希表197

8.3.3从哈希表中检索元素199

8.3.4测试哈希表200

8.3.5将哈希表实现为字典200

8.3.6分离链接法207

8.4符号表212

8.5总结213

练习213

第9章图和算法214

9.1图214

9.1.1有向图和无向图215

9.1.2有向无环图216

9.1.3加权图216

9.1.4二分图217

9.2图的表示217

9.2.1邻接表218

9.2.2邻接矩阵219

9.3图遍历220

9.3.1广度优先搜索221

9.3.2深度优先搜索226

9.4其他有用的与图相关的方法231

9.4.1最小生成树231

9.4.2Kruskal的最小生成树算法232

9.4.3Prim的最小生成树算法234

9.5总结236

练习236

第10章搜索237

10.1简介237

10.2线性搜索238

10.2.1无序线性搜索238

10.2.2有序线性搜索240

10.3跳跃搜索242

10.4二分搜索246

10.5插值搜索251

10.6指数搜索255

10.7选择搜索算法259

10.8总结259

练习260

第11章排序261

11.1技术要求261

11.2排序算法261

11.3冒泡排序算法262

11.4插入排序算法266

11.5选择排序算法269

11.6快速排序算法272

11.7快速排序算法的实现275

11.8Timsort算法278

11.9总结282

练习282

第12章选择算法284

12.1技术要求284

12.2按排序选择284

12.3随机选择285

12.4确定性选择288

12.5总结296

练习297

第13章字符串匹配算法298

13.1技术要求298

13.2字符串符号和概念298

13.3模式匹配算法299

13.4暴力算法300

13.5RabinKarp算法302

13.6KnuthMorrisPratt算法307

13.6.1prefix函数308

13.6.2理解KnuthMorrisPratt算法310

13.6.3实现KnuthMorrisPratt算法313

13.7BoyerMoore算法314

13.8总结323

练习323

附录练习答案324

第2章算法设计导论324

第3章算法设计技术和策略325

第4章链表326

第5章栈和队列328

第6章树329

第7章堆和优先队列331

第8章哈希表334

第9章图和算法334

第10章搜索336

第11章排序337

第12章选择算法341

第13章字符串匹配算法342

Dr.Basant Agarwal拥有计算机科学与工程专业博士和硕士学位，拥有超过 9 年的科研与教学经验。2016 年，他凭借欧洲信息与数学研究联盟（ERCIM）颁发的 prestigious 奖学金，在挪威科技大学（NTNU）担任博士后研究员，还曾在新加坡国立大学（NUS）淡马锡实验室担任研究科学家。其研究领域涵盖人工智能、信息物理系统、文本挖掘、自然语言处理、机器学习、深度学习、智能系统、专家系统及相关方向。