数据结构 Python语言描述PDF电子书下载

第1章 Python编程基础 1

1.1基本程序要素 1

1.1.1程序和模块 1

1.1.2 Python程序示例：猜数字 1

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

1.1.4程序注释 3

1.1.5词法元素 3

1.1.6拼写和命名惯例 3

1.1.7语法元素 4

1.1.8字面值 4

1.1.9字符串字面值 4

1.1.10运算符和表达式 5

1.1.11函数调用 5

1.1.12 pRInt函数 5

1.1.13 input函数 5

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

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

1.1.16变量和赋值语句 6

1.1.17 Python数据类型 7

1.1.18 import语句 7

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

1.2控制语句 8

1.2.1条件式语句 8

1.2.2使用if name__==“_main” 9

1.2.3循环语句 10

1.3字符串及其运算 10

1.3.1运算符 10

1.3.2格式化字符串以便输出 11

1.3.3对象和方法调用 13

1.4内建Python集合及其操作 13

1.4.1列表 14

1.4.2元组 14

1.4.3遍历序列 14

1.4.4字典 15

1.4.5搜索一个值 15

1.4.6对集合应用模式匹配 15

1.5编写新的函数 16

1.5.1函数定义 16

1.5.2递归函数 17

1.5.3嵌套的函数定义 19

1.5.4高阶函数 19

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

1.6捕获异常 20

1.7文件及其操作 21

1.7.1文本文件的输出 22

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

1.7.3从文本文件读取文本 23

1.7.4从文件读取数字 24

1.7.5使用pickle读写对象 24

1.8创建新的类 25

1.9编程项目 28

第2章 集合概览 30

2.1集合类型 30

2.1.1线性集合 30

2.1.2层级集合 31

2.1.3图集合 31

2.1.4无序集合 31

2.1.5有序集合 31

2.1.6集合类型的分类 32

2.2集合上的操作 32

2.3集合的实现 34

2.4小结 35

2.5复习题 35

2.6编程项目 36

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

3.1评估算法的性能 37

3.1.1度量算法的运行时间 37

3.1.2统计指令 39

3.1.3度量算法所使用的内存 41

3.1.4练习3.1 41

3.2复杂度分析 41

3.2.1复杂度的阶 41

3.2.2大O表示法 43

3.2.3常量比例的作用 43

3.2.4练习3.2 43

3.3搜索算法 44

3.3.1搜索最小值 44

3.3.2顺序搜索一个列表 44

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

3.3.4有序列表的二叉搜索 45

3.3.5比较数据项 47

3.3.6练习3.3 48

3.4基本排序算法 48

3.4.1选择排序 48

3.4.2冒泡排序 49

3.4.3插入排序 50

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

3.4.5练习3.4 52

3.5更快的排序 53

3.5.1快速排序简介 53

3.5.2合并排序 56

3.5.3练习3.5 59

3.6指数算法：递归式的Fibonacci 59

3.7案例学习：算法探查器 61

3.7.1需求 61

3.7.2分析 61

3.7.3设计 62

3.7.4实现（编写代码） 63

3.8小结 65

3.9复习题 66

3.10编程项目 67

第4章 数组和链表结构 69

4.1数组数据结构 69

4.1.1随机访问和连续内存 71

4.1.2静态内存和动态内存 72

4.1.3物理大小和逻辑大小 72

4.1.4练习4.1 73

4.2数组的操作 73

4.2.1增加数组的大小 73

4.2.2减小数组的大小 74

4.2.3在数组中插入一项 74

4.2.4从数组中删除一项 75

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

4.2.6练习4.2 76

4.3二维数组 77

4.3.1处理网格 77

4.3.2创建并初始化网格 77

4.3.3定义Grid类 78

4.3.4杂乱的网格和多维数组 79

4.3.5练习4.3 79

4.4链表结构 80

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

4.4.2非连续性内存和节点 81

4.4.3定义一个单链表节点类 82

4.4.4使用单链表节点类 82

4.4.5练习4.4 84

4.5单链表结构上的操作 84

4.5.1遍历 84

4.5.2搜索 85

