《数据结构（Python语言描述）》教学PPT

编辑推荐

不管你是程序设计爱好者、计算机专业的学生还是一位专业程序员，本书都是你通过Python编程语言学习面向对象设计和数据结构的不错的入门教程。通过清晰的示例、按部就班的讲解以及众多实用的练习，本书教你通过Python理解并使用数据结构。
● 使用多态和继承来设计集合类；
● 集合接口的多个实现；
● 不同的集合实现的时间/空间代价分析。

内容简介

在计算机科学中，数据结构是一门进阶性课程，概念抽象，难度较大。Python语言的语法简单，交互性强。用Python来讲解数据结构等主题，比C语言等实现起来更为容易，更为清晰。
《数据结构 Python语言描述》第1章简单介绍了Python语言的基础知识和特性。第2章到第4章对抽象数据类型、数据结构、复杂度分析、数组和线性链表结构进行了详细介绍，第5章和第6章重点介绍了面向对象设计的相关知识、第5章包括接口和实现之间的重点差异、多态以及信息隐藏等内容，第6章主要讲解继承的相关知识，第7章到第9章以栈、队列和列表为代表，介绍了线性集合的相关知识。第10章介绍了各种树结构，第11章讲解了集和字典的相关内容，第12章介绍了图和图处理算法。每章最后，还给出了复习题和案例学习，帮助读者巩固和思考。
《数据结构 Python语言描述》不仅适合高等院校计算机专业师生阅读，也适合对Python感兴趣的读者和程序员阅读。

作者简介

Kenneth A .Lambert是华盛顿与李大学的计算机科学教授和系主任。他教授编程课程30 年 ，并且是计算机科学教育的积极研究者。Lambert编著以及与人合著了一共2 5 本教材，包括与Douglas Nance和Thomas Naps编写的一系列C++ 入门教材，与MartiOsbor ne编写的一系列Java入门教材， 以及一系列Python入门教材。他还是《Easy GUI Progr amming iPython》的作者。

目录

