数据结构 Python语言描述 PDF 完整源码版

在电子信息科学中，数据结构是这门升阶性课程内容，定义抽象性，难度系数很大。Python语言的英语的语法简易，易用性强。用Python来解读数据结构等主题风格，比c语言等保持起來更加非常容易，更加清楚。 《数据结构 Python语言描述》第1章简易详细介绍了Python语言的基本知识和特点。第2章到第4章对抽象数据类型、数据结构、复杂性剖析、数组和线形链表构造开展了详解，第5章和第6章重中之重详细介绍了面向对象设计的有关专业知识、第5章包含插口和保持中间的重中之重差别、多态及其信息内容掩藏等內容，第6章关键解读承继的有关专业知识，第7章到第9章以栈、序列和目录为意味着，详细介绍了线形结合的有关专业知识。第10章详细介绍了各种各样树结构，第11章解读了集和词典的有关內容，第12章详细介绍了图和图解决优化算法。每章*后，还得出了复习题和实例学习培训，协助用户推进和思索。 《数据结构 Python语言描述》不但合适高等学校计算机专科老师学生阅读文章，也合适对Python喜欢的用户和程序猿阅读文章。

核心主题：详细介绍,数据结构,內容,语言,专业知识,重中之重,解读,阅读文章,线形,起來

目录

• 第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