4.5.3替换 86

4.5.4在开始处插入 86

4.5.5在末尾插入 87

4.5.6从开始处删除 87

4.5.7从末尾删除 88

4.5.8在任何位置插入 89

4.5.9从任意位置删除 90

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

4.5.11练习4.5 92

4.6链表的变体 92

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

4.6.2双链表结构 93

4.6.3练习4.6 95

4.7小结 95

4.8复习题 96

4.9编程项目 96

第5章 接口、实现和多态 98

5.1开发接口 98

5.1.1定义包接口 98

5.1.2指定参数和返回值 99

5.1.3构造方法和实现类 101

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

5.1.5用Python编写接口 102

5.1.6练习5.1 103

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

5.2.1选择并初始化数据结构 103

5.2.2先完成容易的方法 104

5.2.3完成迭代器 105

5.2.4完成使用迭代器的方法 106

5.2.5 in运算符和contains方法 106

5.2.6完成remove方法 107

5.2.7练习5.2 107

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

5.3.1初始化数据结构 108

5.3.2完成迭代器 109

5.3.3完成clear和add方法 109

5.3.4完成remove方法 109

5.3.5练习5.3 110

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

5.5测试两个包实现 111

5.6用UML图表示包资源 112

5.7小结 113

5.8复习题 113

5.9编程项目 114

第6章 继承和抽象类 115

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

6.1.1已有类的子类化 115

6.1.2再谈init方法 116

6.1.3添加新的contains方法 117

6.1.4修改已有的add方法 117

6.1.5 ArraySortedBag的运行时间性能 118

6.1.6 Python中的类层级 118

6.1.7练习6.1 119

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

6.2.1设计一个AbstractBag类 119

6.2.2重新编写AbstractBag中的init方法 120

6.2.3修改AbstractBag的子类 120

6.2.4将AbstractBag中的add方法泛化 121

6.3所有集合的一个抽象类 122

6.3.1将AbstractCollection整合到集合层级中 122

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

6.3.3练习6.2 124

6.4小结 124

6.5复习题 124

6.6编程项目 125

第7章 栈 127

7.1栈概览 127

7.2使用栈 128

7.2.1栈接口 128

7.2.2初始化一个栈 129

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

7.2.4练习7.1 131

7.3栈的3种应用 131

7.3.1计算算术表达式 131

7.3.2计算后缀表达式 132

7.3.3练习7.2 133

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

7.3.5练习7.3 135

7.3.6回溯算法 135

7.3.7内存管理 137

7.4栈的实现 138

7.4.1测试驱动程序 138

7.4.2将栈添加到集合层级中 139

7.4.3数组实现 140

7.4.4链表实现 141

7.4.5 AbstractStack类的作用 144

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

7.4.7练习7.4 145

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

7.5.1要求 145

7.5.2分析 145

7.5.3设计 148

7.5.4实现 150

7.6小结 153

7.7复习题 153

7.8编程项目 154

第8章 队列 156

8.1队列概览 156

8.2队列接口及其应用 157

练习8.1 158

8.3队列的两个应用 159

8.3.1模拟 159

8.3.2轮询CPU调度 161

8.3.3练习8.2 161

8.4队列的实现 161

8.4.1队列的链表实现 161

8.4.2数组实现 163

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

8.4.4练习8.3 165

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

8.5.1要求 165

8.5.2分析 165

8.5.3用户界面 166

8.5.4类及其作用 166

8.6优先队列 171

练习8.4 175

8.7案例学习：急症室调度 175

8.7.1需求 175

8.7.2分析 175

8.7.3类 176

8.7.4设计和实现 177

8.8小结 179

8.9复习题 179

8.10编程项目 180

第9章 列表 182

9.1概览 182

9.2使用列表 183

9.2.1基于索引的操作 183

9.2.2基于内容的操作 183

9.2.3基于位置的操作 184

9.2.4列表的接口 187

9.2.5练习9.1 188

9.3列表的应用 188

9.3.1堆存储管理 188

9.3.2组织磁盘上的文件 189

9.3.3其他集合的实现 190