• 第1章 Python编程基础t1
• 1．1 基本程序要素t1
• 1．1．1 程序和模块t1
• 1．1．2 Python程序示例：猜数字t1
• 1．1．3 编辑、编译并运行Python程序t2
• 1．1．4 程序注释t3
• 1．1．5 词法元素t3
• 1．1．6 拼写和命名惯例t3
• 1．1．7 语法元素t4
• 1．1．8 字面值t4
• 1．1．9 字符串字面值t4
• 1．1．10 运算符和表达式t5
• 1．1．11 函数调用t5
• 1．1．12 print函数t5
• 1．1．13 input函数t5
• 1．1．14 类型转换函数和混合模式运算t6
• 1．1．15 可选的和关键字函数参数t6
• 1．1．16 变量和赋值语句t6
• 1．1．17 Python数据类型t7
• 1．1．18 import语句t7
• 1．1．19 获取关于程序组件的帮助t7
• 1．2 控制语句t8
• 1．2．1 条件式语句t8
• 1．2．2 使用if __name__ =="__main__"t9
• 1．2．3 循环语句t10
• 1．3 字符串及其运算t10
• 1．3．1 运算符t10
• 1．3．2 格式化字符串以便输出t11
• 1．3．3 对象和方法调用t13
• 1．4 内建Python集合及其操作t13
• 1．4．1 列表t14
• 1．4．2 元组t14
• 1．4．3 遍历序列t14
• 1．4．4 字典t15
• 1．4．5 搜索一个值t15
• 1．4．6 对集合应用模式匹配t15
• 1．5 编写新的函数t16
• 1．5．1 函数定义t16
• 1．5．2 递归函数t17
• 1．5．3 嵌套的函数定义t19
• 1．5．4 高阶函数t19
• 1．5．5 使用lambda表达式创建匿名函数t20
• 1．6 捕获异常t20
• 1．7 文件及其操作t21
• 1．7．1 文本文件的输出t22
• 1．7．2 将数字写入到一个文本文件t22
• 1．7．3 从文本文件读取文本t23
• 1．7．4 从文件读取数字t24
• 1．7．5 使用pickle读写对象t24
• 1．8 创建新的类t25
• 1．9 编程项目t28
• 第2章 集合概览t30
• 2．1 集合类型t30
• 2．1．1 线性集合t30
• 2．1．2 层级集合t31
• 2．1．3 图集合t31
• 2．1．4 无序集合t31
• 2．1．5 有序集合t31
• 2．1．6 集合类型的分类t32
• 2．2 集合上的操作t32
• 2．3 集合的实现t34
• 2．4 小结t35
• 2．5 复习题t35
• 2．6 编程项目t36
• 第3章 搜索、排序和复杂度分析t37
• 3．1 评估算法的性能t37
• 3．1．1 度量算法的运行时间t37
• 3．1．2 统计指令t39
• 3．1．3 度量算法所使用的内存t41
• 3．1．4 练习3．1t41
• 3．2 复杂度分析t41
• 3．2．1 复杂度的阶t41
• 3．2．2 大O表示法t43
• 3．2．3 常量比例的作用t43
• 3．2．4 练习3．2t43
• 3．3 搜索算法t44
• 3．3．1 搜索最小值t44
• 3．3．2 顺序搜索一个列表t44
• 3．3．3 最好情况、最坏情况和平均情况的性能t45
• 3．3．4 有序列表的二叉搜索t45
• 3．3．5 比较数据项t47
• 3．3．6 练习3．3t48
• 3．4 基本排序算法t48
• 3．4．1 选择排序t48
• 3．4．2 冒泡排序t49
• 3．4．3 插入排序t50
• 3．4．4 再谈最好情况、最坏情况和平均情况的性能t52
• 3．4．5 练习3．4t52
• 3．5 更快的排序t53
• 3．5．1 快速排序简介t53
• 3．5．2 合并排序t56
• 3．5．3 练习3．5t59
• 3．6 指数算法：递归式的Fibonaccit59
• 3．7 案例学习：算法探查器t61
• 3．7．1 需求t61
• 3．7．2 分析t61
• 3．7．3 设计t62
• 3．7．4 实现（编写代码）t63
• 3．8 小结t65
• 3．9 复习题t66
• 3．10 编程项目t67
• 第4章 数组和链表结构t69
• 4．1 数组数据结构t69
• 4．1．1 随机访问和连续内存t71
• 4．1．2 静态内存和动态内存t72
• 4．1．3 物理大小和逻辑大小t72
• 4．1．4 练习4．1t73
• 4．2 数组的操作t73
• 4．2．1 增加数组的大小t73
• 4．2．2 减小数组的大小t74
• 4．2．3 在数组中插入一项t74
• 4．2．4 从数组中删除一项t75
• 4．2．5 复杂度权衡：时间、空间和数组t76
• 4．2．6 练习4．2t76
• 4．3 二维数组t77
• 4．3．1 处理网格t77
• 4．3．2 创建并初始化网格t77
• 4．3．3 定义Grid类t78
• 4．3．4 杂乱的网格和多维数组t79
• 4．3．5 练习4．3t79
• 4．4 链表结构t80
• 4．4．1 单链表结构和双链表结构t80
• 4．4．2 非连续性内存和节点t81
• 4．4．3 定义一个单链表节点类t82
• 4．4．4 使用单链表节点类t82
• 4．4．5 练习4．4t84
• 4．5 单链表结构上的操作t84
• 4．5．1 遍历t84
• 4．5．2 搜索t85
• 4．5．3 替换t86
• 4．5．4 在开始处插入t86
• 4．5．5 在末尾插入t87
• 4．5．6 从开始处删除t87
• 4．5．7 从末尾删除t88
• 4．5．8 在任何位置插入t89
• 4．5．9 从任意位置删除t90
• 4．5．10 复杂度权衡：时间、空间和单链表结构t91
• 4．5．11 练习4．5t92
• 4．6 链表的变体t92
• 4．6．1 带有一个哑头节点的循环链表结构t92
• 4．6．2 双链表结构t93
• 4．6．3 练习4．6t95
• 4．7 小结t95
• 4．8 复习题t96
• 4．9 编程项目t96
• 第5章 接口、实现和多态t98
• 5．1 开发接口t98
• 5．1．1 定义包接口t98
• 5．1．2 指定参数和返回值t99
• 5．1．3 构造方法和实现类t101
• 5．1．4 先验条件、后验条件、异常和文档t101
• 5．1．5 用Python编写接口t102
• 5．1．6 练习5．1t103
• 5．2 开发一个基于数组的实现t103
• 5．2．1 选择并初始化数据结构t103
• 5．2．2 先完成容易的方法t104
• 5．2．3 完成迭代器t105
• 5．2．4 完成使用迭代器的方法t106
• 5．2．5 in运算符和__contains__方法t106
• 5．2．6 完成remove方法t107
• 5．2．7 练习5．2t107
• 5．3 开发一个基于链表的实现t107
• 5．3．1 初始化数据结构t108
• 5．3．2 完成迭代器t109
• 5．3．3 完成clear和add方法t109
• 5．3．4 完成remove方法t109
• 5．3．5 练习5．3t110
• 5．4 两个包实现的运行时性能t110
• 5．5 测试两个包实现t111
• 5．6 用UML图表示包资源t112
• 5．7 小结t113
• 5．8 复习题t113
• 5．9 编程项目t114
• 第6章 继承和抽象类t115
• 6．1 使用继承定制一个已有的类t115
• 6．1．1 已有类的子类化t115
• 6．1．2 再谈__init__方法t116
• 6．1．3 添加新的contains方法t117
• 6．1．4 修改已有的add方法t117
• 6．1．5 ArraySortedBag的运行时间性能t118
• 6．1．6 Python中的类层级t118
• 6．1．7 练习6．1t119
• 6．2 使用抽象类去除代码冗余性t119
• 6．2．1 设计一个AbstractBag类t119
• 6．2．2 重新编写AbstractBag中的__init__方法t120
• 6．2．3 修改AbstractBag的子类t120
• 6．2．4 将AbstractBag中的__add__方法泛化t121
• 6．3 所有集合的一个抽象类t122
• 6．3．1 将AbstractCollection整合到集合层级中t122
• 6．3．2 在__eq__方法中使用两个迭代器t123
• 6．3．3 练习6．2t124
• 6．4 小结t124
• 6．5 复习题t124
• 6．6 编程项目t125
• 第7章 栈t127
• 7．1 栈概览t127
• 7．2 使用栈t128
• 7．2．1 栈接口t128
• 7．2．2 初始化一个栈t129
• 7．2．3 示例应用程序：匹配括号t129
• 7．2．4 练习7．1t131
• 7．3 栈的3种应用t131
• 7．3．1 计算算术表达式t131
• 7．3．2 计算后缀表达式t132
• 7．3．3 练习7．2t133
• 7．3．4 将中缀表达式转换为后缀表达式t133
• 7．3．5 练习7．3t135
• 7．3．6 回溯算法t135
• 7．3．7 内存管理t137
• 7．4 栈的实现t138
• 7．4．1 测试驱动程序t138
• 7．4．2 将栈添加到集合层级中t139
• 7．4．3 数组实现t140
• 7．4．4 链表实现t141
• 7．4．5 AbstractStack类的作用t144
• 7．4．6 两种实现的时间和空间分析t144
• 7．4．7 练习7．4t145
• 7．5 案例学习：计算后缀表达式t145
• 7．5．1 要求t145
• 7．5．2 分析t145
• 7．5．3 设计t148
• 7．5．4 实现t150
• 7．6 小结t153
• 7．7 复习题t153
• 7．8 编程项目t154
• 第8章 队列t156
• 8．1 队列概览t156
• 8．2 队列接口及其应用t157练习8．1t158
• 8．3 队列的两个应用t159
• 8．3．1 模拟t159
• 8．3．2 轮询CPU调度t161
• 8．3．3 练习8．2t161
• 8．4 队列的实现t161
• 8．4．1 队列的链表实现t161
• 8．4．2 数组实现t163
• 8．4．3 两种实现的时间和空间复杂度分析t164
• 8．4．4 练习8．3t165
• 8．5 案例学习：模拟超市排队结账t165
• 8．5．1 要求t165
• 8．5．2 分析t165
• 8．5．3 用户界面t166
• 8．5．4 类及其作用t166
• 8．6 优先队列t171练习8．4t175
• 8．7 案例学习：急症室调度t175
• 8．7．1 需求t175
• 8．7．2 分析t175
• 8．7．3 类t176
• 8．7．4 设计和实现t177
• 8．8 小结t179
• 8．9 复习题t179
• 8．10 编程项目t180
• 第9章 列表t182
• 9．1 概览t182
• 9．2 使用列表t183
• 9．2．1 基于索引的操作t183
• 9．2．2 基于内容的操作t183
• 9．2．3 基于位置的操作t184
• 9．2．4 列表的接口t187
• 9．2．5 练习9．1t188
• 9．3 列表的应用t188
• 9．3．1 堆存储管理t188
• 9．3．2 组织磁盘上的文件t189
• 9．3．3 其他集合的实现t190
• 9．4 列表实现t191
• 9．4．1 AbstractList类的角色t191
• 9．4．2 基于数组的实现t192
• 9．4．3 链表实现t194
• 9．4．4 两种实现的时间和空间分析t196
• 9．4．5 练习9．2t197
• 9．5 实现列表迭代器t197
• 9．5．1 列表迭代器的角色和作用t197
• 9．5．2 设置和实例化一个列表迭代器类t198
• 9．5．3 列表迭代器中的导航方法t199
• 9．5．4 列表迭代器中的修改器方法t200
• 9．5．5 链表列表的列表迭代器的设计t201
• 9．5．6 列表迭代器实现的时间和空间分析t201
• 9．6 案例学习：开发一个有序的列表t201
• 9．6．1 要求t201
• 9．6．2 分析t202
• 9．6．3 设计t202
• 9．6．4 实现（代码）t204
• 9．7 小结t205
• 9．8 复习题t205
• 9．9 编程项目t206
• 第10章 树t208
• 10．1 树的概览t208
• 10．1．1 树的术语t208
• 10．1．2 普通的树和二叉树t209
• 10．1．3 树的递归定义t210
• 10．1．4 练习10．1t210
• 10．2 为什么要使用树t210
• 10．3 二叉树的形状t211练习10．2t213
• 10．4 二叉树的3种常见应用t213
• 10．4．1 堆t213
• 10．4．2 二叉搜索树t214
• 10．4．3 表达式树t215
• 10．4．4 练习10．3t216
• 10．5 二叉树的遍历t216
• 10．5．1 前序遍历t216
• 10．5．2 中序遍历t217
• 10．5．3 后序遍历t217
• 10．5．4 层序遍历t217
• 10．6 开发二叉搜索树t217
• 10．6．1 二叉搜索树接口t218
• 10．6．2 链表实现的数据结构t219
• 10．6．3 二叉搜索树的复杂度分析t223
• 10．6．4 练习10．4t224
• 10．7 递归的后代解析和编程语言t224
• 10．7．1 语法简介t224
• 10．7．2 在语言中识别、解析和解释句子t226
• 10．7．3 词法分析和扫描器t226
• 10．7．4 解析策略t227
• 10．8 案例学习：解析和表达式树t227
• 10．8．1 要求t227
• 10．8．2 分析t228
• 10．8．3 节点类的设计和实现t228
• 10．8．4 解析器类的设计和实现t230
• 10．9 二叉树的数组实现t231
• 练习10．5t232
• 10．10 实现堆t232
• 练习10．6t234
• 10．11 小结t234
• 10．12 复习题t235
• 10．13 编程项目t236
• 第11章 集和字典t238
• 11．1 使用集t238
• 11．2 Python的set类t239
• 11．2．1 集的一个示例会话t239
• 11．2．2 集的应用t240
• 11．2．3 集和包的关系t240
• 11．2．4 集和字典的关系t240
• 11．2．5 集的实现t240
• 11．2．6 练习11．1t241
• 11．3 集的基于数组和链表的实现t241
• 11．3．1 AbstractSet类t241
• 11．3．2 ArraySet类t242
• 11．4 使用字典t243
• 11．5 基于数组和基于链表的字典实现t244
• 11．5．1 Item类t244
• 11．5．2 AbstractDict类t245
• 11．5．3 ArrayDict类t246
• 11．5．4 集和字典的基于数组和列表的实现的复杂度分析t247
• 11．5．5 练习11．2t248
• 11．6 哈希策略t248
• 11．6．1 冲突和密度的关系t249
• 11．6．2 非数字键的哈希t250
• 11．6．3 线性探测t251
• 11．6．4 二次探测t252
• 11．6．5 链化t253
• 11．6．6 复杂度分析t253
• 11．6．7 练习11．3t254
• 11．7 案例学习：探查哈希策略t254
• 11．7．1 需求t255
• 11．7．2 分析t255
• 11．7．3 设计t256
• 11．8 集的哈希实现t258
• 11．9 字典的哈希实现t261练习11．4t263
• 11．10 有序的集和字典t263
• 11．11 小结t264
• 11．12 复习题t264
• 11．13 编程项目t265
• 第12章 图t267
• 12．1 图的术语t267练习12．1t269
• 12．2 为什么使用图t270
• 12．3 图的表示t270
• 12．3．1 相邻矩阵t270
• 12．3．2 邻接表t271
• 12．3．3 两种表示的分析t272
• 12．3．4 运行时间的进一步考虑t272
• 12．3．5 练习12．2t273
• 12．4 图的遍历t273
• 12．4．1 泛型遍历算法t273
• 12．4．2 广度优先遍历和深度优先遍历t274
• 12．4．3 图区域t275
• 12．4．4 练习12．3t276
• 12．5 图中的树t276
• 12．5．1 生成树和森林t276
• 12．5．2 最小生成树t277
• 12．5．3 最小生成树的算法t277
• 12．6 拓扑排序t279
• 12．7 最短路径问题t279
• 12．7．1 Dijkstra算法t280
• 12．7．2 初始化步骤t280
• 12．7．3 计算步骤t281
• 12．7．4 无限的表示和用法t282
• 12．7．5 分析t282
• 12．7．6 练习12．4t282
• 12．7．7 Floyd算法t283
• 12．7．8 分析t283
• 12．8 开发一个图集合t284
• 12．8．1 使用图集合的示例t284
• 12．8．2 LinkedDirected-Graph类t285
• 12．8．3 LinkedVertex类t288
• 12．8．4 LinkedEdge类t289
• 12．9 案例学习：测试图算法t290
• 12．9．1 需求t290
• 12．9．2 分析t290
• 12．9．3 GraphDemoView类和GraphDemoModel类t291
• 12．9．4 实现（代码）t292
• 12．10 小结t295
• 12．11 复习题t296
• 12．12 编程项目t297
• 附录 供Python程序员使用的
• 集合框架t299