9.4列表实现 191

9.4.1 AbstractList类的角色 191

9.4.2基于数组的实现 192

9.4.3链表实现 194

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

9.4.5练习9.2 197

9.5实现列表迭代器 197

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

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

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

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

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

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

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

9.6.1要求 201

9.6.2分析 202

9.6.3设计 202

9.6.4实现（代码） 204

9.7小结 205

9.8复习题 205

9.9编程项目 206

第10章 树 208

10.1树的概览 208

10.1.1树的术语 208

10.1.2普通的树和二叉树 209

10.1.3树的递归定义 210

10.1.4练习10.1 210

10.2为什么要使用树 210

10.3二叉树的形状 211

练习10.2 213

10.4二叉树的3种常见应用 213

10.4.1堆 213

10.4.2二叉搜索树 214

10.4.3表达式树 215

10.4.4练习10.3 216

10.5二叉树的遍历 216

10.5.1前序遍历 216

10.5.2中序遍历 217

10.5.3后序遍历 217

10.5.4层序遍历 217

10.6开发二叉搜索树 217

10.6.1二叉搜索树接口 218

10.6.2链表实现的数据结构 219

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

10.6.4练习10.4 224

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

10.7.1语法简介 224

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

10.7.3词法分析和扫描器 226

10.7.4解析策略 227

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

10.8.1要求 227

10.8.2分析 228

10.8.3节点类的设计和实现 228

10.8.4解析器类的设计和实现 230

10.9二叉树的数组实现 231

练习10.5 232

10.10实现堆 232

练习10.6 234

10.11小结 234

10.12复习题 235

10.13编程项目 236

第11章 集和字典 238

11.1使用集 238

11.2 Python的set类 239

11.2.1集的一个示例会话 239

11.2.2集的应用 240

11.2.3集和包的关系 240

11.2.4集和字典的关系 240

11.2.5集的实现 240

11.2.6练习11.1 241

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

11.3.1 AbstractSet类 241

11.3.2 ArraySet类 242

11.4使用字典 243

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

11.5.1 Item类 244

11.5.2 AbstractDict类 245

11.5.3 ArrayDict类 246

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

11.5.5练习11.2 248

11.6哈希策略 248

11.6.1冲突和密度的关系 249

11.6.2非数字键的哈希 250

11.6.3线性探测 251

11.6.4二次探测 252

11.6.5链化 253

11.6.6复杂度分析 253

11.6.7练习11.3 254

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

11.7.1需求 255

11.7.2分析 255

11.7.3设计 256

11.8集的哈希实现 258

11.9字典的哈希实现 261

练习11.4 263

11.10有序的集和字典 263

11.11小结 264

11.12复习题 264

11.13编程项目 265

第12章 图 267

12.1图的术语 267

练习12.1 269

12.2为什么使用图 270

12.3图的表示 270

12.3.1相邻矩阵 270

12.3.2 邻接表 271

12.3.3两种表示的分析 272

12.3.4运行时间的进一步考虑 272

12.3.5练习12.2 273

12.4图的遍历 273

12.4.1泛型遍历算法 273

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

12.4.3图区域 275

12.4.4练习12.3 276

12.5图中的树 276

12.5.1生成树和森林 276

12.5.2最小生成树 277

12.5.3最小生成树的算法 277

12.6拓扑排序 279

12.7最短路径问题 279

12.7.1 Dijkstra算法 280

12.7.2初始化步骤 280

12.7.3计算步骤 281

12.7.4无限的表示和用法 282

12.7.5分析 282

12.7.6练习12.4 282

12.7.7 Floyd算法 283

12.7.8分析 283

12.8开发一个图集合 284

12.8.1使用图集合的示例 284

12.8.2 LinkedDirected-Graph类 285

12.8.3 LinkedVertex类 288

12.8.4 LinkedEdge类 289

12.9案例学习：测试图算法 290

12.9.1需求 290

12.9.2分析 290

12.9.3 GraphDemoView类和GraphDemoModel类 291

12.9.4实现（代码） 292

12.10小结 295

12.11复习题 296

12.12编程项目 297

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